Проверка вхождения точки

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

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

В Leaflet геометрические сущности представлены объектами:

  • L.LatLng — точка на сфере (широта/долгота)
  • L.LatLngBounds — прямоугольная область
  • L.Polygon / L.Polyline — произвольные ломаные и многоугольники

Базовые стратегии проверки:

  • инклюзия в ограничивающий прямоугольник (bounding box)
  • принадлежность многоугольнику (point-in-polygon)
  • проверка в сложных мультигеометриях
  • касание границ как отдельный случай

Проверка вхождения в LatLngBounds

Самый быстрый и часто используемый способ — проверка попадания точки в прямоугольные границы.

Leaflet предоставляет встроенный метод:

const bounds = L.latLngBounds(
  L.latLng(50.0, 30.0),
  L.latLng(55.0, 40.0)
);

const point = L.latLng(52.5, 35.0);

const result = bounds.contains(point);

Внутренняя логика сводится к сравнению диапазонов:

  • latitude ∈ [south, north]
  • longitude ∈ [west, east]

Эквивалентная ручная реализация:

function isPointInBounds(point, bounds) {
  return (
    point.lat >= bounds.getSouth() &&
    point.lat <= bounds.getNorth() &&
    point.lng >= bounds.getWest() &&
    point.lng <= bounds.getEast()
  );
}

Особенности:

  • работает в O(1)
  • не учитывает кривизну геометрии
  • применяется как предварительная фильтрация перед более дорогими проверками

Предфильтрация через bounding box для полигонов

Любой многоугольник в Leaflet имеет ограничивающий прямоугольник:

const polygonBounds = polygon.getBounds();

if (!polygonBounds.contains(point)) {
  // точка гарантированно вне полигона
}

Такой подход снижает число вычислений при массовой обработке точек, особенно при кластеризации или фильтрации событий.

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

Для произвольных полигонов применяется алгоритм ray casting (алгоритм пересечения луча).

Идея:

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

Базовая реализация

function isPointInPolygon(point, latlngs) {
  let inside = false;

  for (let i = 0, j = latlngs.length - 1; i < latlngs.length; j = i++) {
    const xi = latlngs[i].lng, yi = latlngs[i].lat;
    const xj = latlngs[j].lng, yj = latlngs[j].lat;

    const intersect =
      ((yi > point.lat) !== (yj > point.lat)) &&
      (point.lng < (xj - xi) * (point.lat - yi) / (yj - yi) + xi);

    if (intersect) inside = !inside;
  }

  return inside;
}

Получение геометрии полигона в Leaflet

Структура координат полигона:

const latlngs = polygon.getLatLngs();

Для простого полигона:

const ring = polygon.getLatLngs()[0];

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

const multi = polygon.getLatLngs();
// multi = [ [ring1], [ring2], ... ]

Учёт отверстий (holes)

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

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

  • точка должна быть внутри внешнего контура
  • точка не должна попадать ни в одно отверстие
function isPointInPolygonWithHoles(point, polygonLatLngs) {
  const outer = polygonLatLngs[0];
  const holes = polygonLatLngs.slice(1);

  if (!isPointInPolygon(point, outer)) {
    return false;
  }

  for (const hole of holes) {
    if (isPointInPolygon(point, hole)) {
      return false;
    }
  }

  return true;
}

Геодезическая интерпретация координат

Leaflet оперирует географическими координатами в WGS84, однако алгоритмы point-in-polygon работают в декартовой проекции.

Следствия:

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

Использование Turf.js для точной проверки

Для геопространственной точности часто применяется библиотека геоанализа:

import booleanPointInPolygon from '@turf/boolean-point-in-polygon';

const point = turf.point([lng, lat]);
const poly = turf.polygon([coordinates]);

const result = booleanPointInPolygon(point, poly);

Преимущества:

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

Обработка событий Leaflet с проверкой вхождения

Типичный сценарий — фильтрация кликов по слоям:

map.on('click', (e) => {
  const point = e.latlng;

  polygons.forEach(poly => {
    const bounds = poly.getBounds();

    if (!bounds.contains(point)) return;

    const latlngs = poly.getLatLngs()[0];

    if (isPointInPolygon(point, latlngs)) {
      poly.fire('pointinside', { latlng: point });
    }
  });
});

Оптимизация массовых проверок

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

  1. Spatial hashing или grid indexing
  2. Проверка bounds
  3. Проверка полигонов
  4. Детальная геометрическая проверка

Пример структуры индекса:

const index = new Map(); // cellId -> polygons[]

Фильтрация:

const candidates = index.get(cellId) || [];

Особенности работы с кривыми и сегментами

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

function distanceToSegment(p, v, w) {
  const l2 = (w.lat - v.lat)**2 + (w.lng - v.lng)**2;
  if (l2 === 0) return Math.hypot(p.lat - v.lat, p.lng - v.lng);

  let t = ((p.lat - v.lat)*(w.lat - v.lat) + (p.lng - v.lng)*(w.lng - v.lng)) / l2;
  t = Math.max(0, Math.min(1, t));

  const projLat = v.lat + t * (w.lat - v.lat);
  const projLng = v.lng + t * (w.lng - v.lng);

  return Math.hypot(p.lat - projLat, p.lng - projLng);
}

Пограничные случаи

При проверке принадлежности точки учитываются:

  • совпадение с вершиной полигона
  • попадание на ребро
  • численные ошибки floating point
  • анти-паттерны самопересекающихся полигонов

Типичная стабилизация:

  • epsilon сравнения
  • нормализация координат
  • предварительная фильтрация по bounds
const EPS = 1e-12;

function nearlyEqual(a, b) {
  return Math.abs(a - b) < EPS;
}

Практическая схема комбинированной проверки

function pointInLayer(point, layer) {
  if (!layer.getBounds().contains(point)) return false;

  const latlngs = layer.getLatLngs()[0];

  return isPointInPolygon(point, latlngs);
}

Многоуровневый подход минимизирует стоимость вычислений и обеспечивает стабильную работу при больших наборах геометрий.

Оглавление