Re: [boost] Preview 2 of a template Geometry Library

From: Fernando Cacciola (fernando.cacciola_at_[hidden])
Date: 2008-03-27 19:00:39

Hi Barend,

There was so much already discussed that I don't know where to start, so I 
decided to just sort of top-post touching a bit of everything.

1) First of all, please pay close attention to Joel's suggestion and 
reconsider your library's design from a truly generic programming POV, 
specially to separate models (data structures) from algorithms and 
properties (coordintes, etc)

In particular, try to understand the the free-member approach portraid by 
Joel's version of "distance".

2) As somneone said (sorry I couldn't keep track of who said what just yet), 
a monolithic point concept is almost as bad as a monolithc point class. 
Recall the coordinate-free suggestion from Hervé? Then a point is a point 
regardless of its coordinates just as a line is a line regardless of the two 
points that can be used to define it. Orthogonal requirements imply separate 
concepts so I would start from the requirements, that is, the algorithms: 
that will tell you what set of concepts collectively correspond to a point.

3) Don't forget aritmetic, that is, you'll need numeric concepts as well, 
and (as you can see what is done in CGAL), a super number concept is too 
much and too little at the same time. Again, work from the algorithms, 
backwards, to discover the numeric concepts you need.

4) IMO you definitely need to bring Vectors into the game and their two most 
important operators: dot and cross products. For instance, the 
square_distance between two points should be defined AND implemented as the 
squared length of the vector from one point to the other. This removes any 
requirement that points have coordinates. And vectors don't need coordinates 
either (from a concept POV) since the squared length of a vector v is its 
dot product with itself, so, all you need to define and implement a square 
distance between two points is a dot product operation between vectors. As 
long as vector models (which know about their components) supply that, you 
don't need any mention of coordinates at all anywhere (to support that 
operation generically). Granted, some *users* may need to get their hands at 
the coordinate of a point, but the more coordinate-free the library itself 
is the better.

5) There is a reason why CGAL doesn't provide a distance function at all but 
only a squared_distance, and I agree with that reason: sqrt() kills 
robustness and distances are usually used for comparisons, so you seldom 
need that.

6) There is a reason why CGAL is parametrized in a Kernel and not a 
coordinate type, and I agree with that reason: effective robustness is the 
result of the proper encapsulation of predicates and constructions, and a 
Kernel type provides a mechanism to *choose* that easily. That is, I can 
call an algorithm taking JUST a point class with double coordinates but 
having it balance accuaracy vs speed as I need it and at compile time 
without wrapping the point class at all. That means I need to give the 
algorithm additional compile-time information. In CGAL that information is 
given by the Kernel type expose by the Point type. It doesn't have to be 
like that exactly, but it is important to use a sufficiently useful type to 
tailor the algorithm. Parametrization on just the coordinate types is not 
enough.

.. more to come...

Best

-- 
Fernando Cacciola
SciSoft
http://fcacciola.50webs.com
http://groups.google.com/group/cppba