Заливка области с затравкой
Основы
Алгоритм применим, когда область, подлежащая заливке, не является многоугольником. Множество пикселей на растре не задает область однозначно, поэтому требуется задать координаты "затравочного" пикселя, принадлежащего области. При данном способе заливки тем или иным способом выбирается произвольная точка, являющаяся заведомо внутренней для заданной области. Эта точка закрашивается. Закрашиваются также все ее не закрашенные соседи по заданному критерию связности и их адреса записываются в стек. Далее из стека извлекается адрес очередной точки и с ней поступают точно так же, как с предыдущей. Процедура повторяется до тех пор, пока в стеке будет находиться адрес хотя бы одной точки.
Пример простого алгоритма
Простейший алгоритм заполнения с затравкой - это так называемый алгоритм короеда, получивший подобное название, поскольку заполняемая область последовательно "выедается" по одному пикселю. При обходе соседних пикселей может рассматриваться и 4-связность , и 8-связность. В зависимости от этого результат будет различным.
Модифицированный алгоритм
Простой алгоритм выше можно модифицировать, вместо того что бы на каждой итерации закрашивать один пиксель, закрашивать линию. Для этого используется пространственная когерентность:
- пиксели в строке меняются только на границах
- при перемещении к следующей строке размер заливаемой строки скорее всего или неизменен, или меняется на 1 пиксель
Таким образом, на каждый закрашиваемый фрагмент строки в стеке хранятся координаты только одного начального пикселя, что приводит к существенному уменьшению размера стека.
Последовательность работы алгоритма следующая:
- Координата затравки помещается в стек, затем до исчерпания стека выполняются пункты 2-4
- Координата очередной затравки извлекается из стека и выполняется максимально возможное закрашивание вправо и влево по строке с затравкой, т.е. пока не попадется граничный пиксель. Пусть это ХLeft и ХRight, соответственно.
- Анализируется строка ниже закрашиваемой в пределах от ХLeft до ХRight и в ней находятся крайние правые пиксель всех не закрашенных фрагментов. Их координаты заносятся в стек
- То же самое проделывается для строки выше закрашиваемой