Алгоритмы вывода фигур.

4. Фигурой будем считать плоский геометрический объект, который состоит из линий контура и точек, которые содержатся внутри контура. В общем случае линии контура может быть несколько – когда объект имеет внутри пустоты. В этом случае для описания таких фигур необходимы два и более контуров.

Графический вывод фигур разделяется на 2 задачи: вывод контура и вывод точек заполнения.

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

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

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

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

Простейший алгоритм закрашивания.

Для всех алгоритмов закрашивания нужно задать начальную точку внутри контура с координатами (). Простейший алгоритм можно описать так:

Шаг 1. Определить .

Шаг 2. Выполнить функцию Закрашивание ().

Эту функцию определить так:

Функция Закрашивание (х, у)

{ если цвет пиксела (х, у) не равен цвету границы, то {установить для пиксела (х, у) цвет заполнения;

Закрашивание (х+1, у);

Закрашивание (х-1, у);

Закрашивание (х, у+1);

Закрашивание (х, у-1);

}

}

Такое определение функции является рекурсивным. Рекурсия позволяет упростить запись некоторых алгоритмов, но для этого алгоритма рекурсия порождает существенные проблемы – рекурсивные вызовы функции Закрашивание точки делается для каждого пиксела, что обычно приводит к перевыполнению стека входе выполнения программы. Этот алгоритм не приемлем для фигур площадью в тысячу и больше пикселов.

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

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

1)эти вершины связаны с начальной;

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

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

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

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

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

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

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

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

For (у=у1; у<=y2,y++);

//рис. горизонт. линию с координатами (х1,у)-(х2,у)

х1

у1

у2

х2

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

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

Заполнение полигонов.

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

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

Выполнить цикл по у=min до у=max

{

Нахождение точек пересечения всех отрезков контура с горизонталью у. Координаты точек пересечения записать в массив.

Сортировка массива { } по возрастанию х.

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

(

(

………………..

(

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

}

В этом алгоритме использовано свойство топологии контура фигуры: любая прямая линия пересекает любой замкнутый контур четное количество раз. Для выпуклых фигур точек пересечения с любой прямой всегда две. Т.е на шаге 3 в массив { всегда должно заполнятся парное число точек сечения. При нахождении точек пересечения горизонтами с контуром необходимо принимать во внимание особые точки. Если горизонталь имеет координату у совпадающую с вершины , то надо проанализировать то, как горизонталь проходит через вершину. Если горизонталь пересекает контур (как например в вершине Р или , то в массив заполняется одна точка сечения. Если горизонталь касается вершины контура (в этом случае вершина соответствует локальному мин или мак, как например в вершине , или ), тогда координата точки касания или не записывается, или записывается в массив 2 раза.

Процедура определения точек пересечения контура с горизонтальной разверткой, учитывая анализ на локальный мак, может быть достаточно сложной, что будет замедлять работу. Решением для упрощения поиска точек сечения может быть смещение координат вершин контура или горизонталей заполнения таким образом, чтобы ни одна горизонталь не попала в вершину. Смещение можно выполнить различными способами, например, ввести в растр дробные координаты для горизонталей: ymin+0,5; ymin+1,5;….; ymax-0,5. Но такое упрощение процедуры нахождения точек пересечения приводит к искажению формы полигона.

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

x = xi+(yk-y)(xk-xi)/(yk-yi).

Количество тактов работы такого алгоритма N≈(ymax-ymin)Nгор, где ymax, ymin – диапазон координаты y, Nгор – число тактов, необходимых для одной горизонтали. Оценим величину Nгор как пропорциональную числу вершин Nгор ≈ k*n, k – коэффициент пропорциональности, n – число вершин полигона.

Возможны модификации описанного алгоритма для ускорения его работы. Например, можно принять во внимание то, что каждая горизонталь в большинстве случаев пересекает небольшое количество ребер контура. Поэтому, если при поиске точек сечения делать предварительный отбор реьер, которые находятся вокруг каждой горизонтали, то можно добиться уменьшения количества тактов работы до k+nр, где np – число отобранных ребер.

Например, разделим диапазон ymax-ymin пополам. Если для диапазона от ymin до yср составить список отрезков (или вершин), которые попадают в этот диапазон, то в список будет включено приблизительно вдвое меньшее количество, чем для всего диапазона от ymin до ymax. Т.о., при работе алгоритма для каждой горизонтали в диапазоне от ymin до yср уже нужно не k*n тактов, а k*n/2.

Аналогично для диапазона yср - ymin, также можно составить список ребер, который также будет почти вдвое меньше(Nгор/2). Тогда общее число тактов N≈(ymax-ymin)Nгор/2+Nдоп, где Nдоп – количество тактов для создания списка ребер.

Такой способ повышения быстродействия эффективен для большого количества вершин. Контур можно делить не пополам, а на более мелкие части.

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

Дата добавления: 2015-07-10