09. Алгоритм заполнения с затравкой, простой алгоритм заполнения с затравкой. - chrislvt/CG GitHub Wiki
Алгоритм затравочного заполнения.
- Должна быть задана область для заполнения(произвольная) не обязательно многоугольные, могут быть области, ограниченные кривой.
- Должна быть задана затравочная точка(затравка) - точка, расположенная внутри области.
Идея затравочного заполнения: ищем точки, соседние с затравочными и лежащие внутри контура – рассматриваем их, как следующие затравочные.
Область может задаваться:
- Путем задания цвета границы – гранично-определенные области
- Путем задания цвета пикселей, расположенных внутри области – внутренне-определенные области.
Область может быть:
- 4-xсвязная – 4 направления движения для достижения точек
- 8-мисвязная – 8 направлений движения для достижения точек
4-х связанная область: для достижения любого пиксела области мы можем использовать 4 направления(2 гориз.направления и 2 вертикальных направления)
8-и связанная область: добавляются диагональные направления.
лекция Курова
Простой алгоритм затравочного заполнения:- Здание исходных данных: Цвет границы и координаты затравочного пиксела(x,y).
- Очертить границы заполняемой области.
- Занесение затравочного пиксела в стек.
- Пока стек не пуст выполнить следующие действия:
4.1 Извлечь пиксель из стека.
4.2 Закрасить пиксель(x, y).
4.3 Анализ 4-х соседних пикселей. (x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)
Если цвет соседнего пиксела не равен цвету границе и цвет этого пиксела не равен цвету заполнения, то текущий пиксель помещаем в стек.
Анализ пиксела на примере (x – 1, y):
Если (x – 1, y) != цвет_границы && (x – 1, y) != цвет_заполнения, то: добавить (x – 1, y) в стек затравочных пикселей
Алгоритм из Д.Роджерса:
Данный алгоритм является неэффективным. Так как в стек будет заноситься очень много затравочных пикселей (любой пиксел, в рассматриваемой области является затравочным). Требуется большой объем памяти для хранения затравочных пикселей. Также это проблему усугубляет то, что некоторые пикселы могут заноситься в стек не по одному разу. Возможна ситуация, что извлекаемые пиксели из стека могут быть уже закрашены.
Быстродействие алгоритмов заполнения зависит от:
- Кол-ва изменений цвета каждого пиксела
- Кол-ва считываний цвета каждого пиксела
- Кол-ва обрабатываемых пикселей
В простом алгоритме:
- Каждый пиксел области меняет цвет один раз
- С каждого пиксела области цвет считывается ~4 раза (кроме пикселей, примыкающих к граничным – там считываний меньше)
- Анализируются только пикселы закрашиваемой области и граничные (с них считывается цвет), пикселы внешней области не анализируются.