Geometry Boost List: Re: [geometry] rtree nearest polygon to a point

Subject: Re: [geometry] rtree nearest polygon to a point
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2014-12-02 18:25:58

Hi,

Andrew Hundt wrote:
>
> On Mon, Dec 1, 2014 at 9:01 PM, Adam Wulkiewicz 
> <adam.wulkiewicz_at_[hidden] <mailto:adam.wulkiewicz_at_[hidden]>> wrote:
>
>     Hi Andrew,
>
>     Andrew Hundt wrote:
>
>         I'm considering using rtree to store a set of triangles (I
>         will use polygons), and query for the closet triangle to a
>         point. Are there any examples I could use to help with setting
>         up the appropriate objects and types?
>
>
>     You could store pairs of triangle bounding box and index and then
>     iterate over the nearest boxes using iterative nearest query and
>     check distance to corresponding triangles. If the distance to the
>     next box was greater than to the nearest triangle or the distance
>     to the triangle was equal to 0 you could break the loop.
>
>
> Hmm, I'm implementing iterative closest point for sensor data 
> registration. Most of the time the distance won't be 0, but typically 
> the next box will be greater. There would be some strange corner cases 
> however if I only search for a few results and keep increasing the 
> size... Maybe the current rtree implementation isn't the right tool 
> for this since I can't directly check for the closest polygon?

Any spatial index (or space partinioning data structure) would do it the 
same way. Indexing would be done using some bounding regions, not 
polygons, for fast pruning. Then the searching for the nearest Polygon 
would be done similar way as I described above. If the data structure 
allowed to store Polygons the above procedure would be done internally.

What do you mean by "keep increasing the size"? I didn't mention it 
explicitly but you could pass rtree.size() or some big number (as 
k-number of nearest elements) to the nearest predicate passed to the 
qbegin(). Then the query iterator would iterate over all of the elements 
stored in the rtree, the nearest ones first. You then would be able to 
stop iteration at some point - after it'd be not possible to find a 
closer Polygon, when a bounding box was further than the nearest 
distance. So if the data was sparsely distributed it'd require 2 iterations.

Regards,
Adam