Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
2.2. Задачи локализации точки
59
вообразив реализацию этого бесконечно малого поворота, мы увидим: если обе вершины ребра принадлежат /, то это ребро следует отбросить; если же ровно одна вершина ребра лежит на /, то пересечение будет учтено, когда эта вершина с большой
Рис. 2.5. Решение задачи о принадлежности точки простому многоугольнику при уникальном запросе. Есть только одно пересечение Р линией / слева от z, поэтому г внутри многоугольника.
ординатой, и игнорируется в противном случае. Резюмируя, по-"лучаем следующий алгоритм:
begin L := 0;
for / := 1 until N do if ребро (i) не горизонтально then if (ребро (i) пересекает / нижним концом слева от г)
then L:=L+ 1; if (L нечетно) then z внутри else z снаружи
end.
Очевидно, что этот простой алгоритм выполняется за время 0{N).
Для массовых запросов сначала рассмотрим случай, когда Р — выпуклый многоугольник. Предлагаемый метод использует выпуклость Р, а именно свойство, что вершины выпуклого многоугольника упорядочены по полярным углам относительно любой внутренней точки. Такую точку q можно легко найти; например, можно взять центр масс (центроид) треугольника, образованного любой тройкой вершин Р. Теперь рассмотрим N лучей, исходящих из точки q и проходящих через вершины многоугольника Р (рис. 2.6).
Эти лучи разбивают плоскость на N клиньев. Каждый клин разбит на две части одним из ребер Р. Одна из этих частей лежит целиком внутри Р, другая — целиком снаружи. Считая q началом полярных координат, мы можем отыскать тот клин, где
60
Гл. 2. Геометрический поиа
лежит точка z, проведя один раз двоичный поиск, поскольку лучи следуют в порядке возрастания их углов. После нахождения клина остается только сравнить z с тем единственным ребром из Р, которое разрезает этот клин, и решить, лежит ли z внутри Р.
Рис. 2.6. Разбиение на клинья для задачи о принадлежности выпуклому многоугольнику. 1. Двоичным поиском находим, что z лежит в клине p\qpi. 2. Определяя, по какую сторону ребра р\Рг лежит z, находим, что г сна-
Предобработка в вышеописанном способе решения состоит в поиске q как центра масс трех вершин из Р и размещении вершин plt р2, ..., Pn в структуре данных, пригодной для двоичного поиска (например, в векторе). Очевидно, это можно проделать за время О(N) для заданной последовательности pi, р2, Ры- Теперь сосредоточим внимание на процедуре поиска:
Процедура ПРИНАДЛЕЖНОСТЬ ВЫПУКЛОМУ МНОГОУГОЛЬНИКУ
1. Дана пробная точка z. Определяем методом двоичного поиска клин, в котором она лежит. Точка z лежит между лучами, определяемыми р,- и р,-+ь тогда и только тогда, когда угол (zqpi+l) положительный, а угол (zqpi) отрицательный1).
2. Если р, и p,+i найдены, то z — внутренняя точка тогда и только тогда, когда угол (p,p,+iz) отрицательный.
') Заметим, что определению знака угла (pi/вд) соответствует вычисление определителя матрицы третьего лорядка, образованной координатами этих точек. Конкретно, если положить р,- = (x;,yi), то этот определитель,
равный *2 </» 1 , дает удвоенную ориентированную площадь треугольника I х3 у, 1 |
{Р\Р2рз), где знак плюс будет тогда и только тогда, когда обход (рхРгРз) ориентирован против часовой стрелки. Итак, (Р1Р2Р3) соответствует левому повороту тогда и только тогда, когда этот определитель положителен.
2.2. Задачи локализации точки
61
Теорема 2.2. Время ответа на запрос о принадлежности точки выпуклому N-угольнику равно O(logjV) при затрате 0(N) памяти и 0(N) времени на предварительную обработку.
Какое же свойство выпуклого многоугольника позволяет провести быстрый поиск? Чтобы можно было применить двоичный поиск, вершины должны быть упорядочены по углу относительно некоторой точки. Очевидно, что выпуклость является только достаточным условием обладания этим свойством. На самом же деле существует более обширный класс простых, многоугольников, включающий в себя и выпуклые многоугольники, который обладает этим свойством: это класс звездных многоугольников (см. разд. 1.3.1). Действительно, звездный многоугольник Р (рис. 2.7) содержит по меньшей мере одну точку q такую, что отрезок qpi лежит целиком внутри многоугольника Р для любой вершины pi из P,i=\.....N.
Для определения принад- Рис. 2.7. Звездный многоугольник, лежности точки звездному
многоугольнику можно непосредственно использовать предыдущий алгоритм, если найден соответствующий центр q, служащий основой поиска. Множество подходящих центров внутри Р было определено в разд. 1.3.1 как ядро Р. Построение ядра простого Af-угольника лежит за рамками этой главы; мы вернемся к этой задаче в разд. 7.2.6, где доказан неожиданный результат, что ядро может быть найдено за время O(N). А сейчас предположим, что ядро Р извес1ни (и непусто); по-этому можно выбрать центр, относительно которого строятся клинья, необходимые для поиска. Получаем следующую теорему:
Теорема 2.3. Время ответа на запрос о принадлежности точки звездному N-угольнику равно 0(\ogN) при затрате O(N) памяти и 0(N) времени на предварительную обработку.
