Генерация сплошных областей. Методы. Растровая развертка многоугольников.


Генерация сплошных областей из простых описаний ребер или вершин называется — растровой разверткой сплошных областей (заполнением контура).
Методы решения этой задачи можно разделить на 2 группы:
а) растровую развертку; б) затравочное заполнение.
В методах растровой развертки пытаются определить (в порядке сканирования строк), лежит ли точка внутри контура. Направление сканирования — сверху вниз. Применимы и в векторных дисплеях (для задания штриховки).
В методах затравочного заполнения предполагают, что известна некоторая точка внутри контура (затравка). Если соседняя находится не внутри  обнаружена граница контура. В противном случае — она становится новой затравочной точкой, и поиск продолжается рекурсивно.
Заполнение многоугольников.
Многие замкнутые контуры — многоугольники. Если контур в виде кривой линии, то его аппроксимируют подходящим многоугольником (многоугольниками).
Простейший метод заполнения многоугольника состоит в проверке на принадлежность его внутренней области каждого пикселя растра. Однако, поскольку большинство пикселов находится вне растра — то на процедуру уходит много времени. Ускорить процесс можно путем вычисления для многоугольника оболочки — min прямоугольной зоны, содержащей в себе многоугольник. Число проверяемых пикселов резко уменьшается.
Растровая развертка многоугольников.
Если воспользоваться тем, что соседние пикселы, вероятно, имеют одинаковые характеристики, кроме пикселов граничных ребер, то можно разработать более эффективный метод, чем тест внутренней области (см. выше).
Свойство, при котором соседние пикселы имеют одинаковые характеристики называют пространственной когерентностью. Для растровых графических устройств соседние пикселы на сканирующей строке так же могут иметь вероятно одинаковые пикселы. Это свойство называют когерентностью растровых строк.
Характеристики пикселов на данной строке изменяются лишь там, где ребро многоугольника пересекает строку. Эти пересечения делят сканирующую строку на отдельные области (см. Рис. 3). Здесь многоугольник определяется либо списком вершин, либо списком ребер (совокупностью смежных вершин). Точки пересечения сканирующих строк с ребрами следует отсортировать по X (в порядке возрастания) в строке и по Y (в порядке нумерации сканирующих строк). Для каждого интервала, задаваемого парой пересечений, используется интенсивность или цвет заполняемого многоугольника.
Проблема возникает, когда сканирующие строки проходят через вершины многоугольника (трудно выделить пары, определяющие интенсивность участка). Поэтому, учитывая соглашение о середине интервала между сканирующими строками (заключается в том, что поскольку адресация пиксела связано с левой нижней точкой, решено координировать сканирующие строки, проходящими через середину пиксела, добавлением к координате Y значания 1/2, т.е. Yстроки = Yпиксела + 1/2) получим, что можно использовать четность и нечетность количества пересечений. Т.е. при пересечении вершины и ребер (y = 3.5 на Рис.3) количество пар пересечений нечетно. Для определения границы зоны заполнения в точке вершины применяют метод локального минимума (максимума). Смысл заключается в сравнении координат Y смежных вершин отрезков. Если их значения Y больше, чем у рассматриваемой  имеем min (P4), если меньше ? max (P3). Промежуточные варианты определят точки излома (типа P2).