КГ Лекция 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 арифметических операций определяем, что нужно закрасить кусок строки. Это происходит довольно быстро, и число запросов цвета минимально (не сильно больше числа закрашиваний).
- Пиксели не могут иметь цвет границы.
- Пиксели могут иметь цвет закраски, но в ограниченном количестве. Может быть и в неограниченном, но важно, как распределены в области.
- Любой другой цвет они могут иметь.
Изначально пиксели области могут иметь любой цвет, кроме граничного. Если же весь многоугольник был окрашен цветом заливки, то перекрасится только та строка, где выставлен затравочный пиксел. Затем проанализируется верхняя и нижняя строки, ни один новый пиксел не будет добавлен в стек и алгоритм будет прекращен. Также возможен случай когда 3 строки окрашены цветом заливки, а затравочный пиксел выбран в средней строке. Тогда фигура закрашена не будет.
В среднем 3 раза. Первый раз на строке пиксела, второй раз при поиске затравки на нижней, а третий раз на верхней.
В заданном интервале поиска необходимо найти не первый попавшийся затравочный пиксель, а искать до тех пор пока не найдем самый правый затравочный пиксель в заданном интервале. Это нужно делать потому что рассматриваемый интервал пикселей может прерываться граничными пикселами или уже закрашенными пикселами, т.е рассматриваемый интервал может содержать в своем составе несколько непрерывных интервалов пикселей. Здесь будет понятно почему нужно брать самый правый, потому что если возьмем самый левый при движении слева направо, то мы не найдем затравочные пиксели для других интервалов входящий в состав исходного интервала и тем самым задачу не решим.
"Потому что в ином случае мы можем потерять одну из областей, которую необходимо было закрасить"
В растровых методах делается попытка определить в порядке сканирования строк принадлежность точки внутренней области контура или многоугольника. Эти алгоритмы обычно просматривают многоугольники (контуры) от верхней точки до нижней. Методы растровой развертки применимы обычно и к векторным дисплеям, в которых они используются для штриховки или закраски контуров. (растровая развертка = закраска)
В методах затравочного заполнения предполагается, что известна некоторая точка (затравка), лежащая внутри замкнутого контура. В алгоритмах затравочного заполнения ищут точки, соседние с затравочными и расположенные внутри контура. Если точка оказывается внутри контура, то она становится новой затравочной точкой и поиск продолжается рекурсивно. Если же точка расположена не внутри контура, то это означает, что обнаружена граница контура. Затравочные алгоритмы применимы только к растровым дисплеям.