The most dangerous number in a geometry engine is sometimes not a coordinate.

It is a sign.

left turn
right turn
collinear

That one-bit-ish answer decides whether a point enters a convex hull, whether two segments cross, whether a Delaunay edge flips, whether a polygon is inside out, and whether a sweep-line data structure keeps a coherent topology.

The formula is small enough to memorize:

\[\operatorname{orient}(A,B,C) = (B_x-A_x)(C_y-A_y) - (B_y-A_y)(C_x-A_x).\]

Positive means A -> B -> C turns left. Negative means it turns right. Zero means collinear.

The formula is not the problem.

The problem is that a geometric algorithm usually treats that sign as a mathematical predicate, while the machine computes it as a rounded arithmetic program.

This Is Not Just Numerical Error

Goldberg’s floating-point tutorial starts from the unavoidable fact that real results must often be rounded into a finite representation.1 IEEE 754 makes that world dramatically better by specifying formats, operations, rounding, exceptional values, and interchange behavior.2 This is a great engineering contract.

It is not real arithmetic.

For many numerical programs, a small relative error is acceptable. A simulation with a slightly different final decimal may still be a good simulation. A linear solve with a small backward error may be perfectly respectable.

Computational geometry is less forgiving because arithmetic decisions become combinatorial decisions. If one predicate says three points are clockwise while another nearby predicate says the implied edge order is impossible, the program may not merely be inaccurate. It may build a data structure that has no geometric interpretation.

The CGAL manual states the practical issue plainly: geometric algorithms are usually proved assuming exact arithmetic, while hardware arithmetic does not implement the real numbers; wrong or contradictory decisions can lead to crashes or garbage outputs.3

So the unit of correctness is not:

small determinant error

It is:

correct determinant sign

Two Ways to Lose a Triangle

The lab below separates two failures that often get blended together.

The first is determinant rounding. The input coordinates are exactly representable as JavaScript Number values, but the two products in the determinant are large enough that subtracting them loses the unit difference.

The second is input rounding. The intended source coordinates live on an integer grid, but converting them to binary64 has already rounded away the small offsets. No predicate over the rounded Number values can recover the original triangle. You need to keep a more exact source representation, or accept that the input geometry changed.

point A point B point C certified sign wrong sign

Deterministic predicate test bench with a 624-assertion audit. It sweeps the product-cancellation band from 2^20 through 2^32, the source-coordinate-loss band from 10^12 through 10^18, exact binary64 sign reconstruction, sanitizer behavior, tolerance decisions, and the filtered fallback. It is not a complete Shewchuk expansion implementation; it is a small source-grid and rounded-input verifier.

With the default wide-product cancellation case, the points are:

A = (0, 0)
B = (M,   M + 1)
C = (M+1, M + 2)
M = 2^27

The exact determinant is:

\[M(M+2) - (M+1)(M+1) = -1.\]

All three coordinates around (M) are exactly representable as binary64 numbers. The input is not the issue. The issue is the products. They are around (2^{54}), where binary64 spacing is larger than one, so the two products round to the same floating-point value. The naive determinant becomes zero.

The exact sign says:

right turn

The naive double path says:

collinear

That is enough to break an algorithm whose next branch expects a real orientation predicate.

Now switch to lost input bit at scale 10^16.

The intended source-grid points are:

A = (10^16,     10^16)
B = (10^16 + 1, 10^16 + 1)
C = (10^16 + 2, 10^16 + 3)

The exact determinant is +1, a left turn. But around 10^16, a binary64 number cannot represent every adjacent integer. The +1 offset disappears. Two vertices partially collapse before the orientation formula runs.

This is a different failure. A robust predicate over binary64 inputs can tell you the exact sign of the rounded binary64 coordinates. It cannot infer that the caller meant an integer grid point that was never delivered.

The fix is not “use Shewchuk harder.” The fix is to keep the right representation at the boundary: integer coordinates, fixed-point coordinates, rationals, decimal strings, or another exact source model when those low bits matter.

Why Filters Work

Shewchuk’s robust predicates are famous because they do not simply replace every operation with slow arbitrary precision. The fast path computes an ordinary floating-point estimate. If an error bound proves that the sign cannot change, the predicate returns. If the sign is uncertain, the computation expands precision adaptively until the sign is guaranteed.4

Fortune and Van Wyk used a related filtering idea for exact integer arithmetic: try a fast approximate test, then use exact arithmetic only when interval-style error analysis says the approximate sign is not reliable.5

That is the key pattern:

approximate value + certified error bound

If zero is outside the error interval, the sign is known. If zero is inside, the sign is not known yet. Guessing with an epsilon is not the same thing.

The lab’s filtered path is deliberately small. It uses a standard-looking forward-error bound for the 2D orientation estimate and falls back to exact BigInt arithmetic on the source integer grid. It also computes the exact sign of the rounded binary64 inputs by decoding the Number bits into rational values. That second ledger is there to keep the caveat honest.

The Epsilon Trap

The common patch is:

if abs(det) < eps:
    pretend collinear

Sometimes that is a product decision, not a numerical method. Games, UI systems, physics engines, and CAD importers may intentionally snap geometry to a tolerance because the application wants a finite-resolution world.

But then the tolerance is part of the geometry.

It must be tied to the coordinate scale, downstream topology, and user promise. One global epsilon cannot mean “close enough” for a tiny glyph outline and a city-scale map at the same time. Worse, tolerance decisions can violate predicate consistency: one triangle is declared collinear, a neighboring one is not, and the mesh inherits a crack.

Exact geometric computation takes the opposite stance. CGAL’s exact computation paradigm uses higher precision when needed so that predicates behave according to their mathematical specification; common kernels distinguish exact predicates from exact constructions because many algorithms only need the branch decisions to be exact.67

That split is worth remembering:

predicate:     a decision, such as orientation or in-circle
construction:  a new geometric object, such as an intersection point

Exact predicates with inexact constructions are often a practical compromise. The branches are protected. The constructed coordinates may still be rounded. If later predicates depend on those constructed objects, the contract has to be revisited.

A Debugging Checklist

When a geometry bug only appears on some inputs, ask questions in this order:

What predicate made the first wrong topological decision?
Were the source coordinates already rounded before the predicate saw them?
Is the determinant sign wrong, or merely too close for the current fast path?
Does the algorithm require exact predicates, exact constructions, or both?
Is an epsilon being used as a numerical proof or as a deliberate snapping rule?
Are coordinate transforms increasing scale before small offsets are tested?
Can the code isolate predicates behind a kernel instead of scattering arithmetic?

The last item is a software-engineering point, not a math point. Robustness is hard to retrofit when every caller computes its own little determinant. It is much easier when orientation, incircle, side-of-plane, and distance comparisons live behind a small predicate API with an explicit arithmetic contract.

The tiny determinant is not just a formula.

It is where continuous coordinates become discrete control flow.

The triangle has a sign bit. Treat it like one.

  1. David Goldberg, “What Every Computer Scientist Should Know About Floating-Point Arithmetic”, ACM Computing Surveys 23(1), 1991. ↩

  2. IEEE Standards Association, “IEEE 754-2019: Standard for Floating-Point Arithmetic”, approved 2019. ↩

  3. Olivier Devillers and Stefan Schirra, “Robustness Issues”, CGAL Manual. ↩

  4. Jonathan Richard Shewchuk, “Adaptive Precision Floating-Point Arithmetic and Fast Robust Predicates for Computational Geometry”, Discrete & Computational Geometry 18:305-363, 1997. PDF: robustr.pdf. ↩

  5. Steven Fortune and Christopher J. Van Wyk, “Efficient Exact Arithmetic for Computational Geometry”, SCG, 1993. OpenAIRE summary: publication page. ↩

  6. CGAL, “The Exact Computation Paradigm”. ↩

  7. CGAL, “2D and 3D Linear Geometry Kernel: Predefined Kernels”. ↩