On Wed, Mar 5, 2008 at 11:55 AM, John Femiani <JOHN.FEMIANI@asu.edu> 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