Построение кратчайшего пути

Работа с кратчайшими маршрутами в геопространственных задачах на базе Turf.js строится вокруг представления дорожной сети как графа, где рёбра имеют вес, равный длине геометрического сегмента, а вершины соответствуют точкам пересечения и конечным узлам линий. Такой подход позволяет применять классические алгоритмы теории графов поверх геометрических данных GeoJSON.

Любая транспортная сеть в Turf.js обычно представляется набором объектов LineString или MultiLineString, объединённых в FeatureCollection. Для корректного поиска кратчайшего пути необходимо привести данные к графовой структуре:

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

Ключевая проблема исходных данных заключается в том, что пересечения линий в GeoJSON не всегда представлены как явные узлы. Поэтому первым этапом выполняется топологическая нормализация.

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

Для извлечения узлов используется анализ пересечений геометрий. В Turf.js для этого применяются:

  • lineIntersect — поиск точек пересечения линий
  • lineSplit — разбиение линий в точках пересечений
  • booleanEqual — проверка совпадений геометрий

Алгоритм построения узлов:

  1. Найти все пересечения между линиями
  2. Добавить концы каждой линии как узлы
  3. Объединить близкие точки (кластеризация по порогу расстояния)
  4. Разбить линии в точках пересечения

После этого каждая линия превращается в набор сегментов, полностью соответствующих рёбрам графа.

Формирование взвешенного графа

Каждый сегмент линии преобразуется в ребро графа. Вес рассчитывается через длину геометрии:

import length from "@turf/length";

const weight = length(segment, { units: "kilometers" });

Для каждого сегмента создаются две связи (граф неориентированный):

graph.addEdge(nodeA, nodeB, weight);
graph.addEdge(nodeB, nodeA, weight);

Структура графа чаще всего реализуется через Map:

const graph = new Map();

function addEdge(a, b, w) {
  if (!graph.has(a)) graph.set(a, []);
  graph.get(a).push({ to: b, weight: w });
}

Нормализация координат и устранение дубликатов

Геометрические данные часто содержат:

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

Для стабилизации графа применяется округление координат:

function normalizeCoord(coord, precision = 6) {
  return coord.map(v => Number(v.toFixed(precision)));
}

После нормализации узлы можно безопасно хешировать:

function nodeKey(coord) {
  return coord.join(",");
}

Поиск кратчайшего пути: алгоритм Дейкстры

После построения графа применяется алгоритм Дейкстры. Он подходит для неотрицательных весов, что соответствует длинам дорог.

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

function dijkstra(graph, start, end) {
  const distances = new Map();
  const previous = new Map();
  const visited = new Set();

  const pq = new Map();

  for (const node of graph.keys()) {
    distances.set(node, Infinity);
  }
  distances.set(start, 0);

  pq.set(start, 0);

  while (pq.size > 0) {
    const current = [...pq.entries()].reduce((a, b) =>
      a[1] < b[1] ? a : b
    )[0];

    pq.delete(current);

    if (current === end) break;

    visited.add(current);

    for (const neighbor of graph.get(current) || []) {
      if (visited.has(neighbor.to)) continue;

      const newDist =
        distances.get(current) + neighbor.weight;

      if (newDist < distances.get(neighbor.to)) {
        distances.set(neighbor.to, newDist);
        previous.set(neighbor.to, current);
        pq.set(neighbor.to, newDist);
      }
    }
  }

  const path = [];
  let curr = end;

  while (curr) {
    path.unshift(curr);
    curr = previous.get(curr);
  }

  return path;
}

Привязка графа к геометрии

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

import lineString from "@turf/linestring";

function buildRouteGeometry(path, coordMap) {
  const coords = path.map(node => coordMap.get(node));
  return lineString(coords);
}

coordMap хранит соответствие между ключом узла и координатами.

Учет реальной дорожной топологии

При работе с реальными данными возникают дополнительные сложности:

Односторонние дороги

Граф становится ориентированным:

graph.addEdge(a, b, w);
// нет обратного ребра

Пересечения без соединения

Эстакады и мосты требуют проверки высотности или тегов layer и bridge.

Различные классы дорог

Вес ребра может модифицироваться:

  • автомагистрали — коэффициент 0.8
  • грунтовые дороги — коэффициент 1.5
const adjustedWeight = length(segment) * roadFactor;

Оптимизация поиска

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

Очередь с приоритетом

Замена линейного поиска минимального элемента на кучу:

  • бинарная куча
  • Fibonacci heap (теоретически)

Двунаправленный поиск

Одновременный запуск от старта и финиша уменьшает пространство поиска.

Предвычисление индексов

Геометрии индексируются через R-tree (например, rbush), чтобы ускорить поиск пересечений.

Построение сети из GeoJSON

Полный цикл обработки начинается с FeatureCollection:

function buildGraph(features) {
  const graph = new Map();
  const coordMap = new Map();

  features.forEach(feature => {
    const coords = feature.geometry.coordinates;

    for (let i = 0; i < coords.length - 1; i++) {
      const a = normalizeCoord(coords[i]);
      const b = normalizeCoord(coords[i + 1]);

      const keyA = nodeKey(a);
      const keyB = nodeKey(b);

      coordMap.set(keyA, a);
      coordMap.set(keyB, b);

      const segment = {
        type: "Feature",
        geometry: {
          type: "LineString",
          coordinates: [a, b]
        }
      };

      const w = length(segment);

      if (!graph.has(keyA)) graph.set(keyA, []);
      if (!graph.has(keyB)) graph.set(keyB, []);

      graph.get(keyA).push({ to: keyB, weight: w });
      graph.get(keyB).push({ to: keyA, weight: w });
    }
  });

  return { graph, coordMap };
}

Восстановление полного маршрута

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

const route = buildRouteGeometry(path, coordMap);

Полученная геометрия может использоваться в Mapbox GL, Leaflet или любом GeoJSON-совместимом рендерере.

Масштабирование на большие данные

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

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

Графовая модель остаётся неизменной, меняется только стратегия хранения и поиска.

Обобщённая архитектура пайплайна

  1. Загрузка GeoJSON дорожной сети
  2. Нормализация координат
  3. Вычисление пересечений
  4. Построение узлов графа
  5. Формирование рёбер с весами
  6. Запуск алгоритма Дейкстры
  7. Восстановление геометрии маршрута
  8. Визуализация результата

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

Оглавление