11

只是想在开始实施之前检查我的理论。

常数：

  • 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？

4

2 回答 2

5

You're on the right lines. Your terminology/physics is a bit off: what you're calling mass and "k" is sort of all mixed up with what would better be called "charge" (for the inverse-square law repulsion) and "spring constant" for the Hooke's Law attraction.

As noted in comment replies to your question, you do need some damping which actually takes energy out of the system, else it will just oscillate converting potential energy to kinetic energy and back forever. Worse, simulation accuracy issues can easily lead to energy increasing indefinitely and the simulation "going crazy" if you're not careful.

This wikipedia article has some nice pseudocode which you'll find very similar to yours, but with the above points addressed (although note that even that pseudocode is missing a divide-by-mass in the acceleration calculation; see the page's discussion).

You also need to think a bit about the initial distribution you'll start the simulation from, and how you much you care about the possibility of getting stuck in a local minimum if a (perhaps) much better global minimum exists. These points are related; a lot depends on the topology of your graph. If it's a simple tree you'll have little trouble getting a nice layout. If it's got lots of loops and structure... good luck.

于 2011-05-13T19:59:19.180 回答
1

我不会为每个顶点选择相同的 m。相反，我会让它与它所连接的其他顶点的数量成正比。这样，图的末端飞到他们的位置比高度连接的末端更快。

我不知道k。

于 2011-05-13T19:01:25.743 回答