integers vs floating point
eppstein at ics.uci.edu
Mon Jul 23 20:22:20 CEST 2001
The following looks like the perfect example of what happens when you use
floating point in a situation where exact arithmetic is necessary, in case
anyone is still unconvinced that integers are not "just a special case of
In comp.graphics.algorithms, "Kenny Erleben" <kenny at diku.dk> wrote:
> I got this little practical problem, I have implemented an incremental
> randomized convex hull algorithm (pretty much like the one described in "de
> Berg", for those familiar with this book).
> The algorithm works nicely for a large range of point sets, however in some
> cases everything just breaks down:-( I get into nasty cases where the
> conflict graph suddenly reports an incorrect number of visible faces and the
> horizon is no longer a simple closed cycle, I have investigated why the
> problem occurs and have concluded that it must be due to numerical
> inaccuracy when determing the visibility of a face. Currently Im using the
> plane equation of a face and the signed distance from it to determine
> Does anybody know a way around these nasty numerical difficulties?
> Oh, perhaps I should mention that plane equations are important for my
> application of the convex hulls (Im using v-clip on convex hierarchies).
David Eppstein UC Irvine Dept. of Information & Computer Science
eppstein at ics.uci.edu http://www.ics.uci.edu/~eppstein/
More information about the Python-list