Расчет матриц расстояний

Матрица расстояний в геопространственных вычислениях представляет собой таблицу попарных расстояний и/или времен маршрутизации между наборами точек. В контексте веб-картографии и клиентских приложений эта задача решается через сервисы маршрутизации и API, наиболее типичным из которых в экосистеме Mapbox GL JS является Matrix API платформы Mapbox.

Пусть задан набор источников ( O = {o_1, o_2, …, o_n} ) и набор назначений ( D = {d_1, d_2, …, d_m} ). Требуется получить матрицу ( M ), где каждый элемент:

  • ( M_{ij} = f(o_i, d_j) )

Функция ( f ) может возвращать:

  • географическое расстояние (метры, километры)
  • время маршрута (секунды)
  • комбинированные метрики (время + расстояние)

В Mapbox Matrix API чаще всего используется именно время маршрута по дорожному графу, а не евклидово расстояние.

Основные ограничения и особенности API

При работе с матрицей расстояний важно учитывать ограничения:

  • максимальное количество точек в одном запросе (обычно до 25×25 в стандартном тарифе)

  • необходимость деления задач на батчи при больших наборах координат

  • зависимость от выбранного профиля маршрутизации:

    • driving
    • walking
    • cycling
    • driving-traffic

Каждый профиль использует собственный граф дорог и, соответственно, даёт разные результаты.

Подготовка координат для расчёта матрицы

Все точки передаются в формате долгота/широта:

longitude,latitude

Пример набора координат:

const coordinates = [
  [71.4304, 51.1284],
  [71.4631, 51.1605],
  [71.4100, 51.1500]
];

Ключевой момент: порядок координат строго фиксирован — сначала долгота, затем широта.

Формирование запроса к Matrix API

Запрос строится через HTTP GET:

https://api.mapbox.com/directions-matrix/v1/mapbox/{profile}/{coordinates}

Пример:

https://api.mapbox.com/directions-matrix/v1/mapbox/driving/71.4304,51.1284;71.4631,51.1605;71.4100,51.1500?annotations=distance,duration&access_token=YOUR_TOKEN

Параметр annotations определяет тип возвращаемых данных:

  • distance — расстояние в метрах
  • duration — время в секундах

Пример расчёта матрицы через fetch

const accessToken = 'YOUR_TOKEN';

const coords = [
  [71.4304, 51.1284],
  [71.4631, 51.1605],
  [71.4100, 51.1500]
];

const coordString = coords.map(c => c.join(',')).join(';');

const url = `https://api.mapbox.com/directions-matrix/v1/mapbox/driving/${coordString}` +
  `?annotations=distance,duration&access_token=${accessToken}`;

async function getMatrix() {
  const response = await fetch(url);
  const data = await response.json();
  return data;
}

getMatrix().then(matrix => {
  console.log(matrix.distances);
  console.log(matrix.durations);
});

Структура ответа Matrix API

Ответ содержит две ключевые матрицы:

{
  "distances": [
    [0, 1200, 3400],
    [1100, 0, 2100],
    [3300, 2000, 0]
  ],
  "durations": [
    [0, 180, 420],
    [170, 0, 300],
    [400, 290, 0]
  ]
}

Каждая строка соответствует источнику, каждый столбец — назначению.

Интеграция с логикой Mapbox GL JS

Хотя Mapbox GL JS отвечает за визуализацию карты, матрица расстояний используется как вычислительный слой поверх карты.

Типичный сценарий:

  1. Пользователь выбирает точки на карте

  2. Координаты передаются в Matrix API

  3. Результат используется для:

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

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

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

  if (selectedPoints.length >= 3) {
    calculateMatrix(selectedPoints);
  }
});

Алгоритмы обработки матрицы

После получения данных обычно применяются вычисления:

Поиск ближайшего объекта

function findNearest(matrix, index) {
  const row = matrix.durations[index];

  let minTime = Infinity;
  let minIndex = -1;

  row.forEach((val, i) => {
    if (i !== index && val < minTime) {
      minTime = val;
      minIndex = i;
    }
  });

  return minIndex;
}

Построение графа связности

Матрица интерпретируется как взвешенный граф:

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

Это позволяет применять алгоритмы:

  • Дейкстры
  • Флойда–Уоршелла
  • жадные алгоритмы маршрутизации

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

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

  • один запрос: ( O(n^2) )
  • память ответа: ( O(n^2) )

Практические техники оптимизации:

Разбиение на батчи

function chunkArray(arr, size) {
  const chunks = [];
  for (let i = 0; i < arr.length; i += size) {
    chunks.push(arr.slice(i, i + size));
  }
  return chunks;
}

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

Матрицы часто пересчитываются для одинаковых наборов точек, поэтому применяется:

  • ключ хэша координат
  • localStorage / IndexedDB
  • серверное кэширование

Упрощение набора точек

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

  • кластеризация (DBSCAN, k-means)
  • удаление дубликатов
  • географическая агрегация

Использование временного профиля движения

Профиль driving-traffic учитывает:

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

Это критично для:

  • логистики
  • сервисов доставки
  • расчёта ETA в реальном времени

Комбинирование с визуализацией на карте

Результаты матрицы часто отображаются в интерфейсе:

  • линии между точками
  • heatmap доступности
  • изохроны (области достижимости)

Пример логики подсветки:

function drawConnections(points, matrix) {
  const features = [];

  for (let i = 0; i < points.length; i++) {
    for (let j = 0; j < points.length; j++) {
      if (i !== j) {
        features.push({
          type: 'Feature',
          geometry: {
            type: 'LineString',
            coordinates: [points[i], points[j]]
          },
          properties: {
            duration: matrix.durations[i][j]
          }
        });
      }
    }
  }

  map.getSource('connections').setData({
    type: 'FeatureCollection',
    features
  });
}

Ошибки и обработка ограничений

Типичные проблемы:

  • превышение лимита точек
  • некорректные координаты
  • отсутствие маршрута между точками (water/isolated roads)
  • таймаут API при больших запросах

Стратегия обработки:

if (!data.durations) {
  throw new Error('Matrix calculation failed');
}

Дополнительно применяются fallback-режимы:

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

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

В реальных системах матрица расстояний обычно является частью слоя сервисов:

  • UI (Mapbox GL JS)
  • сервис маршрутизации (Matrix API)
  • слой агрегации данных
  • аналитический модуль

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

Оглавление