4.11. Алгоритм заполнения с затравкой

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

Рассмотрим алгоритм заполнения с затравкой, использующий стек. Стек - это просто массив или другая структура данных, в которую можно последовательно помещать значения и из которой их можно последовательно извлекать. Когда новые значения добавляются или помещаются в стек, все остальные значения опускаются вниз на один уровень. Когда значение удаляется или извлекается из стека, остальные значения всплывают или поднимаются вверх на один уровень. Такой стек называется стеком прямого действия или стеком с дисциплиной обслуживания FILO (первым пришёл, последним обслужен). Начнем с того, что поместим затравочный пиксель в стек. Далее, пока стек не пуст, будем извлекать из него очередной пиксель и, закрасив его, будем изучать соседние с ним пиксели. Если среди них будут пиксели, не принадлежащие границе и не окрашенные нужным цветом, то поместим их в стек, после этого вернемся к операции извлечения пикселя из стека. По окончанию алгоритма все пиксели будут закрашены.

Формально же алгоритм можно записать так:

{c(X,Y) – цвет пикселя с координатами X,Y

c_b – цвет границы

c_i – цвет внутренней области

(X₀,Y₀) – координаты затравочного пикселя}

{помещаем X₀,Y₀ в стек}

while {стек не пуст} do

begin

{извлекаем пиксель X,Y из стека}

if (c(X,Y)<>c_i) then c(X,Y):=c_i;

for {для каждого соседнего пикселя X,Y} do

if (c(X,Y)<>c_b) and (c(X,Y)<>c_i) then

{поместить пиксель (X,Y) в стек}

end;

end.

Приведенный алгоритм весьма не эффективен, т.к. предполагает неоднократную обработку одних и тех же пикселов и не контролирует рост величины стека.

4.12. Построчный алгоритм заполнения с затравкой

Применим идею построчного сканирования для решения задачи заполнения. Заметим, что на каждой строке множество пикселов, подлежащих закраске, состоит из интервалов принадлежащих внутренней области. Эти интервалы отделяются друг от друга интервалами из пикселов, принадлежащих границе или внешней области. Кроме того, если набор пикселов образует связанный интервал, принадлежащий внутренней части области, то пиксель над и под этим интервалом или является граничным, либо принадлежит внутренней области. Последний может служить в качестве затравочного пикселя для пикселов строк, лежащих выше или ниже рассмотренной строки. Можно предположить следующую схему заполнения области: инициализируем стек, помещая в него затравочный пиксель.

Пока стек не пуст:

1. извлекаем пиксель (X,Y) из стека;

2. заполняем максимум возможного интервала, в котором находится пиксель вправо и влево до достижения граничных пикселов;

3. заполняем крайнюю левую L_x и крайнюю правую R_x абсциссы заполненного интервала;

4. в соседних строках над и под интервалом L_x и R_x находим незаполненные к настоящему моменту внутренние пиксели области, как мы уже заметили, объединенные в интервалы, а в каждом из этих интервалов находим крайние правые пиксели, каждый из этих пикселов вставляем в стек в качестве затравочных.