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

Алгоритм растровой развертки многоугольников основан на построчном сканировании многоугольника с верхней его вершины до нижней. При этом производится заполнение многоугольника по сканируемым строкам. Рассмотрим характер пересечения сканирующей строки с многоугольником (рис. 1.11).

Сканирующая строка разбивается многоугольником на пять интервалов в точках ее пересечения со сторонами многоугольника. Необходимо выделить на сканирующей строке точки, принадлежащие внутренней области многоугольника. Из рисунка видно, что внутри многоугольника лежат точки интервалов (x₁ - x₂) и (x₃ - x₄). Если вычислить x-координаты точек пересечения сканирующей строки с ребрами многоугольника и упорядочить их по возрастанию, то нечетные интервалы будут лежать во внутренней области многоугольника. Тогда процедура сканирования и поиска точек закрашивания может иметь следующий вид:

1. Находятся x-координаты всех точек пересечения сканирующей строки с ребрами многоугольника.

2. X-координаты упорядочиваются по возрастанию.

3. Закрашиваются точки в нечетных интервалах.

Однако алгоритм требует уточнения для двух частных случаев.

Первый случай. Пересечение сканирующей строки с горизонтальным ребром (рис. 1.12).

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

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

В первом варианте (рис. 1.13) сканирующая строка пересекает два ребра, пересечения с которыми дают две совпадающие точки - саму вершину многоугольника. Требуется заполнить интервал длиной в одну точку. Этот случай является просто экстремальным. Здесь интервал заполнения вырожден в одну точку.

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

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

где x_к,y_н,x_к,y_н - координаты концевых точек ребра.

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

Активные ребра содержатся в таблице активных ребер (ТАР)

Окончательно алгоритм растровой развертки многоугольников будет следующим.

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

2. Поиск и удаление горизонтальных ребер.

3. Построение упорядоченной ТР.

4. Принимают первоначальное значение номера сканирующей строки i равной y_min первой записи ТР.

5. Создается пустая ТАР.

6. Выполняется обработка сканирующей строки.

7. Пока ТАР или ТР не пусты, выполняется переход к п. 6.

8. Окончание процедуры.

 

Растровая развертка круга

Растровую развертку круга можно построить с помощью алгоритма Брезенхема для первого октанта. При этом использование симметричности точек окружности позволяет организовать заполнение четырех интервалов со следующими координатами:

- первый интервал - (-y,x) - (y,x);

- второй интервал - (-x,y) - (x,y);

- третий интервал - (-x,-y) - (x,-y);

- четвертый интервал - (-y,-x) - (y,-x).

Следует выделить граничные ситуации, когда

(x,y) = (R,0) и (x,y) =(, ).

В первом случае вместо четырех интервалов получают один интервал, совпадающий с горизонтальным диаметром - (0,R) -(0,-R), и две точки - (R,0) и

(-R,0). Во втором случае получается только два интервала:

первый - (- , ) - (, );

второй - (- ,- ) - (,- ).

Кроме того, при реализации алгоритма необходимо учитывать выбор узла растра при движении “а" и движении “b", так как в первом случае меняется только координата y, а координата x остается неизменной. Во втором случае меняются обе координаты. Это приводит к тому, что интервалы, расположенные во 2, 3, 6 и 7 октантах - ((-y,x) - (y,x)) и ((-y,-x) - (-y,x)), при движении “а" совпадают с предыдущими интервалами по координате x, а по координате y больше на два пикселя - по одной точке с каждого конца интервала. Это приводит к тому, что приходится повторно заполнять интервал, а при выводе линии в инверсных режимах (стили XOR или NOT) ранее заполненный интервал будет стерт