09. Алгоритм заполнения с затравкой, простой алгоритм заполнения с затравкой. - p1xelse/CG GitHub Wiki

Алгоритм затравочного заполнения.

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

Идея затравочного заполнения: ищем точки, соседние с затравочными и лежащие внутри контура – рассматриваем их, как следующие затравочные.

Область может задаваться:

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

Область может быть:

  1. 4-xсвязная – 4 направления движения для достижения точек
  2. 8-мисвязная – 8 направлений движения для достижения точек

4-х связанная область: для достижения любого пиксела области мы можем использовать 4 направления(2 гориз.направления и 2 вертикальных направления)

8-и связанная область: добавляются диагональные направления.

Простой алгоритм затравочного заполнения: лекция Курова

  1. Здание исходных данных: Цвет границы и координаты затравочного пиксела(x,y).
  2. Очертить границы заполняемой области.
  3. Занесение затравочного пиксела в стек.
  4. Пока стек не пуст выполнить следующие действия:
    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 раза (кроме пикселей, примыкающих к граничным – там считываний меньше)
  • Анализируются только пикселы закрашиваемой области и граничные (с них считывается цвет), пикселы внешней области не анализируются.