Локализация точки в выпуклом многоугольнике

Материал из Algocode wiki
Перейти к: навигация, поиск

Пусть у нас есть выпуклый многоугольник $A_1 A_2 \ldots A_n$. Рассмотрим его триангуляцию на треугольники $$\Delta A_1 A_2 A_3, \Delta A_1 A_3 A_4, \ldots, \Delta A_1 A_{n-1} A_n$$. Тогда пусть у нас есть запросы: есть точка $P$. Найти какому треугольнику $\Delta A_1 A_i A_{i + 1}$ из этих она принадлежит или сказать, что точка лежит вне многоугольника.

Рассмотрим вектора $\overrightarrow{A_1 A_2}, \overrightarrow{A_1 A_3}, \ldots, \overrightarrow{A_1 A_n}$. Заметим, что они отсортированы по углу. Рассмотрим вектор $\overrightarrow{A_1 P}$ и найдем его $upper\_bound$ в этом массиве из $n-1$ векторов. Это можно сделать стандартным бинарным поиском. Тогда пусть мы нашли такое $2 \leq i < n$, что $\angle(\overrightarrow{A_1 A_i}, \overrightarrow{A_1 P}) \geq 0$ и $\angle(\overrightarrow{A_1 P}, \overrightarrow{A_1 A_{i+1}}) > 0$. Просто проверим, попала ли точка $P$ в треугольник $\Delta A_1 A_i A_{i + 1}$ или нет. Если попала, то точка $P$ лежит внутри многоугольника и мы локализовали ее положение, иначе точка $P$ дежит снаружи многоугольника. При этом такой запрос мы обрабатываем за время $O(\log{n})$.



Автор конспекта: Константин Амеличев

По всем вопросам пишите в telegram @kik0s