Boost logo

Geometry :

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
page had two levels of detail in the same manner as the general Reference
page, or ideally both could be like the boost.asio reference

It would also be nice to see some additional discussion of the various
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.

Andrew Hundt

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

> 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]

Geometry list run by mateusz at