Geometry Boost List: Re: [geometry] access all tree leaves

Subject: Re: [geometry] access all tree leaves
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2013-09-24 08:06:35

florian buecherl wrote:
> Hello,
>
> I just make some performance measurements with an rtree algorithm and I
> would like to access all leaf nodes. Is there a way to do it with an
> iterator or something like that? I tried it with an query but this is a very
> slow solution and not really comparable.
>

I assumie you need only read access.

First of all get the BG from trunk : 
https://svn.boost.org/svn/boost/trunk/boost/geometry/

Tree traversal is implemented using visitor pattern. See the statistics 
utility:

https://svn.boost.org/svn/boost/trunk/boost/geometry/index/detail/rtree/utilities/statistics.hpp

struct statistics

is such visitor. At the beginning

internal_node

and

leaf

types are defined, then there is an implementation of operators taking 
the nodes. The approach used e.g. by Boost.Variant.

void operator()(internal_node const& n)
void operator()(leaf const& n)

Inside those functions you'll have read access to nodes. See how it's 
done in statistics. This is how you can access the elements of internal 
node:

typedef typename rtree::elements_type<internal_node>::type elements_type;
elements_type const& elements = rtree::elements(n);

Elements are implemented as a container with random access so they have 
methods like size(), empty(), const_iterators, etc.
The elements of a leaf node are of type Value (passed as the first 
parameter of the rtree), internal_node elements are pairs of a 
rtree::box_type and a pointer to the child node so to traverse the tree 
you must take the second member of the pair and call

rtree::apply_visitor(*this, *it->second);

Have in mind that everything there is defined in namespace 
boost::geometry::index::detail.

To be honest you may just copy the statistics.hpp somewhere, remove what 
you don't need and #include your version.

Regards,
Adam