D3

d3-quadtree ​

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

🌐 A quadtree recursively partitions two-dimensional space into squares, dividing each square into four equally-sized squares. Each distinct point exists in a unique leaf node; coincident points are represented by a linked list. Quadtrees can accelerate various spatial operations, such as the Barnes–Hut approximation for computing many-body forces, collision detection, and searching for nearby points.

四叉树(data, x, y) ​

🌐 quadtree(data, x, y)

来源 · 创建一个新的、空的四叉树，具有空的范围以及默认的x和y访问器。如果指定了data，则将指定的可迭代数据添加到四叉树中。

js
const tree = d3.quadtree(data);

这等同于：

🌐 This is equivalent to:

js
const tree = d3.quadtree().addAll(data);

如果还指定了 x 和 y，则在将指定的数据可迭代对象添加到四叉树之前，将 x 和 y 访问器设置为指定的函数，相当于：

🌐 If x and y are also specified, sets the x and y accessors to the specified functions before adding the specified iterable of data to the quadtree, equivalent to:

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

quadtree.x(x) ​

来源 · 如果指定了 x，则设置当前的 x 坐标访问器并返回四叉树。

js
const tree = d3.quadtree().x((d) => d.x);

x 访问器用于在向树中添加和移除数据时获取数据的 x 坐标。它还用于在查找时重新访问之前添加到树中的数据的坐标；因此，x 和 y 访问器必须保持一致，在相同输入下返回相同的值。

🌐 The x accessor is used to derive the x coordinate of data when adding to and removing from the tree. It is also used when finding to re-access the coordinates of data previously added to the tree; therefore, the x and y accessors must be consistent, returning the same value given the same input.

如果未指定 x，则返回当前的 x 访问器。

🌐 If x is not specified, returns the current x accessor.

js
tree.x() // (d) => d.x

x 访问器默认为：

🌐 The x accessor defaults to:

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

quadtree.y(y) ​

来源 · 如果指定了 y，则设置当前的 y 坐标访问器并返回四叉树。

js
const tree = d3.quadtree().y((d) => d.y);

y 访问器用于在向树中添加和移除数据时获取数据的 y 坐标。它还用于在查找时重新访问之前添加到树中的数据的坐标；因此，x 和 y 访问器必须保持一致，在相同输入下返回相同的值。

🌐 The y accessor is used to derive the y coordinate of data when adding to and removing from the tree. It is also used when finding to re-access the coordinates of data previously added to the tree; therefore, the x and y accessors must be consistent, returning the same value given the same input.

如果未指定y，则返回当前的y访问器。

🌐 If y is not specified, returns the current y accessor.

js
tree.y() // (d) => d.y

y 访问器默认为：

🌐 The y accessor defaults to:

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

quadtree.extent(extent) ​

来源 · 如果指定了 extent，则将四叉树扩展以覆盖 指定的点 [[x0, y0], [x1, y1]] 并返回四叉树。

js
const tree = d3.quadtree().extent([[0, 0], [1, 1]]);

如果未指定 extent，则返回四叉树当前的范围 [[x0, y0], [x1, y1]]，其中 x0 和 y0 是包含的下界，x1 和 y1 是包含的上界，如果四叉树没有范围，则返回未定义。

🌐 If extent is not specified, returns the quadtree’s current extent [[x0, y0], [x1, y1]], where x0 and y0 are the inclusive lower bounds and x1 and y1 are the inclusive upper bounds, or undefined if the quadtree has no extent.

js
tree.extent() // [[0, 0], [2, 2]]

也可以通过调用 quadtree.cover 或 quadtree.add 来扩展范围。

🌐 The extent may also be expanded by calling quadtree.cover or quadtree.add.

quadtree.cover(x, y) ​

来源 · 扩展四叉树以覆盖指定点 ⟨x,y⟩，并返回该四叉树。

js
const tree = d3.quadtree().cover(0, 0).cover(1, 1);

如果四叉树的范围已经覆盖指定点，则此方法不执行任何操作。如果四叉树已有范围，则该范围会反复加倍以覆盖指定点，并根据需要封装根节点；如果四叉树为空，范围将初始化为范围[[⌊x⌋, ⌊y⌋], [⌈x⌉, ⌈y⌉]]。（需要进行取整，以便在范围以后加倍时，现有象限的边界不会因浮点误差而发生变化。）

🌐 If the quadtree’s extent already covers the specified point, this method does nothing. If the quadtree has an extent, the extent is repeatedly doubled to cover the specified point, wrapping the root node as necessary; if the quadtree is empty, the extent is initialized to the extent [[⌊x⌋, ⌊y⌋], [⌈x⌉, ⌈y⌉]]. (Rounding is necessary such that if the extent is later doubled, the boundaries of existing quadrants do not change due to floating point error.)

quadtree.add(datum) ​

Source · 将指定的 datum 添加到四叉树中，使用当前的 x 和 y 访问器推导其坐标 ⟨x,y⟩，并返回四叉树。

js
const tree = d3.quadtree().add([0, 0]);

如果新点在四叉树当前的范围之外，四叉树会自动扩展以覆盖新点。

🌐 If the new point is outside the current extent of the quadtree, the quadtree is automatically expanded to cover the new point.

quadtree.addAll(data) ​

来源 · 将指定的可迭代 data 添加到四叉树中，使用当前的 x 和 y 访问器获取每个元素的坐标 ⟨x,y⟩，并返回此四叉树。

js
const tree = d3.quadtree().addAll([[0, 0], [1, 2]]);

这大致等同于重复调用 quadtree.add：

🌐 This is approximately equivalent to calling quadtree.add repeatedly:

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

然而，这种方法会产生一个更紧凑的四叉树，因为在添加数据之前，先计算了数据的范围。

🌐 However, this method results in a more compact quadtree because the extent of the data is computed first before adding the data.

quadtree.remove(datum) ​

来源 · 从四叉树中移除指定的 datum，使用当前的 x 和 y 访问器推导其坐标 ⟨x,y⟩，并返回四叉树。

js
tree.remove(data[0]);

如果在此四叉树中不存在指定的 datum（通过与 datum 的严格相等性确定，并且与计算的位置无关），此方法不会执行任何操作。

🌐 If the specified datum does not exist in this quadtree (as determined by strict equality with datum, and independent of the computed position), this method does nothing.

quadtree.removeAll(data) ​

Source · 从四叉树中移除指定的 data，使用当前的 x 和 y 访问器推导它们的坐标 ⟨x,y⟩，并返回该四叉树。

js
tree.removeAll(data);

如果在此四叉树中不存在指定的数据（通过与 datum 的严格相等性确定，并且独立于计算位置），则会被忽略。

🌐 If a specified datum does not exist in this quadtree (as determined by strict equality with datum, and independent of the computed position), it is ignored.

quadtree.copy() ​

js
const t1 = d3.quadtree(data);
const t2 = t1.copy();

来源 · 返回四叉树的副本。返回的四叉树中的所有节点都是四叉树中对应节点的完全复制；然而，四叉树中的任何数据都是通过引用共享的，而不是复制的。

四叉树.根() ​

🌐 quadtree.root()

来源 · 返回四叉树的根节点。

js
tree.root() // [{…}, empty × 2, {…}]

quadtree.data() ​

Source · 返回四叉树中所有数据的数组。

js
tree.data() // [[0, 0], [1, 2]]

四叉树.size() ​

🌐 quadtree.size()

Source · 返回四叉树中数据的总数量。

js
tree.size() // 2

quadtree.find(x, y, radius) ​

来源 · 返回最接近位置 ⟨x,y⟩ 且位于给定搜索 radius 内的数据。如果未指定 radius，则默认为无限大。

js
tree.find(0.000, 0.000) //

如果搜索区域内没有数据，则返回 undefined。

🌐 If there is no datum within the search area, returns undefined.

js
tree.find(10, 10, 1) // undefined

quadtree.visit(callback) ​

来源 · 以先序遍历的方式访问四叉树中的每个 节点，对每个节点调用指定的 callback，参数为 node、x0、y0、x1、y1，其中 node 是正在访问的节点，⟨x0, y0⟩ 是节点的下界，⟨x1, y1⟩ 是节点的上界，并返回四叉树。（假设正 x 向右，正 y 向下，这通常是 Canvas 和 SVG 中的情况，⟨x0, y0⟩ 是左上角，⟨x1, y1⟩ 是右下角；然而，坐标系是任意的，因此更严格地说应满足 x0 <= x1 且 y0 <= y1。）

如果对给定节点的 callback 返回 true，则该节点的子节点将不被访问；否则，所有子节点都将被访问。这可以用来快速访问树的某些部分，例如在使用 Barnes–Hut 近似 时。不过，请注意，子象限总是按兄弟顺序访问：左上、右上、左下、右下。在诸如 搜索 的情况下，以特定顺序访问兄弟节点可能会更快。

🌐 If the callback returns true for a given node, then the children of that node are not visited; otherwise, all child nodes are visited. This can be used to quickly visit only parts of the tree, for example when using the Barnes–Hut approximation. Note, however, that child quadrants are always visited in sibling order: top-left, top-right, bottom-left, bottom-right. In cases such as search, visiting siblings in a specific order may be faster.

例如，以下代码访问四叉树并返回矩形范围 [xmin, ymin, xmax, ymax] 内的所有节点，忽略不可能包含任何此类节点的四叉树：

🌐 As an example, the following visits the quadtree and returns all the nodes within a rectangular extent [xmin, ymin, xmax, ymax], ignoring quads that cannot possibly contain any such node:

js
function search(quadtree, xmin, ymin, xmax, ymax) {
  const results = [];
  quadtree.visit((node, x1, y1, x2, y2) => {
    if (!node.length) {
      do {
        let d = node.data;
        if (d[0] >= xmin && d[0] < xmax && d[1] >= ymin && d[1] < ymax) {
          results.push(d);
        }
      } while (node = node.next);
    }
    return x1 >= xmax || y1 >= ymax || x2 < xmin || y2 < ymin;
  });
  return results;
}

quadtree.visitAfter(callback) ​

来源 · 按后序遍历访问四叉树中的每个节点，并对每个节点调用指定的callback，传入参数node、x0、y0、x1、y1，其中node是正在访问的节点，⟨x0, y0⟩是节点的下界，⟨x1, y1⟩是上界，并返回四叉树。（假设正x方向向右，正y方向向下，如Canvas和SVG中通常那样，⟨x0, y0⟩为左上角，⟨x1, y1⟩为右下角；然而坐标系是任意的，因此更正式地表示为x0 <= x1且y0 <= y1。）返回root。

四叉树节点 ​

🌐 Quadtree nodes

四叉树的内部节点以从左到右、从上到下的顺序表示为稀疏的四元素数组：

🌐 Internal nodes of the quadtree are represented as sparse four-element arrays in left-to-right, top-to-bottom order:

  • 0 - 左上象限（如果有）。
  • 1 - 右上象限（如果有）。
  • 2 - 左下象限（如果有）。
  • 3 - 右下象限（如果有）。

如果子象限为空，则可能未定义。

🌐 A child quadrant may be undefined if it is empty.

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

🌐 Leaf nodes are represented as objects with the following properties:

  • data - 与这个点相关的数据，作为参数传递给 quadtree.add。
  • next - 此叶子节点中的下一个基准（如果有）。

length 属性可用于区分叶节点和内部节点：对于叶节点它是未定义的，对于内部节点则为 4。例如，要遍历叶节点中的所有数据：

🌐 The length property may be used to distinguish leaf nodes from internal nodes: it is undefined for leaf nodes, and 4 for internal nodes. For example, to iterate over all data in a leaf node:

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

在点位于四叉树中时，点的 x 和 y 坐标 不得被修改。要更新点的位置，请先移除该点，然后在新位置重新添加到四叉树中。或者，你可以完全丢弃现有的四叉树，从头创建一个新的四叉树；如果许多点已经移动，这种方法可能更高效。

🌐 The point’s x and y coordinates must not be modified while the point is in the quadtree. To update a point’s position, remove the point and then re-add it to the quadtree at the new position. Alternatively, you may discard the existing quadtree entirely and create a new one from scratch; this may be more efficient if many of the points have moved.