Точка в полигоне

Об инструменте

Инструмент «Точка в полигоне» проверяет, попадает ли набор географических точек внутрь или наружу нарисованного полигона. Используется в пространственных запросах — например, для определения, какие адреса находятся в зоне доставки, какие датчики расположены в пределах исследуемой территории или какие инциденты произошли в границах юрисдикции.

Входные данные

Сначала полигон, нарисованный кликами по карте (минимум 3 вершины; замыкается автоматически при повторном клике на первую вершину). Затем одна или несколько тестовых точек, вводимых как координаты (по одной паре шир., долг. в строке) в текстовом поле под картой.

Результат

Каждая тестовая точка классифицируется как Внутри или Снаружи полигона. Результаты отображаются в виде цветных маркеров на карте (зелёный = внутри, красный = снаружи) и в таблице со списком координат и классификации каждой точки. Таблицу можно скопировать в буфер обмена.

Ключевые понятия

Алгоритм трассировки лучей

Из тестовой точки проводится горизонтальный луч до бесконечности. Количество пересечений этого луча с границей полигона определяет результат: нечётное число означает, что точка внутри полигона; чётное (включая ноль) — что она снаружи. Это алгоритм сложности O(n), где n — количество рёбер полигона. Граничные случаи — точки, лежащие точно на границе — классифицируются как находящиеся внутри.

Число оборотов

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

Геометрический охват

Алгоритм работает с проецированными двумерными координатами. Результаты точны для полигонов протяжённостью до приблизительно 500 км. Очень крупные полигоны, охватывающие несколько зон UTM, могут показывать незначительные позиционные расхождения у краёв из-за эффектов сферической проекции.