Построчное заполнение(Список активных ребер)

ЗАПОЛНЕНИЕ МНОГОУГОЛЬНИКА.

Существует две разновидности заполнения:

1) заполнение внутренней части многоугольника, заданного координатами его вершин.

2) заливка области, которая либо очерчена границей с кодом пиксела, отличающимся от кодов любых пикселов внутри области, либо закрашена пикселами с заданным кодом;

Рассмотрим алгоритм заполнения многоугольника.

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

Определить принадлежность пиксела многоугольнику можно, например, подсчетом суммарного угла с вершиной на пикселе при обходе контура многоугольника. Если пиксел находиться внутри, то угол будет равен 360, если вне - 0 (рис. 7.2).

Рис. 7.2: Определение принадлежности пиксела многоугольнику

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

Построчное заполнение(Список активных ребер)

Алгоритмы построчного заполнения основаны на том, что соседние пикселы в строке скорее всего одинаковы и меняются только там, где строка пересекается с ребром многоугольника. Это называется когерентностью растровых строк (строки сканирования Yi, Yi+1, Yi+2 на рис. 7.3). При этом достаточно определить X-координаты пересечений строк сканирования с ребрами. Пары отсортированных точек пересечения задают интервалы заливки.

Рис. 7.3: Построчная закраска многоугольника

Кроме того, если какие-либо ребра пересекались i-й строкой, то они скорее всего будут пересекаться также и строкой i+1. (строки сканирования Yi и Yi+1 на рис. 7.3). Это называется когерентностью ребер. При переходе к новой строке легко вычислить новую X-координату точки пересечения ребра, используя X-координату старой точки пересечения и тангенс угла наклона ребра:

(тангенс угла наклона ребра - k = dy/dx, так как dy = 1, то 1/k = dx).

Смена количества интервалов заливки происходит только тогда, когда в строке сканирования появляется вершина.

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

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

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

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

Рис. 7.4. Заполнение прямоугольника

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

Рис. 7.5. Заполнение кругаРис. 7.6. Заполнение круга

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

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

Рис. 7.7. Заполнение полигона

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

В этом алгоритме использовано топологическое свойство контура фигуры. Оно состоит в том, что любая прямая линия пересекает любой замкнутый контур четное количество раз (рис. 7.7). Для выпуклых фигур точек пересечения с любой прямой всегда две.

При нахождении точек пересечения горизонтали с контуром необходимо принимать во внимание особые точки. Если горизонталь имеет координату (у), совпадающую с координатой yi вершины Рi, тогда необходимо анализировать то, как горизонталь проходит через вершину. Если горизонталь при этом пересекает контур, как, например, в вершинах Р0 или Р4, то в массив записывается одна точка пересечения. Если горизонталь касается вершины контура (в этом случае вершина соответствует локальному минимуму или максимуму, как, например, в вершинах Р1, Р2, Р3 или Р5), тогда координата точки касания или НЕ записывается, или записывается в массив два раза. Это является условием четного количества точек пересечения, хранящихся в массиве {хj}.

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

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

Для определения координат (х) точек пересечения для каждой горизонтали необходимо перебирать все η – разбиений ребер контура. Координата пересечения peбра pi -pk c горизонталью (у) равняется

x= x_i+ (у_k - у)(х_к- х_i)/(у_k - у_i).

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

N_тактов≈(у_мах–y_min)N_гор,

где y_max, y_min — диапазон координат y, Ν_гоρ — число тактов, нужных для одной горизонтали. Оценим величину Ν_гоρ как пропорциональную числу вершин

Ν_гоρ ≈k∙n,

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

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

с N_гор = к ∙ n до N_гор = к∙ n_р,

где n_p — количество отобранных ребер.

Если, разделим диапазон y_min -y_max пополам,то для диапазона от y_min до y_ср необходимо составить список ребер (или вершин), попадающих в этот диапазон.В этом случае в список будет включено приблизительно вдвое меньшее количество, чем для всего диапазона от y_min до y_max. (приблизительно т.к. это зависит от размещения вершин контура полигона). Таким образом, при работе алгоритма для каждой горизонтали в диапазоне от y_min до y_ср уже нужно не ( k · n ) тактов, а (k · n/2).

Аналогично для диапазона от у_ср до y_mах можно составить список ребер, который также будет почти вдвое меньшим. Если принять, что подсчеты для каждой горизонтали теперь выполняются за вдвое меньшее количество тактов, а именно за (N_гор /2), то общее число тактов:

N_тактов≈(у_мах–y_min) N_гор/2+N_доп,

где Ν_доп — количество тактов, которые необходимы при создании списка ребер.

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

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

ПРОСТОЙ АЛГОРИТМ С УПОРЯДОЧЕННЫМ СПИСКОМ РЕБЕР

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

Простой алгоритм с упорядоченным списком ребер:

1. Подготовить данные о координатах окончаний каждого отрезка
2. Определить прямоугольную область, охватывающую многоугольник
3. Запустить цикл по оси Y_скан.
4. Выделить список активных ребер
5. Определить для каждого активного ребра многоугольника точки пересечений со сканирующими строками для чего можно использовать алгоритм Брезенхема или ЦДА.
6. Горизонтальные ребра игнорируются.
7. Занести каждое пересечение в список.
8. Отсортировать список по строкам и по возрастанию х в строке; т. е. (x1, у1) предшествует (х2, у2), если у1> у2 илиУ1 = У2и Х1<= X2-
9. Преобразовать эти данные в растровую форму:
10. Выделить из отсортированного списка пары элементов x1 и x2 на одной сканирующей строке Yскан = Y1 = Y2
11. Активировать на сканирующей строке у пикселы для целых значений х, таких, что х1<Xскан <x2.

Если закрашивается треугольник то этапы 8 и 10 не проводятся.