数据结构——四叉树

四叉树（Quadtree）是一种用于表示和管理二维空间的树状数据结构。它将二维空间递归地分割成四个象限，每个象限可以继续分割，以实现对空间的更精细的划分。四叉树通常用于解决空间搜索和查询问题，例如碰撞检测、图像压缩、地理信息系统等领域。

特别适合大规模的广阔室外场景管理。一般来说如果游戏场景是基于地形的（甚至没有高度）（如城市、平原、2D场景），那么适合用四叉树来管理。而如果游戏场景在高度轴上也有大量物体需要管理（如太空、高山），那么适合用八叉树来管理。

#include <iostream>

// 定义二维点的结构体
struct Point {
    float x;
    float y;
    Point(float _x, float _y) : x(_x), y(_y) {}
};

// 定义四叉树节点
struct QuadTreeNode {
    Point point;
    QuadTreeNode* topLeft;
    QuadTreeNode* topRight;
    QuadTreeNode* bottomLeft;
    QuadTreeNode* bottomRight;

    QuadTreeNode(Point _point) : point(_point), topLeft(nullptr), topRight(nullptr), bottomLeft(nullptr), bottomRight(nullptr) {}
};

class QuadTree {
private:
    QuadTreeNode* root;
    int maxDepth; // 最大深度

    // 在指定深度下递归插入节点
    QuadTreeNode* insert(QuadTreeNode* node, Point point, int depth) {
        if (node == nullptr) {
            return new QuadTreeNode(point);
        }

        // 根据点的位置选择象限
        if (point.x < node->point.x && point.y < node->point.y) {
            node->bottomLeft = insert(node->bottomLeft, point, depth + 1);
        } else if (point.x >= node->point.x && point.y < node->point.y) {
            node->bottomRight = insert(node->bottomRight, point, depth + 1);
        } else if (point.x < node->point.x && point.y >= node->point.y) {
            node->topLeft = insert(node->topLeft, point, depth + 1);
        } else {
            node->topRight = insert(node->topRight, point, depth + 1);
        }

        return node;
    }

    // 在指定深度下递归搜索节点
    bool search(QuadTreeNode* node, Point point, int depth) {
        if (node == nullptr) {
            return false;
        }

        if (node->point.x == point.x && node->point.y == point.y) {
            return true;
        }

        // 根据点的位置选择象限
        if (point.x < node->point.x && point.y < node->point.y) {
            return search(node->bottomLeft, point, depth + 1);
        } else if (point.x >= node->point.x && point.y < node->point.y) {
            return search(node->bottomRight, point, depth + 1);
        } else if (point.x < node->point.x && point.y >= node->point.y) {
            return search(node->topLeft, point, depth + 1);
        } else {
            return search(node->topRight, point, depth + 1);
        }
    }

public:
    QuadTree(float minX, float minY, float maxX, float maxY, int depth) : root(nullptr), maxDepth(depth) {}

    // 插入一个点
    void insert(Point point) {
        root = insert(root, point, 0);
    }

    // 搜索一个点是否存在
    bool search(Point point) {
        return search(root, point, 0);
    }
};

int main() {
    QuadTree quadtree(0.0f, 0.0f, 100.0f, 100.0f, 4); // 创建四叉树，定义边界和最大深度

    Point point1(10.0f, 20.0f);
    Point point2(80.0f, 90.0f);

    quadtree.insert(point1); // 插入点1
    quadtree.insert(point2); // 插入点2

    Point searchPoint(80.0f, 90.0f);
    bool found = quadtree.search(searchPoint); // 搜索点2
    if (found) {
        std::cout << "Point found in the quadtree." << std::endl;
    } else {
        std::cout << "Point not found in the quadtree." << std::endl;
    }

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101