Тест принадлежности точки многоугольнику

Обозначим ребра простого многоугольника на рис. .10. P₁P₂, P₂P₃, ..., P_nP₁. Пусть A(x, y) - точка, не лежащая на ломаной и нужно определить, принадлежит она многоугольнику или нет.

Проведем через точку горизонтальную полупрямую с правым концом в точке. Отметим на ней точку Q, которая заведомо не принадлежит многоугольнику.

В результате возникают следующие варианты:

1. Нет пересечений с многоугольником ==> точка А внешняя (точка 1).

2. Нечетное число пересечений ==> точка А внутренняя (точки 3 и 4).

3. Четное число пересечений ==> точка А внешняя (точка 5).

Точное определение тех пикселов, которые должны активироваться, требует некоторой осторожности. Рассмотрим простой прямоугольник, изображенный на рис. 2.11. Прямоугольник имеет координаты (1,1) (5,1), (5,4), (1,4). Сканирующие строки с 1 по 4 имеют пересечения с ребрами многоугольника при х = 1 и 5. Вспомним, что пиксел адресуется координатами своего левого нижнего угла, значит, для каждой из этих сканирующих строк будут активированы пикселы с x-координатами 1, 2, 3, 4 и 5. На рис. 2.11,а показан результат. Заметим, что площадь, покрываемая активированными пикселами, равна 20, в то время как настоящая площадь прямоугольника равна 12.

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

Алгоритм можно улучшить, если повысить эффективность сортировки. Последнее достигается разделением сортировки по строкам в направлении y и сортировки в строке в направлении x с помощью групповой сортировки по y. Таким образом, развертка начинается до завершения

Простейший алгоритм построчного сканирования.

1	2	3
BC	BC	BC
BA	BA	BA
BD	BD	B D
CD	CD	CD
AD	AB	A D

1	2	3
BA	BA	BA
BC	BC	BC
BD	BD	BD
CD	CD	CD
A D	AD	AD

2 формы сортировки

Порядок сортировки начинаемый с у влияет на размер списка активных ребер.

Либо обрабатывается больше информации чем нужно для данной строки.

Развертка с групповой сортировкой.

Проблема борьбы с избыточной информацией решается за счет введения дополнительных данных.

Вначале выполняется групповая сортировка по у всех отрезков изображения.

У – группа

1- пусто

2 -

3 – пусто

4 -

5 – пусто

6 -

7 – пусто

8 – пусто

При групповой сортировке по у образуются области памяти или группы.

При просмотре дисплейного списка заносится информация в группу, соответствующей наибольшей у координате.

х –координата точки пересечения со сканирующей строкой.

- изменение координаты х при переходе одной с другой

- число сканирующих строк пересекаемых данным отрезком.

Алгоритм

Список активных ребер для каждой сканирующей строки формируется добавлением информации из каждой у группы соответствующей сканирующей строке.

Координаты х точек пересечения

сортируется в порядке сканирования, а ребра из списка активных ребер преобразуются в растровую форму.

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

Для каждого отрезка координата х получается добавлением

список активных ребер

сканирование строки 3

сканирование строки 5

сканирование строки 7

тип гранично определенный

4-рех или 8-ми связные пикселы

4-х связный связан в 4-х направлениях

8-ми связный соответственно в 8-ми

(используются реже – сложный алгоритм многопроходный)

Простой рекурсивный алгоритм закрашивания по затравке

Тек(x,y)=

old_value