有一个区域,区域中有很多矩形,每个矩形都有自己的id,如何用c++通过四叉树遍历实现输入一个点,判断这个点是否在矩形中如果是返回对应矩形的id

可以通过以下步骤实现：

1. 定义一个矩形类，包括矩形的坐标、宽度和高度等信息，以及矩形的id。

2. 定义一个四叉树节点类，包括节点的坐标、宽度和高度等信息，以及该节点包含的矩形列表和四个子节点。

3. 构建四叉树，将矩形按照位置信息逐一加入到四叉树中。

4. 对于输入的点，从四叉树的根节点开始递归遍历，判断点是否在当前节点的范围内，如果是，则遍历当前节点包含的矩形列表，判断点是否在其中任意一个矩形内，如果是，则返回该矩形的id；如果不是，则递归遍历当前节点的四个子节点。

以下是一个示例代码实现：

#include <iostream>
#include <vector>

using namespace std;

// 矩形类
class Rectangle {
public:
    int id; // 矩形id
    int x;  // 矩形左上角x坐标
    int y;  // 矩形左上角y坐标
    int w;  // 矩形宽度
    int h;  // 矩形高度

    Rectangle(int id, int x, int y, int w, int h) : id(id), x(x), y(y), w(w), h(h) {}
};

// 四叉树节点类
class QuadTreeNode {
public:
    int x;  // 节点左上角x坐标
    int y;  // 节点左上角y坐标
    int w;  // 节点宽度
    int h;  // 节点高度
    vector<Rectangle*> rectangles;  // 节点包含的矩形列表
    QuadTreeNode* children[4];      // 节点的四个子节点

    QuadTreeNode(int x, int y, int w, int h) : x(x), y(y), w(w), h(h) {
        for (int i = 0; i < 4; i++) {
            children[i] = nullptr;
        }
    }

    ~QuadTreeNode() {
        for (int i = 0; i < 4; i++) {
            delete children[i];
        }
    }

    // 判断点是否在当前节点范围内
    bool contains(int px, int py) {
        return px >= x && px < x + w && py >= y && py < y + h;
    }

    // 插入矩形到当前节点
    void insert(Rectangle* rect) {
        if (!contains(rect->x, rect->y)) {
            return;
        }
        rectangles.push_back(rect);
        if (rectangles.size() <= 1) {
            return;
        }
        if (children[0] == nullptr) {
            split();
        }
        for (int i = 0; i < 4; i++) {
            children[i]->insert(rect);
        }
    }

    // 分裂当前节点
    void split() {
        children[0] = new QuadTreeNode(x, y, w / 2, h / 2);
        children[1] = new QuadTreeNode(x + w / 2, y, w / 2, h / 2);
        children[2] = new QuadTreeNode(x, y + h / 2, w / 2, h / 2);
        children[3] = new QuadTreeNode(x + w / 2, y + h / 2, w / 2, h / 2);
    }

    // 遍历四叉树查找包含输入点的矩形
    int search(int px, int py) {
        if (!contains(px, py)) {
            return -1;
        }
        for (int i = 0; i < rectangles.size(); i++) {
            if (px >= rectangles[i]->x && px < rectangles[i]->x + rectangles[i]->w &&
                py >= rectangles[i]->y && py < rectangles[i]->y + rectangles[i]->h) {
                return rectangles[i]->id;
            }
        }
        for (int i = 0; i < 4; i++) {
            if (children[i] != nullptr) {
                int id = children[i]->search(px, py);
                if (id != -1) {
                    return id;
                }
            }
        }
        return -1;
    }
};

int main() {
    // 构建四叉树
    QuadTreeNode* root = new QuadTreeNode(0, 0, 100, 100);
    Rectangle rect1(1, 10, 10, 20, 20);
    Rectangle rect2(2, 40, 40, 30, 30);
    Rectangle rect3(3, 60, 20, 20, 40);
    root->insert(&rect1);
    root->insert(&rect2);
    root->insert(&rect3);

    // 查找点(15, 15)是否在矩形中
    int id = root->search(15, 15);
    if (id != -1) {
        cout << "Point is in rectangle " << id << endl;
    } else {
        cout << "Point is not in any rectangle" << endl;
    }

    // 释放内存
    delete root;
    return 0;
}