Теория графов - алгоритм автоматического размещения на основе силы

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

Константы:

  • m = масса вершины (все равно - возможно, установите это значение радиус узла)
  • k = постоянная сила на краю.
  • l = длина кромки в «состоянии минимальной энергии».

Переменные:

  • d = расстояние между двумя вершины.
  • cl = текущая длина ребра.

Теория: Каждая вершина имеет силу отталкивания на каждую другую вершину, которая равна: m / (d ^ 2) . Для каждого ребра он проявляет силу, обе вершины «тянут» их в направлении, чтобы ребро перешло в «энергетически минимальное состояние»; поэтому каждая вершина: -k * ((l - cl) / 2) .

Псевдокод:

until energy minimal state
   for each vertex v1
      for each vertex v2
         if v1 != v2
            v1.velocity += m / square_distance (v1, v2)
         endif
      end
   end
   for each edge e
      e.v1.velocity += -k * (delta_min_energy_len (e) / 2)
      e.v2.velocity += -k * (delta_min_energy_len (e) / 2)
   end
   for each vertex v
      v.position += (v.velocty * dampening_constant)
   end                
end

Комментарии: Так будет ли это работать? Что мне следует установить для m и k ?

11
задан Cheetah 25 April 2011 в 15:57
поделиться