Class S2Predicates.Sign
- java.lang.Object
-
- com.google.common.geometry.S2Predicates.Sign
-
- Enclosing class:
- S2Predicates
public static class S2Predicates.Sign extends java.lang.Object
Tests of whether three points represent a left turn (+1), right turn (-1), or neither (0).
-
-
Constructor Summary
Constructors Modifier Constructor Description private
Sign()
No instantiation.
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static int
exact(S2Point a, S2Point b, S2Point c, boolean perturb)
Computes the determinant using exact arithmetic and/or symbolic permutations.static int
expensive(S2Point a, S2Point b, S2Point c, boolean perturb)
Returns the sign of the determinant using more expensive techniques.static int
sign(S2Point a, S2Point b, S2Point c, boolean perturb)
Returns the sign of the turn ABC.static int
sos(BigPoint a, BigPoint b, BigPoint c, BigPoint bc)
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
stable(S2Point a, S2Point b, S2Point c)
Compute the determinant in a numerically stable way.static int
triage(S2Point a, S2Point b, S2Point c)
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.
-
-
-
Method Detail
-
triage
public static int triage(S2Point a, S2Point b, S2Point c)
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
public static int sign(S2Point a, S2Point b, S2Point c, boolean perturb)
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
public static int expensive(S2Point a, S2Point b, S2Point c, boolean perturb)
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
public static int stable(S2Point a, S2Point b, S2Point c)
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
public static int exact(S2Point a, S2Point b, S2Point c, boolean perturb)
Computes the determinant using exact arithmetic and/or symbolic permutations. Requires that the three points are distinct.
-
sos
public static int sos(BigPoint a, BigPoint b, BigPoint c, BigPoint bc)
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 < B < 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
-
-