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

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

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

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

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