D3

d3-quadtree ​

quadtree 递归地将二维空间划分为正方形，将每个正方形划分为四个大小相等的正方形。每个不同的点都存在于一个唯一的叶子节点 node 中；重合点由链表表示。四叉树可以加速各种空间运算，例如用于计算多体力、碰撞检测和搜索邻近点的 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.

quadtree(data, x, y) ​

源代码 · 使用空的 extent 以及默认的 x 和 y 访问器创建一个新的空四叉树。如果指定了 data，则将指定的 data 可迭代对象 adds 到四叉树中。

¥Source · Creates a new, empty quadtree with an empty extent and the default x and y accessors. If data is specified, adds the specified iterable of data to the quadtree.

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) {#quadtree_x} ​

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

¥Source · If x is specified, sets the current x-coordinate accessor and returns the quadtree.

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

x 访问器用于在 adding 和 removing 从树中取出时获取数据的 x 坐标。它也用于 finding 重新访问先前添加到树中的数据的坐标；因此，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) {#quadtree_y} ​

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

¥Source · If y is specified, sets the current y-coordinate accessor and returns the quadtree.

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

y 访问器用于获取 adding 和 removing 从树中取出时数据的 y 坐标。它也用于 finding 重新访问先前添加到树中的数据的坐标；因此，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) {#quadtree_extent} ​

源代码 · 如果指定了 extreme，则将四叉树扩展至指定点 [[x0, y0], [x1, y1]] 并返回四叉树。

¥Source · If extent is specified, expands the quadtree to cover the specified points [[x0, y0], [x1, y1]] and returns the quadtree.

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

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

¥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) {#quadtree_cover} ​

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

¥Source · Expands the quadtree to cover the specified point ⟨x,y⟩, and returns the quadtree.

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

如果四叉树的范围已经覆盖指定点，则此方法不执行任何操作。如果四叉树具有范围，则范围会反复加倍以覆盖指定点，并根据需要包裹 root node；如果四叉树为空，则范围初始化为 [[⌊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) {#quadtree_add} ​

源代码 · 将指定的数据添加到四叉树，使用当前的 x 和 y 访问器获取其坐标 ⟨x,y⟩，并返回四叉树。

¥Source · Adds the specified datum to the quadtree, deriving its coordinates ⟨x,y⟩ using the current x and y accessors, and returns the quadtree.

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

如果新点位于四叉树当前 extent 之外，则四叉树将自动扩展为 cover 新点。

¥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) {#quadtree_addAll} ​

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

¥Source · Adds the specified iterable of data to the quadtree, deriving each element’s coordinates ⟨x,y⟩ using the current x and y accessors, and return this quadtree.

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) {#quadtree_remove} ​

源代码 · 从四叉树中移除指定的基准，使用当前的 x 和 y 访问器获取其坐标 ⟨x,y⟩，并返回四叉树。

¥Source · Removes the specified datum from the quadtree, deriving its coordinates ⟨x,y⟩ using the current x and y accessors, and returns the quadtree.

js
tree.remove(data[0]);

如果指定的基准不存在于此四叉树中（由与基准严格相等确定，并且与计算的位置无关），则此方法不执行任何操作。

¥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) {#quadtree_removeAll} ​

源代码 · 从四叉树中移除指定的数据，使用当前的 x 和 y 访问器获取它们的坐标 ⟨x,y⟩，并返回四叉树。

¥Source · Removes the specified data from the quadtree, deriving their coordinates ⟨x,y⟩ using the current x and y accessors, and returns the quadtree.

js
tree.removeAll(data);

如果指定的数据不存在于此四叉树中（由与数据严格相等确定，并且与计算的位置无关），则忽略该数据。

¥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() {#quadtree_copy} ​

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

源代码 · 返回四叉树的副本。返回的四叉树中的所有 nodes 都是四叉树中相应节点的相同副本；但是，四叉树中的任何数据都是通过引用共享的，而不是复制的。

¥Source · Returns a copy of the quadtree. All nodes in the returned quadtree are identical copies of the corresponding node in the quadtree; however, any data in the quadtree is shared by reference and not copied.

quadtree.root() {#quadtree_root} ​

源代码 · 返回四叉树的根 node。

¥Source · Returns the root node of the quadtree.

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

quadtree.data() {#quadtree_data} ​

源代码 · 返回四叉树中所有数据的数组。

¥Source · Returns an array of all data in the quadtree.

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

quadtree.size() {#quadtree_size} ​

源代码 · 返回四叉树中数据的总数。

¥Source · Returns the total number of data in the quadtree.

js
tree.size() // 2

quadtree.find(x, y, radius) {#quadtree_find} ​

源代码 · 返回距离位置 ⟨x,y⟩ 最近的、具有给定搜索半径的基准。如果未指定半径，则默认为无穷大。

¥Source · Returns the datum closest to the position ⟨x,y⟩ with the given search radius. If radius is not specified, it defaults to infinity.

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) {#quadtree_visit} ​

源代码 · 以前序遍历的方式访问四叉树中的每个 node，对每个节点调用指定的回调函数，参数分别为 node、x0、y0、x1、y1，其中 node 是正在访问的节点，⟨x0, y0⟩ 是节点的下界，⟨x1, y1⟩ 是节点的上界，并返回四叉树。（假设正 x 向右，正 y 向下，这在 Canvas 和 SVG 中很常见，⟨x0, y0⟩ 表示左上角，⟨x1, y1⟩ 表示右下角；但是，坐标系是任意的，因此更正式的表示方式是 x0 <= x1 且 y0 <= y1。）

¥Source · Visits each node in the quadtree in pre-order traversal, invoking the specified callback with arguments node, x0, y0, x1, y1 for each node, where node is the node being visited, ⟨x0, y0⟩ are the lower bounds of the node, and ⟨x1, y1⟩ are the upper bounds, and returns the quadtree. (Assuming that positive x is right and positive y is down, as is typically the case in Canvas and SVG, ⟨x0, y0⟩ is the top-left corner and ⟨x1, y1⟩ is the lower-right corner; however, the coordinate system is arbitrary, so more formally x0 <= x1 and y0 <= y1.)

如果回调函数对给定节点返回 true，则不会访问该节点的子节点；否则，访问所有子节点。这可用于快速访问树的某些部分，例如在使用 Barnes-Hut 近似 时。但请注意，子象限始终按同级顺序访问：左上角、右上角、左下角、右下角。在诸如 search 的情况下，按特定顺序访问兄弟元素可能会更快。

¥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) {#quadtree_visitAfter} ​

源代码 · 以后序遍历的方式访问四叉树中的每个 node，对每个节点调用指定的回调函数，参数分别为 node、x0、y0、x1、y1，其中 node 是正在访问的节点，⟨x0, y0⟩ 是节点的下界，⟨x1, y1⟩ 是节点的上界，并返回四叉树。（假设正 x 向右，正 y 向下，这在 Canvas 和 SVG 中很常见，⟨x0, y0⟩ 表示左上角，⟨x1, y1⟩ 表示右下角；但是，坐标系是任意的，因此更正式的表示方式是 x0 <= x1 且 y0 <= y1。）返回根。

¥Source · Visits each node in the quadtree in post-order traversal, invoking the specified callback with arguments node, x0, y0, x1, y1 for each node, where node is the node being visited, ⟨x0, y0⟩ are the lower bounds of the node, and ⟨x1, y1⟩ are the upper bounds, and returns the quadtree. (Assuming that positive x is right and positive y is down, as is typically the case in Canvas and SVG, ⟨x0, y0⟩ is the top-left corner and ⟨x1, y1⟩ is the lower-right corner; however, the coordinate system is arbitrary, so more formally x0 <= x1 and y0 <= y1.) Returns root.

四叉树节点 ​

¥Quadtree nodes

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

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

  • 0 - 左上象限（如果有）。

    ¥0 - the top-left quadrant, if any.

  • 1 - 右上象限（如果有）。

    ¥1 - the top-right quadrant, if any.

  • 2 - 左下象限（如果有）。

    ¥2 - the bottom-left quadrant, if any.

  • 3 - 右下象限（如果有）。

    ¥3 - the bottom-right quadrant, if any.

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

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

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

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

  • data - 与此点关联的数据，传递给 quadtree.add。

    ¥data - the data associated with this point, as passed to quadtree.add.

  • next - 此叶子节点中的下一个基准（如果有）。

    ¥next - the next datum in this leaf, if any.

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 坐标。要更新某个点的位置，请先 remove 该点，然后将其重新 add 到四叉树的新位置。或者，你可以完全丢弃现有的四叉树，并从头创建一个新的四叉树；如果许多点都移动了，这可能会更有效。

¥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.