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

Hi Andy,

On Aug 27, 2015, at 1:02 AM, Andy Edwards wrote:

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

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?

Thanks! Andy _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users