Hello,
I noticed that there were discussions about geometry partition/spatial index in Boost Geometry Library, is it available to use? If so, could anyone pointer me some example or codes to look at? Thanks, Jeff |
jeffpoly wrote:
> Hello, > > I noticed that there were discussions about geometry partition/spatial index > in Boost Geometry Library, is it available to use? If so, could anyone > pointer me some example or codes to look at? > The code and docs are in the sandbox: https://svn.boost.org/svn/boost/sandbox-branches/geometry/index/ If you want to check the old one you must download Boost.Geometry from the repo: http://svn.boost.org/svn/boost/trunk/boost/geometry In both cases the index is in boost/geometry/extensions/index. Regards, Adam _______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
Hello Adam,
Thanks for your reply. I looked at the example, they are all queried about points. Given a lot of geometry rings, is it possible to get all the rings within a bounding box? some portion of the rings may lie outside the box, as long as some portion of the ring lie inside the box. Thanks, Jeff |
jeffpoly wrote:
> Hello Adam, > > Thanks for your reply. I looked at the example, they are all queried about > points. Given a lot of geometry rings, is it possible to get all the rings > within a bounding box? some portion of the rings may lie outside the box, as > long as some portion of the ring lie inside the box. I assume that you're using the version from the sandbox. So you want to make an index of rings. Objects which may be indexable by the Rtree are Points or Boxes. The simplest way of connecting other types of objects (Rings in your case) with indexables is passing std::pair of e.g. Box and ID of the Ring. E.g. using namespace boost::geometry; typedef std::pair<Box, size_t> Value; index::rtree< Value, index::quadratic<32, 8> > rt; // then for each Ring inserting a new Value std::vector<Ring> rings; for(...) index::insert(rt, std::make_pair(make_envelope(rings[i]), i)); // and performing a query. std::vector <Value> returned_values; index::query(rt, index::within(box_region), std::back_inserter(returned_values)); Additional info you may find in the docs: https://svn.boost.org/svn/boost/sandbox-branches/geometry/index/doc/html/ Regards, Adam _______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
Hi, Adam,
Did you make any benchmarks of the spatial index? Just wanted to see some number to be aware of. I am planning to use it as a point location data structure for my Voronoi diagram implementation.
Additional info you may find in the docs: BTW, your documentation is displayed as a raw HTML. I had the same issue. The reason is that you don't have MIME types properly configured https://svn.boost.org/trac/boost/wiki/BoostSubversion. Thus your html files are treated as text files by the server, you may check it using web sniffer: http://web-sniffer.net/.
Thanks, Andrii
_______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
Andrii Sydorchuk wrote:
> Did you make any benchmarks of the spatial index? Just wanted to see > some number to be aware of. I am planning to use it as a point location > data structure for my Voronoi diagram implementation. I've tested it on sparse random data only. You may run /tests/additional_sizes_and_times.cpp on your machine if you like. On i7 2.94GHz, VS2010 and values of type pair<box<point<double, 2, cartesian>>, size_t> for linear creation algorithm with max=32, min=8 it takes 2.76s to create the index of 1M values, 1.03s to perform 100k box intersection queries and 0.26s to perform 10k nearest neighbor searches. For quadratic creation algorithm times are 4.24s, 0.35s and 0.12s respectively. I were using these tests to compare my implementation with the old one. If you plan to compare it to other implementations or on some real-life data please share results. > > Additional info you may find in the docs: > https://svn.boost.org/svn/__boost/sandbox-branches/__geometry/index/doc/html/ > <https://svn.boost.org/svn/boost/sandbox-branches/geometry/index/doc/html/> > > > BTW, your documentation is displayed as a raw HTML. I had the same > issue. The reason is that you don't have MIME types properly configured > https://svn.boost.org/trac/boost/wiki/BoostSubversion. Thus your html > files are treated as text files by the server, you may check it using > web sniffer: http://web-sniffer.net/. Thanks for the info, I should be ok now. _______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
In reply to this post by Andrii Sydorchuk
On Fri, Apr 13, 2012 at 3:51 PM, Andrii Sydorchuk
<[hidden email]> wrote: > Hi, Adam, > > Did you make any benchmarks of the spatial index? Just wanted to see some > number to be aware of. I am planning to use it as a point location data > structure for my Voronoi diagram implementation. I just realized you are the person giving the BoostCon presentation. I will be attending for sure and look forward to hearing your results. Cheers, Jeff > >> Additional info you may find in the docs: >> https://svn.boost.org/svn/boost/sandbox-branches/geometry/index/doc/html/ > > > BTW, your documentation is displayed as a raw HTML. I had the same issue. > The reason is that you don't have MIME types properly > configured https://svn.boost.org/trac/boost/wiki/BoostSubversion. Thus your > html files are treated as text files by the server, you may check it using > web sniffer: http://web-sniffer.net/. > > Thanks, > Andrii > > _______________________________________________ > 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 |
for linear creation algorithm with max=32, min=8 it takes 2.76s to create the index of 1M values, 1.03s to perform 100k box intersection queries and 0.26s to perform 10k nearest neighbor searches. For quadratic creation algorithm times are 4.24s, 0.35s and 0.12s respectively. I were using these tests to compare my implementation with the old one. If you plan to compare it to other implementations or on some real-life data please share results. Well I wasn't planning to compare it with other implementation. The Voronoi library is going now through the review process and implementation of the spatial index on top of the Voronoi cells is one of the features I'd like to add within the next few months. Thanks for the numbers! Besides what is the memory consumption of the spatial index data structure?
Regards, Andrii
_______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
Jeff, I just realized you are the person giving the BoostCon presentation. Very glad to hear! I don't think that I will give any numbers on spatial index as this is not something I was directly working on. But you'll definitely see some on multiprecision algorithms, Voronoi diagrams and triangulation :-).
Cheers, Andrii
_______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
In reply to this post by Andrii Sydorchuk
Andrii Sydorchuk wrote:
> for linear creation algorithm with max=32, min=8 it takes 2.76s to > create the index of 1M values, 1.03s to perform 100k box > intersection queries and 0.26s to perform 10k nearest neighbor > searches. For quadratic creation algorithm times are 4.24s, 0.35s > and 0.12s respectively. I were using these tests to compare my > implementation with the old one. If you plan to compare it to other > implementations or on some real-life data please share results. > > > Well I wasn't planning to compare it with other implementation. The > Voronoi library is going now through the review process and > implementation of the spatial index on top of the Voronoi cells is one > of the features I'd like to add within the next few months. Thanks for > the numbers! Besides what is the memory consumption of the spatial index > data structure? Size depends on data type, creation algorithm, probably compiler etc. Example results: For 1M values: pair<box<point<double, 2, cartesian>>, size_t> ~ 65MB, point<double, 2 cartesian> ~ 29MB, point<float, 2, cartesian> ~ 15MB, point<float, 3, cartesian> ~ 20MB. For 500k values: pair<box<point<double, 2, cartesian>>, size_t> ~ 32MB. Btw, if you store points in some container with random access you may use plain indexes as rtree's values. This should probably produce smaller rtree. To do it you need to use translator::index<Container> instead of default one. Regards, Adam _______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
For 1M values: Sounds pretty good, I was interested in those. Btw, if you store points in some container with random access you may use plain indexes as rtree's values. This should probably produce smaller rtree. To do it you need to use translator::index<Container> instead of default one. Good, will be aware of this. Cheers, Andrii
_______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
Free forum by Nabble | Edit this page |