d3-quadtree

四叉树通过递归将二维空间分为正方形，将每个正方形划分为四个大小相同的正方形。每个不同的点存在于一个唯一的叶节点中；重合的点由一个链表表示。四叉树可以加速各种空间操作，如用于计算many-body forces（多体力）的Barnes–Hut approximation，碰撞检测及搜索附近的点。

Installing

如果你使用npm，请键入npm install d3-quadtree。否则，请下载最新版本。你也可以直接从d3js.org加载，作为standalone library（独立库）或D3 4.0的一部分来使用。支持AMD，CommonJS和vanilla环境。在vanilla环境下，会输出一个全局的d3：

<script src="https://d3js.org/d3-quadtree.v1.min.js"></script>
<script>

var quadtree = d3.quadtree();

</script>

API Reference

d3.quadtree([data[, x, y]])

生成一个新的范围为空、默认x-accessor和y-accessor的空四叉树，如果指定了data，则将data数组添加至四叉树中。相当于：

var tree = d3.quadtree()
    .addAll(data);

如果同时指定了x和y，则在将data数组添加至四叉树前设置x-accessor和y-accessor为给定函数，相当于：

var tree = d3.quadtree()
    .x(x)
    .y(y)
    .addAll(data);

quadtree.x([x])

如果指定了x，则设置当前横坐标accessor并返回该四叉树。如果不指定x，则返回当前的x-accessor，默认为：

function x(d) {
  return d[0];
}

x-accessor用于在向树中添加或移除数据时导出数据的横坐标。它也可以用来查找之前添加到树的数据的坐标；因此，x-accessor和y-accessor必须一致，返回相同的值。

quadtree.y([y])

如果指定了y，则设置当前纵坐标accessor并返回该四叉树。如果不指定y，则返回当前的y-accessor，默认为：

function y(d) {
  return d[1];
}

y-accessor用于在向树中添加或移除数据时导出数据的纵坐标。它也可以用来查找之前添加到树的数据的坐标；因此，y-accessor和y-accessor必须一致，返回相同的值。

quadtree.extent([extent])

如果指定extent，则扩展四叉树，以覆盖给定点[ [ x0，y0 ]、[ x1，y1 ] ]。如果不指定extent，则返回四叉树当前的范围[[x0, y0], [x1, y1]]，其中x0和y0为下界（包含），x1和y1为上界（包含），如果没有范围则返回undefined。范围也可以通过quadtree.cover 或quadtree.add。

quadtree.cover(x, y)

扩展四叉树以覆盖给定点⟨X，Y⟩并返回该树。如果四叉树的范围已经覆盖了指定的点，此方法将什么也不做。如果树有范围，则范围将不断翻倍以覆盖给定点，必要时会涵盖根节点；如果树为空，则范围将初始化为[[⌊x⌋, ⌊y⌋], [⌈x⌉, ⌈y⌉]]。（如果之后范围扩大一倍则四舍五入是必要的，现有象限的边界不会因浮点误差而改变）。

quadtree.add(datum)

向四叉树中添加给定datum，使用当前x-accessor和y-accessor获取坐标⟨X，Y⟩，并返回该树。如果新的点超出了四叉树的当前范围，四叉树将自动扩展以覆盖新的点。

quadtree.addAll(data)

将给定data数组添加至四叉树，使用当前x-accessor和y-accessor导出每个元素的坐标⟨X，Y⟩，并返回该树。大致相当于重复调用quadtree.add。

for (var i = 0, n = data.length; i < n; ++i) {
  quadtree.add(data[i]);
}

然而，这种方法会导致一个更紧凑的四叉树，因为在添加data之前会先计算data的范围。

quadtree.remove(datum)

从四叉树中移除给定datum，使用当前x-accessor和y-accessor获取坐标⟨X，Y⟩，并返回该树。如果给定的datum不在四叉树中，此方法将什么也不做。

quadtree.removeAll(data)

…

quadtree.copy()

返回四叉树的一个副本。所有返回四叉树中的所有节点都是原四叉树中对应节点的相同副本；然而，四叉树中的任何数据都是通过引用共享的而不是复制。

quadtree.root()

返回四叉树的根节点。

quadtree.data()

返回一个包含四叉树中所有数据的数组。

quadtree.size()

返回四叉树的数据总数。

quadtree.find(x, y[, radius])

返回用给定的radius查找到的离位置position ⟨x,y⟩最近的数据集。如果不指定radius，默认为无穷大。如果搜索区域中没有数据，则返回undefined。

quadtree.visit(callback)

以前序遍历方式访问树中的每一个节点，将节点的node, x0, y0, x1, y1作为参数传入给定callback中，node即为访问的节点本身，⟨x0，y0⟩为节点的下界，⟨x1，y1⟩为上界，然后返回该四叉树。（假设x的正方向向右，y的正方向向下，就像Canvas和SVG一样，⟨x0, y0⟩是左上角，⟨x1, y1⟩是右下角；然而坐标系是任意的，因此更正式的表述应该是x0 <= x1，y0 <= y1）

如果callback对给定节点返回true，则不会访问该节点的子节点；否则将访问其所有子节点。这样可以快速访问树的一些部分，如当使用Barnes–Hut approximation时。不过请注意：该child quadrants（子象限）总是以同级顺序访问的：左上、右上、左下、右下。在搜索等情况下，按特定顺序访问兄弟节点可能更快。

quadtree.visitAfter(callback)

以后序遍历方式访问树中的每一个节点，将节点的node, x0, y0, x1, y1作为参数传入给定callback中，node为访问的节点本身，⟨x0，y0⟩为节点的下界，⟨x1，y1⟩为上界，然后返回该四叉树。（假设x的正方向向右，y的正方向向下，就像Canvas和SVG一样，⟨x0, y0⟩是左上角，⟨x1, y1⟩是右下角；然而坐标系是任意的，因此更正式的表述应该是x0 <= x1，y0 <= y1）返回root。

Nodes

四叉树的内部节点按照从左向右、从上到下的次序分别表示为四个元素数组：

  • 0- 左上象限，如果有的话
  • 1- 右上象限，如果有的话
  • 2- 左下象限，如果有的话
  • 3- 右下象限，如果有的话

当子象限为空时可能为undefined。

叶节点为具有以下属性的对象：

  • data- 该点的数据，即传入quadtree.add的（如果有的话）
  • next- 此叶节点的下一datum（如果有的话）

length属性可用于区分叶节点和内部节点：叶节点为undefined，内部结点为4。例如，便利叶节点中的所有数据：

if (!node.length) do console.log(node.data); while (node = node.next);

当点在四叉树中时，其x和y坐标不能修改。要更新一个点的位置，先移除该点，然后重新添加到树中。或者，你可以完全抛弃现有的四叉树，从头创建一个新的，如果有多点需要移动，这可能会更有效。

results matching ""

    No results matching ""