Geometry Boost List: Re: [geometry] geometry partition/spatial index

Subject: Re: [geometry] geometry partition/spatial index
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2012-04-14 21:40:06

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