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

Subject: Re: [geometry] rtree nearest polygon to a point
From: Andrew Hundt (athundt_at_[hidden])
Date: 2014-12-03 16:31:38

By "keep increasing the size" I meant do a query for 4 results then check
if I definitively have the closest point. If not, double the query size and
start over. It turns out I had a bug in the "if I definitively have the
closest point" check, I was comparing points to polygons instead of points
to polygon envelope boxes.

I've always been hoping for a chance to use your rtree class, and now that
I have it works great! About 100 lines of code based of the examples, 10 of
which were typedefs, gave me a 10x speedup in my algorithm without any
tuning. Thanks Adam!

A couple comments on the Spatial Index documentation:

It would be nice if the Spatial Indexes
<http://www.boost.org/doc/libs/1_57_0/libs/geometry/doc/html/geometry/reference/spatial_indexes.html>
page had two levels of detail in the same manner as the general Reference
<http://www.boost.org/doc/libs/1_57_0/libs/geometry/doc/html/geometry/reference.html>
page, or ideally both could be like the boost.asio reference
<http://www.boost.org/doc/libs/1_57_0/doc/html/boost_asio/reference.html>
 page.

It would also be nice to see some additional discussion of the various
parameters
<http://www.boost.org/doc/libs/1_57_0/libs/geometry/doc/html/geometry/reference/spatial_indexes/boost__geometry__index__rtree.html>
and what the advantages/disadvantages are, and some example situations for
choosing each. Either that or a reference to some external resource with
that information.

Cheers!
Andrew Hundt

On Tue, Dec 2, 2014 at 6:25 PM, Adam Wulkiewicz <adam.wulkiewicz_at_[hidden]>
wrote:

>  Hi,
>
> Andrew Hundt wrote:
>
>
>  On Mon, Dec 1, 2014 at 9:01 PM, Adam Wulkiewicz <
> 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
>
> _______________________________________________
> Geometry mailing list
> Geometry_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/geometry
>
>