Re: [boost] Summer of Code 2008 Ideas

From: Michael Fawcett (michael.fawcett_at_[hidden])
Date: 2008-03-05 12:24:02

On Wed, Mar 5, 2008 at 11:55 AM, John Femiani <JOHN.FEMIANI_at_[hidden]> wrote:
> >>
>  >> Something that I miss very much is library for
>  >> multidimensional/spatial data structures.
>  >>
>  >
>  >I strongly agree with this too. I often develop libraries that are related
>  >to 3D geometry, and I always end up regretting that there doesn't exist any
>  >somehow "standard" spatial data structure that wouldn't be related to any
>  >particular implementation or product. As a consequence it's very difficult
>  >in this domain to deliver libraries that are really portable and easily
>  >integrable.
>
>  What are we talking about-- Meshes? Trees?  Didn't somebody work on a half-edge mesh last summer?
>  I personally would love it if somebody would work on interval range trees or kd trees etc. as well as meshes that work with BGL.

Hopefully we could have Bounding Interval Hierarchies, kd-trees,
oct-trees, quad-trees, etc...all built on a generic tree framework.

I have some code that provides generic iterators (post-order,
parent-iterator, child-iterator) that could be extended to pre-order,
and breadth-first iterators.  They are built on boost:iterator_facade.

Adobe also has a generic forest class that seems to be very close to
what has been discussed here before when talking about a generic n-ary
tree class.

I also have some rough code for a Bounding Interval Hierarchy, and a
generic n-ary tree, but they are definitely not boost-ified or ready
for public use.

Some other items - the generic n-ary tree should have a
Boost.Intrusive counter-part, the iterators are probably generic
enough to live in Boost.Iterators, and there exists SoC tree code that
might be able to be used for providing tree rebalancing functions.

>  Hopefully these can avoid the boost minefield relating to 'point' types because trees only work on coordinates (no need to intepret them as "points" per se),  and meshes are entirely topological.

I don't see anything wrong with a CartesianCoordinateConcept that
requires x(), y(), z() along with typedefs or something to that
effect.  I think the consensus that was reached with the "point"
discussion is that too many people want too many different things out
of a generic point class, but the algorithms are concerned with very
few details of the point class, mainly just "expose x, y, and z, and
the types of each" - so don't try to make the perfect generic point
class, let people use their own.  Just provide algorithms that will
work with their point classes, as well as the default (very basic)
point class provided by the library.

--Michael Fawcett