<div dir="ltr"><div dir="ltr"><div dir="ltr"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div class="gmail_quote"><br><div><br></div><div>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:</div><div><br></div><div><a href="https://www.cs.cmu.edu/~quake/robust.html" target="_blank">https://www.cs.cmu.edu/~quake/robust.html</a><br></div><div><br></div><div><a href="https://www.cs.cmu.edu/afs/cs/project/quake/public/code/predicates.c" target="_blank">https://www.cs.cmu.edu/afs/cs/project/quake/public/code/predicates.c</a></div><div><br></div><div>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.</div></div></div></div></div></div></blockquote><div><br></div><div>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).</div><div><br></div><div>AFAIK double-double precision is sufficient for robust evaluation of orientation.  Seems to work well, anyway.  </div><div><br></div><div>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.</div><div><br></div><div>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).</div><div><br></div><div><br></div><div>[1] <a href="https://github.com/locationtech/jts/blob/master/modules/core/src/main/java/org/locationtech/jts/algorithm/CGAlgorithmsDD.java">https://github.com/locationtech/jts/blob/master/modules/core/src/main/java/org/locationtech/jts/algorithm/CGAlgorithmsDD.java</a></div><div><br></div><div>[2] <a href="https://github.com/locationtech/jts/blob/master/modules/core/src/main/java/org/locationtech/jts/triangulate/quadedge/TrianglePredicate.java#L187">https://github.com/locationtech/jts/blob/master/modules/core/src/main/java/org/locationtech/jts/triangulate/quadedge/TrianglePredicate.java#L187</a></div><div> </div></div></div></div></div>