Вычисление расстояний между множеством точек

В веб-картографии расстояние между точками редко рассматривается как евклидово. Поверхность Земли моделируется сферой или эллипсоидом, поэтому прямолинейная формула Пифагора даёт систематическую ошибку уже на небольших дистанциях. В контексте Google Maps JavaScript API применяются сферические вычисления, основанные на геодезических моделях WGS84.

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

Сферическая геометрия и базовые принципы

В основе большинства операций лежит модель сферы радиуса Земли:

  • средний радиус: 6 371 000 метров
  • координаты задаются в формате широта/долгота (lat/lng)
  • расстояние измеряется вдоль дуги большого круга

Большой круг — кратчайший путь между двумя точками на сфере.

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

const distance = google.maps.geometry.spherical.computeDistanceBetween(
  new google.maps.LatLng(lat1, lng1),
  new google.maps.LatLng(lat2, lng2)
);

Метод computeDistanceBetween реализует вычисление ортодромии и возвращает расстояние в метрах.

Формула гаверсинусов как математическая основа

При внутренней реализации используется вариация формулы гаверсинусов:

d = 2R ()

где:

  • ( ) — широта
  • ( ) — долгота
  • ( R ) — радиус Земли

Данная формула устойчива к численным ошибкам при малых расстояниях и используется вместо классической сферической теоремы косинусов.

Вычисление расстояний между множеством точек

При наборе точек ( P = {p_1, p_2, …, p_n} ) возникает задача построения полной матрицы расстояний:

[ D_{ij} = d(p_i, p_j)]

Количество вычислений растёт квадратично: ( O(n^2) ), что становится критичным при больших выборках.

Прямое использование computeDistanceBetween в двойном цикле:

const points = [...]; // массив LatLng
const matrix = [];

for (let i = 0; i < points.length; i++) {
  matrix[i] = [];
  for (let j = 0; j < points.length; j++) {
    matrix[i][j] = google.maps.geometry.spherical.computeDistanceBetween(
      points[i],
      points[j]
    );
  }
}

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

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

Одним из способов ускорения является переход к радианам заранее:

function toRad(value) {
  return (value * Math.PI) / 180;
}

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

Более значимая оптимизация — сокращение числа парных вычислений:

  • симметрия матрицы: ( D_{ij} = D_{ji} )
  • диагональ равна нулю
  • вычисление только верхнего треугольника
for (let i = 0; i < n; i++) {
  for (let j = i + 1; j < n; j++) {
    const d = google.maps.geometry.spherical.computeDistanceBetween(
      points[i],
      points[j]
    );
    matrix[i][j] = d;
    matrix[j][i] = d;
  }
}

Использование Distance Matrix Service

Для сценариев с большим количеством точек более эффективным становится использование серверного сервиса — Distance Matrix API, входящего в Google Maps Platform.

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

Пример запроса:

const service = new google.maps.DistanceMatrixService();

service.getDistanceMatrix(
  {
    origins: originList,
    destinations: destinationList,
    travelMode: google.maps.TravelMode.DRIVING
  },
  (response, status) => {
    if (status === "OK") {
      console.log(response.rows);
    }
  }
);

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

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

Различие между геодезическим и маршрутным расстоянием

При вычислениях важно различать два типа расстояний:

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

  • прямая линия по сфере
  • не учитывает дороги
  • используется computeDistanceBetween

Маршрутное расстояние

  • учитывает дорожную сеть
  • требует Distance Matrix или Directions API
  • зависит от транспорта

Расхождение между ними может достигать десятков процентов в городской среде.

Работа с большими наборами точек

При росте количества точек применяются дополнительные стратегии:

Пространственное разбиение

Использование grid-сетки или geohash позволяет ограничить число сравнений только соседними ячейками.

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

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

  • k-means по координатам
  • spatial clustering (DBSCAN-подобные алгоритмы)

Это снижает сложность последующих операций.

Отсечение по радиусу

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

const MAX_DISTANCE = 50000; // 50 км

if (approxDistance < MAX_DISTANCE) {
  // точное вычисление
}

Предварительное приближение через евклидову проекцию

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

function approxDistance(lat1, lng1, lat2, lng2) {
  const x = (lng2 - lng1) * Math.cos((lat1 + lat2) / 2);
  const y = lat2 - lat1;
  return Math.sqrt(x * x + y * y);
}

Это не геодезическое расстояние, но эффективно для предварительного отбора.

Матрицы расстояний и задачи графов

После построения матрицы расстояний данные часто интерпретируются как полный взвешенный граф:

  • вершины — точки
  • рёбра — расстояния

Типовые задачи:

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

В таких сценариях матрица расстояний становится базовым слоем для графовых алгоритмов.

Асинхронная обработка и Web Workers

При больших объёмах данных вычисления выносятся в отдельный поток:

const worker = new Worker("distanceWorker.js");

worker.postMessage({ points });

worker.onmess age = (e) => {
  console.log(e.data.matrix);
};

Это предотвращает блокировку UI-потока при квадратичной сложности вычислений.

Кэширование результатов расстояний

Повторяющиеся пары координат встречаются часто, особенно при динамических интерфейсах.

Используется хэширование пары точек:

function key(a, b) {
  return `${a.lat},${a.lng}-${b.lat},${b.lng}`;
}

Кэш позволяет избежать повторных вызовов computeDistanceBetween и существенно снижает нагрузку при интерактивных сценариях.

Численные особенности и точность

Сферические вычисления подвержены следующим особенностям:

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

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

Оглавление