Re: [Boost-users] is it possible to group values with Boost's rtree?

Subject: Re: [Boost-users] is it possible to group values with Boost's rtree?
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2015-08-27 19:39:20

Hi Andy,

Andy Edwards wrote:
> Hi everyone,
> I need a way to take a collection of 3D objects and put them into 
> disjoint minimally overlapping groups no bigger than some N.  Can this 
> be done with Boost's rtree or any other Boost libraries?
>
> I've done this by putting the objects in an R* tree and using the 
> nodes at a certain level of the tree (for example, 2 levels up from 
> the leaf level) to determine the groups.
> However, that was in my own Java R* tree implementation that provided 
> read-only access to its internal nodes.
> I'd like to port this program to C++ using Boost's rtree, but it 
> doesn't provide read-only access to its nodes, does it?  Does anyone 
> know if it would be possible to extend the rtree to provide this?
> Or would it be possible to write a custom predicate to get the groupings?

It is possible though it isn't officially supported. Have a look at the 
utilities in this directory:

https://github.com/boostorg/geometry/tree/master/include/boost/geometry/index/detail/rtree/utilities

To traverse the rtree you must write a visitor similar to the 
Boost.Variant visitor, defining operator() overloads taking nodes. There 
is a boost::geometry::index::detail::rtree::utilities::view<> providing 
read-only access to the rtree's internals, in particular to the 
apply_visitor() method applying the visitor to the root node of the 
rtree and depth() function returning the number of tree levels. To 
access the node's elements container you may use 
boost::geometry::index::detail::rtree::elements() function and to apply 
the visitor to the child node you may call 
boost::geometry::index::detail::rtree::apply_visitor() function. The 
elements of an internal node are of type similar to std::pair<> where 
the first member is a Box and the second member is a pointer to the 
child node. The elements of a leaf node are of type value_type. This way 
you may recursively traverse the rtree in depth-first order counting the 
current level, create containers of values when some level is met and 
then gather the values from leafs. See e.g. how the utilities in the 
directory mentioned above are implemented.

Regards,
Adam