Разложение в растр сплошных многоугольников

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

Когерентность сканирующих строк

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

Но такой подход очень трудоемок, приходится проделывать много лишних операций.

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

Рис. 3.25

На этом и основан принцип пространственной когерентности:

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

Используя этот принцип, можно предположить следующий алгоритм:

· Определить точки пересечения текущей сканирующей строки со сторонами многоугольника.

· Сортировать т. пересечения по увеличению x – координаты.

· Попарно закрасить.

Рассмотрим строку 2: строка 6:

1) т. пересечения: 3, 6 1) 8, 6, 3, 1

2) сортировка: 3, 6 2) 1, 3, 6, 8

3) закраска: 3-6 3) 1, -3, 6, -8

строка 3: строка 5:

1) 2, 8, 8 1) 8, 4, 4, 1

2) 2, 8, 8 не верно! 2) 1, 4, 4, 8 верно!

3) 2, -8, 8 – правая граница буфера 3) 1, -4, 4, -8

Чтобы алгоритм работал верно, во всех случаях поступают следующим образом:

Все вершины разбивают на 2 типа:

1) промежуточные (1, 3)

2) локальные и глобальные экстремумы (2, 5, 6, 4).

Если вершина является промежуточной, то одно из ребер, ее составляющих, уменьшается на 1 по y.

Тогда для строки 3: (ребро е₃ укоротили на 1, появилась вершина 3¹)

1) 2, 8

2) 2, 8

3) 2, -8

Когерентность ребер

Принцип когерентности ребер: если ребро пересекается строкой i, то велика вероятность, что оно будет пересекаться и (i+1) – ой строкой.

,

,

Алгоритм: Создается таблица ребер (ТР), в которой все ребра сортируются по увеличению y – координаты. В ней содержатся все ребра и каждое ребро представлено в виде:

На основе ТР создается ТАР (таблица активных ребер), которая содержит только текущие ребра для каждой сканирующей строки. Они сортируются по увеличению x – координаты.

Каждое ребро представлено в виде:

Рис. 3.26

Алгоритм создания ТАР:

1) Установить y=min – ому значению координаты y среди элементов ТР.

2) Инициализировать ТАР, сделать ее пустой.

3) Повторять шаг 3 до тех пор, пока ТАР и ТР не станут пустыми.

· Слить информацию из группы у таблицы ребер (ТР) с информацией в ТАР, сохраняя упорядочивание по x – координате.

· Занести желаемые значения в на сканирующей строке, определяемой текущим значением y, используя пары x – координат из ТАР.

· Удалить из ТАР те элементы, которые .

· Для всех элементов, содержащихся в ТАР, заменить x на .

· Т.к. на предыдущем шаге могла нарушиться упорядоченность ТАР по x, провести пересортировку ТАР.

· Увеличить y на 1 и т.о. перейти к следующей сканирующей строке.