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

Материал из Algocode wiki
Версия от 21:45, 27 апреля 2020; Romanchenko (обсуждение | вклад) (Локация точки относительно многоугольника)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Выпуклый многоугольник

Пусть в многоугольнике $n$ вершин. Рассмотрим алгоритм за $O(\log n)$.

Рассмотрим самую левую, а из таких самую нижнюю точку многоугольника - $O$. Если наша точка $P$ лежит левее или ниже нее, то сразу можем сказать, что она не принадлежит многоугольнику.

Проведем из $O$ диагонали ко всем вершинам многоугольника, получим, что он разбит на треугольники, одновременно соседние диагонали образуют последовательные углы. Давайте бинарным поиском найдем угол, в котором лежит точка $P$. Если бинарный поиск попал в один из крайних треугольников, то можно проверить руками, лежит ли точка внутри угла (для этого достаточно рассмотреть три векторных произведения), если это не так, то возвращаем FALSE.

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

Произвольный многоугольник

Предыдущий способ нельзя применить в данном случае, так как принадлежность треугольнику не будет означать принадлежность фигуре (в невыпуклом многоугольнике если $A$ и $B$ лежат в многоугольнике, то весь отрезок $AB$ может не лежать в нем целиком). Рассмотрим два способа за $O(n)$.

Подсчет углов

Мы считаем, что вершины даны в порядке обхода. Будем последовательно рассматривать углы с вершиной в точке $P$ (для которой определяем положение) и лучами, проходящими через соседние вершины многоугольника. Теперь, если просуммировать все эти углы по порядку (как ориентированные углы), то получится некоторая величина $\psi$.

В том случае, если точка лежит внутри многоугольника, $\psi = \pm 2\pi$. Иначе $\psi = 0$.

Луч

Если из произвольной точки пустить горизонтальный луч и если этот луч пересечет многоугольник, то он рано или поздно выйдет из этого многоугольника. Допустим, луч проходил строго через внутренние точки каких-то сторон, не задевая вершины. Если посчитать число пересечений с многоугольником, то для точки, находящейся внутри, это число будет нечетным ("наружу-внутрь-наружу", 3 пересечения), в противном случае - четным. Отдельно стоит обработать случай, когда точка находится на границе.

Но как учесть прохождение через вершины? Во-первых, если луч на каком-то отрезке пути совпал со стороной многоугольника (то есть она была ему параллельна и они совпали), то это пересечение можно игнорировать, такую сторону можно сжать в одну точку и объединить концы ее соседних сторон.

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

Горизонтальные лучи

Заметим, что каждый отрезок рассматривается независимо, поэтому при прохождении луча через вершину, он пройдет как бы через две вершины - для одной стороны и для другой.

Посмотрим на пример. Луч, выпущенный из $G$, пройдет через два нижних конца отрезков - $ID$ и $CD$. То есть число пересечений четное, точка вне многоугольника.

Луч, выпущенный из $F$ наберет только одно пересечение, так как он пересекает одну верхнюю и одну нижнюю вершину отрезков. Поэтому точка внутри многоугольника.

Луч, выпущенный из $J$, проходит через две верхних и две нижних вершины, засчитывается два пересечения, точка вне многоугольника.

Луч выпущенный из $H$, проходит через два верхних конца, поэтому засчитывается ноль пересечений, точка вне многоугольника.

Решение удобно реализовывать, работая со списком сторон, при этом нам не важен порядок их рассмотрения. Решение работает за $O(n)$, так как надо просмотреть каждый отрезок.



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

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