我有一个区域 区域中有很多矩形,用左上和右下两个点的坐标记录,每个矩形有自己的id.现在我有一个点,我想快速判断这个点在区域的哪个矩形中,如何通过c++用四叉树实现

四叉树是一种常用的空间索引结构，可以用于快速地查询某个点属于哪个矩形。四叉树的基本思想是将区域递归地划分为四个象限，每个节点都代表一个区域，同时保存该区域中所有的矩形信息。划分的过程可以采用递归的方式进行，当某个节点中矩形的数量达到一定的阈值或者节点的深度达到一定的限制时，就停止划分。以下是一个基本的四叉树实现代码：

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

struct QuadTreeNode {
    QuadTreeNode *children[4];
    vector<Rect> rects;
    double x1, y1, x2, y2;
};

class QuadTree {
public:
    QuadTree(double x1, double y1, double x2, double y2, int maxDepth, int maxRects);
    ~QuadTree();
    void insert(Rect rect);
    int search(double x, double y);

private:
    QuadTreeNode *root;
    int maxDepth;
    int maxRects;

    void subdivide(QuadTreeNode *node);
};

QuadTree::QuadTree(double x1, double y1, double x2, double y2, int maxDepth, int maxRects) {
    root = new QuadTreeNode();
    root->x1 = x1;
    root->y1 = y1;
    root->x2 = x2;
    root->y2 = y2;
    this->maxDepth = maxDepth;
    this->maxRects = maxRects;
    subdivide(root);
}

QuadTree::~QuadTree() {
    // TODO: release memory
}

void QuadTree::insert(Rect rect) {
    QuadTreeNode *node = root;
    while (node != NULL) {
        if (node->children[0] == NULL && node->rects.size() < maxRects) {
            // Leaf node, add the rectangle to the list
            node->rects.push_back(rect);
            break;
        } else if (node->children[0] == NULL) {
            // Leaf node, but the list is full, subdivide
            subdivide(node);
        }

        // Find the quadrant that the rectangle belongs to
        int quadrant = -1;
        double xm = (node->x1 + node->x2) / 2;
        double ym = (node->y1 + node->y2) / 2;
        if (rect.x1 < xm && rect.y1 < ym) {
            quadrant = 0;
        } else if (rect.x1 >= xm && rect.y1 < ym) {
            quadrant = 1;
        } else if (rect.x1 >= xm && rect.y1 >= ym) {
            quadrant = 2;
        } else if (rect.x1 < xm && rect.y1 >= ym) {
            quadrant = 3;
        }

        node = node->children[quadrant];
    }
}

int QuadTree::search(double x, double y) {
    QuadTreeNode *node = root;
    while (node != NULL) {
        for (int i = 0; i < node->rects.size(); i++) {
            if (node->rects[i].x1 <= x && x <= node->rects[i].x2 &&
                node->rects[i].y1 <= y && y <= node->rects[i].y2) {
                return node->rects[i].id;
            }
        }

        int quadrant = -1;
        double xm = (node->x1 + node->x2) / 2;
        double ym = (node->y1 + node->y2) / 2;
        if (x < xm && y < ym) {
            quadrant = 0;
        } else if (x >= xm && y < ym) {
            quadrant = 1;
        } else if (x >= xm && y >= ym) {
            quadrant = 2;
        } else if (x < xm && y >= ym) {
            quadrant = 3;
        }

        node = node->children[quadrant];
    }

    return -1;
}

void QuadTree::subdivide(QuadTreeNode *node) {
    double xm = (node->x1 + node->x2) / 2;
    double ym = (node->y1 + node->y2) / 2;

    node->children[0] = new QuadTreeNode();
    node->children[0]->x1 = node->x1;
    node->children[0]->y1 = node->y1;
    node->children[0]->x2 = xm;
    node->children[0]->y2 = ym;

    node->children[1] = new QuadTreeNode();
    node->children[1]->x1 = xm;
    node->children[1]->y1 = node->y1;
    node->children[1]->x2 = node->x2;
    node->children[1]->y2 = ym;

    node->children[2] = new QuadTreeNode();
    node->children[2]->x1 = xm;
    node->children[2]->y1 = ym;
    node->children[2]->x2 = node->x2;
    node->children[2]->y2 = node->y2;

    node->children[3] = new QuadTreeNode();
    node->children[3]->x1 = node->x1;
    node->children[3]->y1 = ym;
    node->children[3]->x2 = xm;
    node->children[3]->y2 = node->y2;

    // Move the rectangles into the children
    for (int i = 0; i < node->rects.size(); i++) {
        int quadrant = -1;
        if (node->rects[i].x1 < xm && node->rects[i].y1 < ym) {
            quadrant = 0;
        } else if (node->rects[i].x1 >= xm && node->rects[i].y1 < ym) {
            quadrant = 1;
        } else if (node->rects[i].x1 >= xm && node->rects[i].y1 >= ym) {
            quadrant = 2;
        } else if (node->rects[i].x1 < xm && node->rects[i].y1 >= ym) {
            quadrant = 3;
        }

        node->children[quadrant]->rects.push_back(node->rects[i]);
    }

    node->rects.clear();
}

在这个示例中，Rect 结构体用于表示矩形，包括左上角和右下角的坐标以及矩形的 id。QuadTreeNode 结构体用于表示四叉树的节点，包括四个子节点和该节点中包含的矩形列表。QuadTree 类用于管理整个四叉树，包括初始化、插入和查询等操作。构造函数 QuadTree() 用于初始化根节点和一些参数，subdivide() 函数用于递归地划分区域，insert() 函数用于插入一个新的矩形，search() 函数用于查询某个点所在的矩形。

使用四叉树进行查询时，从根节点开始递归，如果当前节点是叶子节点，则在其中的所有矩形中查找是否包含该点；否则，根据点所在的象限找到下一个子节点，并继续递归。查询结束后返回该点所在的矩形的 id。