C++实现四叉树效果(附源码下载)

四叉树也称为四元树或者八叉树，是一种树形数据结构，其特点是每个内部节点有四个子节点或是八个子节点。四叉树在计算机图形学和图像处理领域中得到了广泛应用。本文将讲解如何用 C++ 实现四叉树，并提供源码下载。

实现思路

基本概念

四叉树的基本概念是将二维空间划分为四个象限，每个象限为一个节点。每个节点又可以继续向下划分，直到一个节点的范围内只有一个对象为止。下面是四叉树的示意图：

      <-y
     +------------+
     | 1 |  2 |    |
     |---+----|    |
     | 3 |  4 |    |
     +------------+
            x->

主要思路

根据基本概念，我们可以用递归来实现四叉树的构建过程。具体来说，我们可以按以下步骤进行：

1. 定义一个 QuadTree 类，其中包含四个指向子节点的指针，以及当前节点包含的数据。

2. 当一个节点中的数据超过一定数量时（如 4 个），将该节点拆分为四个子节点。同时将该节点中的数据逐个插入四个子节点中。

3. 对于每个节点，我们将其平面上的范围存储为一个矩形。如果一个矩形与某个节点相交，则该矩形内的所有数据都需要遍历该节点的四个子节点。

4. 对于插入、查找和删除操作，我们同样使用递归来实现。对于插入操作，我们从根节点开始，递归查找一个能够插入该数据的叶子节点，并将数据插入到该叶子节点中。对于查找和删除操作，也是从根节点开始，先查找在哪个节点中，然后在该节点中递归进行查找或删除操作。

示例说明

插入操作

假设我们要在一个四叉树中插入一个矩形，具体操作如下：

1. 从根节点开始，检查当前节点是否有四个子节点。

2. 如果当前节点有四个子节点，则查找该矩形与四个子节点的相交情况。如果矩形与某个子节点相交，则递归到该子节点中进行插入操作。

3. 如果当前节点没有四个子节点，根据具体情况确定是否需要将该节点划分为四个子节点。

4. 如果节点被划分为四个子节点，则将之前保存在节点中的数据逐个插入到四个子节点中。

5. 如果矩形与当前节点不相交，则不需要进行任何操作。

6. 如果矩形与当前节点相交，则将该矩形存储在当前节点中。

查找操作

假设我们要在一个四叉树中查找某个矩形，具体操作如下：

1. 从根节点开始，检查当前节点是否有四个子节点。

2. 如果当前节点有四个子节点，则查找该矩形与四个子节点的相交情况。如果矩形与某个子节点相交，则递归到该子节点中进行查找操作。

3. 如果当前节点没有四个子节点，则返回该节点中包含的所有数据，这些数据都与该节点的范围相交。

示例代码

下面是四叉树实现的主要代码。

QuadTree 类

class QuadTree {
public:
    QuadTree();
    QuadTree(float x, float y, float w, float h, int level, int maxLevel, int maxObjects);

    // 插入矩形
    bool insert(float x, float y, float w, float h);

    // 搜索矩形
    std::vector<Rectangle> search(float x, float y, float w, float h);

    // 删除矩形
    bool remove(float x, float y, float w, float h);

private:
    // 划分子节点
    void split();

    // 获取子节点
    int getIndex(float x, float y, float w, float h);

    // 保存子节点
    void save(int index, float x, float y, float w, float h);

    // 获取相交的子节点
    std::vector<int> getIntersectedIndexes(float x, float y, float w, float h);

    // 删除指定矩形
    bool removeInternal(float x, float y, float w, float h);

    // 矩形
    struct Rectangle {
        float x, y, w, h;
    };

    float m_x, m_y, m_w, m_h;
    int m_level, m_maxLevel, m_maxObjects;
    std::vector<Rectangle> m_objects;
    QuadTree* m_child[4];
};

插入操作

bool QuadTree::insert(float x, float y, float w, float h) {
    // 判断矩形是否超出边界
    if (x + w < m_x || x > m_x + m_w || y + h < m_y || y > m_y + m_h) {
        return false;
    }

    // 判断当前节点是否为叶子节点
    if (!m_child[0] && m_objects.size() < m_maxObjects) {
        m_objects.push_back({ x, y, w, h });
        return true;
    }

    // 判断当前节点是否达到最大深度
    if (m_level >= m_maxLevel) {
        m_objects.push_back({ x, y, w, h });
        return true;
    }

    // 判断是否需要划分子节点
    if (!m_child[0]) {
        split();
    }

    // 插入到相交的子节点中
    for (int i : getIntersectedIndexes(x, y, w, h)) {
        m_child[i]->insert(x, y, w, h);
    }

    return true;
}

查找操作

std::vector<QuadTree::Rectangle> QuadTree::search(float x, float y, float w, float h) {
    std::vector<Rectangle> result;

    // 检查当前节点中包含的矩形
    for (const Rectangle& rect : m_objects) {
        if (rect.x + rect.w >= x && rect.x <= x + w && rect.y + rect.h >= y && rect.y <= y + h) {
            result.push_back(rect);
        }
    }

    // 检查子节点中包含的矩形
    for (int i : getIntersectedIndexes(x, y, w, h)) {
        std::vector<Rectangle> childResult = m_child[i]->search(x, y, w, h);
        result.insert(result.end(), childResult.begin(), childResult.end());
    }

    return result;
}

示例应用

应用场景

四叉树在计算机图形学和图像处理领域中有广泛应用，比如：

1. 游戏开发

2. 图像压缩

3. 卫星图像处理

案例分析

下面是一个简单的应用程序，用于演示四叉树的插入和查找操作：

#include <iostream>
#include "QuadTree.h"

int main() {
    QuadTree quadtree(0, 0, 100, 100, 0, 6, 4);

    std::cout << "Inserting rectangles..." << std::endl;

    // 插入一些矩形
    quadtree.insert(10, 10, 10, 10);
    quadtree.insert(30, 30, 20, 20);
    quadtree.insert(60, 40, 15, 10);
    quadtree.insert(70, 70, 10, 10);
    quadtree.insert(80, 80, 5, 5);

    std::cout << "Searching rectangles..." << std::endl;

    // 查找矩形
    std::vector<QuadTree::Rectangle> result = quadtree.search(25, 25, 25, 25);
    for (const auto& rect : result) {
        std::cout << "Found rectangle: x=" << rect.x << ", y=" << rect.y << ", w=" << rect.w << ", h=" << rect.h << std::endl;
    }

    return 0;
}

运行结果

Inserting rectangles...
Searching rectangles...
Found rectangle: x=30, y=30, w=20, h=20

结语

本篇文章介绍了如何使用 C++ 实现四叉树，并提供了示例代码和应用程序。对于计算机图形学和图像处理领域的开发人员，掌握四叉树的实现和应用方法非常重要。希望本文对读者有所帮助。