四叉树通过递归划分二维空间提升查询效率，每个节点最多含四个子节点，适用于碰撞检测与区域查询；八叉树将其扩展至三维，划分为八个子节点，需处理更多内存与分裂控制；两者均用于快速排除无关对象，配合细粒度检测实现高效空间索引。
在C++中实现四叉树（Quadtree）或八叉树（Octree），主要用于空间数据索引和碰撞检测，核心在于递归划分空间并管理子区域中的对象。这类结构能显著提升查询效率，比如判断哪些物体可能相交、查找某区域内的所有点等。
四叉树的基本原理与实现
四叉树适用于二维空间，每个节点代表一个矩形区域，最多有四个子节点，分别对应左上、右上、左下、右下四个象限。
关键设计点：
- 节点包含边界（x, y, width, height）
- 存储当前节点内的对象（如点或小范围物体）
- 设定最大容量，超过后分裂并迁移对象到子节点
- 提供插入、查询、碰撞检测等接口
示例代码片段（简化版）：
立即学习“C++免费学习笔记（深入）”；
class Quadtree {
private:
static const int CAPACITY = 4;
bool divided = false;
float x, y, w, h;
std::vector points;
Quadtree* northWest = nullptr;
Quadtree* northEast = nullptr;
Quadtree* southWest = nullptr;
Quadtree* southEast = nullptr;
bool contains(float qx, float qy, float qw, float qh, float px, float py) {
return px >= qx && px < qx + qw && py >= qy && py < qy + qh;
}
void split() {
float subW = w / 2;
float subH = h / 2;
northWest = new Quadtree(x, y, subW, subH);
northEast = new Quadtree(x + subW, y, subW, subH);
southWest = new Quadtree(x, y + subH, subW, subH);
southEast = new Quadtree(x + subW, y + subH, subW, subH);
divided = true;
}public:
Quadtree(float x, float y, float w, float h) : x(x), y(y), w(w), h(h) {}
bool insert(float px, float py) {
if (!contains(x, y, w, py)) return false;
if (points.size() < CAPACITY && !divided) {
points.push_back({px, py});
return true;
}
if (!divided) split();
northWest->insert(px, py);
northEast->insert(px, py);
southWest->insert(px, py);
southEast->insert(px, py);
return true;
}
void query(float rx, float ry, float rw, float rh, std::vectorzuojiankuohaophpcnPointyoujiankuohaophpcn& results) {
if (!doRectsIntersect(rx, ry, rw, rh, x, y, w, h)) return;
for (auto& p : points) {
if (contains(rx, ry, rw, rh, p.x, p.y)) {
results.push_back(p);
}
}
if (divided) {
northWest->query(rx, ry, rw, rh, results);
northEast->query(rx, ry, rw, rh, results);
southWest->query(rx, ry, rw, rh, results);
southEast->query(rx, ry, rw, rh, results);
}
}};
八叉树的扩展思路
八叉树是四叉树在三维空间的自然延伸，每个节点划分为八个子立方体。实现方式类似，但需处理三个维度的分割。
- 边界由 (x, y, z, width, height, depth) 定义
- 八个子节点对应 xyz 各方向的组合（如 minX,minY,minZ 到 maxX,maxY,maxZ）
- 插入和查询逻辑增加一层 z 轴判断
由于维度上升，内存开销更大，应更谨慎设置最大深度或对象容量，避免过度分裂。
用于碰撞检测的优化技巧
直接用四叉树/八叉树做精确碰撞检测不现实，它们的作用是快速排除不可能相交的对象对。
- 先调用 query 获取目标区域附近的所有候选对象
- 再对这些候选者进行细粒度碰撞判断（如 AABB、圆形距离、多边形相交）
- 动态场景中，每帧重建树成本高，可采用“惰性更新”：只标记变动，批量重插
- 移动物体可在树中保留引用，并在其位置变化时触发重新插入
基本上就这些。结构清晰、控制好分裂条件、配合合适的查询策略，四叉树和八叉树能在空间索引和碰撞粗检中发挥很好作用。实际项目中也可考虑 R-Tree 或 BVH 等更高级结构，但在多数2D/简单3D场景下，四叉树已足够高效。
