Почему boost официально не поддерживает способы обхода иерархии дерева?

Угадывание:

• они реализовывали примитивы высокого уровня с дружественным API. Исключение нижних уровней в задокументированном интерфейсе дает гораздо больше гибкости для повторения дизайна этих интерфейсов, не создавая проблем для пользователей библиотеки. Таким образом, конечный результат будет строго лучше, больше низкоуровневых интерфейсов, которые можно будет задокументировать после стабилизации.

• Семантика обхода будет тесно связана со стратегией балансировки/структурирования. Это означает, что было бы сложно понять/задокументировать значение порядка обхода во всех случаях, что, вероятно, было бы источником ошибки. Отсутствие документирования сигнализирует об этом пользователю (он может использовать его, но на свой страх и риск)

Случай 1

Согласовано. Я бы сказал, что в идеале вы должны выполнить BFS для первого дерева и запросить пересечения со вторым деревом. Таким образом, вы можете быстро удалить «участки» дерева (поддеревья), которые не представляют интереса.

Основываясь на коде, приведенном здесь разработчиком библиотеки, я придумал грубый, минимальный посетитель:

namespace rtree = bgi::detail::rtree;

template <typename Predicate, typename Value, typename Options, typename Box, typename Allocators>
struct BFSQuery : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type
{
    typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
    typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;

    inline BFSQuery(Predicate const& p) : pr(p) {}

    inline void operator()(internal_node const& n) {
        for (auto&& [bounds, node] : rtree::elements(n))
            if (pr(bounds))
                rtree::apply_visitor(*this, *node);
    }

    inline void operator()(leaf const& n) {
        for (auto& item : rtree::elements(n))
            if (pr(item)) results.insert(&item);
    }

    Predicate const& pr;

    std::set<Value const*> results;
};

Примечание: один случайный выбор заключался в дедупликации результатов с использованием std::set, что имеет побочный эффект, заключающийся в том, что результаты будут в неопределенном порядке («порядок адресов», если хотите).

Сам алгоритм может быть довольно простым, используя этого посетителя:

template <typename TreeA, typename TreeB, typename F>
void tree_insersects(TreeA const& a, TreeB const& b, F action) {
    using V = rtree::utilities::view<TreeA>;
    V av(a);

    auto const pred = [&b](auto const& bounds) {
        return bgi::qbegin(b, bgi::intersects(bounds)) != bgi::qend(b);
    };

    BFSQuery<
      decltype(pred),
      typename V::value_type,
      typename V::options_type,
      typename V::box_type,
      typename V::allocators_type
    > vis(pred);

    av.apply_visitor(vis);

    auto tr = av.translator();
    for (auto* hit : vis.results)
        action(tr(*hit));
}

Обратите внимание, что он максимально общий.

Используй это:

Жить на Coliru

int main() {
    using Box = bg::model::box<bg::model::d2::point_xy<int> >;

    // generate some boxes with nesting
    bgi::rtree<Box, bgi::rstar<5>> a;
    for (auto [k,l] : { std::pair(0, 1), std::pair(-1, 2) }) {
        std::generate_n(bgi::insert_iterator(a), 10,
            [k,l,i=1]() mutable { Box b{ {i+k,i+k}, {i+l,i+l} }; i+=2; return b; });
    }

    // another simple tree to intersect with
    bgi::rtree<Box, bgi::quadratic<16> > b;
    b.insert({ {9,9}, {12,12} });
    b.insert({ {-9,-9}, {1,2} });

    Demo::tree_insersects(a, b, [](auto& value) {
        std::cout << "intersects: " << bg::dsv(value) << "\n";
    });
}

Принты (порядок может меняться):

intersects: ((1, 1), (2, 2))
intersects: ((0, 0), (3, 3))
intersects: ((11, 11), (12, 12))
intersects: ((10, 10), (13, 13))
intersects: ((12, 12), (15, 15))
intersects: ((6, 6), (9, 9))
intersects: ((8, 8), (11, 11))
intersects: ((9, 9), (10, 10))

Случай 2

Я думаю, вы можете добиться этого с помощью стандартного предиката запроса:

for (auto& value : boost::make_iterator_range(bgi::qbegin(a, bgi::intersects(sphere)), {})) {
    std::cout << "intersects: " << bg::dsv(value) << "\n";
}

Смотрите Прямой эфир на Coliru

ПОЛНЫЙ СПИСОК Дело №1

Алгоритма tree_insersects для потомков

Жить на Coliru

#include <boost/geometry/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/index/rtree.hpp>
#include <boost/geometry/index/detail/utilities.hpp>
#include <boost/geometry/index/predicates.hpp>
#include <iostream>

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

namespace Demo {
    namespace rtree = bgi::detail::rtree;

    template <typename Predicate, typename Value, typename Options, typename Box, typename Allocators>
    struct BFSQuery : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type
    {
        typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
        typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;

        inline BFSQuery(Predicate const& p) : pr(p) {}

        inline void operator()(internal_node const& n) {
            for (auto&& [bounds, node] : rtree::elements(n)) {
                if (pr(bounds))
                    rtree::apply_visitor(*this, *node);
            }
        }

        inline void operator()(leaf const& n) {
            for (auto& item : rtree::elements(n))
                if (pr(item)) results.insert(&item);
        }

        Predicate const& pr;

        std::set<Value const*> results;
    };

    template <typename TreeA, typename TreeB, typename F> void tree_insersects(TreeA const& a, TreeB const& b, F action) {
        using V = rtree::utilities::view<TreeA>;
        V av(a);

        auto const pred = [&b](auto const& bounds) {
            return bgi::qbegin(b, bgi::intersects(bounds)) != bgi::qend(b);
        };

        BFSQuery<
          decltype(pred),
          typename V::value_type,
          typename V::options_type,
          typename V::box_type,
          typename V::allocators_type
        > vis(pred);

        av.apply_visitor(vis);

        auto tr = av.translator();
        for (auto* hit : vis.results)
            action(tr(*hit));
    }
}

int main() {
    using Box = bg::model::box<bg::model::d2::point_xy<int> >;

    // generate some boxes with nesting
    bgi::rtree<Box, bgi::rstar<5>> a;
    for (auto [k,l] : { std::pair(0, 1), std::pair(-1, 2) }) {
        std::generate_n(bgi::insert_iterator(a), 10,
            [k,l,i=1]() mutable { Box b{ {i+k,i+k}, {i+l,i+l} }; i+=2; return b; });
    }

    // another simple tree to intersect with
    bgi::rtree<Box, bgi::quadratic<16> > b;
    b.insert({ {9,9}, {12,12} });
    b.insert({ {-9,-9}, {1,2} });

    Demo::tree_insersects(a, b, [](auto& value) {
        std::cout << "intersects: " << bg::dsv(value) << "\n";
    });
}