Hi,

Jpb Via Geometry wrote:

So for this application each of the N-groups are all pretty localized and N
is a large number, so I think I could keep each group in a group-r-tree and
then keep each group-r-tree in an overarching-r-tree (with things like
indexable and compariable_distance for a group-r-tree and a point overloaded
to give the distance between the closest object in the r-tree to the point).
If I did that, I could run a nearest neighbor search on the
overarching-r-tree and get the k closest group-r-tree's, but then in order
to get the objects in each group-r-tree, I'd have to run another nearest
neighbor search on the group-r-tree. Is there a good way around that
repeated computation?

What do you mean by localized? That the elements each group are close to each other? It's the separation of groups or overlap of groups I'm talking about. AFAIU it would be possible to have groups localized and still overlapping each other. If they all overlap then you'd still have to check all of the trees.

Yes I guess you could create another tree keeping pairs of group-trees' bounding boxes and ids of the group-trees. You could also have distance-box-id tuples in a vector and sort them by the distance to the point. Then call query for group-trees in the order taken from the sorted vector. Always query for only one element (note that in this case you can replace back_inserter with pointer). Stop when you have sufficient number of elements gathered and the distance to the next group-tree is greater than the furthest distance to the element you already found. Of course you could also use the rtree to do the sorting for you. But to implement this stopping mechanics you should use the iterative query (qbegin() qend()) instead of regular query().


If that doesn't work, I might just put all of the objects in a single r-tree
and get all or the objects withing a certain range (using something like the
intersects query) and then process those items to get what I want, and then
just live with the fact that fewer than k groups might intersect a range, so
it would be a find the nearest k-or-less neighbors with at most one in each
group query.

Yes, but as you said the result may be different than you desire. So this approximation/heuristic might be used if the first solution was too slow for you or if low level of detail was needed in a some specific situation.

Adam