NearestPoint

В интерактивных картах на основе Mapbox GL JS одной из ключевых задач является определение ближайшего географического объекта к заданной точке. Такая операция используется при кликах по карте, построении маршрутов, выборе POI, реализации инструментов анализа и динамической подсветки данных.

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

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

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

  • точки (Point)
  • линии (LineString)
  • полигоны (Polygon)
  • мультигеометрии

Расстояние может определяться:

  • в пикселях экрана (screen-space)
  • в географических координатах (longitude/latitude)
  • в метрах (геодезическое расстояние)

В веб-картах чаще всего используются два подхода:

  • экранная метрика (быстро, подходит для UI-взаимодействий)
  • геодезическая метрика (точнее, используется для аналитики)

Получение объектов из карты

В Mapbox GL JS данные слоя не доступны напрямую как массив геометрий. Вместо этого используется выборка через рендер-слой:

map.on('click', (e) => {
  const features = map.queryRenderedFeatures(e.point, {
    layers: ['cities-layer']
  });

  console.log(features);
});

Метод queryRenderedFeatures возвращает объекты, которые уже прошли этап рендеринга и видимы в текущем масштабе.

Каждый feature содержит:

  • geometry
  • properties
  • layer metadata

Однако этот метод не возвращает «ближайший» объект автоматически. Он лишь ограничивает набор кандидатов.

Простая реализация NearestPoint через перебор

Базовый алгоритм поиска ближайшей точки можно реализовать через линейный проход по всем объектам:

function getDistance(a, b) {
  const dx = a[0] - b[0];
  const dy = a[1] - b[1];
  return Math.sqrt(dx * dx + dy * dy);
}

function findNearestPoint(clickCoord, features) {
  let nearest = null;
  let minDistance = Infinity;

  for (const feature of features) {
    const coords = feature.geometry.coordinates;

    const distance = getDistance(clickCoord, coords);

    if (distance < minDistance) {
      minDistance = distance;
      nearest = feature;
    }
  }

  return nearest;
}

Такой подход применим только для Point-геометрий. Для линий и полигонов требуется вычисление расстояния до сегмента.

Работа с линиями и полигонами

Для LineString и Polygon необходимо вычислять минимальное расстояние до отрезков.

Упрощённая логика:

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

Пример вычисления расстояния от точки до отрезка:

function distanceToSegment(p, a, b) {
  const x = p[0], y = p[1];
  const x1 = a[0], y1 = a[1];
  const x2 = b[0], y2 = b[1];

  const dx = x2 - x1;
  const dy = y2 - y1;

  const t = ((x - x1) * dx + (y - y1) * dy) / (dx * dx + dy * dy);

  const clampedT = Math.max(0, Math.min(1, t));

  const projX = x1 + clampedT * dx;
  const projY = y1 + clampedT * dy;

  const distX = x - projX;
  const distY = y - projY;

  return Math.sqrt(distX * distX + distY * distY);
}

Для полигона алгоритм аналогичен, но учитываются все ребра внешнего и внутренних контуров.

Использование Turf.js для NearestPoint

В реальных приложениях ручные вычисления обычно заменяются специализированными библиотеками. Наиболее распространённый инструмент — Turf.

Функция nearestPoint позволяет находить ближайший объект в наборе:

import nearestPoint from '@turf/nearest-point';
import { featureCollection, point } from '@turf/helpers';

const queryPoint = point([87.134, 53.756]);

const points = featureCollection([
  point([87.120, 53.760]),
  point([87.200, 53.700]),
  point([87.140, 53.750])
]);

const nearest = nearestPoint(queryPoint, points);

Внутри используется геодезическое расстояние, что делает результат корректным для больших расстояний.

Интеграция NearestPoint с Mapbox GL JS

Типичный сценарий — обработка клика по карте и выбор ближайшего объекта слоя:

map.on('click', (e) => {
  const clicked = [e.lngLat.lng, e.lngLat.lat];

  const features = map.queryRenderedFeatures(e.point, {
    layers: ['places']
  });

  let nearest = null;
  let minDistance = Infinity;

  for (const f of features) {
    const coords = f.geometry.coordinates;

    const dx = coords[0] - clicked[0];
    const dy = coords[1] - clicked[1];

    const d = dx * dx + dy * dy;

    if (d < minDistance) {
      minDistance = d;
      nearest = f;
    }
  }

  if (nearest) {
    map.setFeatureState(
      { source: 'places-source', id: nearest.id },
      { selected: true }
    );
  }
});

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

Оптимизация поиска ближайшего объекта

При большом количестве объектов линейный перебор становится неэффективным. Основные подходы оптимизации:

Пространственные индексы

  • R-tree
  • QuadTree
  • grid-based indexing

Эти структуры позволяют уменьшить количество проверяемых объектов с O(n) до O(log n).

Кластеризация

В Mapbox GL JS часто применяется кластеризация через GeoJSON source:

map.addSource('points', {
  type: 'geojson',
  data: data,
  cluster: true,
  clusterRadius: 50
});

Кластеры уменьшают количество объектов, среди которых выполняется поиск.

Экранные координаты против географических

При взаимодействии с пользователем важна разница между системами координат:

  • e.point — пиксели
  • e.lngLat — географические координаты

Экранное расстояние используется для UI-подсветки, так как визуально соответствует восприятию пользователя.

Пример:

const p1 = map.project([lng, lat]);
const p2 = e.point;

const dx = p1.x - p2.x;
const dy = p1.y - p2.y;

const screenDistance = Math.sqrt(dx * dx + dy * dy);

NearestPoint для линий маршрута

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

  • пользователь отклонился от маршрута
  • требуется привязка GPS-трека
  • построение «snap to road»

Алгоритм включает:

  • перебор сегментов LineString
  • проекцию точки на сегмент
  • выбор минимального расстояния

Использование source query вместо полного перебора

Mapbox GL JS позволяет ограничивать область поиска:

map.queryRenderedFeatures([
  [x - 10, y - 10],
  [x + 10, y + 10]
], {
  layers: ['roads']
});

Это снижает количество проверяемых объектов, ограничивая поиск радиусом в пикселях.

Проблемы точности и проекций

При работе с координатами важно учитывать:

  • Web Mercator искажается на высоких широтах
  • евклидова метрика в lng/lat некорректна для больших расстояний
  • пиксельная точность зависит от zoom

Поэтому:

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

Типичные сценарии применения NearestPoint

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

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

В реальных системах используется комбинация:

  1. queryRenderedFeatures — фильтрация по видимой области
  2. экранная метрика — быстрый выбор кандидата
  3. геодезическая проверка — уточнение результата

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

Оглавление