8.4.1. РЕКУРСИВНАЯ ПРОЦЕДУРА ЗАПОЛНЕНИЯ ПО КРИТЕРИЮ СВЯЗНОСТИ

Обход внутренней части области можно осуществлять различными способами с помощью структур данных, рассмотренных в гл. 6. Алгоритм, простейший в смысле длины соответствующей программы, основан на рекурсии и использует сетку пикселов. Он представлен ниже в виде алгоритма 8.4. В нем предусматривается обследование четырех н-соседей затравочного пиксела и к каждому из них, не принадлежащему контуру, снова применяется процедура FILL (ЗАПОЛНЕНИЕ), при выполнении которой затравочным пикселом служит уже этот сосед. С помощью небольшой модификации процедуры можно вводить во внутреннюю часть области любой пиксел, окрашенный в тот же цвет, что и затравочный пиксел.

Алгоритм 8.4. Рекурсивное заполнение контура

Обозначения. Затравочный пиксел — заданный пиксел, С — цвет внутренней части заполняемой области. Пикселы контура уже окрашены в этот цвет. Переменная обозначает -соседа пиксела (см. определение 7.1).

(см. скан)

Простота этого алгоритма только кажущаяся, так как каждое обращение к подпрограмме сопровождается определенными

затратами вычислительных ресурсов, размер которых трудно оценить по записи алгоритма. В разд. 8.5 мы еще вернемся к этой проблеме.