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

Пусть у нас есть многоугольник $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