CODEWITHSUNDEEP
c++optimizationboostboost-geometryr-tree
Ranjeeth Mahankali
Ranjeeth Mahankali

Reputation: 390

Do I need to traverse the hierarchy of the boost rtree to achieve maximum efficiency?

After some reading I learned that hierarchy traverse, though possible is not officially supported in boost rtree. I have a couple of different use cases where I can manage without hierarchy traverse, but I am not sure about the efficiency. So I am seeking advice on how boost rtree works internally and what are the best practices for these use cases.

case 1 - I have 2 trees and I want to filter these two trees for elements that intersect with atleast one element from the other tree. I have the code below that does this and gives me the results I want:

    std::set<int> results2;
    std::vector<rtree3d_item> tempResults, results1;
    std::vector<rtree3d_item>::iterator it;
    tree1->query(bgi::satisfies(
        [&](const rtree3d_item& item) {
            tempResults.clear();
            tree2->query(bgi::intersects(item.first), std::back_inserter(tempResults));
            for (it = tempResults.begin(); it < tempResults.end(); it++)
            {
                results2.insert(it->second);
            }
            return tempResults.size() > 0;
        }
    ), std::back_inserter(results1));

Though I get the results I want, the approach seems non-optimal. The lambda expression I pass to the satisfies() is run once for every leaf node in tree1. If I could traverse the hierarchy of the tree, I could have tested the large boxes of the parent nodes and ruled out large chunks of tree1 and made the process a lot more efficient. Its almost like tree1 being a tree structure is useless.

case 2 - I just want to query an rtree for all items that intersect with a sphere. I do it with a predicate lambda expression:

bgi::satisfies(
        [=](const rtree3d_item &item) {
            return bg::distance(item.first, cpt) < radius;
        })

This expression is run once for each leaf node of the rtree inside, which again seems wasteful. If I do this test for parent nodes, I could rule out several leaf nodes in one go.

Seems like I would run into the same situation whenever I am testing the rtree for a condition that satisfies - (if a boundinbox fails the condition, any boundingbox contained within it will also fail the condidion). I mean, what is the point of having a "tree" structure if I am going to test all leaf nodes all the time ? Why doesn't boost officially support ways to traverse the hierarchy of the tree ?

I found a source that talks about unsupported, unofficial ways (link) to do it, but I want to try official, supported ways to optimize my code.

FYI, My experience in C++ is limited so all advice is welcome, and Thanks !

Upvotes: 1

Views: 384

Answers (1)

sehe
sehe

Reputation: 393507

Why doesn't boost officially support ways to traverse the hierarchy of the tree ?

Guessing:

  • they were implementing high-level primitives with a s friendly API. Not including the lower level(s) in the documented interface gives a lot more flexibility to iterate on the design of these interfaces without causing trouble for users of the library. So, the end-result would strictly be better, more low-level interfaces that could be documented once stabilized.

  • The semantics of the traversal would intimately tie to the balancing/structuring strategy. This means that it would be tricky to understand/documentation the meaning of the traversal order in all cases, which would probably be a source of error. Not having it documented signals this to the user (they can use it, but at their own peril)

Case 1

Agreed. I'd say you would ideally do a BFS on the first tree, and query for intersections with the second tree. This way, you can quickly elminate "sections" of the tree (subtrees) that aren't of any interest.

Based on code linked by the library dev here, I came up with a rough, minimal visitor:

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;
};

Note: one random choice was to deduplicate results using a std::set, which has the side-effect that results will be in unspecified order ("address order" if you will).

The algorithm itself can be pretty simple using this visitor:

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));
}

Note that it is as generic as possible.

Using it:

Live On 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";
    });
}

Prints (the order may vary):

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))

Case 2

I think you can achieve this with a standard query predicate:

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

See it Live On Coliru

FULL LISTING Case #1

Of the tree_insersects algorithm for posterity

Live On 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";
    });
}

Upvotes: 1

Related Questions