10. Алгоритмы заполнения с затравкой. Построчный алгоритм заполнения с затравкой.

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

См. тут

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

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

Непрерывный интервал пикселей - группа примыкающих друг к другу пикселей, расположенных на одной сканирующей строке, ещё не закрашенных и не являющих граничными. Но, ограниченная граничными или уже закрашенными пикселями.

Группа - красные, граничные - зеленые. Класть в стек будем только один пиксель из этой группы.

Псевдокод

1. Ввод исходных данных (информация о границах, цвет границы, цвет закрашивания, затравочный пиксель)
2. Вычерчивание границ закрашеваемой области.
3. Занесение затравочного пикселя в стек.
4. Пока стек не пусть, выполнить:
   4.1. Извлечь затравочный пиксель из стека.
   4.2. Закрашивание пикселей текущей строки, начиная с затравочного, 
   влево и вправо от него до достижения границы (левой и правой)
   4.3 Запоминание х левого и х правого (абсциссы самого левого и самого правого закрашенных пикселей).
   !!! То есть берем не граничный, а справа / слева от него !!!
   /*
   Достигли левой - запомнили абсциссу самого левого, но еще закрашенного пикселя. 
   Восстановить абсциссу затравочного пикселя, прежде чем двигаться вправо 
   (поэтому надо запомнить абсциссу затравочного)
   */
   4.4. Поиск на двух соседних по отношению к текущей строке в интервале [х левое; х правое]
   новых затравочных пикселей. Любой ещё не закрашенный и не граничный пиксель в заданном
   интервале, может рассматриваться как затравочный. Но, в качестве нового затровочного пикселя
   необходимо взять самый правый из затравочных, если поиск идется слева направо. 
   Справа налево - наооборот.
5. Конец.

Начальные цвета

• Пиксели внутри не могут иметь цвет границы, иначе будет закрашен только затравочный пиксель.
• Пиксели могут иметь цвет закраски (в ограниченном количестве, но не всегда), иногда это может привести к неполной закраске, например как тут.

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

однако если уже существующая закраска не перекрывает интервал полностью, то вся фигура будет закрашена, как в таком примере:

Анализ эффективности

• Цвет пикселя меняется всего лишь один раз.
• Обрабатываются пиксели внутри области и граничные пиксели. В среднем, пиксель будет обработан 3 раза: при проходе по его строке, и при поиске затравочных пикселей слева и справа.
• Размещаем в стеке только лишь один затравочный пиксель, для непрерывного интервала пикселей.

Алгоритм уступает растровым. В растровых за минимальное число операций можно определить, что нужно закрасить. Например, алгоритм по ребрам, за 2-3 арифметические операциии определяет что нужно закрасить кусок строки (Однако перекрашивания дают проигрыш во времени, поэтому лучше сравнивать с алгоритмами, у которых нет перекрашиваний).

Алгоритм позволяет закрасить любую гранично-определенную область. Так как алгоритм не работает с отрезками (или многоугольниками), а отталкивается от расположения границ, то он позволяет закрашивать и более сложные фигуры, нежели многоугольники.

Следующий вопрос: 11. Основы методов устранения ступенчатости. Алгоритм Брезенхема с устранением ступенчатости. Алгоритм Ву.

Предыдущий вопрос: 09. Алгоритм заполнения с затравкой, простой алгоритм заполнения с затравкой.