用vs2022实现四叉树

四叉树是一种常用的空间数据结构，可以用于快速查找、插入和删除二维空间中的对象。下面是使用 C++ 在 Visual Studio 2022 中实现四叉树的示例代码：

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// 二维点结构体
struct Point {
    float x, y;
    Point(float x = 0, float y = 0) : x(x), y(y) {}
};

// 二维矩形结构体
struct Rectangle {
    Point center;
    float width, height;
    Rectangle(Point c = Point(), float w = 0, float h = 0) : center(c), width(w), height(h) {}
};

// 四叉树节点
class QuadtreeNode {
public:
    QuadtreeNode(Rectangle rect, int level = 0, int maxLevel = 5, int maxObjects = 10)
        : m_rect(rect), m_level(level), m_maxLevel(maxLevel), m_maxObjects(maxObjects) {}
    ~QuadtreeNode();

    void insert(Point point); // 插入一个点
    vector<Point> query(Rectangle rect); // 查询在指定矩形内的点

private:
    Rectangle m_rect; // 节点表示的矩形区域
    int m_level; // 节点深度
    int m_maxLevel; // 最大深度
    int m_maxObjects; // 最大存储对象数目
    vector<Point> m_points; // 存储当前节点包含的所有点
    QuadtreeNode* m_children[4] = { nullptr }; // 存储四个子节点

    int getIndex(Point point); // 获取点所在子节点的索引
    void split(); // 分裂当前节点
};

QuadtreeNode::~QuadtreeNode()
{
    for (int i = 0; i < 4; i++) {
        if (m_children[i] != nullptr) {
            delete m_children[i];
            m_children[i] = nullptr;
        }
    }
}

void QuadtreeNode::insert(Point point)
{
    if (m_children[0] != nullptr) { // 如果有子节点，则将点添加到子节点中
        int index = getIndex(point);
        if (index != -1) {
            m_children[index]->insert(point);
            return;
        }
    }

    m_points.push_back(point); // 否则将点添加到当前节点中

    if (m_points.size() > m_maxObjects && m_level < m_maxLevel) { // 如果当前节点存储的点数超过了最大值，并且当前深度小于最大深度，则分裂当前节点
        if (m_children[0] == nullptr) {
            split();
        }

        int i = 0;
        while (i < m_points.size()) {
            int index = getIndex(m_points[i]);
            if (index != -1) {
                m_children[index]->insert(m_points[i]);
                m_points.erase(m_points.begin() + i);
            }
            else {
                i++;
            }
        }
    }
}

vector<Point> QuadtreeNode::query(Rectangle rect)
{
    vector<Point> result;

    if (m_rect.center.x - m_rect.width / 2 > rect.center.x + rect.width / 2 ||
        m_rect.center.x + m_rect.width / 2 < rect.center.x - rect.width / 2 ||
        m_rect.center.y - m_rect.height / 2 > rect.center.y + rect.height / 2 ||
        m_rect.center.y + m_rect.height / 2 < rect.center.y - rect.height / 2) { // 如果矩形与当前节点表示的矩形没有交集，则直接返回空结果
        return result;
    }

    for (Point p : m_points) {
        if (p.x >= rect.center.x - rect.width / 2 &&
            p.x <= rect.center.x + rect.width / 2 &&
            p.y >= rect.center.y - rect.height / 2 &&
            p.y <= rect.center.y + rect.height / 2) { // 如果点在矩形范围内，则将其加入结果中
            result.push_back(p);
        }
    }

    if (m_children[0] != nullptr) { // 如果有子节点，则递归查询子节点
        for (int i = 0; i < 4; i++) {
            vector<Point> childResult = m_children[i]->query(rect);
            result.insert(result.end(), childResult.begin(), childResult.end());
        }
    }

    return result;
}

int QuadtreeNode::getIndex(Point point)
{
    if (point.x < m_rect.center.x && point.y < m_rect.center.y) {
        return 0;
    }
    else if (point.x >= m_rect.center.x && point.y < m_rect.center.y) {
        return 1;
    }
    else if (point.x < m_rect.center.x && point.y >= m_rect.center.y) {
        return 2;
    }
    else if (point.x >= m_rect.center.x && point.y >= m_rect.center.y) {
        return 3;
    }
    else {
        return -1;
    }
}

void QuadtreeNode::split()
{
    float halfWidth = m_rect.width / 2;
    float halfHeight = m_rect.height / 2;

    m_children[0] = new QuadtreeNode(Rectangle(Point(m_rect.center.x - halfWidth / 2, m_rect.center.y - halfHeight / 2), halfWidth, halfHeight), m_level + 1, m_maxLevel, m_maxObjects);
    m_children[1] = new QuadtreeNode(Rectangle(Point(m_rect.center.x + halfWidth / 2, m_rect.center.y - halfHeight / 2), halfWidth, halfHeight), m_level + 1, m_maxLevel, m_maxObjects);
    m_children[2] = new QuadtreeNode(Rectangle(Point(m_rect.center.x - halfWidth / 2, m_rect.center.y + halfHeight / 2), halfWidth, halfHeight), m_level + 1, m_maxLevel, m_maxObjects);
    m_children[3] = new QuadtreeNode(Rectangle(Point(m_rect.center.x + halfWidth / 2, m_rect.center.y + halfHeight / 2), halfWidth, halfHeight), m_level + 1, m_maxLevel, m_maxObjects);
}

下面是一个简单的测试程序，用于演示如何使用四叉树进行点的查询：

int main()
{
    QuadtreeNode root(Rectangle(Point(0, 0), 100, 100));

    // 插入一些点
    root.insert(Point(10, 10));
    root.insert(Point(20, 20));
    root.insert(Point(30, 30));
    root.insert(Point(40, 40));
    root.insert(Point(50, 50));
    root.insert(Point(60, 60));
    root.insert(Point(70, 70));
    root.insert(Point(80, 80));
    root.insert(Point(90, 90));

    // 查询指定矩形内的点
    vector<Point> result = root.query(Rectangle(Point(45, 45), 20, 20));

    // 输出查询结果
    cout << "query result:" << endl;
    for (Point p : result) {
        cout << "(" << p.x << ", " << p.y << ")" << endl;
    }

    return 0;
}

上述代码中，首先创建一个根节点，然后向其中插入一些点，最后查询指定矩形内的点，并输出查询结果。