General robust, adaptive geometric predicates

A number of geometric algorithms, such as the triangulation of a point set, employ geometric predicates (implemented as strategies in Boost.Geometry). One example for such a predicate is the 2d orientation test, which, given three points p1, p2, p3, determines whether p3 lies on the left or right side of the line segment that goes through p1 and p2.

Using floating-point arithmetics to answer that question can lead to incorrect and ultimately inconsistent results that may cause the algorithm that employs the predicate to produce nonsensical results or crash entirely for certain inputs.

Using algorithms for exact floating-point arithmetics combined with some considerations regarding forward error analysis, a complicated method can be implemented that evaluates such predicates robustly and only adaptively increases the precision if necessary to avoid expensive high precision computations whenever possible.

I propose a general, automated approach that generates such robust, adaptive predicates from arbitrary arithmetic expressions.