Class S2Predicates.Sign
- Enclosing class:
S2Predicates
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionstatic int
Computes the determinant using exact arithmetic and/or symbolic permutations.static int
Returns the sign of the determinant using more expensive techniques.static int
Returns the sign of the turn ABC.static int
Returns the sign of the determinant of three column vectors A, B, C under a model where every possible S2Point is slightly perturbed by a unique infinitesimal amount such that no three perturbed points are collinear and no four points are coplanar.static int
Compute the determinant in a numerically stable way.static int
This version of Sign returns +1 if the points are definitely CCW, -1 if they are definitely CW, and 0 if two points are identical or the result is uncertain.
-
Constructor Details
-
Sign
private Sign()No instantiation.
-
-
Method Details
-
triage
This version of Sign returns +1 if the points are definitely CCW, -1 if they are definitely CW, and 0 if two points are identical or the result is uncertain. Uncertain cases can be resolved, if desired, byexpensive(com.google.common.geometry.S2Point, com.google.common.geometry.S2Point, com.google.common.geometry.S2Point, boolean)
.The purpose of this method is to allow additional cheap tests to be done, where possible, in order to avoid calling more expensive operations unnecessarily.
-
sign
Returns the sign of the turn ABC. Exactly straight points will only result in 0 if 'perturb' is false, otherwise the points are perturbed according to the rules in Simulation of Simplicity, to provide a logically consistent non-zero result for all inputs. -
expensive
Returns the sign of the determinant using more expensive techniques. To be used when the magnitude of the determinant is close enough to zero that its value is uncertain using faster but less robust techniques. -
stable
Compute the determinant in a numerically stable way. Unliketriage(com.google.common.geometry.S2Point, com.google.common.geometry.S2Point, com.google.common.geometry.S2Point)
, 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%.This method could be extended to also handle nearly-antipodal points (and in fact an earlier version of this code did exactly that), but antipodal points are rare in practice so it seems better to simply fall back to exact arithmetic in that case.
-
exact
Computes the determinant using exact arithmetic and/or symbolic permutations. Requires that the three points are distinct. -
sos
Returns the sign of the determinant of three column vectors A, B, C under a model where every possible S2Point is slightly perturbed by a unique infinitesimal amount such that no three perturbed points are collinear and no four points are coplanar. The perturbations are so small that they do not change the sign of any determinant that was non-zero before the perturbations, and therefore can be safely ignored unless the determinant of three points is exactly zero (using multiple-precision arithmetic).Since the symbolic perturbation of a given point is fixed (i.e., the perturbation is the same for all calls to this method and does not depend on the other two arguments), the results of this method are always self-consistent. It will never return results that would correspond to an "impossible" configuration of non-degenerate points.
Requirements:
- The 3x3 determinant of A, B, C must be exactly zero.
- The points must be distinct, with A invalid input: '<' B invalid input: '<' C in lexicographic order.
Returns +1 or -1 according to the sign of the determinant after the symbolic perturbations are taken into account. This method is suitable as a tie breaker when all other tests fail to choose a distinct turning direction.
Reference:
"Simulation of Simplicity" Edelsbrunner and Muecke, ACM Transactions on Graphics, 1990
-