Физическая симуляция: силы и параметры

В графовых компонентах Nivo используется модель силовой симуляции, основанная на подходе, разработанном в D3.js. Эта модель применяется для автоматического размещения узлов графа таким образом, чтобы структура оставалась читаемой, а пересечения рёбер минимизировались.

Физическая симуляция рассматривает граф как систему частиц, где каждый узел — это объект с массой, а связи между узлами — это пружины. Поведение системы определяется набором сил, каждая из которых влияет на движение узлов в пространстве координат.

Базовая структура force-системы

В основе лежит итеративный алгоритм, который на каждом шаге пересчитывает положение узлов:

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

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

  • координаты узлов (x, y)
  • скорость (vx, vy)
  • сила воздействия (fx, fy)
  • коэффициент затухания (alpha)

Сила отталкивания (charge force)

Сила отталкивания предотвращает наложение узлов друг на друга и формирует общую структуру графа.

Математически она задаётся как:

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

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

  • strength — интенсивность отталкивания
  • distanceMax — максимальная дистанция действия
  • theta (Barnes-Hut) — точность аппроксимации для ускорения вычислений

Поведение:

  • отрицательная сила раздвигает узлы
  • высокая strength приводит к более «разреженному» графу
  • низкая strength — к компактной структуре

Связывает узлы, которые соединены ребром, имитируя пружину.

Каждое ребро имеет:

  • целевую длину
  • жёсткость (stiffness)
  • коэффициент демпфирования

Ключевые параметры:

  • distance — целевая длина связи
  • strength — жёсткость пружины
  • iterations — количество итераций стабилизации

Поведение:

  • при большой distance граф становится более разреженным
  • при высокой strength связи становятся жёсткими
  • при низкой strength структура становится «плавающей»

Центрирующая сила (center force)

Возвращает систему в заданную область координат.

Используется для:

  • удержания графа в пределах viewport
  • предотвращения ухода узлов за границы сцены

Параметры:

  • координаты центра (cx, cy)
  • сила притяжения к центру

Эта сила не зависит от связей между узлами и действует глобально.

Сила столкновений (collision force)

Отвечает за предотвращение пересечения узлов.

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

Параметры:

  • radius — радиус узла
  • strength — сила реакции столкновения
  • iterations — точность расчёта

Поведение:

  • при высокой strength узлы не пересекаются, но могут «отталкиваться резко»
  • при низкой strength возможны наложения

Коэффициент затухания (alpha decay)

Симуляция не бесконечна — она постепенно стабилизируется за счёт затухания энергии системы.

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

  • alpha — текущая энергия системы
  • alphaMin — порог остановки
  • alphaDecay — скорость затухания

Поведение:

  • высокая alphaDecay ускоряет стабилизацию, но снижает точность
  • низкая alphaDecay делает граф более стабильным, но требует больше итераций

Скорость и инерция узлов

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

  • vx, vy — компоненты скорости
  • inertia — сохраняемая часть движения

Обновление состояния:

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

Это позволяет графу выглядеть «физически правдоподобным», а не дискретным.

Инициализация симуляции

В контексте Nivo симуляция запускается при монтировании графа и принимает входные данные:

  • список узлов
  • список связей
  • конфигурацию сил

Пример структуры данных:

const nodes = [
  { id: 'A', value: 10 },
  { id: 'B', value: 20 }
];

const links = [
  { source: 'A', target: 'B' }
];

Далее конфигурация force-модели:

const config = {
  linkDistance: 120,
  linkStrength: 0.7,
  repulsionStrength: -300,
  collisionRadius: 10,
  centerStrength: 0.1
};

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

Все силы действуют одновременно, формируя результирующий вектор ускорения:

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

Итоговое поведение определяется балансом параметров, а не одной силой.

Численная интеграция

Алгоритм обновления состояния основан на дискретной симуляции:

  1. вычисление всех сил
  2. суммирование ускорений
  3. обновление скорости
  4. применение затухания
  5. обновление координат

Метод относится к классу явной интеграции Эйлера, что делает его быстрым, но чувствительным к параметрам шага.

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

Для больших графов используется несколько оптимизаций:

  • пространственное разбиение (quadtree в стиле D3.js)
  • ограничение радиуса взаимодействия
  • аппроксимация дальних сил

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

Настройка поведения через параметры

Комбинации параметров определяют характер визуализации:

  • высокая отталкивающая сила + слабые связи → кластерная структура
  • сильные связи + слабое отталкивание → плотные цепочки
  • сильное центрирование → компактный радиальный граф
  • высокая collision strength → строгая геометрическая упаковка

Поведение при стабилизации

По мере уменьшения alpha:

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

При достижении alphaMin симуляция останавливается, фиксируя итоговое расположение узлов.

Оглавление