[geos-devel] double double

[Martin Davis]

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

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


[1]
https://github.com/locationtech/jts/blob/master/modules/core/src/main/java/org/locationtech/jts/algorithm/CGAlgorithmsDD.java

[2]
https://github.com/locationtech/jts/blob/master/modules/core/src/main/java/org/locationtech/jts/triangulate/quadedge/TrianglePredicate.java#L187
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20181208/690bc6bc/attachment.html>