Module orientation 

Certified orientation predicates.

orient2d answers “does C lie left of, right of, or exactly on the directed line AB”. The answer is a sign, and a sign drives topology, so a plausible answer is not good enough: this module returns Certified and escalates to exact arithmetic rather than guessing when the filter is inconclusive.

The strategy is the standard filtered cascade:

1. Evaluate the determinant in plain f64 and compute a forward error bound.
2. If the magnitude exceeds the bound, the sign is proven; return it.
3. Otherwise evaluate the determinant exactly (see below).

Step 1 succeeds for almost all real inputs, so the exact path is rare.

The exact path first tries an expansion: each coordinate difference is split into its rounded head and its exact rounding tail, and the products of heads and tails are summed exactly (four terms when no difference rounds, as on grid-aligned collinear points, the common degenerate case, and up to sixteen otherwise). It runs only where none of its products can overflow or underflow: every difference in [1e-90, 1e90] and every nonzero tail at least 1e-120. Any other input goes to a fixed-size dyadic evaluation over the original coordinates, as orient3d’s fallback does (#404): it forms no difference and no rounded product, so it is exact for every finite input. An earlier expansion evaluation had no such guard; it overflowed beyond about 1e154, lost error terms to underflow, and could misjudge coordinates of very different magnitudes. The filter itself declines an input whose differences are outside [1e-90, 1e90], where its products may overflow or underflow, and so hands it to the exact path.

Functions

orient2d

Orientation of c relative to the directed line a -> b.

orient2d_filter

The fast filter alone, exposed so the escalation can be observed and tested.