geometry partition/spatial index

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

geometry partition/spatial index

jeffpoly
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
Reply | Threaded
Open this post in threaded view
|

Re: geometry partition/spatial index

Adam Wulkiewicz
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
Reply | Threaded
Open this post in threaded view
|

Re: geometry partition/spatial index

jeffpoly
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
Reply | Threaded
Open this post in threaded view
|

Re: geometry partition/spatial index

Adam Wulkiewicz
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
Reply | Threaded
Open this post in threaded view
|

Re: geometry partition/spatial index

Andrii Sydorchuk
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:
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
Reply | Threaded
Open this post in threaded view
|

Re: geometry partition/spatial index

Adam Wulkiewicz
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
Reply | Threaded
Open this post in threaded view
|

Re: geometry partition/spatial index

Jeff Trull-2
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
Reply | Threaded
Open this post in threaded view
|

Re: geometry partition/spatial index

Andrii Sydorchuk
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
Reply | Threaded
Open this post in threaded view
|

Re: geometry partition/spatial index

Andrii Sydorchuk
Jeff,
 
I just realized you are the person giving the BoostCon presentation.
I will be attending for sure and look forward to hearing your results.

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
Reply | Threaded
Open this post in threaded view
|

Re: geometry partition/spatial index

Adam Wulkiewicz
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
Reply | Threaded
Open this post in threaded view
|

Re: geometry partition/spatial index

Andrii Sydorchuk
For 1M values:
pair<box<point<double, 2, cartesian>>, size_t> ~ 65MB,
For 500k values:
pair<box<point<double, 2, cartesian>>, size_t> ~ 32MB.

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