rtree nearest polygon to a point

classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

rtree nearest polygon to a point

Andrew Hundt
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?

Cheers!
Andrew Hundt


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: rtree nearest polygon to a point

Millman, Mark
I know this is self evident but in none of the Delaunay triangle libraries I recently reviewed did they first test if the point fell in the previous triangle.  I had to modify one so that I could pass the index to the previous triangle back to it.  In my data set (LiDAR data with billions of points) this improved my searches by a hundred-fold or more.  It's very common in spatial data for points to be relatively close to each other and providing an optional "hint" index can speed things along.

Mark

On Mon, Dec 1, 2014 at 4:35 PM, Andrew Hundt <[hidden email]> 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?

Cheers!
Andrew Hundt


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry




--

Mark Millman | Mizar, LLC
[hidden email] | www.mizar.com
(360) 220-3504
9908 Alegria Dr | Las Vegas, NV 89144

 The information contained in this communication may be confidential, is intended only for the use of the recipient(s) named above, and may be legally privileged. If the reader of this message is not the intended recipient, you are hereby notified that any dissemination, distribution, or copying of this communication, or any of its contents, is strictly prohibited. If you have received this communication in error, please return it to the sender immediately and delete the original message and any copy of it from your computer system. If you have any questions concerning this message, please contact the sender.


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: rtree nearest polygon to a point

Adam Wulkiewicz
In reply to this post by Andrew Hundt
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.

Some examples:
http://www.boost.org/doc/libs/1_57_0/libs/geometry/doc/html/geometry/spatial_indexes/rtree_examples/index_of_polygons_stored_in_vector.html
http://www.boost.org/doc/libs/1_57_0/libs/geometry/doc/html/geometry/spatial_indexes/rtree_examples/iterative_query.html

Regards,
Adam
_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: rtree nearest polygon to a point

Adam Wulkiewicz
In reply to this post by Millman, Mark
Hi Mark,

Mark Millman wrote:
> I know this is self evident but in none of the Delaunay triangle
> libraries I recently reviewed did they first test if the point fell in
> the previous triangle.  I had to modify one so that I could pass the
> index to the previous triangle back to it.  In my data set (LiDAR data
> with billions of points) this improved my searches by a hundred-fold
> or more. It's very common in spatial data for points to be relatively
> close to each other and providing an optional "hint" index can speed
> things along.

Yes, this is a valid point. However I'm guessing that this depends on
the case. The points acquired from LIDAR are often close to each other
since the environment is scanned this way that subsequent points often
hit the same or very close obstacle. I'm guessing that for some random
points the result wouldn't be the same.

Btw, is this a general advice or a suggestion how the library (e.g.
rtree) could be improved?

Regards,
Adam

P.S. Top-posting is discouraged on this mailing list.


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: rtree nearest polygon to a point

Andrew Hundt
In reply to this post by Adam Wulkiewicz

On Mon, Dec 1, 2014 at 9:01 PM, Adam Wulkiewicz <[hidden email]> 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?

Cheers!
Andrew Hundt
 


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: rtree nearest polygon to a point

Adam Wulkiewicz
Hi,

Andrew Hundt wrote:

On Mon, Dec 1, 2014 at 9:01 PM, Adam Wulkiewicz <[hidden email]> 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
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: rtree nearest polygon to a point

Andrew Hundt
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 page.

It would also be nice to see some additional discussion of the various parameters 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 <[hidden email]> wrote:
Hi,

Andrew Hundt wrote:

On Mon, Dec 1, 2014 at 9:01 PM, Adam Wulkiewicz <[hidden email]> 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
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry



_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: rtree nearest polygon to a point

Barend
Hi Andrew,

Partial answer:




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 page.

Do you mean this:

http://www.boost.org/doc/libs/1_57_0/libs/geometry/doc/html/geometry/indexes/matrix.html

Regards, Barend< /html>
_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: rtree nearest polygon to a point

Andrew Hundt

On Thu, Dec 4, 2014 at 4:01 AM, Barend Gehrels <[hidden email]> wrote:

aha! yes, apparently I didn't notice that, thanks. In Boost.asio that is directly under "Reference". Maybe that way is easier to find since that index is simply under "Reference" and geometry could be switched? Alternately perhaps a link to the tabular reference could be under the plain "Reference" page?

_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: rtree nearest polygon to a point

Adam Wulkiewicz
Andrew Hundt wrote:

On Thu, Dec 4, 2014 at 4:01 AM, Barend Gehrels <[hidden email]> wrote:

aha! yes, apparently I didn't notice that, thanks. In Boost.asio that is directly under "Reference". Maybe that way is easier to find since that index is simply under "Reference" and geometry could be switched? Alternately perhaps a link to the tabular reference could be under the plain "Reference" page?

Putting the matrix and the alphabetical index in the "Reference" section probably isn't a good idea, but I'm guessing that indeed the ToC could be more readable if the "Indexes" section (which btw can be confused with "Spatial indexes") was removed. On the top-level we could then have:

...
Reference
    Access Functions
    Adapted models
    ...
Reference matrix
Reference index
...

would that be ok?

Regards,
Adam

_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: rtree nearest polygon to a point

Andrew Hundt
yeah that's a good idea I think that small layout change would be a nice improvement


Cheers!
Andrew Hundt

On Mon, Dec 8, 2014 at 7:16 AM, Adam Wulkiewicz <[hidden email]> wrote:
Andrew Hundt wrote:

On Thu, Dec 4, 2014 at 4:01 AM, Barend Gehrels <[hidden email]> wrote:

aha! yes, apparently I didn't notice that, thanks. In Boost.asio that is directly under "Reference". Maybe that way is easier to find since that index is simply under "Reference" and geometry could be switched? Alternately perhaps a link to the tabular reference could be under the plain "Reference" page?

Putting the matrix and the alphabetical index in the "Reference" section probably isn't a good idea, but I'm guessing that indeed the ToC could be more readable if the "Indexes" section (which btw can be confused with "Spatial indexes") was removed. On the top-level we could then have:

...
Reference
    Access Functions
    Adapted models
    ...
Reference matrix
Reference index
...

would that be ok?

Regards,
Adam

_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry



_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Loading...