Трансформация voronoi

Геометрическая основа построения диаграммы Вороного

Диаграмма Вороного представляет собой разбиение плоскости на области влияния точек-наблюдателей. Каждая область содержит все точки пространства, которые находятся ближе к соответствующему генератору, чем к любому другому. Формально, для множества точек ( P = {p_1, p_2, …, p_n} ) каждая область определяется как:

V(p_i)={x ^2 d(x,p_i) d(x,p_j), j i}

В контексте Vega и Vega-Lite эта конструкция используется для пространственного разбиения визуализаций, чаще всего на основе scatter plot, heatmap-подобных структур и интерактивных карт влияния.

Модель трансформации voronoi в Vega

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

Базовая структура трансформации:

{
  "transform": [
    {
      "type": "voronoi",
      "x": "x",
      "y": "y",
      "size": [width, height]
    }
  ]
}

Каждый параметр определяет ключевую часть вычисления:

  • x, y — поля входных данных, задающие положение точек
  • size — размер вычислительного пространства (границы диаграммы)
  • extent — альтернативный способ задания границ области
  • as — имя выходного поля с геометрией полигонов

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

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

Внутренне Vega использует вычисление через триангуляцию Делоне, после чего строит двойственную к ней структуру — диаграмму Вороного. Это обеспечивает:

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

Параметры трансформации voronoi

Основные параметры

x / y Определяют координаты точек. Могут быть числовыми полями данных или выражениями.

size Определяет прямоугольную область вычисления:

"size": [width, height]

При отсутствии используется viewport сцены.

extent Альтернативное задание границ:

"extent": [[x0, y0], [x1, y1]]

Используется при работе с вложенными или смещёнными системами координат.

as Позволяет задать имя выходного поля:

"as": "cell"

Формирование полигональной структуры

После применения трансформации каждая точка получает ассоциированный полигон. Структура данных обычно включает:

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

Пример результата:

{
  "x": 120,
  "y": 80,
  "cell": [
    [100, 50],
    [140, 60],
    [130, 100],
    [90, 90]
  ]
}

Эта структура позволяет напрямую использовать данные в shape или path mark.

Использование в Vega-Lite через compile-to-Vega

Vega-Lite не всегда экспонирует voronoi как высокоуровневую трансформацию напрямую, однако при компиляции спецификации в Vega возможно включение данного этапа через расширенные transform-блоки.

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

  • scatter plot точек
  • наложение невидимых областей влияния
  • обработка событий наведения мыши по регионам

Пример логической структуры Vega-Lite:

{
  "data": {"name": "points"},
  "mark": "circle",
  "encoding": {
    "x": {"field": "x", "type": "quantitative"},
    "y": {"field": "y", "type": "quantitative"}
  },
  "transform": [
    {
      "type": "voronoi",
      "x": "x",
      "y": "y",
      "size": [500, 400],
      "as": "cell"
    }
  ]
}

Использование для интерактивности

Основное применение диаграммы Вороного в Vega — расширение области взаимодействия.

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

Схема взаимодействия:

  1. вычисление полигонов
  2. привязка событий pointerover к полигону
  3. определение ближайшей точки через принадлежность области

Это позволяет:

  • увеличивать удобство наведения
  • снижать требования к точности курсора
  • улучшать UX плотных scatter-диаграмм

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

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

(P) = ((P))

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

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

При увеличении числа точек сложность построения возрастает, поскольку требуется обработка соседских отношений.

Основные характеристики:

  • средняя сложность: ( O(n n) )
  • память: линейная относительно числа точек
  • узкие места: вычисление границ при больших extent

Оптимизация в Vega включает:

  • кэширование триангуляции
  • ограничение области extent
  • упрощение полигонов при рендере

Взаимодействие с mark-слоем

Voronoi часто используется как скрытый слой поверх визуализации:

{
  "mark": "path",
  "from": {"data": "points"},
  "encode": {
    "enter": {
      "path": {"field": "cell"},
      "fill": {"value": "transparent"}
    },
    "hover": {
      "fill": {"value": "rgba(0,0,0,0.05)"}
    }
  }
}

Такой слой не отображает границы, но служит для обработки событий.

Комбинация с другими трансформациями

Voronoi часто используется совместно с:

  • filter — предварительная очистка точек
  • project — преобразование координат
  • stack — подготовка слоёв
  • joinaggregate — добавление метрик соседства

Порядок трансформаций критичен, так как Voronoi требует уже финальных координат.

Типичные ошибки при использовании

Неправильные границы extent При отсутствии корректного extent полигоны могут обрезаться или выходить за пределы визуализации.

Использование нечисловых координат Voronoi требует строгих числовых значений x и y.

Смешивание координатных систем При наличии масштабирования (scale) до Voronoi результат может искажаться.

Игнорирование плотности точек При высокой плотности точек полигоны становятся слишком малыми для практического взаимодействия.

Практические паттерны применения

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

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

Подложка для heatmap-поверхностей Voronoi используется как дискретизация непрерывных полей.

Гибридные визуализации Комбинируется с линиями, потоками и плотностными картами для создания многослойных графиков.

Роль в архитектуре Vega

Voronoi-трансформация находится на уровне геометрических вычислений, между data pipeline и rendering pipeline. Она не является декоративной операцией, а формирует структурный слой данных, влияющий на логику взаимодействия и форму последующего рендера.

Оглавление