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

Алгоритм со списком ребер и флагом

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

1) обрисовка контура: используя соглашения о середине интервала между сканирующими строками для каждого ребра, пересекающего сканирующую строку, отметить самый левый пиксель, центр которого лежит справа от пересечения; т.е. X+1/2>X_{пересечения};

2) заполнение: для каждой сканирующей строки, пересекающей многоугольник:

Внутри = false

for X=0 (левая граница) to X=X_max (правая граница)

if пиксель в точке X имеет граничное значение

then инвертировать значение переменной Внутри

if Внутри = true

then присвоить пикселю в X значение цвета многоугольника

else

присвоить пикселю в X значение цвета фона

end if

next X

В данном алгоритме каждый пиксель обрабатывается только один раз, так что затраты на ввод/вывод значительно меньше, чем в алгоритме со списком ребер или алгоритме с перегородкой.

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

Рассмотрим алгоритм заполнения с затравкой, использующий стек. Стек - это просто массив или другая структура данных, в которую можно последовательно помещать значения и из которой их можно последовательно извлекать. Когда новые значения добавляются или помещаются в стек, все остальные значения опускаются вниз на один уровень. Когда значение удаляется или извлекается из стека, остальные значения всплывают или поднимаются вверх на один уровень. Такой стек называется стеком прямого действия или стеком с дисциплиной обслуживания 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.

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