Network анализ

Сетевой анализ в среде CesiumJS представляет собой совокупность методов работы с графовыми структурами, наложенными на пространственные данные. Под сетью понимается граф, вершины которого соответствуют географическим объектам (перекрёстки, узлы инфраструктуры, остановки), а рёбра — связям между ними (дороги, маршруты, коммуникации). Основная цель анализа — вычисление оптимальных путей, оценка связности, моделирование потоков и анализ доступности объектов в 3D-городской среде.

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

Представление сетей как графов

Любая транспортная или навигационная сеть формализуется как граф:

  • Вершины (nodes) — геометрические точки с координатами (longitude, latitude, height)
  • Рёбра (edges) — соединения между вершинами с весами
  • Вес ребра — метрика стоимости: расстояние, время, энергия, риск

G = (V, E)

где:

  • V — множество вершин
  • E — множество рёбер

В CesiumJS такие структуры часто накладываются поверх:

  • 3D Tiles (городские модели)
  • Terrain Provider (модели рельефа)
  • Imagery Layers (картографическая подложка)

Источники сетевых данных

Сетевые графы редко создаются вручную и обычно импортируются из геоданных:

  • OpenStreetMap — основной источник дорожных графов
  • ГИС-форматы: GeoJSON, Shapefile, KML
  • Серверы маршрутизации: OSRM, GraphHopper, Valhalla
  • Собственные CAD/GIS модели инфраструктуры

CesiumJS не предоставляет встроенный routing engine, но обеспечивает визуализацию и пространственную интеграцию сетей.

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

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

class Graph {
  constructor() {
    this.nodes = new Map();
    this.edges = new Map();
  }

  addNode(id, position) {
    this.nodes.set(id, position);
  }

  addEdge(from, to, weight) {
    if (!this.edges.has(from)) {
      this.edges.set(from, []);
    }
    this.edges.get(from).push({ to, weight });
  }
}

В пространственном контексте CesiumJS позиция узла часто хранится как:

Cesium.Cartesian3.fromDegrees(longitude, latitude, height)

Привязка графа к трехмерной сцене

Каждый узел сети может быть визуализирован как entity:

viewer.entities.add({
  position: Cesium.Cartesian3.fromDegrees(71.4304, 51.1282),
  point: {
    pixelSize: 8,
    color: Cesium.Color.YELLOW
  }
});

Рёбра визуализируются как полилинии:

viewer.entities.add({
  polyline: {
    positions: Cesium.Cartesian3.fromDegreesArrayHeights([
      71.4304, 51.1282, 0,
      71.4400, 51.1300, 0
    ]),
    width: 3,
    material: Cesium.Color.CYAN
  }
});

Алгоритмы поиска маршрута

Сетевой анализ опирается на классические алгоритмы теории графов:

Алгоритм Дейкстры

w(e)

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

Пример реализации:

function dijkstra(graph, start) {
  const dist = new Map();
  const visited = new Set();

  for (let node of graph.nodes.keys()) {
    dist.set(node, Infinity);
  }
  dist.set(start, 0);

  while (visited.size < graph.nodes.size) {
    let current = null;

    for (let [node, value] of dist.entries()) {
      if (!visited.has(node) && (current === null || value < dist.get(current))) {
        current = node;
      }
    }

    visited.add(current);

    const neighbors = graph.edges.get(current) || [];
    for (let { to, weight } of neighbors) {
      const newDist = dist.get(current) + weight;
      if (newDist < dist.get(to)) {
        dist.set(to, newDist);
      }
    }
  }

  return dist;
}

Алгоритм A*

f(n)=g(n)+h(n)

  • g(n) — стоимость пути от старта
  • h(n) — эвристическая оценка до цели

В CesiumJS эвристика часто вычисляется как евклидово расстояние между Cartesian3 точками.

Учет высот и рельефа

Особенность CesiumJS — работа с глобальной моделью Земли. Поэтому вес ребра может включать:

  • расстояние по поверхности
  • перепад высот
  • ограничения движения

d =

При использовании Terrain Provider вычисление высоты выполняется через:

Cesium.sampleTerrainMostDetailed(viewer.terrainProvider, positions);

3D маршрутизация и навигация в пространстве

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

  • учитывать уклоны дорог
  • избегать зданий (3D Tiles)
  • учитывать мосты и туннели
  • разделять уровни высоты

Коллизии с городской моделью решаются через:

  • ray casting
  • bounding volume hierarchy
  • tile-based culling

Интеграция с тайловой структурой

CesiumJS использует иерархию тайлов:

  • quadtree для 2D данных
  • octree для 3D Tiles

Сетевой граф может быть привязан к тайлам:

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

Динамическая маршрутизация

В интерактивных сценах маршрут пересчитывается при изменении условий:

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

Пример пересчёта:

viewer.clock.onTick.addEventListener(() => {
  const route = computeRoute(graph, start, end);
  updatePolyline(route);
});

Многокритериальный анализ

Вес ребра может быть векторным:

  • расстояние
  • время
  • стоимость
  • безопасность

w(e)=d + t + r

где:

  • d — расстояние
  • t — время
  • r — риск

Потоки и нагрузка сети

Сетевой анализ используется не только для маршрутов, но и для моделирования потоков:

  • транспортные потоки
  • пешеходная нагрузка
  • эвакуационные сценарии

Модель потока:

F = _{i=1}^{n} f_i

Пространственная индексация графа

Для ускорения поиска применяются структуры:

  • R-tree (поиск ближайших узлов)
  • KD-tree (поиск в 3D)
  • spatial hashing

CesiumJS эффективно сочетает это с тайловой системой рендеринга, минимизируя количество активных узлов графа в кадре.

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

При больших графах применяются:

  • ленивое вычисление соседей
  • кэширование маршрутов
  • сокращение графа (graph simplification)
  • предрасчет маршрутов на сервере

Особенно критично это в глобальных сценах CesiumJS, где число узлов может достигать миллионов.

Связь с 3D визуализацией

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

  • polyline entities (маршрут)
  • extruded lines (интенсивность потока)
  • цветовую кодировку веса ребра
  • анимацию движения объектов по графу

Пример визуального обновления:

routeEntity.polyline.positions = Cesium.Cartesian3.fromDegreesArray(routeCoords);
routeEntity.polyline.material = Cesium.Color.RED;

Использование временной оси

CesiumJS поддерживает временные сцены, что позволяет анализировать сеть во времени:

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

Вес ребра становится функцией времени:

w(e,t) = f(t)

Оглавление