d3-force 力导图源码解读与原理分析【二：四叉树（一）】

pepperwang 发布于2019-08-20 15:32 / 1889人阅读

摘要：我们在上文源码解析发现版的节点碰撞采用四叉树进行了优化。那么版本的力导图具体和版的有何不同点呢，四叉树又如何优化碰撞校验的呢原文链接被重命名为。性能的提高归功于的新的四叉树。

我们在上文源码解析发现v4版的节点碰撞采用四叉树进行了优化。
那么V4版本的力导图具体和v3版的有何不同点呢，四叉树又如何优化碰撞校验的呢？

v3-force VS v4-force

https://github.com/xswei/D3-V... (原文链接)

d3.layout.force被重命名为d3.forceSimulation。新的力导向仿真使用速度Verlet算法而不是位置Verlet算法，即追踪节点的位置(node.x，node.y)和速度(node.vx,node.vy)而不是之前的位置(node.px，node.py)。

现在的力导向仿真可以很好的扩展：你可以指定哪些受力。这个方法使得作品更柔和。新的力导向也更灵活：可以为每个节点和连接设置参数。可以指定多带带的x和y来代替force.gravity。新的link force代替force.linkStrength并且更稳定。新的many-body force代替原有的force.charge并且支持最小距离参数。性能的提高归功于4.0的新的四叉树。4.0提供了冲突解决和向中对齐的方法。

新的力导向仿真避免不确定性，比如在3.x中结点的初始位置是随机的，如果结点没有初始位置，则被放置在一个类似叶序图案上。

力导向仿真提供了一些方法来控制结点"过热"(根本停不下来那种),比如simulation.alphaMin和simulation.alphaDecay和内部计时器。调用simulation.alpha时对内部计时器没有影响，它由simulation.stop和simulatonrestart独立控制。与3.x一样，4.0使用simulation.tick来打点。force.frition由simulation.velocityDecay代替。新的simulation.alphaTarget方法允许设置期望的仿真"温度"(什么时候停下来)。这样可以使仿真重新开始然后再次冷却，提高了交互过程中的稳定性。

force布局不再依赖拖拽行为，因为你可以直接创建一个可拖动的力导向布局。设置node.fx和node.fy来修正节点的位置。simulation.find方法替代了泰森多边形的SVG叠加，以找到最近节点的引用。

四叉树是什么鬼

四叉树（quad-tree）是一种数据结构，是一种每个节点最多有四个子树的数据结构。

四叉树的定义是：它的每个节点下至多可以有四个子节点，通常把一部分二维空间细分为四个象限或区域并把该区域里的相关信息存入到四叉树节点中。

四叉树可以用来做什么

用来在数据库中放置和定位文件（称作记录或键）

2D空间碰撞校验

地理空间划分常用于GIS查询

图像处理

基于四叉树2D空间碰撞校验

d3.v4里的force就是使用到四叉树的碰撞校验。该方法也经常被游戏领域使用到。

我们来观察一下：每个实体根据他在2D空间的位置而被放入这些子节点（正方形区域）中的一个里。任何不能正好在一个节点区域内的物体会被放在父节点。完全处于一个子区域内的点是不会与另一个区域的点碰撞的，这使得我们在做碰撞校验或者获取相邻的节点时成倍的减少校验计算。

以上图为例，存储方式有多种。存储的最大差异在意当实体坐标位于区域边上的时候，该实体应存储在哪个位置。

存储方法一：

那么所有实体只能与以自己为跟节点的树的所有节点上的实体才有可能发生碰撞。

存储方法二：

同理，实体只能与自身所在象限的其他实体发生碰撞（这里暂时先不考虑碰撞半径）。

d3-quadtree 的四叉树

API地址：https://github.com/d3/d3-quad...

中文地址：https://github.com/Leannechn/...

代码试运行地址：https://runkit.com/npm/d3-qua...

d3-quadtree采用的第二种存储方式，为了避免浮点计算的精确度问题，最小区域单位为1
创建只有一个实体的四叉树

// 测试代码二
var d3Quadtree = require("d3-quadtree")
var data = [[1.1,1.2]];
var tree = d3Quadtree.quadtree().addAll(data);

这里我们要说明几个变量和函数名的含义

Quadtree.extend() // [[x0,y0],[x1,y1]]四叉树的边界，即矩形的左上顶点的坐标，与右下顶点坐标
Quadtree.x0 // 正方形区域左上顶点坐标x
Quadtree.y0 // 正方形区域左上顶点坐标y
Quadtree.x1 // 正方形区域右下顶点坐标x
Quadtree.y1 // 正方形区域右下顶点坐标y

                                        root
                             /                  
         第一象限：_root[0]                      第三象限：_root[2]==> [2,6]
         /                   
        /

第一象限：_root0-->[1.1,1.2] 第二象限：_root0-->[3,1]

在理解了四叉树的存储之后，我们在看d3-quadtree的API。是否一目了然了呢！
下文我们来看看d3-quadtree的源码。

1.1

云服务器 GPU云服务器力导图四叉树平衡二叉树实现二叉树

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/82325.html

d3-force 力导图 源码解读与原理分析【一】

摘要：设置力导图点阵中心碰撞其他引用模块构造常量函数微小晃动随机数四叉树模块设置力导图点阵中心此处代码使用的是单例对象模式，读者要注意，切勿与类对象理解混了。首先先推荐一下某呆翻译的d3-force的中文文档：https://github.com/xswei/D3-V... 。在我们解读源码前还请读者先熟悉一下force相关的API,以及es6语法 . 如有分析不当之处还请留言指出，谢谢...

luckyyulin 2019-08-20 14:48 评论0 收藏0
高仿 ios 相册地图功能

摘要：本篇文章已授权微信公众号郭霖独家发布老规矩先上图最近没有什么时间，后面项目再补上详细说明百度地图新增点聚合功能。百度地图是把整个地球是按照一个平面来展开，并且通过墨卡托投影投射到坐标轴上面。上图很明显墨卡托投影把整张世界地图投影成。本篇文章已授权微信公众号 guolin_blog （郭霖）独家发布老规矩先上图最近没有什么时间，后面项目再补上详细说明 showImg(https:/...

pakolagij 2019-08-15 10:56 评论0 收藏0
数据结构与算法--四叉树（javascript实现）

摘要：最近想要研究研究地形的渲染，然后就想起了四叉树，在网上看了一篇相关的文章，准备拿实现一下备用。四叉树的定义是它的每个节点下至多可以有四个子节点，通常把一部分二维空间细分为四个象限或区域并把该区域里的相关信息存入到四叉树节点中。最近想要研究研究webgl地形的渲染，然后就想起了四叉树，在网上看了一篇相关的文章，准备拿javascript实现一下备用。四叉树原理（这部分就直...

xbynet 2019-08-21 12:17 评论0 收藏0
Java TreeMap 源码解析

摘要：源码剖析由于红黑树的操作我这里不说了，所以这里基本上也就没什么源码可以讲了，因为这里面重要的算法都是，这里的是指，他们是算法导论的作者，也就是说里面算法都是参照算法导论的伪代码。因为红黑树是平衡的二叉搜索树，所以其包含操作的时间复杂度都为。本文章首发于个人博客，鉴于sf博客样式具有赏心悦目的美感，遂发表于此，供大家学习、批评。本文还在不断更新中，最新版可移至个人博客。? 继上篇文章...

rubyshen 2019-08-14 12:28 评论0 收藏0