2014-02-02
1243
Поместить затравочный пиксел в стек
Пока стек не пуст
Извлечь пиксел из стека
Присвоить пикселу требуемое значение
Для каждого из соседних к текущему 4-связных пикселов проверить: является ли он граничным пикселом или не присвоено ли уже пикселу требуемое значение. Проигнорировать пиксел в любом из этих двух случаев. В противном случае поместить пиксел в стек.
Приведем более формальное изложение алгоритма, в котором предполагается существование затравочного пиксела и гранично-определенной области:
В качестве примера применения алгоритма рассмотрим гранично-определенную область, содержащую дыру. Она изображена на рис. 2.15.
Вершины многоугольника заданы пикселами (1,0), (7,0), (8,1), (8,4), (6,6), (1,6), (0,5) и (0,1). Внутренняя дыра определяется пикселами (3,2), (5,2), (5,3), (3,3). Затравочный пиксел — (4,4). Порядок заполнения указан на рисунке линией со стрелками. Числа в квадратике пиксела показывают позицию в стеке, занимаемую пикселом. Когда обработка доходит до пиксела (3,1), все окружающие его 4-связные пикселы либо уже заполнены, либо являются граничными. Поэтому ни один из пикселов не помещается в стек. Глубина стека в этот момент равна 15. В стеке находятся пикселы (7,1), (7,2), (7,3), (6,5), (7,4), (6,5), (3,1), (1,2), (1,3), (1,4), (2,5), (3,5), (4,5), (5,4).
