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: Andy Edwards (jedwards_at_[hidden])
Date: 2015-08-28 15:53:20

Noel wrote:
> I had to do something similar packing 100k 3d objects into the smallest
> number of groups, where each group contains only non-overlapping 3d
> objects.  I used the Boost Graph library with a smallest least ordering
> graph coloring algorithm.   Since this is a quasi-np hard problem, I know
> the packing density is sub-optimal but still quite good for our
> application.  Perhaps that approach would work for you?  Unfortunately
> I?m not familiar with Boost rtree.
> 
> ? Noel Belcourt

Thanks for the tip Noel, but it sounds like I'll be able to accomplish
it using Adam's suggestions (I don't need completely optimal packing
density).  Since I'll be using the rtree for spatial queries as well
it's the best approach for me.

Adam wrote:
> 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

Thanks Adam!  That sounds ideal.  Glad I'll be able to use this!  I
wonder if a per-node predicate is planned for the public API in the
future (rather than the value-only satisfies predicate)?