d3-quadtree
四叉树递归地将二维空间划分为正方形，将每个正方形划分为四个大小相等的子正方形。每个独立点存在于一个唯一的叶节点；重合点由链表表示。四叉树可以加速各种空间操作，例如用于计算多体力的 Barnes–Hut 近似法、碰撞检测以及搜索附近点。
安装
如果您使用 npm，请运行 npm install d3-quadtree。您也可以在 GitHub 上下载最新版本。对于现代浏览器中的原生 HTML，请从 Skypak 导入 d3-quadtree。
<script type="module">
import {quadtree} from "https://cdn.skypack.dev/d3-quadtree@3";
const tree = quadtree();
</script>
对于旧版环境，您可以从基于 npm 的 CDN（如 jsDelivr）加载 d3-quadtree 的 UMD 包；它会导出一个全局变量 d3。
<script src="https://cdn.jsdelivr.net.cn/npm/d3-quadtree@3"></script>
<script>
const tree = d3.quadtree();
</script>
API 参考
# d3.quadtree([data[, x, y]]) <>
创建一个新的、空的四叉树，其 范围 为空，并使用默认的 x 轴 和 y 轴 访问器。如果指定了 data，则将指定的数据数组 添加 到四叉树中。这等同于
const tree = d3.quadtree()
.addAll(data);
如果还指定了 x 和 y，则在将指定的数据数组添加到四叉树之前，将 x 轴 和 y 轴 访问器设置为指定函数，这等同于
const tree = d3.quadtree()
.x(x)
.y(y)
.addAll(data);
如果指定了 x，则设置当前的 x 坐标访问器并返回四叉树。如果未指定 x，则返回当前的 x 访问器，默认情况为
function x(d) {
return d[0];
}
x 访问器用于在 添加 到树中和 从中移除 数据时派生数据的 x 坐标。在 查找 时，它也用于重新访问先前添加到树中的数据的坐标；因此，x 和 y 访问器必须一致，给定相同的输入应返回相同的值。
如果指定了 y，则设置当前的 y 坐标访问器并返回四叉树。如果未指定 y，则返回当前的 y 访问器，默认情况为
function y(d) {
return d[1];
}
y 访问器用于在 添加 到树中和 从中移除 数据时派生数据的 y 坐标。在 查找 时，它也用于重新访问先前添加到树中的数据的坐标；因此，x 和 y 访问器必须一致，给定相同的输入应返回相同的值。
# quadtree.extent([extent]) <>
如果指定了 extent，则将四叉树扩展为 覆盖 指定的点 [[x0, y0], [x1, y1]] 并返回四叉树。如果未指定 extent，则返回四叉树的当前范围 [[x0, y0], [x1, y1]]，其中 x0 和 y0 是包含的下界，x1 和 y1 是包含的上界，或者在四叉树没有范围时返回 undefined。也可以通过调用 quadtree.cover 或 quadtree.add 来扩展范围。
将四叉树扩展为覆盖指定点 ⟨x,y⟩，并返回四叉树。如果四叉树的范围已覆盖指定点，则此方法不执行任何操作。如果四叉树有范围，则范围将重复加倍以覆盖指定点，并根据需要包装 根 节点；如果四叉树为空，则范围将初始化为 [[⌊x⌋, ⌊y⌋], [⌈x⌉, ⌈y⌉]]。（舍入是必需的，以便如果范围后来加倍，现有象限的边界不会因浮点误差而改变。）
使用当前的 x 轴 和 y 轴 访问器派生其坐标 ⟨x,y⟩，将指定的 datum 添加到四叉树，并返回四叉树。如果新点超出四叉树的当前 范围，四叉树将自动扩展以 覆盖 新点。
使用当前的 x 轴 和 y 轴 访问器派生每个元素的坐标 ⟨x,y⟩，将指定的 data 数组添加到四叉树，并返回此四叉树。这大致相当于重复调用 quadtree.add。
for (let i = 0, n = data.length; i < n; ++i) {
quadtree.add(data[i]);
}
但是，此方法可以生成更紧凑的四叉树，因为在添加数据之前会先计算 data 的范围。
使用当前的 x 轴 和 y 轴 访问器派生其坐标 ⟨x,y⟩，从四叉树中移除指定的 datum，并返回四叉树。如果指定的 datum 不存在于此四叉树中，则此方法不执行任何操作。
使用当前的 x 轴 和 y 轴 访问器派生其坐标 ⟨x,y⟩，从四叉树中移除指定的 data，并返回四叉树。如果指定的 datum 不存在于此四叉树中，则会被忽略。
# quadtree.copy()
返回四叉树的副本。返回的四叉树中的所有 节点 都是四叉树中相应节点的副本；但是，四叉树中的任何数据都通过引用共享，而不是复制。
返回四叉树的根 节点。
返回四叉树中的所有数据数组。
返回四叉树中的数据总数。
# quadtree.find(x, y[, radius]) <>
返回距离给定搜索 radius 内的 ⟨x,y⟩ 位置最近的数据。如果未指定 radius，则默认为无穷大。如果在搜索区域内没有数据，则返回 undefined。
以先序遍历访问四叉树中的每个 节点，为每个节点调用指定的 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 近似法 时。但请注意，子象限始终以兄弟顺序访问：左上、右上、左下、右下。在 搜索 等情况下，按特定顺序访问兄弟节点可能会更快。
例如，以下代码访问四叉树并返回矩形范围 [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;
}
# 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。
节点
四叉树的内部节点以从左到右、从上到下的顺序表示为四元素数组。
0- 左上象限（如果存在）。1- 右上象限（如果存在）。2- 左下象限（如果存在）。3- 右下象限（如果存在）。
如果子象限为空，则可能为 undefined。
叶节点表示为具有以下属性的对象。
data- 与该点关联的数据，传递给 quadtree.add。next- 该叶节点中的下一个数据（如果存在）。
length 属性可用于区分叶节点和内部节点：叶节点为 undefined，内部节点为 4。例如，要遍历叶节点中的所有数据。
if (!node.length) do console.log(node.data); while (node = node.next);
点的 x 和 y 坐标在点位于四叉树中时**不得修改**。要更新点的位置，请 移除 该点，然后以新位置重新 添加 它。或者，您可以完全丢弃现有四叉树并从头开始创建新四叉树；如果许多点已移动，这可能更有效。
