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

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

1. В алгоритмах затравочного заполнения должны быть задана область заполнения. Не обязательно многоугольные, могут быть кривые.
2. Должна быть задана затравочная точка (затравка), расположеная внутри области.

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

Области могут 4-х связными и 8-ми связными.

Четырех связные области:

• Используем четыре направления: 2 горизонтальных и 2 вертикальных

Восьми связные области:

• Используем восемь направлений: 2 горизонтальных, 2 вертикальных и четыре диагональных.

Мы будем рассматривать 4-х связные алгоритмы

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

• Прямоугольники могут быть выпуклыми и невыпуклыми, и содержать отверстия.
• Удобная СД для этого алгоритма - стек. В начале кладем в него исходный затравочный пиксель.
• Для нахождения нового затровочного пикселя происходит анализ пикселей по соседству с затравочным пикселем. В простом алгоритме анализируются 4 пикселя от затравочного (справа, слева, сверху, снизу)
• Проанализировать - сравнить цвет с цветом границы и проверить, не закрашен ли рассматриваемый пиксель. Если пиксель не является граничным, и не закрашен, то нужно рассматривать его как новый затравочный пиксель. Кладем его в стек.

Псевдокод

1. Задание исходных данных. Цвет границы и координаты затравочного пикселя х, у.
2. Очертить границы заполняемой области.
3. Занесение затравочного пикселя в стек.
4. Пока стек не пуст, выполнить действия:
   4.1. Извлечь пиксель из стека
   // если операция считывания цвета быстрее чем закраска - стоит проверить, а стоит ли вообще закрашивать
   4.2. Закрасить пиксель (х, у). 
   4.3. Анализ четырех соседних пикселей. 
   4.3.1. Если цвет соседнего пиксела != цвету границе и цвет этого пиксела != заполнения, то push в стек

Оценка эффективности

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

Алгоритм неэффективный! 2 Курова из 10.

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

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