Построчный алгоритм заливки с затравкой

Использует пространственную когерентность:

· пикселы в строке меняются только на границах;

· при перемещении к следующей строке размер заливаемой строки скорее всего или неизменен или меняется на 1 пиксел.

Таким образом, на каждый закрашиваемый фрагмент строки в стеке хранятся координаты только одного начального пиксела [], что приводит к существенному уменьшению размера стека.

Последовательность работы алгоритма для гранично определенной области следующая:

1. Координата затравки помещается в стек, затем до исчерпания стека выполняются пункты 2-4.

1. Координата очередной затравки извлекается из стека и выполняется максимально возможное закрашивание вправо и влево по строке с затравкой, т.е. пока не попадется граничный пиксел. Пусть это Хлев и Хправ, соответственно.
2. Анализируется строка ниже закрашиваемой в пределах от Хлев до Хправ и в ней находятся крайние правые пикселы всех незакрашенных фрагментов. Их координаты заносятся в стек.
3. То же самое проделывается для строки выше закрашиваемой.

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