自适应细分 · 容量阈值 · 剪枝

quadtree 与 octree

均匀网格的毛病写在名字里：均匀。格线一次切到底，密处与疏处切得一样细。quadtree 保留「每刀落在正中」这条规则，只把「切多深」交给局部点密度决定——点多的地方继续四分，点少的地方就此停手。

1 · 按密度细分

结构本身只有一条规则：一个区域装的点超过容量就四等分，把点分给四个孩子，递归处理。

定义 1.1（quadtree） 一棵每个内部节点恰有四个孩子的树。节点对应一个正方形区域，四个孩子对应它的四个象限。叶子存至多 $C$ 个点（ $C$ 为容量阈值）；插入使某叶子超出 $C$ 时，该叶子四分并把点重新分给孩子，直至满足容量或触到深度上限 $D$ 。

定义 1.2（octree） 同一套规则搬到三维：节点对应立方体，八等分成八个孩子。除孩子数从 4 变 8、深度 $d$ 的节点数从 $4^d$ 变 $8^d$ 之外，插入与查询逻辑逐字相同。

四个孩子的区域恰好铺满父区域且两两不重叠，这条在测试里是一个面积守恒断言（spatial.test.ts 的「四个孩子恰好铺满父节点」）。它保证每个点属于且只属于一个叶子，于是「所有叶子的点集之并等于全部点」也成立，范围查询不会重复计数。

图 1-1 · quadtree 的逐点插入过程。每次插入后触发四分的节点会高亮。可单步或连续插入、改容量阈值与点分布，观察密处与疏处切到的深度差别。

节点自身不存边界坐标也行：区域可以从根一路二分算出来。实现里通常还是存着，因为四分时要算中点，存下来省一次递归传参。

2 · 容量阈值与深度上限

容量阈值常被当成「越小越精确」的旋钮。2000 个均匀随机点、200 次 60 见方的窗口查询，实测不是这样：

容量 $C$	节点总数	叶子数	最大深度	范围查询访问节点	点级判定	kNN( $k{=}5$ ) 访问节点
1	5825	4369	12	151.06	13.20	28.12
2	2865	2149	9	96.02	19.82	16.70
4	1441	1081	7	65.76	28.05	14.38
8	741	556	6	44.12	42.48	10.20
16	349	262	5	32.78	56.13	7.62

两列反向变化：容量从 16 调到 1，点级判定从 56.13 降到 13.20，访问的节点数却从 32.78 涨到 151.06。容量的作用不是提高精度，而是在「遍历树」与「过滤点」之间挪开销。经验值取 4 到 16，判据是一个叶子的点集能不能装进一个 cache line 或一个磁盘页。

深度上限 $D$ 是另一回事：它不调性能，它保证递归会终止。均匀分布下这个上限几乎碰不到（ $C = 4$ 时实际深度只有 7），它存在是为了 §3 那种情形。

3 · 重合点导致的无限细分

四分能分开两个点，前提是它们不在同一个象限里。坐标完全相同的两个点在任何深度都落进同一个象限，于是「超出容量就四分」这条规则会无限递归下去。

没有深度上限时这不是性能问题而是崩溃：栈溢出，或内存耗尽。有了上限，触到上限的叶子直接放弃容量约束，装多少算多少。测试里那条断言就写成「未达深度上限的叶子点数不超过容量」，达到上限的豁免。

代价是树的形状。64 个坐标完全相同的点，容量 4、深度上限 12，实测造出 49 个节点、深度 12：每一层只有一个孩子非空，另外三个是空叶子。 $1 + 12 \times 4 = 49$ ，一个不多一个不少：树退化成一条长 12 的链，外挂 36 个永远查不到东西的空叶子。深度上限降到 4，节点数降到 17（ $1 + 4 \times 4$ ）。

原先的猜想是团簇分布也会长出这种病态形状。实测差得远：2000 个点分成 5 个高斯团簇，容量 4 时节点 1485、深度 8，与均匀分布的 1441、深度 7 几乎一样。高斯团簇的密度峰值是有限的，四分几刀就把它们分开了。真正会打穿 quadtree 的是密度无界的输入：重合点，或者精度低到坐标被量化成同一个值的浮点数据。

警示 · 「同一个点插两次」在真实数据里比想象的常见：地图上同一栋楼的多个 POI、传感器在静止期间的重复上报、坐标被取整到整数像素之后的碰撞。深度上限不是可选的防御，而是必需的。

4 · 范围查询的剪枝

范围查询自顶向下走，每个节点先判一次「本区域与查询矩形是否相交」。不相交就整枝剪掉，不再递归。

多出的一条优化是：若本区域整个落在查询矩形内，那么区域里的每个点必然命中，点级判定可以整批省掉。引擎里这一步写在 qtRange 的 rectInside 分支上，它是 quadtree 的点级判定次数（ $C = 4$ 时 28.05）明显低于同规模均匀网格（边长 32 时 62.13）的主要原因：网格没有层级，一个格子只能是「覆盖到」而不能是「整格被包住」，桶里的点仍要逐个判。

图 4-1 · 范围查询在 quadtree 上的剪枝。虚线红框是一进去就被剪掉的节点，实线绿底是整个落在查询矩形内的节点。可拖动查询窗、改容量阈值，读数给出访问节点数与省下的点级判定。

kNN 用的下界是区域到查询点的最小距离（式子见一维索引答不了的问题 §3）。实现上多一步排序：先算四个孩子各自的下界，按下界从小到大依次递归。这个次序很重要：先搜近侧能尽快把「当前第 $k$ 名的距离」压小，后面的剪枝才有力。次序反过来算法仍然正确，只是几乎不剪。

5 · 三维的代价

octree 的逻辑与 quadtree 逐字相同，但两个数字变了。

孩子数从 4 变 8，意味着同样深度下节点数从 $4^d$ 变 $8^d$ 。深度 8 的满四叉树有 87381 个节点，满八叉树有 19173961 个——两百多倍。实践中八叉树几乎从不长满，但空孩子的指针仍要占位：一个内部节点 8 个指针，比 4 个多一倍的内存与一倍的 cache 压力。

更本质的变化是查询矩形与区域的相交概率。二维下一个边长为区域一半的查询窗平均与 2.25 个孩子相交（ $1.5^2$ ），三维下是 3.375 个（ $1.5^3$ ）。维数每加一，一次查询要下的分支数按几何级数涨——这与 k-d tree 与最近邻回溯 §5 那条维度灾难曲线是同一件事的两个面。

6 · 参考文献

Finkel, R. A., & Bentley, J. L. (1974). Quad trees: A data structure for retrieval on composite keys. Acta Informatica, 4(1), 1–9.
Samet, H. (1984). The quadtree and related hierarchical data structures. ACM Computing Surveys, 16(2), 187–260.
Meagher, D. (1982). Geometric modeling using octree encoding. Computer Graphics and Image Processing, 19(2), 129–147.
Ericson, C. (2004). Real-Time Collision Detection (§7.3: Quadtrees and Octrees). Morgan Kaufmann.