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

Конспект готов к прочтению.

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

Выпуклый многоугольник задан как замкнутая полилиния, поэтому для любой вершины этого многоугольника все остальные точки будут отсортированы по углу. Возьмём первую точку многоугольника и мысленно проведём от неё все лучи, содержащие диагонали. Бинпоиском за логарифм можно пройтись по углам и понять, в каком из них лежит точка. Когда найден угол, за константное время можно проверить, с какой стороны от противолежащего первой точке ребра многоугольника лежит точка.

Итоговый алгоритм:

• если искомая точка [math]q[/math] лежит левее самой левой грани или правее самой правой, сразу возвращаем false
• бинпоиском ищем такое ребро [math]a_i a_{i+1}[/math], не инцидентное самой первой точке [math]a_0[/math] заданного многоугольника, что повороты точек [math]a_0, a_i, q[/math] и [math]a_0, a_{i+1}, q[/math] различаются
• проверяем поворот точек [math]a_i, a_{i+1}, q[/math], если он левый — точка лежит внутри, если правый — снаружи

Итоговое время работы: [math]O(\log n)[/math].

Невыпуклый многоугольник

Если точка лежит на ребре, сразу вернём true.

Очевидно, что, если пустить из точки луч, то по чётности числа пересечений с рёбрами многоугольника можно определить, внутри точка лежит или снаружи.

Пустим луч, например, по иксу и за [math]O(n)[/math] переберём все рёбра и проверим их на пересечение с лучом. Как проверять: сначала проверим, что ордината точки лежит между ординатами концов ребра, затем посмотрим, до ребра или после него начался луч.

Луч может попасть в точку, при этом прохождение через точку учтётся два раза (по разу для каждого отрезка, к которым принадлежит точка). Иногда это и есть то, чего нам хочется (когда фигура находится выше или ниже луча), но иногда нам хочется учесть только один раз. Для этого делаем такую штуку: для каждого отрезка учитываем только верхнюю точку. Дальше всё очевидно.

Реализация