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

From: Steve M. Robbins (steve_at_[hidden])
Date: 2008-03-27 05:05:13

On Wed, Mar 26, 2008 at 07:30:07PM -0400, Demian Nave wrote:
> Arash Partow wrote:
> 
> > Writing a geometry library is hard, look at CGAL over $1million Euros in funding, both
> > commercial and academic wings and look at the monstrosity they have
> > produced. If you can determine the intersection point of 2 line
> > segments in under 15lines of code using CGAL I take my hat off to
> > you :>

There's an implied criticism that 15 lines is too much (?)  

Looking at the example intersection code [1], ignoring the typedefs
and variable declarations, the intersection part is a function call
and an "if" statement.  I don't see how that can be simplified.  Are
you complaining about the typedefs?  The fact that you have to take
care of the case that segment intersection is itself a segment?

[1] http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Kernel_23/Chapter_main.html#Subsection_2.4.3

> As someone who has *tried* to use CGAL to do intersections and an variety 
> of other operations in under 15 lines of code, I second this statement. 
>   My only advice: don't let a Boost geometry library turn into CGAL. :-)

CGAL is huge, in part, because it provides all the higher-level stuff
like triangulations, meshing, surfaces, and the like.  The focus here
is much much smaller so I don't think anyone imagines it turning into
CGAL.

Much of the discussion here surrounds defining a Point concept, which
is valuable, but you typically also need related concepts Vector, Ray,
Line, and Segment, together with the predicates (like point
orientation) and constructions (like segment intersection).  CGAL
bundles all these together in a geometric traits class called a
Kernel.

One of the attractive features of CGAL, to me, is that their
algorithms are templated over the Kernel type.  So you can use exact
geometric computing if desired, or play fast and loose with doubles,
or do something in between (exact predicates, but inexact
constructions) just by choosing the appropriate Kernel.

Superficially, the discussion here seems to be talking only about one
tiny part of a geometry kernel, namely points and simple functions
like distance.  Is the end goal just that: a set of primitives with no
regard to robustness?

Alternatively, if the ultimate goal is larger, then how does it differ
from a CGAL kernel?  If the CGAL kernel concept is too complicated,
what is going to be omitted?  Is there some part of a kernel that is
unnecessary?  Are there CGAL design mistakes (from its 12-year
history) that can be done better?

-Steve