我有一个区域,区域中有很多矩形,每个矩形有自己的id,现在给出一个点,如何通过四叉树的方式快速找到点在哪个矩形中返回矩形id,用c++实现

首先，需要实现一个四叉树的数据结构，可以使用递归的方式来构建四叉树。每个节点包含四个子节点，分别表示左上、右上、左下和右下四个象限。

然后，对于每个矩形，可以递归地将其放入四叉树中。如果一个矩形完全包含在某个节点中，则将其放入该节点中，否则将其放入父节点中。

最后，对于给定的点，可以从根节点开始递归查找，直到找到包含该点的叶子节点。然后返回该节点中包含的矩形的id即可。

以下是一个简单的实现示例：

#include <iostream>
#include <vector>

using namespace std;

struct Point {
    double x, y;
};

struct Rect {
    int id;
    double x1, y1, x2, y2;
};

class QuadTree {
public:
    QuadTree(double x1, double y1, double x2, double y2) {
        this->x1 = x1;
        this->y1 = y1;
        this->x2 = x2;
        this->y2 = y2;
        this->is_leaf = true;
    }

    void add(Rect rect) {
        if (rect.x1 >= x1 && rect.y1 >= y1 && rect.x2 <= x2 && rect.y2 <= y2) {
            rects.push_back(rect);
        } else {
            if (is_leaf) {
                split();
            }
            if (rect.x2 < mid_x && rect.y2 < mid_y) {
                nw->add(rect);
            } else if (rect.x1 > mid_x && rect.y2 < mid_y) {
                ne->add(rect);
            } else if (rect.x2 < mid_x && rect.y1 > mid_y) {
                sw->add(rect);
            } else if (rect.x1 > mid_x && rect.y1 > mid_y) {
                se->add(rect);
            } else {
                rects.push_back(rect);
            }
        }
    }

    int find(Point point) {
        if (is_leaf) {
            for (auto rect : rects) {
                if (point.x >= rect.x1 && point.x <= rect.x2 && point.y >= rect.y1 && point.y <= rect.y2) {
                    return rect.id;
                }
            }
            return -1;
        } else {
            if (point.x < mid_x && point.y < mid_y) {
                return nw->find(point);
            } else if (point.x > mid_x && point.y < mid_y) {
                return ne->find(point);
            } else if (point.x < mid_x && point.y > mid_y) {
                return sw->find(point);
            } else {
                return se->find(point);
            }
        }
    }

private:
    QuadTree *nw, *ne, *sw, *se;
    double x1, y1, x2, y2;
    double mid_x = (x1 + x2) / 2;
    double mid_y = (y1 + y2) / 2;
    bool is_leaf;
    vector<Rect> rects;

    void split() {
        nw = new QuadTree(x1, y1, mid_x, mid_y);
        ne = new QuadTree(mid_x, y1, x2, mid_y);
        sw = new QuadTree(x1, mid_y, mid_x, y2);
        se = new QuadTree(mid_x, mid_y, x2, y2);
        for (auto rect : rects) {
            add(rect);
        }
        rects.clear();
        is_leaf = false;
    }
};

int main() {
    QuadTree quad_tree(0, 0, 100, 100);
    quad_tree.add({1, 10, 10, 20, 20});
    quad_tree.add({2, 30, 30, 40, 40});
    quad_tree.add({3, 50, 50, 60, 60});
    quad_tree.add({4, 70, 70, 80, 80});

    Point point = {55, 55};
    int rect_id = quad_tree.find(point);
    cout << rect_id << endl;  // Output: 3

    return 0;
}