四叉树 (Quadtree)

Published: Wed Feb 18 2026 | Modified: Sat Feb 07 2026 , 3 minutes reading.

四叉树：变焦镜头

算法背后的故事：像素化的地图

想象你在绘制一张世界地图。

太平洋是巨大的，大部分是空旷的蓝色海水。
东京很小，但挤满了数百万条街道和建筑物。

如果你使用等大小的正方形网格（矩阵）来存储这张地图，你就会遇到问题。为了捕捉东京的细节，你的网格单元必须非常小（1 米）。但这意味你需要数万亿个微小的蓝色方块来存储空旷的太平洋。这是对内存的巨大浪费。

四叉树 (Quadtree) 通过“变得聪明”来解决这个问题。它看着海洋说：“这整块 1000 公里的区域都是蓝色的。我把它存为一个大方块。”然后它看着东京说：“这里很复杂。我把它切成 4 个小方块。够了吗？不够？那我再把这几个小方块切成 4 份。”

它根据数据的密度自适应地调整分辨率。

为什么需要它？

碰撞检测 (游戏)： 不要检查子弹是否击中了游戏世界里的每一个物体，只检查与子弹处于同一个四叉树叶子节点里的物体。
图像压缩： 通过将大块相似颜色分组来存储图像（概念上类似于 JPEG 的工作原理）。
位置服务： “查找我方圆 1 公里内的所有 Uber 司机。”

算法是如何“思考”的

这个算法是一个递归分割者。

盒子： 每个节点代表一个矩形区域（边界框）。
容量： 每个节点有一个最大容量（例如 4 个点）。
分裂：
- 将一个点插入节点。
- 如果节点超过了容量，它就细分为 4 个孩子：西北、东北、西南、东南。
- 它将现有的点移动到正确的孩子节点中。

工程决策：平衡

深度限制： 如果你有 100 个点完全重叠在一起（精确副本），四叉树会试图无限分裂直到崩溃（栈溢出）。现实世界的实现会设置一个“最大深度”来阻止这种情况。
重建： 四叉树非常适合静态数据。如果物体不断移动（像在游戏中一样），每一帧都重建树可能会很慢。在这种情况下，松散网格或动态 B 树可能是更好的选择。

实现参考 (Python)

class Rectangle:
    def __init__(self, x, y, w, h):
        self.x, self.y, self.w, self.h = x, y, w, h
    
    def contains(self, point):
        return (self.x <= point.x < self.x + self.w and
                self.y <= point.y < self.y + self.h)

class Point:
    def __init__(self, x, y):
        self.x, self.y = x, y

class Quadtree:
    def __init__(self, boundary, capacity=4):
        self.boundary = boundary # 矩形区域
        self.capacity = capacity
        self.points = []
        self.divided = False
        self.nw = self.ne = self.sw = self.se = None

    def subdivide(self):
        x, y, w, h = self.boundary.x, self.boundary.y, self.boundary.w, self.boundary.h
        mw, mh = w/2, h/2
        
        self.nw = Quadtree(Rectangle(x, y, mw, mh), self.capacity)
        self.ne = Quadtree(Rectangle(x + mw, y, mw, mh), self.capacity)
        self.sw = Quadtree(Rectangle(x, y + mh, mw, mh), self.capacity)
        self.se = Quadtree(Rectangle(x + mw, y + mh, mw, mh), self.capacity)
        self.divided = True

    def insert(self, point):
        if not self.boundary.contains(point):
            return False

        if len(self.points) < self.capacity:
            self.points.append(point)
            return True

        if not self.divided:
            self.subdivide()

        return (self.nw.insert(point) or self.ne.insert(point) or
                self.sw.insert(point) or self.se.insert(point))

    def query(self, range_rect, found):
        # 查找 range_rect 范围内的所有点
        # 假设 Rectangle 类有一个 intersects() 方法
        if not self.boundary.intersects(range_rect): 
            return
        
        for p in self.points:
            if range_rect.contains(p):
                found.append(p)
        
        if self.divided:
            self.nw.query(range_rect, found)
            self.ne.query(range_rect, found)
            self.sw.query(range_rect, found)
            self.se.query(range_rect, found)

小结

四叉树教会我们：细节是需要付费的。我们不应该花费内存去描述空旷的空间。通过只将资源（节点）集中在复杂性所在的地方，我们可以以极小的代价表示宏大的世界。它是“细节层次 (LOD)”的终极算法。

Luke Sun