背景
被上图（12.3M 加载较慢）炫酷的视觉效果及强大的数据展示能力所吸引，核心在于三维的力学布局算法以及THREE的荧光效果。THREE部分相对比较容易，瓶颈在三维的布局算法上，一来没找到现成的可以直接搬的轮子（有大神将布局算法封装进了shader从而将节点的坐标计算交给GPU以提升性能，然而在易用性和可复用度上有一定的欠缺），二来有二维的力学图源码可以参考，就想将二维的力学图布局算法引申到三维，在学习算法的同时造个不大不小的轮子。
本文仅介绍算法部分。
算法简介
对适用于一般网状结构数据绘图的算法来说，力导向算法是一种常被应用的方法。我们可以把整张网络想象成一个虚拟的物理系统。系统中的每个节点都可以看成是一个带有一定能量的放电粒子，粒子与粒子之间存在某种库仑斥力，使它们两两相互排斥。同时，有些粒子间被一些“边”所牵连，这些 边产生类似弹簧的胡克引力，又紧紧牵制着“边”两端的粒子。在粒子间斥力和引力的不断作用下，粒子们从随机无序的初态不断发生位移，逐渐趋于平衡有序的终 态。同时整个物理系统的能量也在不断消耗，经过数次迭代后，粒子之间几乎不再发生相对位移，整个系统达到一种稳定平衡的状态，即能量趋于零。
二维力学图算法解析（来自d3.v3）
- 1、计算节点、出度、入度、度。
- 2、初始化位置坐标
- 2.1、d3采用输入范围，节点坐标在该范围内随机的方式
- 3、初始化能量系数
- 3.1 默认值为1 每次迭代 * 0.99 小于0.05后停止迭代
- 3.2 在没有内部修正的情况下 这就意味着对于所有的数据都将在迭代298次后停止计算，这个Magic Number肯定无法满足所有的数据，对于一些庞大的数据或者很小的数据，需要人工进行修正。
- 4、初始化向心力、弹簧力、库仑力
- 4.1、向心力：一个令所有节点都向中心靠拢的力、依赖输入，（距离引力中心的距离*能量系数*引力） 时间复杂度On
- 4.2、弹簧力：令相互链接的节点相互靠近的力，每个节点的弹簧力默认为该节点的度。时间复杂度 On，例如A节点的度为5、B节点的度为1，A和B相连。
- 4.2.1、A节点的移动距离为AB两点之间的距离*能量系数*B节点的弹簧力/（B节点的弹簧力+A节点的弹簧力）。
- 4.2.2、B节点的移动距离为AB两点之间的距离*能量系数*A节点的弹簧力/（B节点的弹簧力+A节点的弹簧力）。
- 4.3、库仑力：令所有节点相互排斥的力，依赖输入默认电荷数-30 算法与物理学库仑力算法一致。时间复杂度On2（二维层次依赖四叉树优化、三维层次依赖八叉树优化原理一致）。
- 5、开始迭代计算
- 5.1、所有节点根据向心力向中心聚拢
- 5.2、各节点根据自身引力相互靠近
- 5.3、所有点根据库仑力相互排斥
- 5.4、能量系数衰减
- 5.5、判断能量系数是否衰减完毕、衰减完毕结迭代
- 6、布局完成
三维引申
步骤1、2、3皆为常规操作二维和三维下并无区别，照抄便是。
步骤4上对于弹簧力和向心力的计算，仅需将距离计算公式从 Math.sqrt((dx*dx+dy*dy))引申为Math.sqrt((dx*dx+dy*dy+dz*dz))即可，中间需要对常量做一些微小的调整。
步骤4上对于库仑力的计算需要把二维空间的基于四叉树的碰撞检测引申为三维空间的基于八叉树的碰撞检测详情请戳还没写，回头补。
算法抽取与封装
由于基于v3版本的d3还没有模块化只能将d3.force下所有的方法抽取出来单独封装，event和drag部分依赖d3的全局模块这部分需要重新实现。
结果
参考 & 引用
https://medium.com/@sxywu/understanding-the-force-ef1237017d5
https://stackoverflow.com/questions/12917037/what-algorithms-does-d3-js-use-for-the-force-directed-graph
http://ialab.it.monash.edu/webcola/
https://baike.baidu.com/item/%E5%8A%9B%E5%AF%BC%E5%90%91%E7%AE%97%E6%B3%95/3373100
https://www.jianshu.com/p/85c4bc006d88
https://github.com/vasturiano/3d-force-graph
https://unpkg.com/3d-force-graph@1.10.1/dist/3d-force-graph.js
https://github.com/jaredmcqueen/analytics