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