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

From: Arash Partow (arash_at_[hidden])
Date: 2008-03-28 09:42:11

Steve M. Robbins wrote:
 > 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
 >

Steve I mispoke, not including your intersections library
contributions (which I've been using for some time now - great stuff!)
that would be the case, in fact all one needs to do is look at the
insides of your routines to see how complex it "was"....

Though to be honest the flexibilty CGAL provides wrt types/kernels is
terrific and I believe is unparalleled (when not including matlab and
mathematica)

 > 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).

That is a very correct and astute observation - I couldn't agree more
predicates specificall and their definitions should be done concurrently
with point concept definitions. specifically the responsiblity of use and
precision should mentioned.

 >
 > One of the attractive features of CGAL, to me, is that their
 > algorithms are templated over the Kernel type.

Its also one of the aspects which makes its learning curve soo
steep and the effort requirement for people to develop for and
around CGAL so great.

 > 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.
 >

I also agree with you here, but would like to propose the EGC (Yap and Co.)
related stuff be done within the object's value type not the algorithm. But
then you'll say: well I can get better than normal precision from certain
perdicates and PODs  using Shewchuk's methods. To that I would say lets define
a series of operators and predicates and then develop algorithms based on those:

ie: distance that was:

return std::sqrt((x1,x2) * (x1,x2) + (y1,y2) * (y1,y2));

now becomes:

return sqrt(add(sqr(sub(x1,x2)),sqr(sub(y1,y2))));

where the routine making the call will have a computation_trait that
will define add,sub,mul,div etc for that type and a policy oriented
approach would easily allow the user to pick and choose between EGC
and "fast and loose" computational precision/speed models.

 > 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?
 >
Damn you're on a roll today, I haven't agreed with anyone in an e-mail as I have with you!

 > 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?
 >

What can be done better:

1. Better/easier access for simple users - Simple things, I've got 4 doubles give me the distance
2. Better use of new paradigms such a metaprogramming, and not just templates in the forms of generics
3. A generally acceptable license for both open and commercial uses
4. Syntax that when used with code such as STL doesn't look out of place (more cosmetic not priority)
5. Something that can hopefully be used in part as a future TR (TR101 perhaps? :D)

Arash Partow
__________________________________________________
Be one who knows what they don't know,
Instead of being one who knows not what they don't know,
Thinking they know everything about all things.
http://www.partow.net