Boost logo

Boost :

Subject: [boost] [geometry] robustness approaches
From: Fernando Cacciola (fernando.cacciola_at_[hidden])
Date: 2009-03-13 17:36:37


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

--
Fernando Cacciola
SciSoft Consulting, Founder
http://www.scisoft-consulting.com

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk