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