Определение пересечения геометрий

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

В модели GeoJSON, используемой в Turf.js, геометрии представлены как стандартизированные объекты: Point, LineString, Polygon, а также их коллекции (FeatureCollection). Пересечение определяется не только визуальным наложением, но и строгими топологическими правилами.

Формальное понимание пересечения

Две геометрии A и B считаются пересекающимися, если выполняется условие:

  • существует хотя бы одна точка p, такая что p ∈ A и p ∈ B.

Это определение охватывает несколько случаев:

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

Базовые типы пересечений

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

Точка считается пересекающейся с полигоном, если она находится внутри или на границе полигона. В Turf.js это проверяется через пространственные предикаты, основанные на алгоритме луча (ray casting) или winding number.

Линия и полигон

Линия пересекает полигон, если:

  • хотя бы один сегмент линии пересекает границу полигона
  • или часть линии лежит внутри полигона

Полигон и полигон

Пересечение полигонов — наиболее сложный случай. Оно может включать:

  • пересечение границ
  • частичное перекрытие областей
  • вложенные контуры
  • мультиполигональные комбинации

Основные функции Turf.js для проверки пересечения

booleanIntersects

Функция определяет, пересекаются ли две геометрии в любом смысле.

import booleanIntersects from '@turf/boolean-intersects';

const result = booleanIntersects(featureA, featureB);

Поведение:

  • возвращает true, если существует хотя бы одна общая точка
  • не различает тип пересечения (касание, перекрытие, вложенность)

Особенность: является наиболее общей и быстрой проверкой пространственного взаимодействия.

intersect

Функция вычисляет фактическую геометрию пересечения.

import intersect from '@turf/intersect';

const result = intersect(polygonA, polygonB);

Возвращаемое значение:

  • Feature<Polygon> или Feature<MultiPolygon>
  • либо null, если пересечения нет

Особенность: в отличие от booleanIntersects, возвращает не булево значение, а новую геометрию, образованную общей областью.

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

Проверка bounding box

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

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

Это резко снижает вычислительную сложность:

  • предварительная проверка: O(1)
  • точная проверка: зависит от сложности геометрий

Сегментное пересечение

Для линий и полигонов используется анализ пересечений отрезков.

Каждый линейный сегмент сравнивается с сегментами другой геометрии.

Ключевая операция — проверка пересечения двух отрезков:

  • ориентация точек (clockwise / counterclockwise)
  • проверка коллинеарности
  • анализ диапазонов координат

Алгоритм “ray casting” для точек

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

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

Особенности пересечений в сферической модели

Turf.js работает в географических координатах (WGS84), где:

  • координаты представлены в градусах
  • поверхность Земли аппроксимируется сферой

Это вносит дополнительные сложности:

  • прямые линии интерпретируются как геодезические (great-circle)
  • пересечения могут искажаться на больших расстояниях
  • требуется учитывать анти-меридиан (±180° долготы)

Краевые случаи пересечений

Касание границ

Геометрии считаются пересекающимися, даже если:

  • они имеют одну общую точку на границе
  • внутренние области не пересекаются

Пример: два полигона, соприкасающиеся по ребру.

Полное вложение

Если один полигон полностью находится внутри другого:

  • пересечение существует
  • результатом intersect будет внутренний полигон

Мультигеометрии

Для MultiPolygon и MultiLineString проверка выполняется поэлементно:

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

Связанные пространственные предикаты

booleanContains

Проверяет, содержит ли одна геометрия другую полностью.

booleanWithin

Обратная операция к contains.

booleanCrosses

Определяет пересечение с пересечением границ, характерное для линий.

booleanDisjoint

Противоположность пересечения: отсутствие общих точек.

Оптимизация вычислений пересечений

При работе с большим количеством объектов применяются:

  • пространственные индексы (R-tree)
  • предварительная фильтрация по bbox
  • кластеризация геометрий
  • упрощение линий (simplify)

Практическая модель вычисления пересечения в Turf.js

Общий процесс выглядит как последовательность:

  1. Проверка bounding box
  2. Определение типа геометрий
  3. Разбиение на сегменты (при необходимости)
  4. Поиск пересечений сегментов
  5. Построение результирующей геометрии (intersect)
  6. Агрегация результатов для коллекций

Ограничения точности

Из-за особенностей чисел с плавающей точкой:

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

Поэтому в критических задачах часто применяется:

  • буферизация (buffer)
  • округление координат
  • предобработка геометрий

Значение операции пересечения в пространственном анализе

Пересечение геометрий является фундаментом для:

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