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

Лекция 12

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

Задача графического вывода фигур

Будем считать фигурой плоский геометрический объект, который состоит из линий контура и точек внутри него.

В общем случае линий контура может быть несколько – когда

объект имеет внутри пустоты. В этом случае для описания таких фигур необходимы два и более контуров (рис. 15).

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

Для вывода точек заполнения известны методы, разделяющиеся в зависимости от использования контура на два типа: алгоритмы закрашивания от внутренней точки к границам произвольного контура и алгоритмы, которые используют математическое описание контура.

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

Рекомендуемые материалы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Волновой алгоритм закрашивания был разработан Т.А. Блиновой и В.Н. Поревым и предназначался для расчета центра тяжести объектов по соответствующим изображениям – на основе волнового алгоритма поиска трассы на графе.

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

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

От начальной точки распространяется волна пикселов закрашивания в виде ромба (рис. 17[1]). В одном цикле закрашиваются пикселы вдоль линии периметра ромба (или нескольких ромбов в зависимости от сложности фигуры).

Необходимо заметить, что этот алгоритм не является самым быстрым из известных алгоритмов закрашивания. Большую скорость закрашивания обеспечивают алгоритмы, которые обрабатывают не отдельные пикселы, а сразу блоки из многих пикселов, которые образуют прямоугольники или линии.

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

На этом алгоритме основан принцип работы процедуры FloodFill API Windows.

Алгоритмы заполнения, использующие математическое
описание контура

Математическим описанием контура может служить уравнение y=f(x) для окружности, эллипса или другой кривой. Для многоугольников (полигонов) контур задается множеством координат вершин (x_i, y_i). Возможны и другие формы описания контура. В любом случае алгоритмы данного класса не предусматривают обязательное предварительное создание пикселов контура растра - контур может совсем не выводиться в растр. Рассмотрим некоторые подобные алгоритмы заполнения.

Заполнение прямоугольника (рис. 19). Если прямоугольник задан координатами противоположных углов, например, левого верхнего (x₁, y₁) и правого нижнего (x₂, y₂), тогда алгоритм может заключаться в последовательном рисовании горизонтальных линий заданного цвета:

для y от y₁ до y₂ с шагом 1:

нарисовать горизонтальную линию с координатами (x₁, y)-(x₂, y)

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

Аналогично может быть построен и алгоритм заполнения эллипса.

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

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

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).

Количество тактов работы этого алгоритма:

N_тактов » (y_max - y_min)N_гор ,

Бесплатная лекция: "Дифференциальная ультразвуковая диагностика" также доступна.

где  y_max, y_min – диапазон координат y, N_гор  – число тактов, необходимых для одной горизонтали.

Оценим величину N_гор как пропорциональную числу вершин:

N_гор » k*n,

где  k – коэффициент пропорциональности,  n – число вершин полигона.

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

---

[1] Примеры  (рис. 17 и 18) взяты из источника [12], с.112-113.