Улучшения классических силовых алгоритмов - Визуализация графа цитирования

Первым улучшением является добавление псевдо-гравитационной силы [11]. Эта сила притягивает все вершины к центру рабочей области. Обычно она линейна относительно расстояния, в отличие от обыкновенной гравитационной силы которая является обратно-квадратичной. Эта сила позволяет решить сразу две проблемы; первая - это то, что она стягивает граф в видимую область и не позволяет ему "уехать" за ее грани во время симуляции, вторая - это то, что она не дает несвязанным подграфам удалиться слишком далеко от центра.

Вторым улучшением является добавление силы трения [11]. Эта сила также является псевдо-силой в том понимании, что она не соответствует силе трения в реальном мире. Обычно она действует линейно на скорость уменьшая ее в определенное количество раз на каждом шаге алгоритма. Тем самым она позволяет не разгоняться вершинам слишком быстро, что часто бывает проблемой при работе подобных алгоритмов.

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

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

Самый простой способ решения - это воспользоваться методом Эйлера [12]. Он не сильно отличается от того, что мы делали раньше. Теперь для каждой вершины вводится понятие скорости, равной изначально 0. На каждом шаге мы вначале находим скорость как:

,

И только после этого вычисляем новые координаты:

.

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

Поэтому чаще всего используют более сложный способ интегрирования - интегрирование Верле [13]. На каждом шаге, вначале высчитывается положение для следующего момента времени:

,

Далее считается скорость:

.

Если есть информация о массе вершины, то сила заменяется на ускорение:

.

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

Теперь необходимо сказать о сложности алгоритма расположения вершин. На каждом шаге алгоритма для каждой из N Вершин необходимо посчитать силы, действующие на нее со стороны остальных N-1 Вершин. Соответственно вычислительная сложность на каждом шаге. Такой алгоритм будет медленно работать даже на сравнительно небольших графах, что неприемлемо для real-time задач и ухудшает user experience.

Для решение данной проблемы используется алгоритм аппроксимации симуляции динамической системы Барнса-Хата [14]. Он позволяет выполнить симуляцию за вместо Этот алгоритм используется полностью на каждом шаге симуляции.

Первый шаг алгоритма Барнса-Хата - это построение квадродерева. Квадродерево рекурсивно делит рабочую область на 4 квадрата, называемых "квадрантами", пока внутри не будет нуля или одной вершины. Тес самым мы получаем дерево, в котором каждый узел - это квадрант и имеет 4 потомка (пример дерева на рис. 2). Сложность построения такого квадродерева. Во время построения дерева считается центр масс и масса каждого узла из всех объектов в его поддереве.

квадродерево из 4 точек. слева - разбиение плоскости на квадранты, справа - представление точек и квадрантов в виде дерева

Рисунок 2. Квадродерево из 4 точек. Слева - разбиение плоскости на квадранты, справа - представление точек и квадрантов в виде дерева

Далее для каждого тела в симуляции высчитывается суммарная сила. Для этого начинается проход квадродерева, если центр масс текущего узла достаточно далек от тела, то мы представляем этот узел как большое тело с центром в центре масс и массой равной суммарной массе, и считаем силу, действующую на текущее тело со стороны узла. После этого потомки узла уже не просматриваются. Если же в какой-то ветке квадродерева мы не нашли такого узла, то мы доходим то листьев и считаем силу, действующую с их стороны.

Узким местом этого алгоритма является понятие "достаточно далеко". Для его определения вводится эмпирический параметр. Если он больше отношения ширины узла к расстоянию от тела до центра масс узла, то узел считается "достаточно далеким". Фактически параметр позволяет управлять балансом между точностью и скоростью аппроксимации. Если имеет большое значение, то алгоритм будет работать быстро но с плохой точностью, а если близка к 0, то наоборот.

Похожие статьи




Улучшения классических силовых алгоритмов - Визуализация графа цитирования

Предыдущая | Следующая