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/inde...

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)?