Orientation predicates and exact arithmetic

For three ordered planar points, subtract the first point from the other two and take the determinant of the resulting vectors. Positive means the third point lies to the left of the directed first-to-second line; negative means right; zero means collinear, including repeated-point cases. Half the determinant is signed triangle area. Reversing two arguments reverses the sign. A point on the supporting line is not necessarily on the closed segment: containment additionally requires coordinate bounds or an equivalent between-endpoints test.

Integer or rational coordinates allow exact sign decisions using sufficiently large arithmetic. A unit-cost real-arithmetic analysis often treats this test as constant time, but an implementation must account for integer bit lengths, overflow, and the cost of arbitrary precision. Even when every input coordinate is exactly representable as a floating-point number, the products and subtraction forming a determinant may not be exact. Cancellation makes this especially dangerous near collinearity, as the worked example demonstrates without any initial input-rounding error.

A filtered predicate first computes a fast approximation together with a rigorous error bound derived for its evaluation scheme. If the approximation's magnitude exceeds that bound, the exact sign is certified. Otherwise the implementation recomputes with stronger arithmetic, such as expansion arithmetic or exact rationals. An interval filter can likewise accept only when its enclosing interval excludes zero. A guessed absolute tolerance is not such a certificate: scaling the coordinates changes determinant magnitudes without changing the combinatorial answer.

Adaptive arithmetic spends additional work on uncertain cases rather than making every test equally expensive. Its guarantees depend on the actual arithmetic environment: rounding mode, supported exponent range, handling of underflow and overflow, and compiler transformations must satisfy the implementation's assumptions. Shewchuk's algorithms establish exact signs for the supplied binary inputs under their specified conditions. A certified zero is retained as a real degeneracy, then handled according to the algorithm's tie policy; it is not silently changed into a convenient nonzero sign.

A predicate returns a discrete answer such as orientation or incidence. A construction creates new coordinates, for example a segment intersection. Exact predicates applied to rounded constructed points answer questions about those rounded points, which can differ from questions about the intended exact intersections. Consequently exact-predicate kernels and exact-construction kernels offer different promises. Select the representation and kernel around the operations the full algorithm needs, rather than assuming that one robust orientation routine makes every subsequent coordinate calculation exact.

Degenerate inputs also need a coherent combinatorial specification. Duplicate points may be merged while retaining their identifiers; collinear hull points may be excluded or explicitly listed; shared intersection endpoints may be reported once. Symbolic perturbation can impose a consistent hypothetical general position, but its output must be interpreted relative to that perturbed problem or mapped back carefully. Independently nudging coordinates or changing signs with an arbitrary tolerance can produce contradictory decisions and destroy an otherwise valid algorithmic invariant.