Проверка точки на принадлежность многоугольнику за O(n): различия между версиями

Текущая версия на 18:50, 15 октября 2020

Пусть у нас есть многоугольник $A_1 A_2 \ldots A_n$ (не обязательно выпуклый) и некоторая точка $P$. Мы хотим проверить, лежит ли точка $P$ внутри, на границе или снаружи многоугольника. Для того, чтобы проверить, что точка $P$ лежит на границе многоугольника переберем его стороны и для каждого отрезка проверим, лежит ли точка $P$ на нем. Для того, чтобы проверить, лежит ли точка внутри или снаружи многоугольника существует $2$ метода.

Посмотрим на следующую сумму углов со знаком: $\sum\limits_{i=1}^n{\angle(\overrightarrow{P A_i}, \overrightarrow{P A_{i+1}})}$. Утверждается, что если точка попала вовнутрь многоугольника, то эта сумма будет равна $\pm 360^{\circ}$ (при этом знак $-$, если обход многоугольника по часовой стрелки, иначе знак $+$). Иначе эта сумма будет равна чему-то другому. Этот метод имеет плюс в том, что тут сложно запутаться. Минус состоит в том, что вычисление углов может быть неточным, из-за чего в крайних случаях метод может работать неправильно;
Выпустим произвольный луч из точки $P$. Пока предположим, что ни одна вершина на него не попала. Посчитаем количество сторон, пересекающих этот луч. Заметим, что если это количество нечетное, то точка лежит внутри многоугольника, иначе снаружи. Для того, чтобы найти луч, на который не попала ни одна из точек, рассмотрим луч выходящий в направлении вектора $(p, 1)$, где $p$ это любое простое число, большее чем $C$ --- максимальная разность координат. На практике обычно можно взять $p = 10^9 + 7$.

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

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

@@ Строка 1: / Строка 1: @@
-Заметим, что если у нас есть некоторая прямая, задаваемая уравнением $ax + by + c = 0$, то множества точек, удовлетворяющие неравенствам $ax + by + c \leq 0$ и $ax + by + c \geq 0$ это полуплоскости, на которые эта прямая разделяет плоскость. Будем задавать поплоскости уравнениями $ax + by + c \leq 0$, потому что для полуплоскостей второго вида можно просто рассмотреть прямую с коэфициентами $-a, -b, -c$. Пусть у нас задано много полуплоскостей. Мы хотим найти их пересечение, то есть как-то описать множество точек, удовлетворяющее всем неравенствам.
+Пусть у нас есть многоугольник $A_1 A_2 \ldots A_n$ (не обязательно выпуклый) и некоторая точка $P$. Мы хотим проверить, лежит ли точка $P$ внутри, на границе или снаружи многоугольника. Для того, чтобы проверить, что точка $P$ лежит на границе многоугольника переберем его стороны и для каждого отрезка проверим, лежит ли точка $P$ на нем. Для того, чтобы проверить, лежит ли точка внутри или снаружи многоугольника существует $2$ метода.
-Для простоты предположим сначала, что нету вертикальных прямых. Рассмотрим множество прямых, полуплоскости которых "смотрит" вних и полуплоскости которых "смотрят" вверх.
+<ol>
+    <li> Посмотрим на следующую сумму углов со знаком: $\sum\limits_{i=1}^n{\angle(\overrightarrow{P A_i}, \overrightarrow{P A_{i+1}})}$. Утверждается, что если точка попала вовнутрь многоугольника, то эта сумма будет равна $\pm 360^{\circ}$ (при этом знак $-$, если обход многоугольника по часовой стрелки, иначе знак $+$). Иначе эта сумма будет равна чему-то другому. Этот метод имеет плюс в том, что тут сложно запутаться. Минус состоит в том, что вычисление углов может быть неточным, из-за чего в крайних случаях метод может работать неправильно;
-Пусть у нас есть множество полуплоскостей, которые "смотрят" в одну сторону. Пусть для простоты они смотрят вверх. Тогда рассмотрим все прямые, которые разделяют плоскость. Мы хотим найти такую верхнюю огибающую всех прямых, то есть выбрать в каждой $x$ координате максимальную точку с такой $x$ координатой, лежащую на одной из прямых. Этот метод также используется в очень известном методе [[Convex hull trick]]. Попробуем повторить что-то типо Алгоритма Грэхэма. Отсортируем все прямые по углу с осью $oX$. Будем перебирать прямые в таком порядке и в стеке поддерживать верхнюю огибающую для тех прямых, которые мы перебрали. Для каждой прямой будем поддерживать минимальную $x$ координату, начиная с которой эта прямая максимальная. При добавлении новой прямой мы должны будем выкинуть из стека несколько последних прямых и добавить новую. Пока стек непустой будем вынимать из него последнюю прямую. Рассмотрим точку пересечения этой прямой с нашей. Если $x$ координата этого пересечения будет не больше чем минимальная $x$ координата, начиная с которой последняя прямая из стека была максимальной, то последняя прямая в стеке больше никогда не будет максимальной и мы должны вынуть ее из стека. После этого надо добавить эту прямую в конец стека и минимальная $x$ координата начиная с которой эта прямая будет максимальной будет равна $x$ координате последней точки пересечения (во время того как мы вынимали последнюю прямую из стека).
+    <li> Выпустим произвольный луч из точки $P$. Пока предположим, что ни одна вершина на него не попала. Посчитаем количество сторон, пересекающих этот луч. Заметим, что если это количество нечетное, то точка лежит внутри многоугольника, иначе снаружи. Для того, чтобы найти луч, на который не попала ни одна из точек, рассмотрим луч выходящий в направлении вектора $(p, 1)$, где $p$ это любое простое число, большее чем $C$ --- максимальная разность координат. На практике обычно можно взять $p = 10^9 + 7$.
+</ol>
-Далее надо пересечь две цепочки: полуплоскостей смотрящих вниз и смотрящих вверх. Для этого переберем все пары звеньев верхней и нижней цепочки и попробуем их пересечь. Таким образом найдется $\leq 2$ точек пересечения, которые надо будет добавить в фигуру пересечения и удалить все звенья левее и правее добавленных точек.
-Для того, чтобы разобраться с вертикальной прямой, можно попробовать пересечь ее с полученной конструкцией (что очень неприятно), а можно просто выбрать любую пару перпендикулярных векторов и сказать, что новые направления осей это эти вектора и в зависимости от этого выбрать какие полуплоскости смотрят вверх, а какие вниз.
-Общее время работы составляет $O(n^2)$.
 {{Автор|Константин Амеличев|kik0s}}
 [[Категория:Конспект]]