Extract indices forming a level of RTree

Question

I have a grid made of squares, where each element has of course its own (integer) index. I used boost to create an RTree of bounding boxes for this grid, and I am able to extract a level of the RTree, which consists of a std::vector<BoundingBox> containing all the bounding boxes that make the given level of the rtree.

So far so good.

My goal is now: for a given level of the RTree, how can I know the indices of the cell that are inside each BoundingBox?

For instance, say that my third level is made of 10 bounding boxes. For each one of these 10 bounding boxes, I'd like to know the indices of the original grid that are inside each bounding box.

I think that logically it should be possible to retrieve such an information from the tree structure, but I can't find any example around. Any help is highly appreciated.

Answer 1

There is no external tree traversal (just geometrical queries and enumeration).

I am able to extract a level of the RTree, which consists of a std::vector containing all the bounding boxes that make the given level of the rtree

If you have the bounding boxes, you can of course do a geometrical query for those on the tree. Note that you can composite indexables as tree value-types. For example std::pair<Geom, Index> is built-in:

using Entry = std::pair<Box, Index>;
using Tree  = bgi::rtree<Entry, bgi::rstar<16>>;

When you get query results, you'll get the entire entry, so both the cell and the index.

Live On Coliru

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

#include <random>
static std::minstd_rand s_prng{std::random_device{}()};

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

using Coord = int;
using Index = unsigned;
using Box   = bgm::box<bgm::d2::point_xy<Coord>>;

template <unsigned Width, unsigned Height = Width> struct Grid {
    static_assert(Width >= 1);
    static_assert(Height >= 1);
    static auto constexpr Size = Width * Height;

    static auto pick_bounding_box() {
        using C = std::uniform_int_distribution<Coord>;
        auto between = [gen = C{}](Coord lower, Coord upper) mutable {
            return gen(s_prng, C::param_type{lower, upper});
        };

        Coord c = between(0, Width-1), r = between(0, Height-1);
        return Box{
             { c,                     r                      },
             { between(c + 1, Width), between(r + 1, Height) },
        };
    }

    static auto level3() { return std::vector{pick_bounding_box(), pick_bounding_box(), pick_bounding_box()}; }

    using Entry = std::pair<Box, Index>;
    using Tree  = bgi::rtree<Entry, bgi::rstar<16>>;

    static Box cell(Index idx) {
        assert(idx < Size);
        Coord row = idx / Width;
        Coord col = idx % Width;
        return Box{{col + 0, row + 0}, {col + 1, row + 1}};
    }

    static Tree build() {
        Tree tree;

        for (Index idx = 0; idx < Size; ++idx)
            tree.insert({cell(idx), idx});

        return tree;
    }
};

#include <fmt/ostream.h>
#include <fmt/ranges.h>
template <typename Geom>
struct fmt::formatter<bg::detail::dsv::dsv_manipulator<Geom>> : fmt::ostream_formatter {};

using bg::dsv;
using bgi::adaptors::queried;

int main() {
    using G = Grid<12, 6>;
    using Cells = std::set<Index>;

    auto const tree = G::build();

    Cells cells;

    for (auto&& bbox : G::level3()) {
        fmt::print("Within bbox {}:\n", dsv(bbox));

        for (auto& [cell, idx] : tree | queried(bgi::within(bbox))) {
            cells.insert(idx);
            fmt::print(" - cell {} with index {}\n", dsv(cell), idx);
        }
    }

    fmt::print("All {} level-3 cells: {}\n", cells.size(), cells);
}

With sample output:

Within bbox ((8, 0), (12, 3)):
 - cell ((8, 0), (9, 1)) with index 8
 - cell ((8, 1), (9, 2)) with index 20
 - cell ((8, 2), (9, 3)) with index 32
 - cell ((9, 0), (10, 1)) with index 9
 - cell ((11, 0), (12, 1)) with index 11
 - cell ((9, 2), (10, 3)) with index 33
 - cell ((10, 1), (11, 2)) with index 22
 - cell ((11, 2), (12, 3)) with index 35
 - cell ((10, 2), (11, 3)) with index 34
 - cell ((11, 1), (12, 2)) with index 23
 - cell ((10, 0), (11, 1)) with index 10
 - cell ((9, 1), (10, 2)) with index 21
Within bbox ((2, 3), (5, 5)):
 - cell ((3, 3), (4, 4)) with index 39
 - cell ((2, 3), (3, 4)) with index 38
 - cell ((4, 3), (5, 4)) with index 40
 - cell ((2, 4), (3, 5)) with index 50
 - cell ((4, 4), (5, 5)) with index 52
 - cell ((3, 4), (4, 5)) with index 51
Within bbox ((2, 5), (6, 6)):
 - cell ((3, 5), (4, 6)) with index 63
 - cell ((2, 5), (3, 6)) with index 62
 - cell ((4, 5), (5, 6)) with index 64
 - cell ((5, 5), (6, 6)) with index 65
All 22 level-3 cells: {8, 9, 10, 11, 20, 21, 22, 23, 32, 33, 34, 35, 38, 39, 40, 50, 51, 52, 62, 63, 64, 65}