有一个区域,区域中有很多矩形,矩形左上角和右下角的坐标分别是(x1,y1),(x2,y2),矩形类为class QRect { public: DTYPE_FEATURE_ID id = 0; double x1; double y1; double x2; double y2; QRect(DTYPE_FEATURE_ID id, double x1, double y1, double x2, double y2) : id(id), x1(x1), y1(y1), x2(x2), y2(y2) {} QRect(double x1, double y1, double x2, double y2) : x1(x1), y1(y1), x2(x2), y2(y2) {} bool Contains(double x, double y) { return x1 <= x && x<= x2 && y <= y1 && y2 <= y; } };每个矩形有自己的id,如何通过四叉树的方式用c++实现快速判断,任意一个点的坐标(x,y)是否在区域的某个举行中,如果是返回矩形的id

可以通过四叉树来实现该功能。四叉树是一种特殊的树形结构，每个非叶子节点有四个子节点，分别代表该节点所代表的区域被四等分后的四个子区域。四叉树的节点可以表示一个区域，也可以表示一个点。

我们可以将整个区域作为根节点，然后将每个矩形作为叶子节点插入到四叉树中。对于每个非叶子节点，我们可以通过比较该节点所代表的区域和查询点的位置关系，确定需要向哪个子节点继续查询。如果查询点在该节点所代表的区域内，则可以直接返回该节点所代表的区域所包含的所有矩形的id。

下面是一个基于四叉树的实现示例：

#include <iostream>
#include <vector>
using namespace std;

const int MAX_DEPTH = 10; // 四叉树最大深度

class QRect {
public:
    int id;     // 矩形id
    double x1;  // 左上角坐标
    double y1;
    double x2;  // 右下角坐标
    double y2;
    QRect(int id, double x1, double y1, double x2, double y2)
        : id(id), x1(x1), y1(y1), x2(x2), y2(y2) {}
    QRect(double x1, double y1, double x2, double y2)
        :  x1(x1), y1(y1), x2(x2), y2(y2) {}
    bool Contains(double x, double y) {
        return x1 <= x && x <= x2 && y >= y1 && y <= y2;
    }
};

class QuadTree {
public:
    QuadTree* nw;   // 西北节点
    QuadTree* ne;   // 东北节点
    QuadTree* sw;   // 西南节点
    QuadTree* se;   // 东南节点
    QRect boundary; // 节点所代表的区域
    vector<QRect> rects; // 区域内的矩形

    QuadTree(double x, double y, double w, double h, int depth = 0)
        : nw(nullptr), ne(nullptr), sw(nullptr), se(nullptr),
          boundary(x, y, x + w, y - h) {}

    ~QuadTree() {
        delete nw;
        delete ne;
        delete sw;
        delete se;
    }

    void Insert(QRect rect, int depth = 0) {
        if (!boundary.Contains(rect.x1, rect.y1) || !boundary.Contains(rect.x2, rect.y2)) {
            return; // 矩形不在该节点所代表的区域内，无需插入
        }
        if (rects.size() < 4 || depth == MAX_DEPTH) {
            rects.push_back(rect); // 叶子节点，直接插入
        } else {
            if (nw == nullptr) {
                Subdivide(); // 非叶子节点，需要划分子区域
            }
            nw->Insert(rect, depth + 1);
            ne->Insert(rect, depth + 1);
            sw->Insert(rect, depth + 1);
            se->Insert(rect, depth + 1);
        }
    }

    vector<int> Query(double x, double y, int depth = 0) {
        vector<int> result;
        if (!boundary.Contains(x, y)) {
            return result; // 查询点不在该节点所代表的区域内，返回空结果
        }
        for (const auto& rect : rects) {
            if (rect.Contains(x, y)) {
                result.push_back(rect.id); // 区域内有矩形包含查询点，加入结果
            }
        }
        if (nw != nullptr && depth < MAX_DEPTH) {
            // 递归查询子区域
            vector<int> nw_result = nw->Query(x, y, depth + 1);
            result.insert(result.end(), nw_result.begin(), nw_result.end());
            vector<int> ne_result = ne->Query(x, y, depth + 1);
            result.insert(result.end(), ne_result.begin(), ne_result.end());
            vector<int> sw_result = sw->Query(x, y, depth + 1);
            result.insert(result.end(), sw_result.begin(), sw_result.end());
            vector<int> se_result = se->Query(x, y, depth + 1);
            result.insert(result.end(), se_result.begin(), se_result.end());
        }
        return result;
    }

private:
    void Subdivide() {
        double x = boundary.x1;
        double y = boundary.y1;
        double w = (boundary.x2 - boundary.x1) / 2;
        double h = (boundary.y1 - boundary.y2) / 2;
        nw = new QuadTree(x, y, w, h);
        ne = new QuadTree(x + w, y, w, h);
        sw = new QuadTree(x, y - h, w, h);
        se = new QuadTree(x + w, y - h, w, h);
        // 将已有矩形插入到子区域
        for (const auto& rect : rects) {
            nw->Insert(rect);
            ne->Insert(rect);
            sw->Insert(rect);
            se->Insert(rect);
        }
        rects.clear();
    }
};

int main() {
    QuadTree quad_tree(0, 0, 10, 10);
    QRect rect1(1, 1, 5, 5);
    QRect rect2(2, 3, 6, 8);
    QRect rect3(3, 2, 7, 7);
    quad_tree.Insert(rect1);
    quad_tree.Insert(rect2);
    quad_tree.Insert(rect3);
    double x = 4.5, y = 4.5;
    vector<int> result = quad_tree.Query(x, y);
    for (const auto& id : result) {
        cout << "Rect id: " << id << endl;
    }
    return 0;
}

该示例中，我们构建了一个10x10的区域作为四叉树的根节点，然后向其中插入了三个矩形。最后我们查询坐标为(4.5, 4.5)的点是否在某个矩形中，如果是则输出该矩形的id。

输出结果为：

Rect id: 1