Заполнение многоугольников

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

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

В случае с многоугольником когерентность пикселей определяется вдоль сканирующей строки. Сканирующие строки обычно изменяются от «верха» многоугольника до его «низа». Характеристики пикселов изменяются только, где ребро многоугольника пересе­кает строку. Эти пересечения делят сканирующую строку на области за­крашенных и не закрашенных пикселов.

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

Рис. 2.9 Прохождение сканирующих строк по многоуголь­нику

1. Простой случай. Например, на рис. 2.9 сканирующая строка y = 4 пересекает многоугольник при x = 1 и x = 6. Получается три области x < 1, 1 ≤ x ≤ 6, x > 8. Сканирующая строка y = 6 пересекает многоугольник при x = 1, x = 2, x = 5, x = 6. Полу­чается пять областей x < 1, 1 ≤ x ≤ 2, 2 < x < 5, 5 ≤ x ≤ 6, x > 6. В этом случае x сорти­руется в порядке возрастания. Далее список иксов рассматривается попарно. Ме­жду парами точек пересечения закраши­ваются все пикселы. Для y = 4 закрашиваются пикселы в интервале (1, 6), для y = 6 закрашиваются пик­селы в интервалах (1, 2) и (5, 6).

2. Сканирующая строка проходит через вершину (Рис. 2.10).

Рис. 2.10 Прохождение сканирующий строки через вер­шину

Например, по сканирующей строке y = 3 упорядоченный список x полу­чится как (2, 2, 4). Вершина многоугольника была учтена дважды, и поэтому закрашиваемый интервал получается неверным: (2, 2). Следова­тельно, при пересечении вершины сканирующей строкой она должна учитываться еди­ножды. И список по х в приведенном примере будет (2, 4).0

3. Сканирующая строка проходит через локальный минимум или максимум (Рис 2.9 при y = 5). В этом случае учитываются все пересечения вершин сканирующей стро­кой. На рис. 2.9 при y = 5 формируется список x (1, 4, 4, 6). Закрашиваемые интервалы: (1, 4) и (4, 6). Условие нахождения локального минимума или максимума определяется при рассмотрении кон­цевых вершин для ребер, соединенных в вершине. Если у обоих концов коор­динаты y больше, чем y вершины пересечения, то вершина локальный мини­мум. Если меньше, то вершина пере­сечения локальный максимум.

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