C++ 四叉树数据结构原理与实现

什么是四叉树（Quadtree）？

四叉树是一种树状数据结构，其每个内部节点恰好有四个子节点。它主要用于对二维空间进行递归细分。你可以将其类比为一维空间中的二叉树，或者是三维空间中的八叉树（Octree）。

核心原理

四叉树的基本思想是：如果一个区域内包含的数据量超过了预设的阈值（容量），就将该区域等分为四个象限，并将数据分配到相应的子象限中。

通常，这四个象限被命名为：

1. NW (North-West)：左上象限
2. NE (North-East)：右上象限
3. SW (South-West)：左下象限
4. SE (South-East)：右下象限

四叉树的类型包括：

• 点四叉树 (Point Quadtree)：用于存储二维点坐标。
• 区域四叉树 (Region Quadtree)：常用于图像处理，根据颜色一致性划分。
• 物体四叉树 (MX-CIF Quadtree)：用于存储具有形状（如矩形、圆）的物体。

为什么要使用四叉树？

想象一个包含 10,000 个单位的游戏地图。如果你想检查哪些单位发生了碰撞，最直观的方法是两两比对。

• 朴素算法复杂度：O(n^2)，即 10,000 * 10,000 = 100,000,000 次检查。
• 四叉树算法复杂度：通过将物体划分到不同的空间区域，你只需要检查同一区域内的物体。理想情况下，复杂度可降至 O(nlog n)。

示例（c++）

#include <iostream>
#include <vector>
#include <memory>
#include <random>
#include <iomanip>

// --- 基础结构定义 ---
// 表示二维平面上的点
struct Point {
    double x, y;
    int id; // 增加 ID 方便辨认
};

// 轴对齐边界框 (Axis-Aligned Bounding Box)
struct AABB {
    double x, y, w, h; // 中心点 (x,y)，半宽 w，半高 h
    // 检查一个点是否在该范围内
    {
         (p.x >= x - w && p.x <= x + w && p.y >= y - h && p.y <= y + h);
    }
    
    {
         !(other.x - other.w > x + w || other.x + other.w < x - w || other.y - other.h > y + h || other.y + other.h < y - h);
    }
};


  {
:
      CAPACITY = ; 
    AABB boundary; 
    std::vector<Point> points; 
     divided = ; 
    
    std::unique_ptr<QuadTree> nw, ne, sw, se;

    
    {
         x = boundary.x;
         y = boundary.y;
         w = boundary.w / ;
         h = boundary.h / ;
        nw = std::<QuadTree>(AABB{x - w, y + h, w, h});
        ne = std::<QuadTree>(AABB{x + w, y + h, w, h});
        sw = std::<QuadTree>(AABB{x - w, y - h, w, h});
        se = std::<QuadTree>(AABB{x + w, y - h, w, h});
        divided = ;
    }

:
    (AABB boundary) : (boundary) {}

    
    {
        
         (!boundary.(p))  ;
        
         (points.() < CAPACITY && !divided) {
            points.(p);
             ;
        }
        
         (!divided) ();
        
         (nw->(p))  ;
         (ne->(p))  ;
         (sw->(p))  ;
         (se->(p))  ;
         ;
    }

    
    {
        
         (!boundary.(range)) ;
        
         ( & p : points) {
             (range.(p)) {
                found.(p);
            }
        }
        
         (divided) {
            nw->(range, found);
            ne->(range, found);
            sw->(range, found);
            se->(range, found);
        }
    }
};


{
    
    AABB worldBoundary = {, , , };
    ;

    
    ; 
    ;
    std::cout <<  << std::endl;
     ( i = ; i < ; ++i) {
        Point p = {(rng), (rng), i};
        qt.(p);
    }

    
    
    AABB searchRange = {, , , };
    std::vector<Point> results;
    qt.(searchRange, results);

    
    std::cout <<  << std::endl;
    std::cout <<  << std::endl;
    std::cout <<  << results.() <<  << std::endl;
    std::cout <<  << std::endl;
    std::cout <<  << std::endl;
     ( & p : results) {
        std::cout << p.id <<  << std::fixed << std::() << p.x <<  << p.y << std::endl;
    }
     ;
}