Алгоритм определения того, к какому многоугольнику принадлежит точка по заданной координате многоугольника

Question

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

Примерный рисунок проблемы выглядит примерно так:

Есть ли алгоритм, который позволил бы мне определить, к какой стране принадлежит данная точка? Можно предположить, что границы страны представлены в виде троек (долгота, широта,ISO2).

Answer 1

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

Answer 2

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

Если у вас нечетное количество пересечений, то ваша точка находится внутри многоугольника. Если у вас четное количество пересечений, то точка находится снаружи.

Это работает для любого несамопересекающегося многоугольника.