Re: [boost] new library (space partitioning)

Subject: Re: [boost] new library (space partitioning)
From: OvermindDL1 (overminddl1_at_[hidden])
Date: 2010-07-26 17:00:47

On Mon, Jul 26, 2010 at 2:35 PM, Adam Wulkiewicz
<adam.wulkiewicz_at_[hidden]> wrote:
> Hi,
>
> It's my first message so I'd like to introduce myself. My name's Adam
> Wulkiewicz, I'm a doctoral student of Technical University of Lodz, Poland.
>
> I'd like to take part in evolution of Boost library. I've implemented some
> space partitioning data structures and k-dimensional generalizations of STL
> containers and thought that since these kind of containers are useful to
> many people it would be nice to have them in Boost.
>
> For people who don't know what are space partitioning data structures:
> These data structures divides arbitrary k-dimensional space containing some
> k-dimensional 'objects' to accelerate searching for an 'object' or subset of
> 'objects' placed in a part of divided space. Just like fe. a binary tree
> divides a set of numbers to accelerate searching.
>
> These data structures are used fe. in:
> - computer graphics to accelerate rendering (searching of 3D objects, fe.
> triangles in raytracing or photons in photon mapping),
> - games to accelerate testing for intersection of rays with a scene and
> movable objects.
>
> In these examples 'the space' is 'common' 3D euclidean space but you may
> divide every space you like to accelerate searching: spherical space, space
> containing features of an object used in image recognition process and so
> on.
>
> I've implemented:
> - k-dimensional generalizations of STL containers (used by some space
> partitioning data structures)
> - k-dimensional space partitioning data structures
> Â  Â  Â  Â - regular grid
> Â  Â  Â  Â - kd-tree
> Â  Â  Â  Â - something I've called regular tree,
> Â  Â  Â  Â it's k-dimensional generalization of quadtree/octree,
> Â  Â  Â  Â so for k=2 it's quadtree, for k=3 it's octree,
> Â  Â  Â  Â for k=4 it's 16tree and so on.
> - k-dimensional euclidean algebra/geometry data structures
> Â  Â  Â  Â - points, vectors etc.,
> - unit tests.
>
> There are boost-like names used in code allready. If you'd like to know more
> just ask.
>
> My question is, what do you think about it?

I am quite interested, I would have use for such a library.