之前我在公司负责开发了一个专用于拓扑图展现的框架，其中实现过一种布局算法——力导布局，我觉得挺有意思的，也曾在团队中做过技术分享，现在整理一下分享出来。
什么是力导布局呢？
其实就是在拓扑图中用于展示节点关系的一种布局算法。比如像这样：
image
通过布局后能够很直观的看出节点之间的关系。
力导布局算法实现了什么效果呢？
- 节点的位置没有重叠，不会互相遮挡；
- 节点位置总体上趋近去画布中心；
- 有关联的节点通过连线相连，并且相互靠拢；
- 节点的位置最终会稳定下来；
原理
首先说明，这里只讲布局原理，不涉及图形的绘制原理。我会根据上文中的实现要求，依次叙述。
-
节点的位置没有重叠，不会互相遮挡
要实现这一步，我们可以回想一下高中物理课堂中讲的带点小球。假设有限空间中有许多个带相同正电荷的小球，它们的初始位置在空间内随机，根据库伦定律这些小球之间会互相排斥，经过足够时间，小球会均匀分布在空间中的各个角落。
库仑定律公式：
image
（其中r是两者之间的距离，k是静电力常量）
受带电小球的启发，我们假设画布中每个节点都是一个小球（具有一定的质量，具有一定的正电荷），然后在每次渲染循环中计算节点之间的库仑力，计算加速度，计算速度，计算位移，最后更新画布。
这时我们会发现，画布中的节点会互相排斥，相距越来越远，最后在画布上消失了。
-
节点位置总体上趋近去画布中心
节点越跑越远最后消失在画布上，这显然不是我们想要的效果。我们的要求是节点互相分散，但是总体上是要靠近画布中心的。我们可以想象一下氢气球，氢气球向上飞，但是只要系一条绳子，就永远在我们的掌控范围内。
现在，我们假设所有节点与画布中心点都有一条看不见的弹性绳，节点距离画布中心越远，收到绳子的拉力越大。这样节点因为中心拉力的存在不至于越跑越远。
拉力（或弹力）计算公式：F=kx （k是弹性系数，x是弹性绳拉伸的长度）
-
有关联的节点通过连线相连，并且相互靠拢
上一步完成后，我们发现节点能够以画布中心为基点，向四周分散开来。但是，节点的关联关系无法体现出来，我们的要求是有关联关系的节点应该能够聚集在一起。有上一步的经验后，我们立马能想到，只要将有关联关系的节点之间加一条弹性绳，不就万事大吉了吗？
-
节点的位置最终会稳定下来
事情就真的万事大吉了吗？
不会！再次回想一下物理课堂，事情不会这么简单。能量是守恒的，这些节点受着库仑力，中心拉力，节点之间的拉力，这些力一直在对节点做工，那么节点的速度就会越来越快，最后在画布上看到的效果就是，所有节点时不时一闪而过。这怎么行，我们要减速！我们需要一个阻尼来消耗这些能量，使得节点最后能够静止下来。我们假设节点的阻尼力跟节点的速度大小成正比，方向相反，这样就行了。
阻尼力计算公式: F=-Vk （V是速度矢量,k是阻尼系数）
示例与代码
最后，力导布局算法的实现原理就叙述到这，如果有小伙伴对代码的具体实现感兴趣，欢迎去我的github仓库上阅读。
网友评论