> > > > 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
_______________________________________________ geos-devel mailing list geos-devel@lists.osgeo.org https://lists.osgeo.org/mailman/listinfo/geos-devel
