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

Фигурой будем считать плоский геометрический объект, который состоит из ли­ний контура и точек заполнения, которые помещаются внутри контура. Контуров может быть несколько — например, если объект име­ет внутри пустоты.

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

Для вывода точек заполнения известны методы, которые разделяются в зависимости от ис­пользования контура на два типа:

— алгоритмы закрашивания от внутренней точки к границам произволь­ного контура;

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

Рассмотрим алгоритмы закрашивания произвольного контура, который уже нарисован в растре. Сначала определяются координаты произвольного пиксела, находящегося внутри очерченного контура фигуры. Цвет этого пиксела изменяем на нужный цвет заполнения. Потом проводится анализ цветов всех соседних пикселов. Если цвет некоторого соседнего пиксела не равен цвету границы контура или цвету заполнения, то цвет этого пиксела изме­няется на цвет заполнения. Потом анализируется цвет пикселов, соседних с предшествую­щими. И так далее, пока внутри контура все пикселы не перекрасятся в цвет заполнения. Пикселы контура образуют границу, за которую нельзя выходить в ходе последователь­ного перебора всех соседних пикселов.

Алгоритм закрашивания линиями получил широкое распростране­ние в компьютерной графике. Сущность его заключается в том, что на каждом шаге закрашивания рисуется горизонтальная линия, которая размещает­ся между пикселами, имеющими цвет контура. Затем проводится анализ цвета пикселов на соседних строчках, и если цвет пикселов не равен цвету пикселов контура, процедура заполнения линии вызывается снова для следующей строки. Закрашивание начинается в некоторой точке А, координаты которой нужно задать при вызове процедуры, и заканчивается, когда внутри контура не остается ни одного незакрашенного пиксела, рис. 13.6.

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

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

Среди всех фигур наиболее просто запол­нять прямоугольник. Если прямо­угольник задан координатами противо­полож­ных углов, например, лево­го верхнего (x₁, y₁) и правого нижнего (x₂, y₂), тогда алгоритм может состоять в пос­ле­дова­тельном рисовании горизонтальных линий заданного цвета рис. 13.7 а.

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

Контур полигона определяется вершинами, которые соединены отрез­ками прямых — ребрами, рис. 13.7 в. Рассмотрим один из наиболее популярных алгоритмов заполнения полигона. Его основ­ная идея — закрашивание фигуры отрезками горизонтальных линий. Алгоритм представляет собою цикл вдоль оси у, в ходе этого цикла выполняется поиск точек пересечения линии контура с соответствующими горизонталями. В алгоритме использовано топологи­ческое свой­ство контура фигуры, состоящее в том, что любая пря­мая линия пересекает любой замкнутый контур четное количество раз.

Для определения координат х точек пересечения для каждой горизонтали необходи­мо перебирать все n ребер контура. Координата х пересечения ребра
P_i – P_i+1 с горизонталью у равняется

. (13.21)

Полученный в результате перебора ребер массив точек пересечения упорядочивается по возрастанию, (x₀, x₁, x₂, x₃, см. рис. 13.7 в.) и разбивается на пары, которые соединяются отрезками горизонтальных линий.

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