Geometry Boost List: [ggl] space partitioning

Subject: [ggl] space partitioning
From: Barend Gehrels (barend.gehrels)
Date: 2011-01-12 09:51:17

Hi Adam,

> First of all I'd like to appologize for my absence on the list. I'd like
> to return to the discussion about the spacial index.

Welcome back!

>
> 1. I'd like to talk about Lucanus' idea that it should be possible to
> build the index on the set-like container providing only keys calculated
> as an indexes on some space-filling curve.
> The base container should be a multimap or multiset but then the
> elements should implement some key concept. The space or some subspace
> should be divided for cells which has equal sizes. And the cells'
> z-curve indexes should be taken as keys.
> The coordinates shouldn't be just transformed into z-curve indexes
> (smallest possible cells). If the precission were too big the structure
> would grow and it would kill the searching process. The same big
> volumetric objects may be present in different cells.
>
> User should just pick suitable cell's dimensions.
>
> The resulting container is some kind of sparse, n-dimensional, self
> balancing regular grid.
>
> What do you think?

Basically it sounds good but it does not yet give me a concrete idea of 
how to use it.
Can you give an example?

>
> 2. Mateusz have you been working on the Federico's quad tree? I have
> version sent by you in 10.09.2010.
>
> Btw. it could be generalized for n-dimensions.
>
> 3. Currently I'm becoming acquainted with boost::geometry and I've 
> notticed
>
> struct access<point<CoordinateType, DimensionCount, CoordinateSystem>,
> Dimension>
>
> I think that Dimension parameter name may be confusing. It might be
> something like DimensionIndex or even better CoordinateIndex.

access is a traits metafunction, so I think there will not be many 
confusions.
Though DimensionIndex is also good. CoordinateIndex does not correspond 
with DimensionCount...

Anyway, if you specialize traits, you may name these parameters 
yourselves, and I can imagine that, for example, for spherical or polar 
systems you might pick another name.

Regards, Barend