有一个区域,区域中有很多矩形,矩形左上角和右下角的坐标分别是(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

可以通过四叉树来实现快速判断一个点落在哪个矩形中。

首先，定义四叉树的节点类型，包含矩形信息及四个子节点指针：

struct QuadTreeNode {
    QRect rect; // 矩形信息
    QuadTreeNode* children[4]; // 四个子节点指针
    QuadTreeNode(const QRect& rect) : rect(rect) {
        memset(children, 0, sizeof(children));
    }
};

接着，定义四叉树的构建函数，这里采用递归方式实现。如果当前节点所代表的矩形不包含目标点，则返回空指针，否则检查子节点中是否有包含目标点的矩形，如果有则递归进入该子节点，否则返回当前节点。

QuadTreeNode* buildQuadTree(const std::vector<QRect>& rects, const QRect& boundary) {
    QuadTreeNode* node = new QuadTreeNode(boundary);
    if (rects.empty()) return node;
    if (rects.size() == 1) {
        node->rect = rects[0];
        return node;
    }
    // 将 boundary 分成四个子区域
    double xmid = (boundary.x1 + boundary.x2) / 2.0;
    double ymid = (boundary.y1 + boundary.y2) / 2.0;
    QRect nw(boundary.x1, ymid, xmid, boundary.y2);
    QRect ne(xmid, ymid, boundary.x2, boundary.y2);
    QRect sw(boundary.x1, boundary.y1, xmid, ymid);
    QRect se(xmid, boundary.y1, boundary.x2, ymid);
    std::vector<QRect> nwRects, neRects, swRects, seRects;
    for (const QRect& r : rects) {
        if (nw.Contains(r.x1, r.y2) || nw.Contains(r.x2, r.y1) || nw.Contains(r.x2, r.y2)) {
            nwRects.push_back(r);
        } else if (ne.Contains(r.x1, r.y2) || ne.Contains(r.x2, r.y1) || ne.Contains(r.x1, r.y1)) {
            neRects.push_back(r);
        } else if (sw.Contains(r.x1, r.y2) || sw.Contains(r.x2, r.y1) || sw.Contains(r.x2, r.y2)) {
            swRects.push_back(r);
        } else if (se.Contains(r.x1, r.y2) || se.Contains(r.x2, r.y1) || se.Contains(r.x1, r.y1)) {
            seRects.push_back(r);
        }
    }
    if (!nwRects.empty()) node->children[0] = buildQuadTree(nwRects, nw);
    if (!neRects.empty()) node->children[1] = buildQuadTree(neRects, ne);
    if (!swRects.empty()) node->children[2] = buildQuadTree(swRects, sw);
    if (!seRects.empty()) node->children[3] = buildQuadTree(seRects, se);
    return node;
}

最后，定义一个函数用来查询目标点所在的矩形的id，也是采用递归方式实现。如果当前节点为叶子节点，则返回该节点代表的矩形的id；否则检查子节点中是否有包含目标点的矩形，如果有则递归进入该子节点，否则返回当前节点代表的矩形的id。

DTYPE_FEATURE_ID queryQuadTree(QuadTreeNode* node, double x, double y) {
    if (!node || !node->rect.Contains(x, y)) return 0;
    if (!node->children[0] && !node->children[1] && !node->children[2] && !node->children[3]) {
        return node->rect.id;
    }
    for (int i = 0; i < 4; ++i) {
        DTYPE_FEATURE_ID id = queryQuadTree(node->children[i], x, y);
        if (id) return id;
    }
    return node->rect.id;
}

完整代码如下：

#include <cstring>
#include <vector>

typedef int DTYPE_FEATURE_ID;

struct QRect {
    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;
    }
};

struct QuadTreeNode {
    QRect rect;
    QuadTreeNode* children[4];
    QuadTreeNode(const QRect& rect) : rect(rect) {
        memset(children, 0, sizeof(children));
    }
};

QuadTreeNode* buildQuadTree(const std::vector<QRect>& rects, const QRect& boundary) {
    QuadTreeNode* node = new QuadTreeNode(boundary);
    if (rects.empty()) return node;
    if (rects.size() == 1) {
        node->rect = rects[0];
        return node;
    }
    double xmid = (boundary.x1 + boundary.x2) / 2.0;
    double ymid = (boundary.y1 + boundary.y2) / 2.0;
    QRect nw(boundary.x1, ymid, xmid, boundary.y2);
    QRect ne(xmid, ymid, boundary.x2, boundary.y2);
    QRect sw(boundary.x1, boundary.y1, xmid, ymid);
    QRect se(xmid, boundary.y1, boundary.x2, ymid);
    std::vector<QRect> nwRects, neRects, swRects, seRects;
    for (const QRect& r : rects) {
        if (nw.Contains(r.x1, r.y2) || nw.Contains(r.x2, r.y1) || nw.Contains(r.x2, r.y2)) {
            nwRects.push_back(r);
        } else if (ne.Contains(r.x1, r.y2) || ne.Contains(r.x2, r.y1) || ne.Contains(r.x1, r.y1)) {
            neRects.push_back(r);
        } else if (sw.Contains(r.x1, r.y2) || sw.Contains(r.x2, r.y1) || sw.Contains(r.x2, r.y2)) {
            swRects.push_back(r);
        } else if (se.Contains(r.x1, r.y2) || se.Contains(r.x2, r.y1) || se.Contains(r.x1, r.y1)) {
            seRects.push_back(r);
        }
    }
    if (!nwRects.empty()) node->children[0] = buildQuadTree(nwRects, nw);
    if (!neRects.empty()) node->children[1] = buildQuadTree(neRects, ne);
    if (!swRects.empty()) node->children[2] = buildQuadTree(swRects, sw);
    if (!seRects.empty()) node->children[3] = buildQuadTree(seRects, se);
    return node;
}

DTYPE_FEATURE_ID queryQuadTree(QuadTreeNode* node, double x, double y) {
    if (!node || !node->rect.Contains(x, y)) return 0;
    if (!node->children[0] && !node->children[1] && !node->children[2] && !node->children[3]) {
        return node->rect.id;
    }
    for (int i = 0; i < 4; ++i) {
        DTYPE_FEATURE_ID id = queryQuadTree(node->children[i], x, y);
        if (id) return id;
    }
    return node->rect.id;
}

int main() {
    std::vector<QRect> rects = {
        QRect(1, 0, 0, 1, 1),
        QRect(2, 1, 1, 2, 2),
        QRect(3, 2, 2, 3, 3),
        QRect(4, 3, 3, 4, 4),
    };
    QuadTreeNode* root = buildQuadTree(rects, QRect(0, 0, 4, 4));
    double x = 2.5, y = 3.5;
    DTYPE_FEATURE_ID id = queryQuadTree(root, x, y);
    printf("Point (%g, %g) is in rect #%d\n", x, y, id);
    return 0;
}