Re: [boost] interest on a geometry library

From: Michael Andersen Nexø (nexo_at_[hidden])
Date: 2006-03-25 20:07:47

rodolfo_at_[hidden] wrote:
> Hi, is there any interest on a geomery library? 
Hi,

Following in the steps of Jason and Andy, I'd like to add into the fray 
my own attempt at a generic geometry library. I've uploaded the code to 
the Boost vault at 'Math - Geometry/MN_Geometry_01.zip'

Obviously my motivation for writing this framework has much in common 
with what has already been stated in this thread: Having a set of nice, 
generic vector/point/... classes that can provide the necessary 
foundation for writing cross platform code in domains such as imaging 
and computational geometry.

However, my focus has been more on examining how to create a looser 
coupling between the geometric data structures and the geometric 
algorithms, much in the spirit of the STL and BGL.

Provided the necessary traits classes have been specialized, it should 
be possible to seamlessly use the same data structures with both the 
'native environment' (be it OpenGL, the Win32 APIs or the like) and the 
generic algorithms provided by this library.

The end goal would be to create something along the lines of CGAL, but 
under the Boost license instead of GPL. But I'm sure something less 
comprehensive (and intimidating!) than CGAL would also be very useful, 
in case taking on such a huge effort seems overly ambitious :-)

A few notes on the code:

At the very core of the library are the classes

   template <class T, size_t D, class R> vector<T,D,R>;
   template <class T, size_t D, class R> point<T,D,R>;

where T is the scalar type, D is the dimensionality, and R is an 
optional class specifying the class internally storing the scalars.

In addition, the 'usual suspects' have been implemented: vector 
addition/subtraction, scalar multiplication, dot, cross, norm and the like.

Finally, a few generic algorithms have been written on top of this 
framework to test the design goal of being generic on the underlying 
representation class: Melkman's Convex Hull algorithm and the Douglas 
Peucker Line Simplification algorithm (Both of these are 2D-only, but 
the Douglas Peucker algorithm could quite easily be generalized to N 
dimensions, I believe).

Ideally, I think one should go even further in terms of genericity than 
I've done: Instead of letting the algorithms work on classes wrapping 
the 'native' geometry types they should operate *directly* on the native 
geometry structures by using traits-based accessors. After experimenting 
a little bit with this I eventually gave up on it, but I do think the 
approach deserves to be examined more.

The library is lacking a number of nice features from Andys and Jasons 
libraries, notably a matrix class, but I do think it has a few selling 
points of its own:

* Provides a generic interface for points, vectors that can be used for
   all scalar types and dimensionalities, thereby allowing the user to
   write generic algorithms that are independent of these parameters.

* The classes provide a Standard C++ container-like interface with
   begin(), end() etc., much in the same way as boost::array. For D<=3
   it also provides the usual x(), y() and z() shorthands.

* The interfaces can function as seamless adapters for platform specific
   geometry classes without incurring any extra overhead.
   All you need to do is specialize sequence_traits and xyz_traits for
   the classes, and you'll have a point/vector class that is compatible
   with the generic algorithms as well as the native platform.
   E.g. point<LONG,2,CPoint> winpoint;

* Optionally implements operators using expression templates, avoiding
   creation of temporaries in expressions such as: v = 2*w+u.

* The classes naturally extend the implicit conversion of the basic
   numeric types in C++.
   E.g: vector<float,2> f = vector<int,2>(3,2)+vector<short,2>(1,1)
   is allowed while vector<int,3> d = vector<float,3>(3.2, 3.0) will
   cause a compile-time truncation warning (if the compiler warns about
   float to int conversions).

* The classes handle type promotion the way it is naturally handled in
   C++ E.g.:
   typeof(point<char,2> + vector<long,2>) == typeof(point<long,2>)

* Whenever it makes sense the utilities and algorithms provide means for
   either explicitly specifying the scalar type of the resulting return
   value(s) or simply having the return type inferred, e.g.:

    1) Explicit return type:
       geom::vector<int,2> v(65536, 65536), w(65536, 65536);
       double d = dot<double>(v, w); // d == 2*(2^32), i.e. no overflow

    2) Automatic return type inference based on standard type promotion,
       (short*short => int):
       geom::vector<short,2> v(200, 200) w(200, 200);
       int d = dot(v,w); // d == 80000, i.e. no overflow

I've tested the code lightly under VC8, gcc 3.4.5 and Intel 9.0. I think 
it should work on relatively conforming compilers (just realized it 
causes an ICE on vc7.1, though).

Have a look and let me know what you think. Obviously, I would be 
willing to release all or parts of the code under the Boost license if a 
library in Boost were to use any of this.

Best regards
Michael Nexø