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

Subject: Re: [Boost-users] [EXTERNAL] is it possible to group values with Boost's rtree?
From: Belcourt, Kenneth (kbelco_at_[hidden])
Date: 2015-08-27 14:06:57

Hi Andy,

> On Aug 27, 2015, at 1:02 AM, Andy Edwards <jedwards_at_[hidden]> 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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users