Рассмотренный способ позволяет создать алгоритм, основанный на определении границ зон заполнения, которыми являются точки перечения ребер со сканирующими строками (Алгоритм с упорядоченным списком ребер). Схема следующая:
I. Подготовить данные:
1. Определить для каждого ребра многоугольника точки пересечений со сканирующими строками, проведенными через середины интервалов (по методу Брезенхема или ЦДА). Горизонтальные ребра игнорируются (y1 = y2).
2. Занести каждое пересечение (x, y + 1/2) в список.
3. Отсортировать список по строкам и по возрастанию х в строке, т.е. (x1, y1) предшествует (х2, у2) если у1 > y2 или y1 = y2 и х1 ? х2.
II. Приеобразовать данные в растовую форму.
3. Выделить из отсортированного списка пары элементов (х1, у1) и (х2, у2). Структура списка гарантирует, что у = у1 = у2 и х1 ? х2.
4. Активировать на сканирующей строке Y пикселы для целых значений X, таких, что x1 ? x + 1/2 ? х2.
Для повышения эффективности работы можно уменьшить список отсортированных значений, применив алгоритм с упорядоченным списком ребер. Для этого надо разделить сортировку на построчную в направлении Y и сортировку в строке по X используя метод групповой сортировки по Y (см. растровая развертка в реальном времени). В этом случае координаты X точек пересечения помещают в группу, соответствующую Y. Затем для каждой Y-группы отсортировать список координат X точек пересечений в порядке возрастания.
Основное достоинство метода — упрощение корректировки дисплейного списка (необходимо корректировать только соответствующую Y-группу). Недостаток — наложение ограничений на число пересечений либо резервирование большой памяти.
Устранить эти недостатки можно применив список активных ребер. Тогда алгоритм с активным списком ребер сокращает объем вычислений и позволяет определить точки пересечения со сканирующими строками в пошаговом режиме. Схема алгоритма будет следующей:
I. Подготовить данные:
1. Используя сканирующие строки, проведенные через середины отрезков (у + 1/2), определить для каждого ребра многоугольника наивысшую сканирующую строку, пересекаемую ребром.
2. Занести ребро многоугольника в Y-группу, соответствующую этой сканирующей строке.
3. Сохранить в связном списке значения: начальное значение координат X точек пересечения, Dу — число сканирующих строк, пересекаемых ребром многоугольника, и Dх — шаг приращения по X при переходе от одной сканирующей строки к другой
II. Преобразование данных в растровый вид:
4. Для каждой сканирующей строки проверить соответствующую Y-группу на наличие новых ребер. Новые ребра добавить в список активных ребер (САР).
5. Отсортировать координаты X точек пересечения из САР в порядке возрастания; т.е. х1 предшествует х2, если х1 ? х2.
6.Выделить пары точек пересечений из отсортированного(пох)списка.
7. Активировать на сканирующей строке Y пикселы для целых значений X, таких, что x1 ? x + 1/2 ? х2.
8. Для каждого ребра из САР уменьшить Dу на 1.
9. Если Dу < 0, то исключить данное ребро из САР.
10. Вычислить новое значение координат X точек пересечения хнов = хстар + D х.
11. Переход к следующей сканирующей строке.
Данный алгоритм достаточно громоздкий (каждый пиксел должен активироваться 1 раз) ® операции input-output сведены к min. Уменьшить большие накладные расходы (поддержка и сортировка больших списков) можно с помощью другого метода, заключающегося в ограничении списков. Это достигается принятием соглашения о середине интервала между сканирующими строками для тех пикселов, половина которых лежит внутри закрашиваемого многоугольника, а другая вне. Все пикселы будут активироваться только в том случае, если внутренняя часть многоугольника окажется слева от центра пиксела. Эффективно использовать этот метод вместе с буфером кадра. Пикселы обрабатывается предварительно в буфере, а затем выводятся на дисплей (после обработки всех ребер). Недостаток — возможность повторной обработки каждого пиксела несколько раз. Важной деталью становится скорость ввода-вывода. Это т.н. алгоритм с перегородкой. Схема его следующая:
I. Для каждой сканирующей строки, пересекающей ребро многоугольника:
1. Дополнить все пикселы , центры которых лежат справа от пересечения сканирующей строки с ребром и слева от перегородки, если пересечение находится слева от перегородки.
2. Дополнить все пикселы, центры которых расположены слева от или на пересечении сканирующей строки с ребром и справа от перегородки, если пересечение находится справа.
Для преодоления указанного ранее недостатка (неоднократное активирование части пикселов) применяют модифицированный алгоритм, известный, как алгоритм со списком ребер и флагом. Он выполняется в 2 этапа. Первый — обрисовка контура (что дает определение пар ограничивающих пикселов на сканирующей строке); второй — заполнение промежуточной зоны между ними. Схема его следующая:
Обрисовка контура:
Отметить самый левый пиксел, центр которого лежит справа от пересечения со сканирующей строкой, используя соглашение о середине интервала, для которого х + 1/2 ? хпересечения
Заполнение контура:
Для каждой сканирующей строки, пересекающей многоугольник
Внутри = FALSE
for x = 0 (левая граница) to х = xmax (правая граница)
if пиксел в точке х имеет граничное значение
then инвертировать значение переменной Внутри
if Внутри = TRUE then
присвоить пикселу в х значение цвета многоугольника
else
присвоить пикселу в х значение цвета фона
end if
next x
