Алгоритмы закрашивания

 

Будем считать фигурой плоский геометрический объект, который состоит из линий контура и точек внутри него. В общем виде алгоритм закрашивания произвольного контура, который уже нарисован в растре, предполагает выполнение следующих действий:

– находим пиксел внутри контура фигуры;

– цвет этого пиксела изменяем на нужный цвет заполнения;

– производим анализ соседних пикселов;

– если цвет некоторого соседнего пиксела не равен цвету границы контура или цвету заполнения, то цвет этого пиксела изменяется на цвет заполнения;

– анализируем цвет пикселов, соседних с предыдущим. Продолжаем этот процесс, до тех пор, пока внутри контура все пикселы не перекрасятся в цвет заполнения.

Простейший алгоритм закрашивания. Для всех алгоритмов закрашивания необходимо задавать начальную точку с координатами x ₀, y ₀ внутри контура. Простейший алгоритм может быть описан следующим образом [21, 24].

1. Определить x ₀, y ₀.

2. Выполнить процедуру Закрасить (x ₀, y ₀).

Процедура Закрасить (x, y) описана в виде:

если цвет пиксела (x,y) не равен цвету границы, то

установить для пиксела (x,y) цвет заполнения;

закрасить(x+1, y);

закрасить(x-1, y);

закрасить(x, y+1);

закрасить(x, y-1).

Такое определение процедуры является рекурсивным. Рекурсия позволяет упростить запись некоторых алгоритмов.

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

Волновые алгоритмы закрашивания. Суть подобных алгоритмов состоит в том, что для начальной точки (вершины на графе) находятся соседние точки (другие вершины), которые отвечают двум условиям: во-первых, эти вершины связаны с начальной; во-вторых, они еще не отмечены, т.е. рассматриваются впервые.

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

Относительно закрашивания растровых фигур вершинами графа являются пикселы, а отметка пройденных пикселов делается прямо в растре цветом закрашивания. Это почти полностью повторяет идею простейшего алгоритма, однако здесь не используется рекурсия, что обусловливает другую последовательность обработки пикселов при закрашивании.

Заполнение полигона. Контур полигона (в векторной форме) определяется вершинами, которые соединены отрезками прямых (рис. 9.6).

Один из наиболее популярных алгоритмов заполнения полигона заключается в закрашивании фигуры отрезками прямых горизонтальных линий. Алгоритм представляет собою цикл вдоль оси y, в ходе этого цикла выполняется поиск точек сечения линии контура с соответствующими горизонталями. Этот алгоритм имеет вид:

 

1. Найти min{y_i} и max{y_i} среди всех вершин P_i.

2. Выполнить цикл по y от y=min до y=max:

3. Найти точки пересечения всех отрезков контура с горизонталью y;

4. Координаты x_j точек сечения записать в массив;

5. Отсортировать массив {x_j} по возрастанию x;

6. Вывести горизонтальные отрезки с координатами

(x₀, y) - (x₁, y)

(x₂, y) - (x₃, y)

………………

(x_2k, y) - (x_2k+1, y)

Каждый отрезок выводится цветом заполнения.

В этом алгоритме использовано свойство топологии контура фигуры. Оно состоит в том, что любая прямая линия пересекает любой замкнутый контур четное число раз. Для выпуклых фигур существуют ровно две точки пересечения с любой прямой. Таким образом, на шаге 4 этого алгоритма в массив { x_j } всегда должно записываться парное число течек сечения.

При нахождении точек пересечения горизонтали с контуром необходимо принимать во внимание особые точки. Если горизонталь имеет координату y, совпадающую с y_i вершины P_i, тогда надлежит анализировать то, как горизонталь проходит через вершину. Если горизонталь при этом пересекает контур (как, например, в вершинах P ₀ или P ₄), то в массив записывается одна точка сечения. Если горизонталь касается вершины контура (в этом случае вершина соответствует локальному минимуму или максимуму, как, например, в вершинах P ₁, P ₂, P ₃ или P ₅), тогда координата точки касания или не записывается, или записывается в массив два раза. Это условие четности числа количества точек пересечения, хранящихся в массиве { x_j }.

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

Для определения координат (x) точек пересечения для каждой горизонтали необходимо перебрать все n отрезков контура. Координаты пересечения отрезка p_i-p_k с горизонталью равны:

x = x_i + (y_k - y)(x_k - x_i) / (y_k - y_i).

Приведенные выше алгоритмы заполнения могут быть использованы не только для рисования фигур. На их основе могут быть разработаны алгоритмы для других целей, например, для определения площади фигуры, если считать площадь пропорциональной числу пикселов заполнения. Или, например, алгоритм для поиска объектов по внутренней точке – эта операция часто используется в векторных графических редакторах.

 

9.3. Сглаживание ступенчатости линий на изображении

 

После растрового преобразования образы прямолинейных отрезков и ребер выглядят как бы состоящими из мелких ступенек. Природа их кроется в самом принципе преобразования непрерывной линии. Пикселы имеют определенное положение и образуют сетку с постоянным шагом. Кроме того, пиксели имеют фиксированный размер и форму. Алгоритм Брезенхема позволяет определить точки ближайшие к линии, но если устройство отображения позволяет воспроизводить оттенки цветов, эффект ступенчатости можно ослабить.

Идеализированный образ математической линии имеет постоянную толщину (1 единицу). Такой образ построить невозможно. В чистом виде алгоритм Брезенхема предполагает, что за каждый шаг перемещения по оси x засвечивается только один пиксел. Но можно поступить по другому – засвечивать те пикселы, которые частично перекрываются идеальным образом линии, но задавать им не полную интенсивность, а частичную, пропорциональную степени перекрытия [24].

Контрольные вопросы и задания

1. В чем принцип алгоритма ЦДА?

2. За счет чего достигается быстродействие в алгоритме Брезенхема?

3. Какими способами осуществляется закраска областей?

4. Как устраняется ступенчатость на изображении в системах компьютерной графики?