
Geometry : 
Subject: Re: [geometry] RTree Nearest Neighbors Unique Member From Group
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 20180521 13:19:20
Hi,
Jpb Via GeometryÂ wrote:
> So for this application each of the Ngroups are all pretty localized and N
> is a large number, so I think I could keep each group in a grouprtree and
> then keep each grouprtree in an overarchingrtree (with things like
> indexable and compariable_distance for a grouprtree and a point overloaded
> to give the distance between the closest object in the rtree to the point).
> If I did that, I could run a nearest neighbor search on the
> overarchingrtree and get the k closest grouprtree's, but then in order
> to get the objects in each grouprtree, I'd have to run another nearest
> neighbor search on the grouprtree. 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 grouptrees'
bounding boxes and ids of the grouptrees. You could also have
distanceboxid tuples in a vector and sort them by the distance to the
point. Then call query for grouptrees 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
grouptree 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 rtree
> 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 korless 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
Geometry list run by mateusz at loskot.net