КГ Лекция 08. Растровая графика. Алгоритмы заполнения с затравкой.

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

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

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

Начиная с затравки алгоритм начинает рассмотрение всех пикселей, находящиеся внутри многоугольника.

Общие требования алгоритма

1. Должна быть задана область, подлежащая заполнению:
   • Внутренне-определенная область;

• Гранично-определенная область;

2. Должна быть задана затравка.

Способы задания области.

1. Гранично-определенная (алгоритм гранично-заполняющий), где задана граница области, т.е. известен цвет границы.

   

2. Внутренне-определенная (алгоритм внутренне-заполняющий), где все пиксели принадлежать внутренней части и имеют один и тот же цвет или интенсивность), внешняя по отношению к внутренней имеет другой цвет.

   

Закрашивания области могут быть:

1. Четырех-связными, любой пиксель в области можно достичь с помощью комбинации движений только в 4 направлениях: налево, направо, вверх, вниз.
2. Восьми-связными, любой пиксель в области можно достичь с помощью комбинации движений: 2-x горизонтальных, 2-х вертикальных и 4-х диагональных направлениях.

Примечание: алгоритм заполнения 8-связной области заполнит 4-связную область, обратное неверно.

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

Используя стек, можно разработать простой алгоритм заполнения гранично-определенной области.

В начале нужно поместить пиксель в стек, и выполнять цикл пока стек не пустую

• Извлечь пиксель из стека
• Присвоить пикселу требуемое значение
• Для каждого из соседних к текущему 4-связных пикселов проверить: является ли он граничным пикселом или не присвоено ли уже пикселу требуемое значение.
• Проигнорировать пиксел в любом из этих двух случаев. В противном случае поместить пиксел в стек.

Примечание: алгоритм можно модифицировать для 8-связных областей, если просматривать 8-связные пикселы, а не только 4-свзяные.

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

1. Здание исходных данных: 
   1.1 Цвет границы и координаты затравочного пиксела (X,Y).
   1.2 Очертить границы заполняемой области.
2 Занесение затравочного пиксела в стек.
3 Пока стек не пуст выполнить следующие действия:
  3.1 Извлечь пиксель из стека.
  3.2 Закрасить пиксель (X, Y) заданным цветом.
  3.3 Анализ 4-х соседних пикселей. 
     (X + 1, Y), 
     (X, Y + 1), 
     (X - 1, Y), 
     (X, Y - 1).
  3.4 Если пиксель не является граничным, то поместить его в стек.

Примечание: Возможность задать эллипс или окружность

Простой алгоритм заполнения с затравкой (Д.Роджерса)

Плюсы

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

Недостатки:

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

Построчный