4 < x < б вне многоугольника

б £ x £ 8 внутри многоугольника

x > 8 вне многоугольника

Совсем необязательно, чтобы точки пересечения для строки 4 сразу определялись в фиксированном порядке (слева направо). Например, если многоугольник задаётся списком вершин P1, P2, P3, P4, а список рёбер - последовательными парами вершин P1P2, P2P3, P3P4, P4P5, P5P1, то для строки 4 будут найдены следующие точки пересечения с рёбрами многоугольника: 8, 6, 4, 1. Эти точки надо отсортировать в возрастающем порядке по x, т. е. получить 1,4, 6, 8.

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

Точное определение тех пикселов, которые должны активироваться, требует некоторой осторожности. Рассмотрим простой прямоугольник, изображенный на рис. 2.8. Прямоугольник имеет координаты (1,1), (5,1), (5,4), (1,4). Сканирующие строки с 1 по 4 имеют пересечения с ребрами многоугольника при x = 1 и 5. Пиксел адресуется координатами своего левого ниж­него угла, значит, для каждой из этих сканирующих строк будут активированы

пикселы с x-координатами 1, 2, 3, 4 и 5. На рис. 2.8 показан результат. Заметим, что площадь, покрываемая активированными пикселами, равна 20, в то время как настоящая площадь прямоугольника равна 12.

Модификация системы координат сканирующей строки и теста активации устраняет эту проблему, как это показано на рис. 2.8,b. Считается, что сканирующие строки проходят через центр строк пикселов, т. е. через середину интервала, как это показано на рис. 2.8,b. Тест активации модифицируется следующим образом: проверяется, лежит ли внутри интервала центр пиксела, расположенного справа от пересечения. Однако пикселы все еще адресуют­ся координатами левого нижнего угла. Как показано на рис.2.8,b, результат данного метода корректен.

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

Дополнительная трудность возникает при пересечении сканирующей строки и многоугольника точно по вершине, как это показа­но на рис. 2.9. При использовании соглашения о середине интерва­ла между сканирующими строками получаем, что строка у = 3.5 пересечет многоугольник в 2, 2 и 8, т. е. получится нечетное количество пересечений. Следовательно, разбиение пикселов на пары даст неверный результат, т. е. пикселы (0,3), (1,3) и от (3,3) до (7,3) будут фоновыми, а пикселы (2,3), (8,3), (9,3) окрасятся в цвет многоугольника. Если учитывать только одну точку пересечения с вершиной. Тогда для строки у = 3.5 получим правильный результат. Однако результат применения метода к строке у = 1.5, имеющей два пересечения в (5,1), показывает, что метод неверен. Для этой строки именно разбиение на пары даст верный результат, т. е. окрашен будет только пиксел (5,1). Если же учитывать в вершине только одно пересечение, то пикселы от (0,1) до (4,1) будут фоновыми, а пикселы от (5,1) до (9,1) будут окрашены в цвет многоугольника.

Рис. 2.9. Особенности пересечения со строками сканирования.

Правильный результат можно получить, учитывая точку пересечения в вершине два реза, если она является точкой локального ми­нимума или максимума и учитывая один раз в противном слу­чае. Определить локальный максимум или минимум многоугольни­ка в рассматриваемой вершине можно с помощью проверки концевых точек двух ребер. Если у обоих рёбер у больше, чем у вершины, значит, вершина является точкой локального минимума. Если меньше, значит, вершина - точка локального максимума. Если одна больше, а другая меньше, следовательно, вершина не является ни точкой локального миниму­ма, ни точкой локального максимума. На рис.2.10 точка Р1 - локальный минимум, Р3 - локальный максимум, а Р2, Р4 - ни то ни другое. Следовательно, в точках Р1 и Р3 учитываются два пере­сечения со сканирующими

строками, а в Р2 и Р4 - одно.

2.7. Алгоритм с упорядоченным списком рёбер

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

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

Подготовить данные:

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

Занести ребро многоугольника в у- группу, соответствующую этой сканирующей строке.

Сохранить в связном списке значения: начальное значение координат x точек пересечения, Dy - число сканирующих строк, пересекаемых ребром многоугольника, и ~ Dx – шаг приращения по x при переходе от одной сканирующей строки к другой.

Преобразовать эти данные в растровую форму:

Для каждой сканирующей строки проверить соответствующую у- группу на наличие новых ребер. Новые ребра доба­вить в список активных рёбер.

Отсортировать координаты x точек пересечения из САР в порядке возрастания; т. е. х1 предшествует x2, если х1 < х2

Выделить пары точек пересечений из отсортированного по

x списка. Активировать на сканирующей строке y пикселы для целых значений x, таких, что x1 £ x + ½ £ x2. Для каждого ребра из САР уменьшить Dу на 1. Если Dу < 0, то исключить данное ребро из САР. Вычислить новое значение координат x точек пересечения xнов = xстар + Dx

Перейти к следующей сканирующей строке

В алгоритме предполагается, что все данные предварительно преобразованы в представление, принятое для многоугольников.

2.8. Алгоритм заполнения по рёбрам

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