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?
Andrew Hundt _______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
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:
Mark Millman | Mizar, LLC 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 |
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 |
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 |
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 _______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
Hi,
Andrew Hundt wrote:
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 |
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. Andrew Hundt On Tue, Dec 2, 2014 at 6:25 PM, Adam Wulkiewicz <[hidden email]> wrote:
_______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
Hi Andrew, Partial answer:
Do you mean this: _______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
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 |
Andrew Hundt wrote:
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 |
yeah that's a good idea I think that small layout change would be a nice improvement Andrew Hundt On Mon, Dec 8, 2014 at 7:16 AM, Adam Wulkiewicz <[hidden email]> wrote:
_______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
Free forum by Nabble | Edit this page |