我们可以构建一个简单的应用案例，其中使用三维 R 树来存储和查询3D空间中的矩形包围盒（Bounding Boxes）。假设我们的应用场景是存储一些 3D 物体（如建筑、车辆、物品等）的空间位置，并根据查询范围来返回哪些物体与查询区域相交。

1.场景设定

假设我们有一个仓库管理系统，其中仓库中的物品被存储在三维空间中，我们将这些物品表示为 Box3D（三维矩形包围盒）。用户可以查询仓库中位于特定区域内的物品。

2.功能需求

1. 插入物品：将物品（表示为三维矩形包围盒）插入到 R 树中。
2. 范围查询：查询一个指定区域内的所有物品（即查询与给定范围相交的所有矩形包围盒）。

3.代码实现

以下是一个简单的三维 R 树应用案例，演示了如何存储物品的空间信息，并进行范围查询。

#include <iostream>
#include <vector>
#include <algorithm>// 定义三维矩形包围盒
struct Box3D {float x_min, y_min, z_min;float x_max, y_max, z_max;Box3D() : x_min(0), y_min(0), z_min(0), x_max(0), y_max(0), z_max(0) {}Box3D(float xmin, float ymin, float zmin, float xmax, float ymax, float zmax): x_min(xmin), y_min(ymin), z_min(zmin), x_max(xmax), y_max(ymax), z_max(zmax) {}// 合并两个三维矩形包围盒static Box3D merge(const Box3D& b1, const Box3D& b2) {return Box3D(std::min(b1.x_min, b2.x_min),std::min(b1.y_min, b2.y_min),std::min(b1.z_min, b2.z_min),std::max(b1.x_max, b2.x_max),std::max(b1.y_max, b2.y_max),std::max(b1.z_max, b2.z_max));}// 判断两个矩形包围盒是否相交bool intersects(const Box3D& other) const {return !(x_max < other.x_min || x_min > other.x_max ||y_max < other.y_min || y_min > other.y_max ||z_max < other.z_min || z_min > other.z_max);}// 输出包围盒信息void print() const {std::cout << "Box: (" << x_min << ", " << y_min << ", " << z_min << ") -> ("<< x_max << ", " << y_max << ", " << z_max << ")\n";}
};// R 树节点类
class RTreeNode {
public:bool is_leaf;  // 是否是叶子节点std::vector<RTreeNode*> children;  // 子节点std::vector<Box3D> entries;  // 节点中的矩形包围盒（或子节点）RTreeNode(bool leaf = false) : is_leaf(leaf) {}// 插入矩形包围盒到节点void insert(const Box3D& box) {entries.push_back(box);if (!is_leaf) {children.push_back(new RTreeNode(true));  // 简化，假设直接插入叶节点}}// 获取当前节点的包围盒（合并所有条目的包围盒）Box3D getBoundingBox() const {if (entries.empty()) return Box3D();Box3D bbox = entries[0];for (const auto& entry : entries) {bbox = Box3D::merge(bbox, entry);}return bbox;}// 递归查询相交的矩形包围盒void query(const Box3D& query_box, std::vector<Box3D>& result) const {// 检查当前节点的包围盒是否与查询框相交Box3D node_bbox = getBoundingBox();if (!node_bbox.intersects(query_box)) {return;  // 如果不相交，直接返回}// 如果是叶子节点，直接检查所有条目if (is_leaf) {for (const auto& entry : entries) {if (entry.intersects(query_box)) {result.push_back(entry);}}} else {// 递归查询子节点for (const auto& child : children) {child->query(query_box, result);}}}
};// 三维 R 树类
class RTree3D {
public:RTreeNode* root;size_t max_entries_per_node;RTree3D(size_t max_entries = 4) : max_entries_per_node(max_entries) {root = new RTreeNode(true);  // 创建根节点，假设为叶子节点}// 插入三维矩形包围盒void insert(const Box3D& box) {insert(root, box);}void insert(RTreeNode* node, const Box3D& box) {if (node->entries.size() < max_entries_per_node) {node->insert(box);} else {// 如果节点已满，进行分裂（这里采用简化的分裂方式）RTreeNode* new_node = new RTreeNode(true);new_node->insert(box);node->insert(box);  // 假设直接插入旧节点// 合并后，处理分裂策略（这里简化为直接插入）}}// 执行范围查询std::vector<Box3D> rangeQuery(const Box3D& query_box) {std::vector<Box3D> result;root->query(query_box, result);return result;}// 打印树结构（深度优先遍历）void printTree(RTreeNode* node, int depth = 0) {if (!node) return;for (int i = 0; i < depth; ++i) std::cout << "  ";std::cout << "Node (entries: " << node->entries.size() << ")\n";for (auto& entry : node->entries) {for (int i = 0; i < depth + 1; ++i) std::cout << "  ";std::cout << "  ";entry.print();}for (auto& child : node->children) {printTree(child, depth + 1);}}
};int main() {RTree3D tree;// 插入一些物品（三维矩形包围盒）tree.insert(Box3D(0, 0, 0, 5, 5, 5));tree.insert(Box3D(6, 6, 6, 10, 10, 10));tree.insert(Box3D(3, 3, 3, 8, 8, 8));tree.insert(Box3D(5, 5, 5, 7, 7, 7));// 打印树结构std::cout << "R-Tree Structure:\n";tree.printTree(tree.root);// 查询一个范围内的物品Box3D query_box(4, 4, 4, 9, 9, 9);  // 查询范围：从 (4,4,4) 到 (9,9,9)std::cout << "\nQuery Range: ";query_box.print();// 获取查询结果std::vector<Box3D> result = tree.rangeQuery(query_box);std::cout << "\nItems in query range:\n";for (const auto& box : result) {box.print();}return 0;
}

4.代码解释

1. Box3D：定义了一个三维矩形包围盒，包含合并、相交判断等操作。
2. RTreeNode：
   • 包含 entries（矩形包围盒列表）和 children（子节点指针列表）。
   • query 方法用于递归查询与给定查询框相交的矩形包围盒。
3. RTree3D：
   • 提供 insert 方法来插入三维矩形包围盒。
   • rangeQuery 方法接受一个查询范围，返回所有与该范围相交的矩形包围盒。
4. main：
   • 插入一些示例物品（三维矩形包围盒）。
   • 执行范围查询，返回与查询范围相交的物品。

5.执行结果

输出树结构和查询结果。例如：

R-Tree Structure:
Node (entries: 2)Box: (0, 0,