Диаграмма Вороного

Диаграмма Вороного представляет собой разбиение плоскости на области влияния точек-наблюдателей (seed points). Для каждой исходной точки формируется полигон, содержащий все точки пространства, которые ближе к данной точке, чем к любым другим.

Формально:

  • задано множество точек ( P = {p_1, p_2, …, p_n} )
  • пространство делится на области ( V_i ), где каждое ( V_i ) состоит из всех точек ( x ), для которых выполняется условие:

[ d(x, p_i) d(x, p_j), j i]

где ( d ) — евклидово расстояние.

Границы диаграммы формируются серединными перпендикулярами между парами точек, а вершины — пересечениями этих перпендикуляров.

Реализация Вороного-разбиения в Turf.js

Библиотека Turf.js реализует вычисление диаграммы Вороного через функцию:

turf.voronoi(points, options)

Входные данные

Функция работает с:

  • points — FeatureCollection<Point> в формате GeoJSON
  • координаты точек должны находиться в плоской системе (обычно долгота/широта в пределах bbox)

Пример структуры:

const points = turf.featureCollection([
  turf.point([37.62, 55.75]),
  turf.point([37.61, 55.76]),
  turf.point([37.63, 55.74])
]);

Ограничивающий прямоугольник (bbox)

Ключевым параметром является bbox, который задаёт границы вычисления диаграммы:

const options = {
  bbox: [37.50, 55.70, 37.70, 55.80]
};

Формат bbox:

[minX, minY, maxX, maxY]

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

Базовый пример построения диаграммы

import * as turf from "@turf/turf";

const points = turf.featureCollection([
  turf.point([0, 0]),
  turf.point([10, 0]),
  turf.point([5, 10])
]);

const bbox = [ -5, -5, 15, 15 ];

const voronoiPolygons = turf.voronoi(points, { bbox });

console.log(voronoiPolygons);

Результат:

  • FeatureCollection<Polygon>
  • каждый полигон соответствует одной входной точке
  • возможны null-результаты при недостатке данных

Геометрическая интерпретация результата

Каждый полигон Вороного:

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

Свойства:

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

Алгоритмическая основа Turf.voronoi

Внутри Turf.js используется геометрический подход:

  1. Построение триангуляции Делоне
  2. Перевод каждой триангуляции в дуальную структуру
  3. Формирование полигонов по окружностям описанных окружностей треугольников
  4. Обрезка по bbox

Ключевой момент:

  • производительность зависит от количества точек
  • при росте входных данных сложность резко возрастает

Особенности работы с координатами

Диаграмма Вороного в Turf.js работает в декартовой интерпретации координат, поэтому:

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

Практическое следствие:

  • локальные наборы (город, регион) дают корректный результат
  • глобальные наборы требуют перевода в projected CRS (например, Web Mercator)

Обработка краевых эффектов

Полигональные ячейки на границах bbox:

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

Причина:

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

Пример интеграции с визуализацией

Использование с Leaflet

const map = L.map("map").setView([55.75, 37.62], 12);

L.tileLayer("https://{s}.tile.openstreetmap.org/{z}/{x}/{y}.png").addTo(map);

L.geoJSON(voronoiPolygons, {
  style: {
    color: "#3388ff",
    weight: 2,
    fillOpacity: 0.2
  }
}).addTo(map);

Поверх слоя Вороного обычно накладываются исходные точки:

L.geoJSON(points, {
  pointToLayer: (feature, latlng) => L.circleMarker(latlng)
}).addTo(map);

Сценарии применения

Диаграмма Вороного в геопространственных задачах используется для:

1. Зоны обслуживания

Каждая точка — объект инфраструктуры, полигон — зона влияния.

2. Оптимизация расположения объектов

Анализ равномерности распределения станций, складов, датчиков.

3. Пространственная кластеризация

Визуальная сегментация плотности точек.

4. Игровые и симуляционные системы

Генерация территорий влияния фракций или объектов.

Ограничения вычислений

При использовании Turf.js проявляются следующие ограничения:

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

Особенно критично:

  • наличие дубликатов координат
  • слишком плотные кластеры точек

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

Возможные ситуации:

Пустой результат

Возникает при:

  • отсутствии bbox
  • некорректной FeatureCollection

Частично null-ячейки

Причины:

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

Связь с триангуляцией Делоне

Диаграмма Вороного и триангуляция Делоне являются дуальными структурами:

  • вершины Вороного ↔︎ центры описанных окружностей Делоне-треугольников
  • ребра Вороного ↔︎ перпендикуляры к ребрам Делоне

Следствие:

  • изменение одной структуры мгновенно перестраивает другую

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

При работе с Turf.js применяются подходы:

  • предварительная фильтрация точек по bbox
  • уменьшение плотности входных данных (simplification)
  • разбиение на регионы перед вычислением
  • кэширование результата при статичных данных

Поведение при больших наборах точек

При увеличении количества точек:

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

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

Геометрическая устойчивость

Проблемы устойчивости возникают при:

  • коллинеарных точках
  • совпадающих координатах
  • почти совпадающих значениях float-координат

Это приводит к:

  • вырожденным ребрам
  • некорректным полигонам
  • артефактам топологии

Структура GeoJSON результата

Выход Turf.voronoi:

{
  "type": "FeatureCollection",
  "features": [
    {
      "type": "Feature",
      "geometry": {
        "type": "Polygon",
        "coordinates": [...]
      },
      "properties": {}
    }
  ]
}

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

Сравнение с альтернативными реализациями

В отличие от серверных библиотек:

  • Turf.js ориентирован на браузер
  • использует GeoJSON как основной формат
  • оптимизирован под интерактивные карты

В отличие от computational geometry библиотек:

  • меньше точность при больших масштабах
  • проще интеграция с веб-картографией
  • ограниченный набор параметров настройки
Оглавление