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

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

Ясно, что для любого многоугольника всегда можно построить луч, не проходящий ни через одну из вершин. Однако построение такого луча связано с некоторыми трудностями и, кроме того, проверку пересечения границы многоугольника с произвольным лучом провести сложнее, чем с фиксированным, например горизонтальным.

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

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

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

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