Boost logo

Geometry :

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 :

Tree traversal is implemented using visitor pattern. See the statistics

struct statistics

is such visitor. At the beginning




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

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

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


Geometry list run by mateusz at