КГ Лекция 08. Растровая графика. Алгоритмы заполнения с затравкой.
В прошлых алгоритмах заполнения применялся подход со сканирующей строкой, т.е. в порядке сканирования начиная с наивысшей сканирующей строки. Иной подход используется в алгоритмах с затравкой - в них предполагается что известный, так называемые затравочный пиксель, находящийся внутри многоугольника.
Затравка(затравочный пиксель) – пиксель, лежащий заведомо внутри области, с которого начинается рассмотрение.
Начиная с затравки алгоритм начинает рассмотрение всех пикселей, находящиеся внутри многоугольника.
- Должна быть задана область, подлежащая заполнению:
- Внутренне-определенная область;
- Гранично-определенная область;
- Должна быть задана затравка.
-
Гранично-определенная (алгоритм гранично-заполняющий), где задана граница области, т.е. известен цвет границы.
-
Внутренне-определенная (алгоритм внутренне-заполняющий), где все пиксели принадлежать внутренней части и имеют один и тот же цвет или интенсивность), внешняя по отношению к внутренней имеет другой цвет.
Закрашивания области могут быть:
- Четырех-связными, любой пиксель в области можно достичь с помощью комбинации движений только в 4 направлениях: налево, направо, вверх, вниз.
- Восьми-связными, любой пиксель в области можно достичь с помощью комбинации движений: 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 Если пиксель не является граничным, то поместить его в стек.
Примечание: Возможность задать эллипс или окружность
Алгоритм достаточно прост в реализации и понимании.
Данный алгоритм является неэффективным. Так как в стек будет заноситься очень много затравочных пикселей (любой пиксел, в рассматриваемой области является затравочным). Требуется большой объем памяти для хранения затравочных пикселей. Также это проблему усугубляет то, что некоторые пикселы могут заноситься в стек не по одному разу. Возможна ситуация, что извлекаемые пиксели из стека могут быть уже закрашены.
В построчном алгоритме заполнения размера стека минимизируется за счет хранения только одного затравочного пиксела для любого непрерывного интервала на сканирующей строке.
Непрерывный интервал - это группа примыкающих друг к другу не закрашенными пикселов(ограниченная уже заполненными и граничными пикселами).
1. Ввод исходных данных
Границы области;
Цвет заполнения;
Цвет границ;
2. Занесения затравочного пикселя в стек
3. Пока стек не пуст, выполнять след действия:
3.1 Извлечь затравочный пиксель из стека
3.2 Закраска пикселей, расположенных в той же строке, что и затравочный,
влево и вправо от него, пока не будут достигнуты границы
(Сам затравочный пиксел тоже закрасим)
3.3 Заполнить координаты самого левого и правого
закрашенных пикселей. X_лев и X_прав
3.4 Поиск новых затравочных пикселей в диапазоне
[X_лев, X_прав], т.е. X_лев <= X <= X_прав проверяются
на двух соседних строках:
Сверху - yв = y + 1
Cнизу - yн = y - 1
Определяется, есть ли на них еще не заполненные пикселы.
Если такие есть(т.е. не все пикселы граничные или заполненные),
то в указанном диапазоне крайний правый пиксел(если поиск ведётся слева направо)
в каждом интервале отмечается как затравочный и помещается в стек.
Иначе, в случае не нахождения - пропускается
Цвет каждого пикселя анализируется 3 раза у всех пикселей, кроме пикселей, примыкающих к граничным пикселям сверху и снизу, а также у первого затравочного пиксела - там 2 считывания.
Почему у пикселей, примыкающих к граничным сверху и снизу меньше считываний: в построчном алгоритме последовательно обрабатываются строка с текущей затравкой, строка над ней и строка под ней. Все строки, кроме примыкающих к граничным будут обработаны в качестве вышележащих относительно какой-то строки, нижележащих и собственно содержащих затравку - это три считывания. Строки, прилежащие к нижним граничным не будут обработаны в качестве вышележащих - остается только два считывания. Строки, примыкающие к верхним граничным не будут обработаны в качестве нижележащих - остается два считывания.
Цвет каждого пикселя меняется только один раз.
Обрабатываются пиксели, находящиеся внутри области закраски, а так же пиксели, расположенные на границе: будет считан цвет граничных пикселей. За пределами области ничего не анализируем.
Размещаем в стеке не каждый затравочный пиксель, а один затравочный пиксель для каждого непрерывного интервала пикселей.
По быстродействию затравочный алгоритм уступает растровым. В растровых мы за минимальное число операций определяем, что нужно красить. Для затравочных алгоритмов дело обстоит по другому. Мы работаем со стеком, так вынуждены еще и трижды (в нашем алгоритме) узнавать цвет каждого пикселя.
Например, сравним затравочный алгоритм с алгоритмом заполнения по рёбрам. В алгоритме по ребрам, например, хоть он и не самый быстрый, мы за 2-3 арифметических операций определяем, что нужно закрасить кусок строки. Это происходит довольно быстро, и число запросов цвета минимально (не сильно больше числа закрашиваний).
- Пиксели не могут иметь цвет границы.
- Пиксели могут иметь цвет закраски, но в ограниченном количестве. Может быть и в неограниченном, но важно, как распределены в области.
- Любой другой цвет они могут иметь.