有一个区域,区域中有很多矩形,矩形左上角和右下角的坐标分别是(x1,y1),(x2,y2),每个矩形有自己的id,如果通过四叉树的方式用c++实现快速判断,任意一个点的坐标(x,y)在区域中的那个矩形中,返回矩形的id

这个问题可以通过使用四叉树来实现。 四叉树是一种可以快速查找和添加元素的数据结构，它将二维空间划分为四个象限，并且每个象限都是一个四叉树节点。每个节点可以包含许多数据点，如果一个节点中包含的数据点过多，它就会被分裂成四个子节点。四叉树的根节点代表整个区域，每个叶子节点代表一个矩形。

我们可以通过递归地遍历四叉树来找到包含给定点的叶子节点，并返回该叶子节点所代表的矩形的id。下面是一个简单的C++实现：

struct Point {
    double x, y;
};

struct Rectangle {
    int id;
    Point topLeft, bottomRight;
};

class QuadTree {
public:
    QuadTree(Rectangle boundary, int capacity);

    bool insert(Rectangle rect);
    int search(Point p);

private:
    Rectangle boundary;
    int capacity;
    std::vector<Rectangle> points;
    QuadTree *northwest;
    QuadTree *northeast;
    QuadTree *southwest;
    QuadTree *southeast;

    bool contains(Rectangle rect, Point p);
    void subdivide();
};

QuadTree::QuadTree(Rectangle boundary, int capacity)
    : boundary(boundary), capacity(capacity), points(), northwest(nullptr),
      northeast(nullptr), southwest(nullptr), southeast(nullptr) {}

bool QuadTree::insert(Rectangle rect) {
    if (!contains(boundary, rect.topLeft) || !contains(boundary, rect.bottomRight)) {
        return false;
    }

    if (points.size() < capacity) {
        points.push_back(rect);
        return true;
    }

    if (northwest == nullptr) {
        subdivide();
    }

    if (northwest->insert(rect)) return true;
    if (northeast->insert(rect)) return true;
    if (southwest->insert(rect)) return true;
    if (southeast->insert(rect)) return true;

    return false;
}

int QuadTree::search(Point p) {
    if (!contains(boundary, p)) {
        return -1;
    }

    for (Rectangle rect : points) {
        if (contains(rect, p)) {
            return rect.id;
        }
    }

    if (northwest == nullptr) {
        return -1;
    }

    int id = northwest->search(p);
    if (id != -1) return id;

    id = northeast->search(p);
    if (id != -1) return id;

    id = southwest->search(p);
    if (id != -1) return id;

    id = southeast->search(p);
    if (id != -1) return id;

    return -1;
}

bool QuadTree::contains(Rectangle rect, Point p) {
    return (p.x >= rect.topLeft.x && p.x <= rect.bottomRight.x &&
            p.y >= rect.topLeft.y && p.y <= rect.bottomRight.y);
}

void QuadTree::subdivide() {
    double x = boundary.topLeft.x + (boundary.bottomRight.x - boundary.topLeft.x) / 2;
    double y = boundary.topLeft.y + (boundary.bottomRight.y - boundary.topLeft.y) / 2;

    Rectangle nw = Rectangle{0, {boundary.topLeft.x, boundary.topLeft.y}, {x, y}};
    northwest = new QuadTree(nw, capacity);

    Rectangle ne = Rectangle{0, {x, boundary.topLeft.y}, {boundary.bottomRight.x, y}};
    northeast = new QuadTree(ne, capacity);

    Rectangle sw = Rectangle{0, {boundary.topLeft.x, y}, {x, boundary.bottomRight.y}};
    southwest = new QuadTree(sw, capacity);

    Rectangle se = Rectangle{0, {x, y}, {boundary.bottomRight.x, boundary.bottomRight.y}};
    southeast = new QuadTree(se, capacity);
}

使用上述代码，你可以这样调用：

int main() {
    // Create a quadtree with the boundary of (0, 0) to (100, 100)
    QuadTree quadtree(Rectangle{0, Point{0, 0}, Point{100, 100}}, 4);

    // Insert some rectangles into the quadtree
    quadtree.insert(Rectangle{1, Point{10, 10}, Point{30, 30}});
    quadtree.insert(Rectangle{2, Point{40, 20}, Point{60, 40}});
    quadtree.insert(Rectangle{3, Point{70, 50}, Point{90, 70}});

    // Search for the rectangle containing point (25, 25)
    int rectId = quadtree.search(Point{25, 25});

    if (rectId != -1) {
        std::cout << "Point (25, 25) is in rectangle " << rectId << std::endl;
    } else {
        std::cout << "Point (25, 25) is not in any rectangle" << std::endl;
    }

    return 0;
}

这将输出：

Point (25, 25) is in rectangle 1