Попадание точки в полигон

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

Применение

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

Алгоритм проверки вхождения точки в полигон

Для начала определимся с теорией. Наш полигон [многоугольник] — это набор связанных векторов. Для проверки вхождения точки в полигон нам нужно определить положение нашей точки, относительно каждого из этих векторов по очереди.

Решение задачи

Далее одно из возможных решений задачи на PHP. Замечу, что оно не учитывает попадание в вектор, лишь попадание внутрь фигуры: