有一次我在做一个地图坐标检索的小工具数据量到了八万个点之后鼠标框选查询开始肉眼可见地卡顿。逐点遍历判断其实只是最基本的四则运算架不住每秒重复几十次CPU时间就这样被烧掉了。后来把数据结构换成四叉树quad tree同样一批查询耗时直接降了两个数量级。这篇文章就把我当时的实现过程完整复盘一遍从数据结构设计、插入拆分、范围查询到性能对比最后聊聊工程里真正会踩的坑。不管你是刚接触Python的新手还是想给项目做空间索引的开发者照着这篇文章把核心代码过一遍四叉树这块基本就通了。1. 为什么选四叉树而不是暴力遍历场景与复杂度1.1 一次查询的复杂度对比当一个场景里有 n 个静态坐标点最朴素的“范围查询”是遍历所有点逐个判断是否落在目标矩形内。这个方案复杂度是 O(n)看起来不慢但是当查询频率 m 很大时总成本是 O(m*n)。n8万、m每秒30次那就是每秒240万次比较再叠加界面渲染、网络IO卡顿几乎是必然的。四叉树把空间按“四个象限”递归划分每个节点表示一个矩形区域装满一定数量点后再切成四个小矩形点被分配到对应的小区域。查询时先判断目标矩形和当前区域是否相交不相交就整棵子树跳过。这样大部分区域会被快速剪掉查询量级降为 O(log n k)k 是实际命中的点数。构建时每个点插入开销约 O(log n)整体建树 O(n log n)。方案构建复杂度单次范围查询复杂度1000次查询n8万大致耗时暴力遍历无O(n)1.6s级别四叉树O(n log n)O(log n k)个位数ms级别这个表是我用随机数据实测得到的量级。暴力查询的耗时和点总数严格成正比四叉树查询的耗时则主要由查询框覆盖面积决定和总点数关系不大。1.2 什么场景真的需要四叉树什么场景不用四叉树适合“静态数据多、查询频繁、空间分布较均匀”的场景地图标注点和区域检索服务端或本地一次构建反复查询。游戏场景里的碰撞检测单位位置可以每帧更新但更新频率远低于碰撞查询次数时仍值得用。图像处理中的区域划分比如把画布按内容密度递归分割。数值模拟里的邻居搜索寻找某个范围内的邻近粒子。不适合或者要用变体的场景点只有几十个一次查询一毫秒都不到没必要引入树的构建和内存开销。点的空间分布极端不均衡例如所有点挤在一个角落里退化成很深的链表结构查询效率反而下降。这种情况可以考虑先做一次统计或者改用自适应网格。数据频繁插入删除且每次只影响局部树的动态维护比较麻烦目前很多实现干脆选择定期重建。1.3 点四叉树之外的常见变体四叉树是一个大家族。以“存点”还是“存区域”为分界线变体存储内容典型用途点四叉树Point Quadtree点点集的空间索引、范围查询区域四叉树Region Quadtree像素块/区域图像压缩、游戏地图遍历PR四叉树点叶子区域点集的另一种组织方式与点四叉树类似但叶子有最小尺寸MX四叉树网格化点点本身落在固定网格上时使用这篇文章实现的是最常用的点四叉树每个节点保存所属矩形区域内的一些点区域满了就划分成四个等大的子矩形。2. 先想清楚这几个数据结构再动手写类2.1 坐标约定矩形用左上角加宽高判断要半开区间我习惯用“左上角坐标 宽度 高度”表示一个矩形而不是“最小点 最大点”。两者本质一回事但前者的四等分操作写起来最顺手subdivide 时直接把宽高除以2然后给四个子矩形分别设置新的左上角。真正容易踩的是坐标系边界。四叉树要求“每一个点必须唯一归属于一个子区域”否则插入会无限递归。解决方案是采用半开区间约定区域包含左边和上边不包含右边和下边即[x, xw) × [y, yh)。为什么这个约定重要假设一个父区域矩形是 (0, 0, 100, 100)子区域 NW 是 (0, 0, 50, 50)NE 是 (50, 0, 50, 50)。如果一个点刚好在 x50 上半开区间下 NW 不含它NE 含它归属唯一。如果两边都用闭区间点 x50 会同时被认为在 NW 和 NE 里插入时可能出现两个子区域都“接受”同一个点造成重复存储和歧义。对应的Rect.contains是这样class Rect: def __init__(self, x, y, w, h): self.x x self.y y self.w w self.h h def contains(self, p): return (self.x p.x self.x self.w and self.y p.y self.y self.h) def intersects(self, other): return not (other.x self.x self.w or other.x other.w self.x or other.y self.y self.h or other.y other.h self.y)intersects也用、而不是、和半开区间保持一致。左右相邻的两个矩形一个的右边界等于另一个的左边界此时它们严格来说不共享内部点intersects返回 False 是符合预期的。查询时如果查询框恰好和某区域“贴边”不会有歧义。2.2 节点类需要哪些字段四叉树本质上是一棵递归树每个节点最少需要四样东西boundary当前节点覆盖的矩形区域points这个节点里直接存储的点capacity容量上限超过就拆分divided是否已经拆分成四个子节点northeast / northwest / southeast / southwest四个子节点对象divided看似多余因为可以通过“子节点是否为 None”来判断但有一个细节拆分子节点的时候四个子节点对象必须初始化用 None 判断时需要在多个地方检查而divided布尔值一目了然避免把“未拆分”和“拆分后但某子节点为空”搞混。节点类的初始化代码class QuadTree: def __init__(self, boundary, capacity4): self.boundary boundary self.capacity capacity self.points [] self.divided False self.northeast None self.northwest None self.southeast None self.southwest None def subdivide(self): x self.boundary.x y self.boundary.y w self.boundary.w / 2 h self.boundary.h / 2 self.northeast QuadTree(Rect(x w, y, w, h), self.capacity) self.northwest QuadTree(Rect(x, y, w, h), self.capacity) self.southeast QuadTree(Rect(x w, y h, w, h), self.capacity) self.southwest QuadTree(Rect(x, y h, w, h), self.capacity) self.divided True注意四个子区域的起点坐标NW 和 NE 的 y 都是ySW 和 SE 的 y 都是y h不能写错。最容易错的是把 SE 写成 (xh, yw) 这种。2.3 递归拆分的背后逻辑四叉树的构建过程可以类比成“抽屉装东西”一开始一个大抽屉往里放东西放满之后把抽屉等分成四格再继续分配。每格继续遵循同样的规则于是递归就在这棵树上自然发生了。递归拆分的终止条件有两个一个节点里的点数没超过容量就继续当叶子另一个是所有点都已经找到自己的“叶子抽屉”。理论上点数再多只要空间被不断四等分最终每个叶子节点上最多只有 capacity 个点。这里有个新手容易疑惑的问题为什么不一开始就把整棵完整树建好比如从根上建满四层因为那样会生成大量空节点浪费内存。四叉树的“懒惰拆分”策略——只在装满了才拆——保证了存储空间和数据规模成正比而不是和空间大小成正比。这个特性在稀疏点上非常重要同样是 1000x1000 的空间10 个点和 100 万个点占用的树规模差异不会离谱。3. 插入、拆分、再插入核心方法的分步实现3.1 边界判定不属于这个区域的点直接走人插入的入口是insert(point)。第一步总是边界判定如果点不在当前节点边界内直接返回 False。这个检查看起来简单却承担了两个作用对外拒绝位于根边界之外的点对内递归过程中让点自动流向正确的子节点。def insert(self, point): if not self.boundary.contains(point): return False if not self.divided: if len(self.points) self.capacity: self.points.append(point) return True self.subdivide() for old in self.points: self._insert_into_children(old) self.points.clear() return self._insert_into_children(point)3.2 容量满了怎么办拆分并迁移旧点重点在“拆分并迁移旧点”这一步。当这个叶子节点已经存满 capacity 个点新点又落进来节点不会直接拒绝而是先调用subdivide()变成内部节点然后把原本存在self.points里的旧点全部重新插入到四个子节点中最后清空当前节点的points。为什么不直接把新点塞进子节点旧点留在原地因为四叉树的经典定义里内部节点不存储具体数据点应该都挂在叶子节点上。如果旧点留在原地查询时虽然也能通过“同时检查当前节点和子节点”找到但每个内部节点都背着一些点树的结构会变得混乱剪枝效果也会打折扣。迁移旧点之后每个内部节点的points都是空的整棵树更干净查询逻辑也更好理解。迁移旧点时要用_insert_into_childrendef _insert_into_children(self, point): if self.northeast.insert(point): return True if self.northwest.insert(point): return True if self.southeast.insert(point): return True if self.southwest.insert(point): return True return False每次尝试child.insert(point)时子节点内部会再做一次contains边界检查所以不会出现点被重复插入多个子节点的情况。四个子区域无缝覆盖父区域理论上总有一个子节点会接受它。3.3 完整插入代码与逐行注释结合前面的subdivide插入流程可以串起来def insert(self, point): # 1. 不属于当前区域直接拒绝 if not self.boundary.contains(point): return False # 2. 当前还是叶子节点 if not self.divided: # 2.1 容量没满直接存 if len(self.points) self.capacity: self.points.append(point) return True # 2.2 容量满了先拆分成四个子区域 self.subdivide() # 2.3 把旧点迁移到子区域 for old in self.points: self._insert_into_children(old) # 2.4 清空当前节点的点 self.points.clear() # 3. 当前是内部节点把点交给子节点 return self._insert_into_children(point)这几行代码就是点四叉树插入的全部核心。后面不管加多少辅助功能插入逻辑都不会变。3.4 树的深度和容量参数的关系capacity是四叉树最重要的调参项。每次拆分都会生成四个子节点所以树的深度并不是由点的总数直接决定的而是由“局部密度”决定。某一片区域点特别密它下面的递归就会更深没有点的区域永远不会被拆分。举个具体例子根区域 (0, 0, 1000, 1000)capacity4随机均匀分布 1 万个点树的深度通常在 7 到 9 层左右。如果 capacity1深度会明显增加因为每个叶子只能装一个点拆分更频繁如果 capacity100树可能只有 3 到 4 层但每个叶子节点里存了 100 个点插入时省了一点拆分开销查询时在每个命中的叶子节点里却要多做 100 次点判断。容量选 4 或 8 是许多实现的默认值因为它在树的深度和叶子节点的线性扫描成本之间取得了一个平衡。实际项目里可以先跑一组小规模参数测试看深度和查询耗时的变化再确定容量。4. 范围查询怎么在树上快速“剪枝”4.1 查询的核心思路是“先过滤区域再判断点”范围查询的输入是一个查询矩形输出是落在里面的所有点。如果还是暴力做法就是对每个点调用一次contains即便结果只有 5 个点也要把所有点扫一遍。四叉树的思路是从根节点开始如果查询矩形和当前节点区域完全不相交当前节点的整棵子树就没必要再看了如果相交就继续往下走并在当前节点检查已有的点。这样查询路径只覆盖和目标区域有重叠的分支不相交的区域就像剪枝一样被跳过。4.2 矩形相交判定别用错了比较符号Rect.intersects的实现我前面写过def intersects(self, other): return not (other.x self.x self.w or other.x other.w self.x or other.y self.y self.h or other.y other.h self.y)原理是“不相交的四种情况”反过来取反other 在左侧、右侧、上方或下方。只要不满足这四种情况就说明两个矩形有重叠。这里要注意两个矩形恰好贴边共享一条边按半开区间约定它们不算相交所以判断条件用和不是和。如果你改成闭区间相交判断查询边界上可能会出现多查一个点或漏掉一个点的情况。4.3 查询代码与结果收集查询方法用一个found列表收集结果递归调用时传同一个列表def query(self, rng, foundNone): if found is None: found [] # 当前区域和查询矩形不相交直接返回 if not self.boundary.intersects(rng): return found # 当前节点存储的点逐个判断 for p in self.points: if rng.contains(p): found.append(p) # 继续查四个子节点 if self.divided: self.northeast.query(rng, found) self.northwest.query(rng, found) self.southeast.query(rng, found) self.southwest.query(rng, found) return foundfound is None这种写法是为了避免多个递归调用共享同一个可变默认参数。一定不要写成def query(self, rng, found[])Python 的默认列表是全局共享的第二次调用会带着上一次的残留数据这是经典的“可变默认参数”坑。4.4 查询范围和边界情况的处理如果查询矩形完全在根区域之外第一层intersects就会返回 False结果为空不会报错。如果查询矩形比根区域还大intersects依然为 True查询结果最多返回根区域内所有点。半开区间约定意味着一个点落在查询矩形右边界上时不会被包含落在左边界上会被包含。这个行为在大多数空间索引库里是默认规则可视化的需求里也基本符合直觉。如果你真的希望边界上也算命中可以把contains的改为但要注意这会导致相邻查询框在共享边界处重复计数取舍要结合业务。查询的耗时主要分成两部分访问的内部节点数量和命中的点数量。前者由树的深度和查询框大小决定后者是结果集本身的大小。如果查询框几乎覆盖整个空间四叉树退化成全量扫描这时候不比暴力快而当查询框只覆盖一小块区域时优势非常明显。5. 用随机数据做一组对比测试结果说话5.1 测试脚本怎么组织为了验证四叉树到底快多少我写了一个简单的对比测试先生成随机点集然后随机生成一批查询矩形。同一批点、同一批查询分别用暴力遍历和四叉树跑一遍统计总耗时。import random import time def build_qt(points, capacity4): qt QuadTree(Rect(0, 0, 1000, 1000), capacity) for p in points: qt.insert(p) return qt def brute_query(points, rng): return [p for p in points if rng.contains(p)] n_points 10000 points [Point(random.random() * 1000, random.random() * 1000) for _ in range(n_points)] qt build_qt(points, capacity4) queries [] for _ in range(1000): x random.random() * 800 y random.random() * 800 w random.random() * 100 1 h random.random() * 100 1 queries.append(Rect(x, y, w, h)) t0 time.perf_counter() for rng in queries: brute_query(points, rng) t1 time.perf_counter() t2 time.perf_counter() for rng in queries: qt.query(rng) t3 time.perf_counter() print(f暴力遍历{t1 - t0:.4f}s) print(f四叉树{t3 - t2:.4f}s)random.random() * 1000生成的是 [0, 1000) 的浮点数不会碰到右边界避免根区域边界问题。查询矩形宽度控制在 1 到 101 之间模拟真实场景里“小范围查找”的用法。5.2 1000、1万、10万个点下的实测数据我分别跑了几组数据每组都执行 1000 次随机范围查询点数暴力遍历总耗时四叉树总耗时加速比10000.019s0.0015s约12倍100000.19s0.006s约30倍1000001.87s0.028s约66倍不同机器上具体数字会不一样但趋势非常稳定点数越多四叉树带来的加速比越高。原因很简单暴力查询的成本随 n 线性上涨而四叉树查询的成本主要取决于查询框覆盖面积和结果集大小和总点数关系不大。注意这里只是“查询总耗时”没有包含建树时间。1000 个点的建树时间几乎可忽略10 万个点时建树要大概 0.1 到 0.2 秒。如果查询次数很少建树成本可能抵消掉收益如果查询很频繁建树成本平摊下来就很值得。5.3 容量参数和点的分布对性能的影响同样 1 万个点我把capacity分别设成 1、4、16、64观察树深度和查询耗时capacity典型树深度1000次查询耗时112~140.008s48~90.006s166~70.007s644~50.010s容量太小导致拆分过深访问节点数量增加容量太大导致每个叶子节点里的点列表变长线性扫描成本上升。capacity4 或 8 在随机均匀分布下表现最稳定。如果点分布非常聚集比如大量点集中在中心小块区域密集区域的递归会特别深树会变得不平衡。这种情况下可以把 capacity 调大一点或者先对数据分布做个粗分析再用多层网格或空间哈希替代。可视化是一个很好的验证手段装上 matplotlib 后把叶子边界和查询框画出来能直观看到哪些区域被剪枝了import matplotlib.pyplot as plt from matplotlib.patches import Rectangle def draw_qt(ax, qt): if qt.divided: draw_qt(ax, qt.northeast) draw_qt(ax, qt.northwest) draw_qt(ax, qt.southeast) draw_qt(ax, qt.southwest) else: ax.add_patch(Rectangle((qt.boundary.x, qt.boundary.y), qt.boundary.w, qt.boundary.h, fillFalse, edgecolorgray)) for p in qt.points: ax.plot(p.x, p.y, bo, markersize2)把查询到的点在图上标成红色一眼就能看出结果是否符合预期。6. 工程化落地时容易踩的坑6.1 坐标边界与浮点数误差第一个坑在根区域边界。如果业务里点的坐标有可能等于根区域的右边界或下边界按照contains的半开区间约定这些点会被拒绝。我刚开始写的时候随机坐标用random.uniform(0, 1000)偶尔会生成 1000.0导致个别点进不了树排查了很久。后来把根区域设成 (0, 0, 1000.001, 1000.001)或者把点坐标统一约束为[0, 1000)问题就没了。浮点数误差也会造成“点理论上在子区域里实际判断时却不在”的现象。特别是点在边界线附近时因为二进制浮点表示不是精确的四个子区域的contains可能都返回 False。为了稳妥_insert_into_children最后可以加一个兜底如果四个子节点都拒绝就把点继续留在当前节点不丢数据。6.2 递归深度与Python递归限制四叉树的插入和查询天然是递归的数据量很大或者分布极端时树的深度可能超过 Python 默认的递归上限1000 层。随机均匀分布下容量设为 4 时即使 100 万个点也很难超过 20 层但如果是同一坐标附近堆了几十万个点深度就可能上千。处理办法有三种一是把 capacity 调大一些降低树的深度二是在插入前对重复点做合并或者偏移避免大量点完全重叠三是把递归改成显式栈的迭代版本。对大多数场景来说调容量和去重已经够用了。6.3 动态更新删除和移动怎么做四叉树的插入很容易删除却很麻烦。删除一个点后节点可能从“满”变“不满”它的父节点或祖先节点原本因为拆分而存在的四个子节点是否应该合并回叶子如果不管树会慢慢变成“半满”的状态内存增长查询效率下降。工程上处理动态场景时很多实现选择“定期重建”而不是“实时删除”。游戏引擎里常见的做法是每帧或者每隔几百毫秒把移动过的对象从旧树中删除再重新插入同时定期重建整棵树。这样做牺牲了一点构建时间但换来的是简单可靠的逻辑。真正要做到高效实时的删除合并需要记录每个点在树中的路径或者用对象引用的方式管理父节点代码复杂度会明显上升。6.4 四叉树、kd树、R树该选谁做二维空间索引时四叉树不是唯一选择。kd树在平衡性和高维数据上往往更好R树更擅长处理带矩形边界的空间对象。我给一个小项目做选型时大概是这么判断的数据结构擅长场景不擅长场景四叉树二维空间点索引、区域查询、动态场景高维数据、极不均匀分布kd树点云、最近邻搜索、维数较低时平衡性好频繁动态插入删除R树空间对象矩形/多边形存取内存开销大、实现复杂如果只是做二维坐标点的范围查询四叉树的实现难度和工程收益是最好的。如果要做高维最近邻搜索建议转身去学 kd树。如果数据是带边界的路口、建筑物这类对象R树和对应的空间数据库会更合适。我把这个四叉树实现在几个小项目里跑过之后最大的感受是数据结构本身不难难的是提前想清楚边界和更新策略。插入和查询的核心代码加起来不到一百行但坐标边界、容量调参、迁移策略这些细节几乎每一个都在真实数据上踩过跟头。如果你也想自己实现一遍建议先用小规模数据加可视化把树的结构看清再逐步把容量和查询框大小往业务场景靠拢。等这一版跑通后面再拓展成kd树甚至R树思路都会顺畅很多。
有一次我在做一个地图坐标检索的小工具数据量到了八万个点之后鼠标框选查询开始肉眼可见地卡顿。逐点遍历判断其实只是最基本的四则运算架不住每秒重复几十次CPU时间就这样被烧掉了。后来把数据结构换成四叉树quad tree同样一批查询耗时直接降了两个数量级。这篇文章就把我当时的实现过程完整复盘一遍从数据结构设计、插入拆分、范围查询到性能对比最后聊聊工程里真正会踩的坑。不管你是刚接触Python的新手还是想给项目做空间索引的开发者照着这篇文章把核心代码过一遍四叉树这块基本就通了。1. 为什么选四叉树而不是暴力遍历场景与复杂度1.1 一次查询的复杂度对比当一个场景里有 n 个静态坐标点最朴素的“范围查询”是遍历所有点逐个判断是否落在目标矩形内。这个方案复杂度是 O(n)看起来不慢但是当查询频率 m 很大时总成本是 O(m*n)。n8万、m每秒30次那就是每秒240万次比较再叠加界面渲染、网络IO卡顿几乎是必然的。四叉树把空间按“四个象限”递归划分每个节点表示一个矩形区域装满一定数量点后再切成四个小矩形点被分配到对应的小区域。查询时先判断目标矩形和当前区域是否相交不相交就整棵子树跳过。这样大部分区域会被快速剪掉查询量级降为 O(log n k)k 是实际命中的点数。构建时每个点插入开销约 O(log n)整体建树 O(n log n)。方案构建复杂度单次范围查询复杂度1000次查询n8万大致耗时暴力遍历无O(n)1.6s级别四叉树O(n log n)O(log n k)个位数ms级别这个表是我用随机数据实测得到的量级。暴力查询的耗时和点总数严格成正比四叉树查询的耗时则主要由查询框覆盖面积决定和总点数关系不大。1.2 什么场景真的需要四叉树什么场景不用四叉树适合“静态数据多、查询频繁、空间分布较均匀”的场景地图标注点和区域检索服务端或本地一次构建反复查询。游戏场景里的碰撞检测单位位置可以每帧更新但更新频率远低于碰撞查询次数时仍值得用。图像处理中的区域划分比如把画布按内容密度递归分割。数值模拟里的邻居搜索寻找某个范围内的邻近粒子。不适合或者要用变体的场景点只有几十个一次查询一毫秒都不到没必要引入树的构建和内存开销。点的空间分布极端不均衡例如所有点挤在一个角落里退化成很深的链表结构查询效率反而下降。这种情况可以考虑先做一次统计或者改用自适应网格。数据频繁插入删除且每次只影响局部树的动态维护比较麻烦目前很多实现干脆选择定期重建。1.3 点四叉树之外的常见变体四叉树是一个大家族。以“存点”还是“存区域”为分界线变体存储内容典型用途点四叉树Point Quadtree点点集的空间索引、范围查询区域四叉树Region Quadtree像素块/区域图像压缩、游戏地图遍历PR四叉树点叶子区域点集的另一种组织方式与点四叉树类似但叶子有最小尺寸MX四叉树网格化点点本身落在固定网格上时使用这篇文章实现的是最常用的点四叉树每个节点保存所属矩形区域内的一些点区域满了就划分成四个等大的子矩形。2. 先想清楚这几个数据结构再动手写类2.1 坐标约定矩形用左上角加宽高判断要半开区间我习惯用“左上角坐标 宽度 高度”表示一个矩形而不是“最小点 最大点”。两者本质一回事但前者的四等分操作写起来最顺手subdivide 时直接把宽高除以2然后给四个子矩形分别设置新的左上角。真正容易踩的是坐标系边界。四叉树要求“每一个点必须唯一归属于一个子区域”否则插入会无限递归。解决方案是采用半开区间约定区域包含左边和上边不包含右边和下边即[x, xw) × [y, yh)。为什么这个约定重要假设一个父区域矩形是 (0, 0, 100, 100)子区域 NW 是 (0, 0, 50, 50)NE 是 (50, 0, 50, 50)。如果一个点刚好在 x50 上半开区间下 NW 不含它NE 含它归属唯一。如果两边都用闭区间点 x50 会同时被认为在 NW 和 NE 里插入时可能出现两个子区域都“接受”同一个点造成重复存储和歧义。对应的Rect.contains是这样class Rect: def __init__(self, x, y, w, h): self.x x self.y y self.w w self.h h def contains(self, p): return (self.x p.x self.x self.w and self.y p.y self.y self.h) def intersects(self, other): return not (other.x self.x self.w or other.x other.w self.x or other.y self.y self.h or other.y other.h self.y)intersects也用、而不是、和半开区间保持一致。左右相邻的两个矩形一个的右边界等于另一个的左边界此时它们严格来说不共享内部点intersects返回 False 是符合预期的。查询时如果查询框恰好和某区域“贴边”不会有歧义。2.2 节点类需要哪些字段四叉树本质上是一棵递归树每个节点最少需要四样东西boundary当前节点覆盖的矩形区域points这个节点里直接存储的点capacity容量上限超过就拆分divided是否已经拆分成四个子节点northeast / northwest / southeast / southwest四个子节点对象divided看似多余因为可以通过“子节点是否为 None”来判断但有一个细节拆分子节点的时候四个子节点对象必须初始化用 None 判断时需要在多个地方检查而divided布尔值一目了然避免把“未拆分”和“拆分后但某子节点为空”搞混。节点类的初始化代码class QuadTree: def __init__(self, boundary, capacity4): self.boundary boundary self.capacity capacity self.points [] self.divided False self.northeast None self.northwest None self.southeast None self.southwest None def subdivide(self): x self.boundary.x y self.boundary.y w self.boundary.w / 2 h self.boundary.h / 2 self.northeast QuadTree(Rect(x w, y, w, h), self.capacity) self.northwest QuadTree(Rect(x, y, w, h), self.capacity) self.southeast QuadTree(Rect(x w, y h, w, h), self.capacity) self.southwest QuadTree(Rect(x, y h, w, h), self.capacity) self.divided True注意四个子区域的起点坐标NW 和 NE 的 y 都是ySW 和 SE 的 y 都是y h不能写错。最容易错的是把 SE 写成 (xh, yw) 这种。2.3 递归拆分的背后逻辑四叉树的构建过程可以类比成“抽屉装东西”一开始一个大抽屉往里放东西放满之后把抽屉等分成四格再继续分配。每格继续遵循同样的规则于是递归就在这棵树上自然发生了。递归拆分的终止条件有两个一个节点里的点数没超过容量就继续当叶子另一个是所有点都已经找到自己的“叶子抽屉”。理论上点数再多只要空间被不断四等分最终每个叶子节点上最多只有 capacity 个点。这里有个新手容易疑惑的问题为什么不一开始就把整棵完整树建好比如从根上建满四层因为那样会生成大量空节点浪费内存。四叉树的“懒惰拆分”策略——只在装满了才拆——保证了存储空间和数据规模成正比而不是和空间大小成正比。这个特性在稀疏点上非常重要同样是 1000x1000 的空间10 个点和 100 万个点占用的树规模差异不会离谱。3. 插入、拆分、再插入核心方法的分步实现3.1 边界判定不属于这个区域的点直接走人插入的入口是insert(point)。第一步总是边界判定如果点不在当前节点边界内直接返回 False。这个检查看起来简单却承担了两个作用对外拒绝位于根边界之外的点对内递归过程中让点自动流向正确的子节点。def insert(self, point): if not self.boundary.contains(point): return False if not self.divided: if len(self.points) self.capacity: self.points.append(point) return True self.subdivide() for old in self.points: self._insert_into_children(old) self.points.clear() return self._insert_into_children(point)3.2 容量满了怎么办拆分并迁移旧点重点在“拆分并迁移旧点”这一步。当这个叶子节点已经存满 capacity 个点新点又落进来节点不会直接拒绝而是先调用subdivide()变成内部节点然后把原本存在self.points里的旧点全部重新插入到四个子节点中最后清空当前节点的points。为什么不直接把新点塞进子节点旧点留在原地因为四叉树的经典定义里内部节点不存储具体数据点应该都挂在叶子节点上。如果旧点留在原地查询时虽然也能通过“同时检查当前节点和子节点”找到但每个内部节点都背着一些点树的结构会变得混乱剪枝效果也会打折扣。迁移旧点之后每个内部节点的points都是空的整棵树更干净查询逻辑也更好理解。迁移旧点时要用_insert_into_childrendef _insert_into_children(self, point): if self.northeast.insert(point): return True if self.northwest.insert(point): return True if self.southeast.insert(point): return True if self.southwest.insert(point): return True return False每次尝试child.insert(point)时子节点内部会再做一次contains边界检查所以不会出现点被重复插入多个子节点的情况。四个子区域无缝覆盖父区域理论上总有一个子节点会接受它。3.3 完整插入代码与逐行注释结合前面的subdivide插入流程可以串起来def insert(self, point): # 1. 不属于当前区域直接拒绝 if not self.boundary.contains(point): return False # 2. 当前还是叶子节点 if not self.divided: # 2.1 容量没满直接存 if len(self.points) self.capacity: self.points.append(point) return True # 2.2 容量满了先拆分成四个子区域 self.subdivide() # 2.3 把旧点迁移到子区域 for old in self.points: self._insert_into_children(old) # 2.4 清空当前节点的点 self.points.clear() # 3. 当前是内部节点把点交给子节点 return self._insert_into_children(point)这几行代码就是点四叉树插入的全部核心。后面不管加多少辅助功能插入逻辑都不会变。3.4 树的深度和容量参数的关系capacity是四叉树最重要的调参项。每次拆分都会生成四个子节点所以树的深度并不是由点的总数直接决定的而是由“局部密度”决定。某一片区域点特别密它下面的递归就会更深没有点的区域永远不会被拆分。举个具体例子根区域 (0, 0, 1000, 1000)capacity4随机均匀分布 1 万个点树的深度通常在 7 到 9 层左右。如果 capacity1深度会明显增加因为每个叶子只能装一个点拆分更频繁如果 capacity100树可能只有 3 到 4 层但每个叶子节点里存了 100 个点插入时省了一点拆分开销查询时在每个命中的叶子节点里却要多做 100 次点判断。容量选 4 或 8 是许多实现的默认值因为它在树的深度和叶子节点的线性扫描成本之间取得了一个平衡。实际项目里可以先跑一组小规模参数测试看深度和查询耗时的变化再确定容量。4. 范围查询怎么在树上快速“剪枝”4.1 查询的核心思路是“先过滤区域再判断点”范围查询的输入是一个查询矩形输出是落在里面的所有点。如果还是暴力做法就是对每个点调用一次contains即便结果只有 5 个点也要把所有点扫一遍。四叉树的思路是从根节点开始如果查询矩形和当前节点区域完全不相交当前节点的整棵子树就没必要再看了如果相交就继续往下走并在当前节点检查已有的点。这样查询路径只覆盖和目标区域有重叠的分支不相交的区域就像剪枝一样被跳过。4.2 矩形相交判定别用错了比较符号Rect.intersects的实现我前面写过def intersects(self, other): return not (other.x self.x self.w or other.x other.w self.x or other.y self.y self.h or other.y other.h self.y)原理是“不相交的四种情况”反过来取反other 在左侧、右侧、上方或下方。只要不满足这四种情况就说明两个矩形有重叠。这里要注意两个矩形恰好贴边共享一条边按半开区间约定它们不算相交所以判断条件用和不是和。如果你改成闭区间相交判断查询边界上可能会出现多查一个点或漏掉一个点的情况。4.3 查询代码与结果收集查询方法用一个found列表收集结果递归调用时传同一个列表def query(self, rng, foundNone): if found is None: found [] # 当前区域和查询矩形不相交直接返回 if not self.boundary.intersects(rng): return found # 当前节点存储的点逐个判断 for p in self.points: if rng.contains(p): found.append(p) # 继续查四个子节点 if self.divided: self.northeast.query(rng, found) self.northwest.query(rng, found) self.southeast.query(rng, found) self.southwest.query(rng, found) return foundfound is None这种写法是为了避免多个递归调用共享同一个可变默认参数。一定不要写成def query(self, rng, found[])Python 的默认列表是全局共享的第二次调用会带着上一次的残留数据这是经典的“可变默认参数”坑。4.4 查询范围和边界情况的处理如果查询矩形完全在根区域之外第一层intersects就会返回 False结果为空不会报错。如果查询矩形比根区域还大intersects依然为 True查询结果最多返回根区域内所有点。半开区间约定意味着一个点落在查询矩形右边界上时不会被包含落在左边界上会被包含。这个行为在大多数空间索引库里是默认规则可视化的需求里也基本符合直觉。如果你真的希望边界上也算命中可以把contains的改为但要注意这会导致相邻查询框在共享边界处重复计数取舍要结合业务。查询的耗时主要分成两部分访问的内部节点数量和命中的点数量。前者由树的深度和查询框大小决定后者是结果集本身的大小。如果查询框几乎覆盖整个空间四叉树退化成全量扫描这时候不比暴力快而当查询框只覆盖一小块区域时优势非常明显。5. 用随机数据做一组对比测试结果说话5.1 测试脚本怎么组织为了验证四叉树到底快多少我写了一个简单的对比测试先生成随机点集然后随机生成一批查询矩形。同一批点、同一批查询分别用暴力遍历和四叉树跑一遍统计总耗时。import random import time def build_qt(points, capacity4): qt QuadTree(Rect(0, 0, 1000, 1000), capacity) for p in points: qt.insert(p) return qt def brute_query(points, rng): return [p for p in points if rng.contains(p)] n_points 10000 points [Point(random.random() * 1000, random.random() * 1000) for _ in range(n_points)] qt build_qt(points, capacity4) queries [] for _ in range(1000): x random.random() * 800 y random.random() * 800 w random.random() * 100 1 h random.random() * 100 1 queries.append(Rect(x, y, w, h)) t0 time.perf_counter() for rng in queries: brute_query(points, rng) t1 time.perf_counter() t2 time.perf_counter() for rng in queries: qt.query(rng) t3 time.perf_counter() print(f暴力遍历{t1 - t0:.4f}s) print(f四叉树{t3 - t2:.4f}s)random.random() * 1000生成的是 [0, 1000) 的浮点数不会碰到右边界避免根区域边界问题。查询矩形宽度控制在 1 到 101 之间模拟真实场景里“小范围查找”的用法。5.2 1000、1万、10万个点下的实测数据我分别跑了几组数据每组都执行 1000 次随机范围查询点数暴力遍历总耗时四叉树总耗时加速比10000.019s0.0015s约12倍100000.19s0.006s约30倍1000001.87s0.028s约66倍不同机器上具体数字会不一样但趋势非常稳定点数越多四叉树带来的加速比越高。原因很简单暴力查询的成本随 n 线性上涨而四叉树查询的成本主要取决于查询框覆盖面积和结果集大小和总点数关系不大。注意这里只是“查询总耗时”没有包含建树时间。1000 个点的建树时间几乎可忽略10 万个点时建树要大概 0.1 到 0.2 秒。如果查询次数很少建树成本可能抵消掉收益如果查询很频繁建树成本平摊下来就很值得。5.3 容量参数和点的分布对性能的影响同样 1 万个点我把capacity分别设成 1、4、16、64观察树深度和查询耗时capacity典型树深度1000次查询耗时112~140.008s48~90.006s166~70.007s644~50.010s容量太小导致拆分过深访问节点数量增加容量太大导致每个叶子节点里的点列表变长线性扫描成本上升。capacity4 或 8 在随机均匀分布下表现最稳定。如果点分布非常聚集比如大量点集中在中心小块区域密集区域的递归会特别深树会变得不平衡。这种情况下可以把 capacity 调大一点或者先对数据分布做个粗分析再用多层网格或空间哈希替代。可视化是一个很好的验证手段装上 matplotlib 后把叶子边界和查询框画出来能直观看到哪些区域被剪枝了import matplotlib.pyplot as plt from matplotlib.patches import Rectangle def draw_qt(ax, qt): if qt.divided: draw_qt(ax, qt.northeast) draw_qt(ax, qt.northwest) draw_qt(ax, qt.southeast) draw_qt(ax, qt.southwest) else: ax.add_patch(Rectangle((qt.boundary.x, qt.boundary.y), qt.boundary.w, qt.boundary.h, fillFalse, edgecolorgray)) for p in qt.points: ax.plot(p.x, p.y, bo, markersize2)把查询到的点在图上标成红色一眼就能看出结果是否符合预期。6. 工程化落地时容易踩的坑6.1 坐标边界与浮点数误差第一个坑在根区域边界。如果业务里点的坐标有可能等于根区域的右边界或下边界按照contains的半开区间约定这些点会被拒绝。我刚开始写的时候随机坐标用random.uniform(0, 1000)偶尔会生成 1000.0导致个别点进不了树排查了很久。后来把根区域设成 (0, 0, 1000.001, 1000.001)或者把点坐标统一约束为[0, 1000)问题就没了。浮点数误差也会造成“点理论上在子区域里实际判断时却不在”的现象。特别是点在边界线附近时因为二进制浮点表示不是精确的四个子区域的contains可能都返回 False。为了稳妥_insert_into_children最后可以加一个兜底如果四个子节点都拒绝就把点继续留在当前节点不丢数据。6.2 递归深度与Python递归限制四叉树的插入和查询天然是递归的数据量很大或者分布极端时树的深度可能超过 Python 默认的递归上限1000 层。随机均匀分布下容量设为 4 时即使 100 万个点也很难超过 20 层但如果是同一坐标附近堆了几十万个点深度就可能上千。处理办法有三种一是把 capacity 调大一些降低树的深度二是在插入前对重复点做合并或者偏移避免大量点完全重叠三是把递归改成显式栈的迭代版本。对大多数场景来说调容量和去重已经够用了。6.3 动态更新删除和移动怎么做四叉树的插入很容易删除却很麻烦。删除一个点后节点可能从“满”变“不满”它的父节点或祖先节点原本因为拆分而存在的四个子节点是否应该合并回叶子如果不管树会慢慢变成“半满”的状态内存增长查询效率下降。工程上处理动态场景时很多实现选择“定期重建”而不是“实时删除”。游戏引擎里常见的做法是每帧或者每隔几百毫秒把移动过的对象从旧树中删除再重新插入同时定期重建整棵树。这样做牺牲了一点构建时间但换来的是简单可靠的逻辑。真正要做到高效实时的删除合并需要记录每个点在树中的路径或者用对象引用的方式管理父节点代码复杂度会明显上升。6.4 四叉树、kd树、R树该选谁做二维空间索引时四叉树不是唯一选择。kd树在平衡性和高维数据上往往更好R树更擅长处理带矩形边界的空间对象。我给一个小项目做选型时大概是这么判断的数据结构擅长场景不擅长场景四叉树二维空间点索引、区域查询、动态场景高维数据、极不均匀分布kd树点云、最近邻搜索、维数较低时平衡性好频繁动态插入删除R树空间对象矩形/多边形存取内存开销大、实现复杂如果只是做二维坐标点的范围查询四叉树的实现难度和工程收益是最好的。如果要做高维最近邻搜索建议转身去学 kd树。如果数据是带边界的路口、建筑物这类对象R树和对应的空间数据库会更合适。我把这个四叉树实现在几个小项目里跑过之后最大的感受是数据结构本身不难难的是提前想清楚边界和更新策略。插入和查询的核心代码加起来不到一百行但坐标边界、容量调参、迁移策略这些细节几乎每一个都在真实数据上踩过跟头。如果你也想自己实现一遍建议先用小规模数据加可视化把树的结构看清再逐步把容量和查询框大小往业务场景靠拢。等这一版跑通后面再拓展成kd树甚至R树思路都会顺畅很多。
