Тесты ориентации точки относительно полигона
1. Выпуклый тест. Определяет положение точки относительно полигона (рис. 10): внешняя точка, внутренняя точка, граничная точка (внешнее подпространство полигона считается положительным, внутреннее – отрицательным, граница соответствует нулю).
 |
2. Габаритный тест. Определяет гарантированную непринадлежность точки q произвольному полигону P путем сравнения ее координат с габаритами полигона – минимальными и максимальными координатами его вершин. Полностью задачу ориентации габаритный тест не решает, тем не менее, благодаря своей простоте, применяется во многих алгоритмах для быстрого обнаружения заведомо непересекающихся геометрических объектов (рис. 11).
3. Угловой тест. Основан на вычислении и анализе алгебраической суммы углов di=Ð(Vi, Vi+1) между смежными векторами Vi=pi-q, соединяющими точку q с вершинами pi, при обходе произвольного полигона P по замкнутому контуру в произвольном направлении.
Точка является внутренней, если сумма углов ∑di=2 π(рис. 12). Точка является внешней, если сумма углов ∑di=0 (рис. 13).
Точка является граничной (принадлежит границе полигона):
● если при расчете векторов получен нулевой вектор çViç=0, то тестируемая точка совпадает с вершиной pi;
● если при расчете углов di получен развернутый угол с модулем | di | = π, то тестируемая точка лежит на ребре pi pi+1.
Существуют две разновидности углового теста – радианный и октантный.
Лучевой тест ориентации точки q относительно полигона p заключается в выпускании из этой точки в произвольном направлении V луча p(t)=q+Vt (" t > 0) и подсчете числа его пересечений с ребрами p. Анализ пар дает следующие критерии ориентации точки относительно полигона: точка является внутренней, если число пар нечетно (ti>0,0<ti<1); точка является внешней, если число пар четно, в том числе равно нулю; точка лежит на границе p, если найдется хотя бы одна пара, для которой ti=0, 0£ti£1.
Особенности лучевого теста (рис. 14):
 |
● неопределенность числа пересечений при прохождении луча точно через вершину pi при ti=1 или вершину pi+1 при ti=0. Необходимо повторить тест заново с другим направлением луча V;
● требуется расчет параметров пересечения луча со всеми ребрами полигона.
Исследуются параметры пересечения луча с отрезками pi+(pi+1–pi)t, "0£t£1.
Лекция 11
Дата добавления: 2015-11-20; просмотров: 3221;