四叉树

> [Wiki](Home) ▸ [[API--中文手册]] ▸ [[几何]] ▸ **四叉树** * 如发现翻译不当或有其他问题可以通过以下方式联系译者: * 邮箱：zhang_tianxu@sina.com * QQ群：[D3数据可视化](http://jq.qq.com/?_wv=1027&k=ZGcqYF)205076374，[大数据可视化](http://jq.qq.com/?_wv=1027&k=S8wGMe)436442115 四叉树是一个二维空间递归细分。它使用了平分划分实现，将每一个块平分成了四个同等大小的方块。每个点存在于一个唯一的节点中；如果同一位置包含多个点，那么这多个点中的其中一些点将存储于内部节点，而非叶子结点。四叉树可用于加速各种空间操作，例如计算正多边形的体积的Barnes-Hut近似算法或者冲突检验。 # d3.geom.quadtree() 创建一个新的四叉树工厂使用默认的x访问器，y访问器及范围。返回的函数可以用来从带有工厂的配置的数据创建任意个四叉树。 # quadtree(points) 为指定的点数据数组构造一个新的四叉树，返回新四叉树的根结点。每一个点的X和Y坐标使用当前x及y访问器函数确定。通过增量地添加点来建立四叉树，指定的点数组可以为空，之后点可以随后添加到返回的根节点；在这种情况下，你必须指定四叉树的范围。 四叉树的每一个结点都有多个属性。 nodes——按顺序排列四个子结点的稀疏数组：top-left, top-right, bottom-left, bottom-right。 leaf ——内部结点与叶子结点的布尔表示。 point ——这个点关联的节点，如果有的话（可能适用于内部或叶节点）。 X——关联点的x坐标，如果有的话。 Y——关联点的y坐标，如果有的话。 返回的根结点也可定义了增加方法add 或者访问方法visit 。 # root.add(point) 为四叉树增加指定的新点。 # root.visit(callback) 访问四叉树的每个结点，利用参数 {node, x1,y1, x2, y2} 为每个结点调用指定的回调函数，结点按先序遍历。若调用给定结点的回调函数返回值为真，则表示不能访问此结点的子结点，否则表示所有子结点均能被访问。 # quadtree.x([x]) 若设置了x参数，则为四叉树设置横坐标访问器，并返回四叉树。反之，则返回当前默认的横坐标访问器。 function(d) { return d[0]; } 对每一个加入到四叉树中的点，不管是初始化构造的还是后面新增的，都可以通过参数 {d, i}调用x访问器，d表示当前点，i表示所有点数组的索引。X访问器必须返回一个数值，表明给定点的x坐标。如果需要得花，x访问器也可以被定义为一个常数，而非一个函数。 # quadtree.y([y]) 若设置了y参数，则为四叉树设置纵坐标访问器，并返回四叉树。反之，则返回当前默认的纵坐标访问器 function(d) { return d[1]; } 对每一个加入到四叉树中的点，不管是初始化构造的还是后面新增的，都可以通过参数 {d, i}调用y访问器，d表示当前点，i表示所有点数组的索引。y访问器必须返回一个数值，表明给定点的y坐标。如果需要得花，y访问器也可以被定义为一个常数，而非一个函数。 # quadtree.extent([extent]) 若设置了extent参数，则为四叉树设置范围，然后返回四叉树。反之，则返回当前范围，其默认为空。 当范围为空时，范围将会自动扫描输入点数组自动计算并传到四叉树构造器。否则，范围必须用二维数组[[x0, y0], [x1,y1]]明确定义，x0和y0为范围的下限，x1和y1为范围的上限。当从最初为空的节点慢慢构建一个四叉树，设置范围是非常必要的。 曼妙征程译20141127咕噜校对2014-12-8 20:24:31