Module s2::predicates

This file contains various predicates that are guaranteed to produce correct, consistent results. They are also relatively efficient. This is achieved by computing conservative error bounds and falling back to high precision or even exact arithmetic when the result is uncertain. Such predicates are useful in implementing robust algorithms.

See also EdgeCrosser, which implements various exact edge-crossing predicates more efficiently than can be done here.

Enums

Direction

Functions

robust_sign

robust_sign returns a Direction representing the ordering of the points. CounterClockwise is returned if the points are in counter-clockwise order, Clockwise for clockwise, and Indeterminate if any two points are the same (collinear), or the sign could not completely be determined.

sign

sign returns true if the points A, B, C are strictly counterclockwise, and returns false if the points are clockwise or collinear (i.e. if they are all contained on some great circle).

stable_sign

stable_sign reports the direction sign of the points in a numerically stable way. Unlike triageSign, this method can usually compute the correct determinant sign even when all three points are as collinear as possible. For example if three points are spaced 1km apart along a random line on the Earth’s surface using the nearest representable points, there is only a 0.4% chance that this method will not be able to find the determinant sign. The probability of failure decreases as the points get closer together; if the collinear points are 1 meter apart, the failure rate drops to 0.0004%.

triage_sign

triage_sign returns the direction sign of the points. It returns Indeterminate if two points are identical or the result is uncertain. Uncertain cases can be resolved, if desired, by calling expensiveSign.