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

From: Barend Gehrels (barend_at_[hidden])
Date: 2008-03-28 17:19:10

Fernando Cacciola wrote:
> 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".
>   
Hi Fernando,
I wrote a reaction on this point 1) already, but as this thread is long 
and there is much discussion, I will repeat it in other words. Joel 
wrote this:
>      liba::point p1;
>      libb::point<int> p2;
>      POINT p3; // MFC
>
>      cout << distance(p1, p2) << endl;
>      cout << distance(p2, p3) << endl;
and it is implemented in the 2nd preview exactly like this. The library 
supports different point types now. For any point type a 
distance-strategy can be built. Of course there are builtin strategies 
for built in points (at this moment point_xy for 2D Euclidian, point_ll 
for latlong). Below a small piece of the distance_example I wrote, from
http://geometrylibrary.geodan.nl/5__distance__example_8cpp-example.html#a6
> std::cout << "latlong: " << 0.001 * distance(a, r) << " km" << std::endl;
> std::cout << "RD:      " << 0.001 * distance(a_rd, r_rd) << " km" << 
> std::endl;
where a, r are instances of the point_ll class, and a_rd, r_rd are 
instances of the point_xy class (forget RD, it is a just specific 
projection). Point classes might be completely different. The classes 
above are derived from a common ancestor, but that is *not* required.

> 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.
>   
I recall Hervé's suggestion, and I followed it literally. It is the 
largest difference between Preview 1, which indeed felt short in this, 
and Preview 2, where points are coordinate-free.

> 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.
>   
I'm not a CGAL expert, and did not plan to rebuild CGAL. Your suggestion 
is interesting. However, it is directed to the xy-case or xyz-case, not 
to the latlong case. In the library in preview distances between points 
on Earth, or on any sphere, can be calculated. Those calculations cannot 
be done using vectors but need trigoniometrics.
The essential point of the library is: total different point types, with 
accompagnying stategies. And of course you can use vector calculations 
in those strategies. I implemented the distance without, just the "good 
old" Pythagoras rule, delivering a squared distance... But point-segment 
distance needs, and has, vector calculations.
> 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.
>   
Agree, and it is implemented like that, for xy-points. For 
latlong-points it doesn't make sense.
> 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.
>   
I think this is solved by the strategy approach. I'm not a CGAL expert, 
for me the problem of CGAL is the license. I cannot use it, and 
therefore I'm not that interested in it. Most things I know because of 
this mailing list.
>
> .. more to come...
>   
OK, thanks for your comments!

Barend