Geometry Boost List: Re: [geometry] R-Tree Nearest Neighbors Unique Member From Group

Subject: Re: [geometry] R-Tree Nearest Neighbors Unique Member From Group
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2018-05-21 13:19:20

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