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

Геометрическая модель пространственной проверки

Операция определения принадлежности точки области, заданной полигоном, относится к базовым задачам вычислительной геометрии и геоинформационных систем. В контексте Web-GIS и клиентских приложений JavaScript эта задача часто решается с использованием библиотеки Turf.js, предоставляющей набор геопространственных функций, работающих с GeoJSON-структурами.

Полигон в Turf.js представляет собой объект формата GeoJSON с типом Polygon или MultiPolygon, а точка — объект типа Point. Проверка выполняется на основе алгоритма лучевого сканирования (ray casting) или его оптимизированных вариаций, скрытых внутри реализации библиотеки.

Базовая структура геометрий

Корректная проверка требует соблюдения строгого формата входных данных.

Точка:

{
  type: "Feature",
  geometry: {
    type: "Point",
    coordinates: [lng, lat]
  }
}

Полигон:

{
  type: "Feature",
  geometry: {
    type: "Polygon",
    coordinates: [
      [
        [lng, lat],
        [lng, lat],
        [lng, lat],
        [lng, lat],
        [lng, lat]
      ]
    ]
  }
}

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

Основная функция Turf.js

Для проверки попадания точки в полигон используется функция:

turf.booleanPointInPolygon(point, polygon)

Минимальный пример использования:

import * as turf from "@turf/turf";

const point = turf.point([76.8897, 43.2389]);

const polygon = turf.polygon([[
  [76.8800, 43.2400],
  [76.9000, 43.2400],
  [76.9000, 43.2300],
  [76.8800, 43.2300],
  [76.8800, 43.2400]
]]);

const result = turf.booleanPointInPolygon(point, polygon);

Результат true означает принадлежность точки области полигона, false — отсутствие принадлежности.

Алгоритмическая основа проверки

Внутренний механизм проверки основан на классическом алгоритме ray casting:

  • проводится условный луч от точки в сторону бесконечности
  • подсчитывается количество пересечений с ребрами полигона
  • нечётное число пересечений означает принадлежность точки
  • чётное число пересечений означает внешнюю область

Формально логика может быть представлена как булева функция:

P = (N_{intersections} = 1)

где P — принадлежность точки, N_intersections — количество пересечений луча с границами полигона.

Работа с MultiPolygon

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

const multiPolygon = turf.multiPolygon([
  [[
    [76.88, 43.24],
    [76.90, 43.24],
    [76.90, 43.23],
    [76.88, 43.23],
    [76.88, 43.24]
  ]],
  [[
    [76.91, 43.24],
    [76.93, 43.24],
    [76.93, 43.23],
    [76.91, 43.23],
    [76.91, 43.24]
  ]]
]);

const result = turf.booleanPointInPolygon(point, multiPolygon);

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

Обработка границ полигона

Особое значение имеет поведение при попадании точки строго на границу полигона. В Turf.js предусмотрен параметр:

turf.booleanPointInPolygon(point, polygon, { ignoreBoundary: false })

Поведение:

  • ignoreBoundary: false — точка на границе считается принадлежащей полигону
  • ignoreBoundary: true — точка на границе считается вне полигона

Это различие критично в задачах пространственной аналитики, где граница может трактоваться как отдельная зона или исключаться из расчётов.

Координатные особенности и система отсчёта

Turf.js использует стандарт GeoJSON, где координаты задаются в порядке:

[longitude, latitude]

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

Особое внимание требуется при работе с:

  • Web Mercator проекцией (EPSG:3857)
  • геодезическими координатами WGS84 (EPSG:4326)

Turf.js предполагает входные данные именно в WGS84.

Производительность вычислений

Алгоритм проверки принадлежности точки имеет линейную сложность относительно количества рёбер полигона:

T(n) = O(n)

где n — число вершин внешнего и внутренних контуров.

При больших полигонах или массовых проверках точек возникает необходимость оптимизации:

  • пространственная индексация (R-tree)
  • предварительная фильтрация bounding box
  • кэширование геометрий
  • разбиение полигона на упрощённые компоненты

Turf.js предоставляет вспомогательную функцию предварительной проверки через bounding box:

turf.bboxPolygon
turf.booleanWithin

Проверка через bounding box как этап оптимизации

Перед полной проверкой используется упрощённая проверка попадания в ограничивающий прямоугольник:

const bbox = turf.bbox(polygon);
const isInsideBBox = turf.booleanPointInPolygon(point, turf.bboxPolygon(bbox));

Если точка не попадает в bbox, дальнейшие вычисления исключаются.

Вложенные полигоны и вырезы

Полигон может содержать внутренние области исключения (holes). Структура координат:

[
  [outer ring],
  [hole 1],
  [hole 2]
]

Логика проверки:

  • точка должна находиться внутри внешнего контура
  • точка не должна находиться внутри ни одного отверстия

Формально:

P = P_{outer} (P_{hole1} P_{hole2} … P_{holen})

Применение в прикладных задачах

Операция принадлежности точки полигону используется в следующих сценариях:

  • геозоны доставки и логистики
  • анализ территорий обслуживания
  • геофенсинг событий в реальном времени
  • проверка попадания GPS-треков в разрешённые зоны
  • анализ пользовательской активности по регионам
  • картографические интерфейсы и редакторы данных

Обработка потоковых данных

В системах реального времени проверка часто выполняется на потоке координат GPS. В этом случае важна минимизация вычислений:

  • предварительная фильтрация по bbox
  • пакетная обработка координат
  • использование Web Worker для изоляции вычислений
  • снижение точности координат при допустимых погрешностях

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

Ошибки и нестабильные случаи

Типичные проблемы при использовании функции:

  • самопересекающиеся полигоны
  • некорректный порядок вершин (не замкнутый контур)
  • дублирование координат
  • смешение типов геометрий
  • нарушение формата GeoJSON

Turf.js частично нормализует входные данные, но корректность геометрии остаётся ответственностью слоя подготовки данных.

Связь с другими геопространственными операциями

Проверка принадлежности точки полигону тесно связана с другими функциями Turf.js:

  • turf.booleanWithin — проверка вложенности геометрий
  • turf.intersect — вычисление пересечений полигонов
  • turf.union — объединение областей
  • turf.buffer — расширение геометрий на заданное расстояние

Эти операции часто комбинируются для построения сложных пространственных правил и аналитических моделей.

Оглавление