C++怎么实现一个四叉树/八叉树_C++空间数据索引与碰撞检测中的数据结构-C++-PHP中文网

C++怎么实现一个四叉树/八叉树_C++空间数据索引与碰撞检测中的数据结构

尼克

发布： 2025-11-20 16:09:14

原创

936人浏览过

四叉树通过递归划分二维空间提升查询效率，每个节点最多含四个子节点，适用于碰撞检测与区域查询；八叉树将其扩展至三维，划分为八个子节点，需处理更多内存与分裂控制；两者均用于快速排除无关对象，配合细粒度检测实现高效空间索引。

c++怎么实现一个四叉树/八叉树_c++空间数据索引与碰撞检测中的数据结构

在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<Point> points;
    Quadtree* northWest = nullptr;
    Quadtree* northEast = nullptr;
    Quadtree* southWest = nullptr;
    Quadtree* southEast = nullptr;
<pre class='brush:php;toolbar:false;'>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::vector<Point>& 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);
    }
}

登录后复制

};