Re: [boost] GGL Review

Subject: Re: [boost] GGL Review
From: Jose (jmalv04_at_[hidden])
Date: 2009-11-16 13:18:25

On Mon, Nov 16, 2009 at 6:34 PM, Phil Endecott
<spam_from_boost_dev_at_[hidden]> wrote:
> A while ago, Fernando Cacciola posted some links to a set of presentations
> and papers about FP line intersection robustness that I found very
> enlightening:
....

> I strongly encourage anyone who wants to express an opinion on this subject
> in the context of the current review to look at this material; it is very
> accessible and on page 2 there's a compelling example of what can go wrong.

I include a the end of this message he 24/3/2009 email on geometry
robustness as it provides a succinct opinion.
It's unfortunate that this email encouraged a confrontational approach
rather than the common boost cooperation approach !

> Personally, I find it better to use fixed point (e.g. for
> latitude/longitude) and relax knowing that I don't have to worry.

One thing is to answer what is the best library design for multiple
application domains and the other one is what is typical in each
domain.

Is it common to use fixed point in the GIS domain ?  I think libraries
have to capture common practice so that is easy to migrate to them

---------------------------
24/3/2009 email on Geometry Robustness by Fernando Cacciola
--------------------------
Hi boost geometers ;)

When Barend first presented his geometric library proposal I argued
that the so-called "epsilon-based" approach used by the library is
just fundamentally wrong, and most importantly, totally unnecessary
since much better methodologies exist.

It deeply worries me to find that the GGL proposal haven't been
updated in this regard, because the instrumentation of the proper
techniques have a significant impact on the overall design.
Robustness can't be treated as an implementation detail to be deal
with later on (and I'm sorry if I haven't made this point clear when I
warn about it before).

If I where to review the library today I would have to strongly vote
for rejection because of this.

Here is a simple example of the fundamental problems I see all over
the proposed library:

There is a point_in_circle algorithm, which (as I can see from its
implementation), essentially returns whether the distance from the
point to the center is smaller than the circle radius.  No doubt
*that* is the one and only correct *mathematical* formulation for the
predicate, but is one that just doesn't stand in practice at all.

Computing *that very particular predicate ROBUSTELY* has been the
subject of active research during the past decade, to such an extent,
that pretty much every paper or article on the subject of robustness
in geometric computing uses the in-circle test as a common example.

The library proposed by Lucannus, OTOH, at least acknowledges the
problem appropriately and approaches a solution in the right direction
(there is still some important design-influencing considerations but
are not showstopers)

Here is a starting point

http://www.mpi-inf.mpg.de/departments/d1/ClassroomExamples/

Best