Упакованные круги (circle packing)

Упакованные круги (circle packing) представляют собой способ визуализации иерархических данных, при котором элементы отображаются в виде окружностей, вложенных друг в друга без пересечений. Размер окружностей соответствует некоторой количественной метрике, а структура вложенности отражает иерархию данных. В экосистеме Vega и Vega-Lite данный тип визуализации реализуется через иерархические преобразования (hierarchy transforms) и алгоритмы упаковки (pack layout), основанные на вычислении оптимального размещения окружностей в ограниченном пространстве.

Основой является иерархическая структура данных в формате дерева. Каждый узел может содержать:

дочерние элементы (children)
числовое значение (value) для листовых узлов или агрегированное значение
идентификатор (name, id)
дополнительные атрибуты (цвет, категория, метаданные)

Типичная структура:

{
  "name": "root",
  "children": [
    {
      "name": "A",
      "children": [
        { "name": "A1", "value": 10 },
        { "name": "A2", "value": 20 }
      ]
    },
    {
      "name": "B",
      "children": [
        { "name": "B1", "value": 15 }
      ]
    }
  ]
}

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

Алгоритмическая основа упаковки

Circle packing основан на вычислении радиусов окружностей и их плотной укладке без пересечений.

Базовые этапы:

Построение иерархии (hierarchy construction)
Вычисление значений узлов (aggregation)
Назначение радиусов (radius scaling)
Компоновка окружностей (packing layout)
Распределение координат (x, y)

В Vega используется алгоритм, вдохновлённый работами Уотсона и Уолша по плотной упаковке кругов, а также модификации D3 hierarchy pack layout.

Иерархическое преобразование (Hierarchy Transform)

В Vega основным шагом является трансформация данных в иерархическую структуру через stratify или hierarchy.

Пример:

{
  "type": "stratify",
  "key": "id",
  "parentKey": "parent"
}

или прямое использование вложенных данных:

{
  "type": "hierarchy",
  "method": "sum",
  "field": "value"
}

Параметр method: "sum" определяет агрегацию значений снизу вверх.

Pack transform в Vega

Ключевым элементом является трансформация pack, которая вычисляет позиции и радиусы окружностей.

{
  "type": "pack",
  "size": [800, 800],
  "padding": 2
}

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

size — размер области визуализации
padding — расстояние между окружностями
aspectRatio — соотношение сторон (опционально)
sort — порядок размещения узлов

Результатом является набор координат:

x
y
r (радиус)

Масштабирование радиусов

Радиус вычисляется на основе площади:

[ r = ]

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

линейная или корневая шкала (sqrt, log)
ограничение минимального и максимального радиуса

Это позволяет избежать доминирования крупных узлов.

Пример полной спецификации Vega

{
  "$schema": "https://vega.github.io/schema/vega/v5.json",
  "width": 600,
  "height": 600,
  "padding": 5,

  "data": [
    {
      "name": "tree",
      "values": [
        {"id": "root.A.A1", "parent": "root.A", "value": 10},
        {"id": "root.A.A2", "parent": "root.A", "value": 20},
        {"id": "root.A", "parent": "root", "value": 0},
        {"id": "root.B.B1", "parent": "root.B", "value": 15},
        {"id": "root.B", "parent": "root", "value": 0},
        {"id": "root", "parent": "", "value": 0}
      ],
      "transform": [
        {
          "type": "stratify",
          "key": "id",
          "parentKey": "parent"
        },
        {
          "type": "pack",
          "field": "value",
          "size": [{"signal": "width"}, {"signal": "height"}],
          "padding": 4
        }
      ]
    }
  ],

  "marks": [
    {
      "type": "symbol",
      "from": {"data": "tree"},
      "encode": {
        "enter": {
          "x": {"field": "x"},
          "y": {"field": "y"},
          "size": {"signal": "pow(datum.r, 2) * 10"},
          "fill": {"value": "#4c78a8"},
          "stroke": {"value": "#fff"}
        }
      }
    }
  ]
}

Геометрическая интерпретация

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

центр окружности: (x, y)
радиус: r
вложенность: определяется containment relation

Родительская окружность полностью содержит дочерние, при этом:

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

Цветовое кодирование и семантика

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

уровень иерархии → оттенок цвета
категория → цветовая палитра
значение → насыщенность или прозрачность

Пример encode:

"fill": {
  "scale": "color",
  "field": "depth"
}

Или:

"fillOpacity": {
  "scale": "opacityScale",
  "field": "value"
}

Vega-Lite и circle packing

В Vega-Lite отсутствует прямой низкоуровневый API упаковки кругов, однако поддержка достигается через:

трансформации aggregate
window
hierarchy (в расширенных версиях)
компиляцию в Vega

Типичный подход:

описать иерархические данные
использовать high-level spec
позволить компилятору сгенерировать Vega pack transform

Пример упрощённой структуры:

{
  "data": {"values": [...]},
  "mark": "circle",
  "encoding": {
    "x": {"field": "x", "type": "quantitative"},
    "y": {"field": "y", "type": "quantitative"},
    "size": {"field": "value"}
  }
}

При этом реальные координаты чаще вычисляются через Vega runtime.

Масштабируемость и ограничения

Circle packing имеет вычислительную сложность, зависящую от числа узлов:

построение иерархии: O(n)
упаковка: приблизительно O(n log n)
плотная оптимизация: итеративные методы

Ограничения:

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

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

Уменьшение глубины

Агрегация уровней:

объединение мелких узлов
фильтрация по порогу значения

Управление padding

малый padding → высокая плотность
большой padding → лучшая читаемость, но меньше узлов

Сортировка узлов

"sort": {
  "field": "value",
  "order": "descending"
}

Позволяет размещать крупные элементы в более центральных позициях.

Интерактивность

В Vega circle packing часто используется:

zoom (масштабирование и фокусировка)
hover (подсветка узла)
tooltip (информация)
drill-down (переход по уровням иерархии)

Zoom реализуется через signal:

"signals": [
  {
    "name": "scale",
    "value": 1
  }
]

И трансформацию координат:

"x": {"signal": "datum.x * scale"},
"y": {"signal": "datum.y * scale"}

Варианты визуального представления

Circle packing может быть реализован в нескольких стилях:

классические вложенные круги (strict containment)
packed bubbles (без строгой вложенности)
radial packing (радиальная композиция)
hybrid layouts (комбинация с treemap)

Применение

анализ иерархий организаций
визуализация файловых систем
распределение бюджета
биоинформатика (таксономии)
анализ кластеров данных

Особенности реализации в Vega runtime

Vega использует декларативный подход:

данные описываются как pipeline transforms
layout вычисляется автоматически
результат передаётся в rendering marks

Это отличает систему от императивных библиотек, где размещение вычисляется вручную.

Геометрические свойства плотной упаковки

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

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

Сравнение с альтернативами

TreeMap: прямоугольная упаковка, точнее для сравнения значений
Sunburst: угловая иерархия
Circle packing: более органичная визуальная структура, но менее точная для сравнения

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