Geometry Boost List: [ggl] space partitioning

Subject: [ggl] space partitioning
From: Simonson, Lucanus J (lucanus.j.simonson)
Date: 2011-01-11 14:17:39

Adam Wulkiewicz wrote:
> 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

My main concern is that spatial indexes and spatial query has been a rich field of research in computer science for about 40 years.  I think anyone who undertakes a boost project should spend some time reading the literature and learn what the current state of the art is and understand it in the context of what the advances were that got us to this point.  Then, in terms of implementation the most important thing is to define an iterface that is generic and sufficiently general to accommodate a range of possible implementations.  Once we have that we have a research test bed for implementing different data structures and testing them through a common iterface to assess their suitability.  Different applications are best served by different data structures, but if we can provide a common iterface then people can map their own data structures to the interface and allow boost.geometry to interoperate with their spatial query data structures when performing algorithms based on spatial query.  This is similar to 
how boost graph allows the same graph algorithms to work on different graph data structures.  I realize that it is tempting to implement things like nearest neighbor using internal knowledge of the query data structure, but I think it should be a priority to decouple the algorithms from the data structures.

Regards,
Luke