d3-quadtree

Fork ↗︎

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

quadtree(data, x, y)

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

const tree = d3.quadtree(data);

这等效于

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

如果也指定了 x 和 y，则在将指定的可迭代数据添加到四叉树之前，将 x 和 y 访问器设置为指定的函数，这等效于

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

quadtree.x(x)

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

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

x 访问器用于在 添加 到和从树中 删除 数据时派生数据的 x 坐标。它也用于在 查找 时重新访问先前添加到树中的数据的坐标；因此，x 和 y 访问器必须一致，在给定相同输入时返回相同的值。

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

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

x 访问器默认为

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

quadtree.y(y)

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

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

y 访问器用于在 添加 到和从树中 删除 数据时派生数据的 y 坐标。它也用于在 查找 时重新访问先前添加到树中的数据的坐标；因此，x 和 y 访问器必须一致，在给定相同输入时返回相同的值。

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

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

y 访问器默认为

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

quadtree.extent(extent)

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

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

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

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

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

quadtree.cover(x, y)

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

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

如果四叉树的范围已经覆盖了指定的点，则此方法不会执行任何操作。如果四叉树有范围，则范围会不断加倍以覆盖指定的点，必要时包裹 根 节点；如果四叉树为空，则范围将初始化为范围 [[⌊x⌋, ⌊y⌋], [⌈x⌉, ⌈y⌉]]。（舍入是必要的，这样如果范围以后加倍，由于浮点数错误，现有象限的边界不会改变。）

quadtree.add(datum)

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

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

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

quadtree.addAll(data)

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

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

这与重复调用 quadtree.add 基本上是等效的

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

但是，此方法会生成更紧凑的四叉树，因为 data 的范围是在添加数据之前计算的。

quadtree.remove(datum)

源代码 · 从四叉树中删除指定的 datum，使用当前的 x 和 y 访问器派生其坐标 ⟨x,y⟩，并返回四叉树。

tree.remove(data[0]);

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

quadtree.removeAll(data)

源代码 · 从四叉树中删除指定的 data，使用当前的 x 和 y 访问器派生它们的坐标 ⟨x,y⟩，并返回四叉树。

tree.removeAll(data);

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

quadtree.copy()

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

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

quadtree.root()

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

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

quadtree.data()

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

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

quadtree.size()

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

tree.size() // 2

quadtree.find(x, y, radius)

源代码 · 返回距离位置 ⟨x,y⟩ 最近的 datum，并使用给定的搜索 radius。如果未指定 radius，则默认为无穷大。

tree.find(0.000, 0.000) // 

如果没有 datum 在搜索区域内，则返回 undefined。

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

quadtree.visit(callback)

源代码 · 以先序遍历的方式访问四叉树中的每个节点，并为每个节点调用指定的回调函数，传入参数节点、x0、y0、x1、y1，其中节点是正在访问的节点，⟨x0, y0⟩ 是节点的下边界，⟨x1, y1⟩ 是节点的上边界，并返回四叉树。 (假设正x 向右，正y 向下，如 Canvas 和 SVG 中通常那样，⟨x0, y0⟩ 是左上角，⟨x1, y1⟩ 是右下角；然而，坐标系是任意的，所以更正式地说，x0 <= x1 且 y0 <= y1。)

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

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

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;
}

四叉树.visitAfter(回调)

源代码 · 以后序遍历的方式访问四叉树中的每个节点，并为每个节点调用指定的回调函数，传入参数节点、x0、y0、x1、y1，其中节点是正在访问的节点，⟨x0, y0⟩ 是节点的下边界，⟨x1, y1⟩ 是节点的上边界，并返回四叉树。 (假设正x 向右，正y 向下，如 Canvas 和 SVG 中通常那样，⟨x0, y0⟩ 是左上角，⟨x1, y1⟩ 是右下角；然而，坐标系是任意的，所以更正式地说，x0 <= x1 且 y0 <= y1。)

四叉树节点

四叉树的内部节点表示为稀疏的四元素数组，按照从左到右、从上到下的顺序排列

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

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

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

• data - 与此点关联的数据，如传递给 四叉树.add。
• next - 此叶节点中的下一个数据，如果有的话。

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

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

在点位于四叉树中时，必须不能修改点的 x 和 y 坐标。要更新点的坐标，请删除 点，然后将其重新添加 到四叉树中的新坐标位置。或者，您可以完全丢弃现有四叉树并从头开始创建一个新的四叉树；如果许多点已移动，这可能更有效。