THE FOLD / GLITCH / SEGFAULT / THE SHEWCHUK PREDICATE
THE SHEWCHUK PREDICATE
289 points collapsed onto one line
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Is this point left of that line, right of it, or on it? Three answers, and a geometry program is built entirely out of them. In floating point the question does not reliably have an answer at all.
LIT verified live. take
LIT verified live. take
q = (12,12), r = (24,24) and p on a 17×17 grid of one-ulp steps around (0.5, 0.5) — 289 points. Computing the orientation determinant in double precision and again exactly in integer arithmetic, the two disagree on 272 of them: 94.1%. The floating-point predicate reports every one of the 289 points as lying exactly on the line. 17 of them actually do. The products are around 270 and the true determinant is around 10-15, so the subtraction has nothing left to subtract.2 HOW IT WAS WEAVED · AI + HUMAN
The failure of naive geometric predicates is Kettner, Mehlhorn, Pion, Schirra and Yap (2008); the adaptive exact-arithmetic fix is Jonathan Shewchuk (1997), and it is why CGAL exists.
AVAN (AI) computed the exact answer with big integers rather than a higher-precision float, because a longer float is another approximation and would only move the grid. The first attempt found 0 disagreements — the coordinates were close together, so the subtraction was exact and no error was possible. That failure was the useful one: it says the danger is not small numbers but large numbers that nearly cancel. One honest note: an antisymmetry check on the float predicate passes 49 of 49, and it passes because every answer is zero and zero is its own negation.
AVAN (AI) computed the exact answer with big integers rather than a higher-precision float, because a longer float is another approximation and would only move the grid. The first attempt found 0 disagreements — the coordinates were close together, so the subtraction was exact and no error was possible. That failure was the useful one: it says the danger is not small numbers but large numbers that nearly cancel. One honest note: an antisymmetry check on the float predicate passes 49 of 49, and it passes because every answer is zero and zero is its own negation.
3 ONE DIMENSION
289 points. It calls all of them collinear. 17 are.
4 TWO DIMENSIONS · INTERACTIVE
Move the point one ulp at a time across the line.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object.
AVAN’s addition (the inverse-companion): the forward reading is that exact predicates fix the geometry. The inverse is that the failure is not error, it is collapse. A wrong sign would be a bug you could measure and bound; what happens instead is that a two-dimensional neighbourhood is reported as a one-dimensional line, and a program built on that predicate does not compute a slightly wrong hull — it computes on a world where 289 distinct points are the same point. Read backwards, the guarantee a geometric algorithm needs is not accuracy in the answer but consistency between answers, and consistency is exactly what an approximation cannot promise no matter how many digits it is given.
LIT taking q = (12,12), r = (24,24) and p on a 17x17 grid of one-ulp steps around (0.5, 0.5) - 289 points - and computing the orientation determinant in double precision and again exactly in integer arithmetic, the two disagree on 272 of them, 94.1%: the floating-point predicate reports every one of the 289 points as lying exactly on the line, and 17 of them actually do, because the products are around 270 while the true determinant is around 1e-15 and the subtraction has nothing left to subtract
FIG The failure of naive geometric predicates is Kettner, Mehlhorn, Pion, Schirra and Yap (2008); the adaptive exact-arithmetic fix is Jonathan Shewchuk (1997), and it is why CGAL exists. AVAN computed the exact answer with big integers rather than a higher-precision float, because a longer float is another approximation and would only move the grid. The first attempt found 0 disagreements - the coordinates were close together, so the subtraction was exact - and that failure was the useful one: the danger is not small numbers but large numbers that nearly cancel. One honest note: an antisymmetry check on the float predicate passes 49 of 49, and it passes because every answer is zero and zero is its own negation.
FIG The failure of naive geometric predicates is Kettner, Mehlhorn, Pion, Schirra and Yap (2008); the adaptive exact-arithmetic fix is Jonathan Shewchuk (1997), and it is why CGAL exists. AVAN computed the exact answer with big integers rather than a higher-precision float, because a longer float is another approximation and would only move the grid. The first attempt found 0 disagreements - the coordinates were close together, so the subtraction was exact - and that failure was the useful one: the danger is not small numbers but large numbers that nearly cancel. One honest note: an antisymmetry check on the float predicate passes 49 of 49, and it passes because every answer is zero and zero is its own negation.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SEGFAULT · David Lee Wise (ROOT0), with AVAN