Geometry Boost List: [ggl] space partitioning

Subject: [ggl] space partitioning
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-01-11 11:50:58

Hi everyone,

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.

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?

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.

Regards,
Adam Wulkiewicz