如何从Boost RTree指定层级的BoundingBox中获取网格单元索引？

核心思路 #

Boost.Geometry的RTree对外屏蔽了内部节点的直接访问接口，无法直接从某个层级的BoundingBox节点获取其包含的原始元素。可行方案是：

1. 遍历RTree定位到目标层级的所有内部节点（即你已提取的BoundingBox集合）；
2. 对每个目标节点的BoundingBox执行范围查询，筛选出所有被该BoundingBox包含的原始网格单元索引。

具体实现步骤 #

1. 基础结构定义 #

假设你的RTree以网格单元的BoundingBox为键、索引为值，基础定义如下：

#include <boost/geometry.hpp>
#include <boost/geometry/index/rtree.hpp>

namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;

// 2D轴对齐BoundingBox类型
using Point = bg::model::point<double, 2, bg::cs::cartesian>;
using Box = bg::model::box<Point>;
// RTree元素：(BoundingBox, 网格单元索引)
using RTreeValue = std::pair<Box, int>;
// RTree实例（采用quadratic拆分策略）
bgi::rtree<RTreeValue, bgi::quadratic<16>> rtree;

2. 提取指定层级的BoundingBox（已完成可跳过） #

如果还未实现层级节点提取，可通过自定义访问器遍历RTree：

struct LevelVisitor : public bgi::detail::rtree::visitor<>
{
    int target_level;
    std::vector<Box> nodes;

    explicit LevelVisitor(int level) : target_level(level) {}

    template <typename Node>
    void operator()(Node const& node)
    {
        // RTree层级规则：根节点为最高层级，叶子节点（存原始元素）层级为0
        int current_level = node.level;
        if (current_level == target_level)
        {
            for (auto const& entry : node.entries)
                nodes.push_back(entry.first);
        }
        else if (current_level > target_level)
        {
            // 递归访问子节点
            for (auto const& child : node.children)
                boost::apply_visitor(*this, child);
        }
    }
};

// 获取指定层级的所有BoundingBox
std::vector<Box> get_level_nodes(bgi::rtree<RTreeValue, bgi::quadratic<16>> const& rtree, int target_level)
{
    LevelVisitor visitor(target_level);
    boost::apply_visitor(visitor, rtree.root());
    return visitor.nodes;
}

3. 绑定BoundingBox与原始网格索引 #

拿到目标层级的BoundingBox后，对每个Box执行范围查询，提取对应网格索引：

// 获取第三层级的BoundingBox集合（注意层级编号规则）
std::vector<Box> level_boxes = get_level_nodes(rtree, 3);

// 存储每个BoundingBox对应的网格索引列表
std::vector<std::vector<int>> box_to_indices;

for (auto const& box : level_boxes)
{
    std::vector<RTreeValue> query_results;
    // 执行范围查询：获取所有与当前Box相交的原始元素
    rtree.query(bgi::intersects(box), std::back_inserter(query_results));
    
    // 提取索引并存储
    std::vector<int> indices;
    for (auto const& val : query_results)
        indices.push_back(val.second);
    box_to_indices.push_back(indices);
}

关键注意事项 #

• 层级编号：Boost RTree中根节点是最高层级，叶子节点层级为0。若你的“第三层级”是从叶子往上计数，需调整target_level数值。
• 查询精度：intersects返回所有与Box相交的元素，若需要完全包含的网格单元，可替换为covered_by(box)。
• 性能优化：若网格数量极大，多次查询会有开销。可在构建RTree时额外维护反向映射（每个原始元素对应所有上层节点Box），但会增加内存占用。

内容的提问来源于stack exchange，提问作者cnewbie