[geos-devel] double double

Martin Davis mtnclimb at gmail.com
Sat Dec 8 12:48:38 PST 2018

> It is not enough to be robust in all cases also though - here
> are Shewchuk's proved-robust predicates that have to use up to four doubles
> to manage long arithmetic:
> https://www.cs.cmu.edu/~quake/robust.html
> https://www.cs.cmu.edu/afs/cs/project/quake/public/code/predicates.c
> If you find 512-bit float somewhere you may get away with it directly
> though, but I don't think they are available on consumer non-DSP CPUs.

JTS now uses DoubleDouble and Shewchuk's adaptive approach to compute the
critical orientation predicate [1].  This solved some long-standing and
subtle problems with the previously-used Robust Determinant algorithm  So
I'd recommend GEOS switch to using it (unless the performance is a real

AFAIK double-double precision is sufficient for robust evaluation of
orientation.  Seems to work well, anyway.

JTS also has a DoubleDouble-based function for computing the intersection
point of two segments, but this isn't yet used as the main intersection
function (not sure why not - maybe I just didn't quite get there.  It would
be nice to use it as it's a lot simpler than the normalization approach now
used.  But probably worth checking it it impacts performance.

There's also a DoubleDouble incircle predicate [2], which is not currently
in the mainline, but probably should be (I think there were some known
failure cases of the other code).


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20181208/690bc6bc/attachment.html>

More information about the geos-devel mailing list