How to iterate over a boost R-tree?

Question

I can't seem to find an efficient way to iterate over a boost R-tree (boost::geometry::index::rtree). The only method I have come up with so far is to perform a query using a very large bounding box so that a copy of all the elements is returned in a vector, however this is obviously neither space-efficient nor time-efficient. Ideally I'd just like to use an STL-style iterator to iterate over the tree in the usual way, but this doesn't seem to be possible ?

Answer 1

If you have a query that contains all the element you want to iterate over, you don't have to execute the query to put it all into a vector, but can use qbegin and qend to iterate over the elements directly. The necessary bounds to catch all elements can be obtained from bounds.

Answer 2

Since 1.59.0

begin() and end() member functions are defined in bgi::rtree, returning a const_iterator. So it's possible to iterate over all elements without the techniques described below. In C++11:

for(auto const& v: rtree)
    /* do something with v */

Before 1.59.0

As others have said to iterate over all elements stored in the rtree you could use query iterator. However there is no need to perform an actual spatial query (pass bounds, etc.). You could pass a dummy UnaryPredicate always returning true wrapped with bgi::satisfies(). In C++11:

std::for_each(rtree.qbegin(bgi::satisfies([](Value const&){ return true; })),
              rtree.qend(),
              [](Value const& v){
                  /* do something with v */
              });

Non-iterative queries could also be used for this purpose but it'd require a special output iterator, e.g. boost::function_output_iterator implemented in Boost.Iterator library (see http://www.boost.org/doc/libs/1_57_0/libs/iterator/doc/function_output_iterator.html). In C++11:

rtree.query(bgi::satisfies([](Value const&){ return true; }),
            boost::make_function_output_iterator([](Value const& v){
                /* do something with v */
            }));

Side notes:

• The above code requires Boost.Geometry library headers mentioned in the documentation
• namespace bgi = boost::geometry::index
• Value is a type of objects stored in the bgi::rtree
• boost::function_output_iterator requires #include <boost/function_output_iterator.hpp>
• in C++14 generic lambdas could be used, then the above code would be Value-type agnostic