Class S2Predicates
sign(A, B, C)
: Compute the orientation of a triple of points as clockwise (-1), colinear (0), or counter-clockwise (1).
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescription(package private) static class
A set of tests to compare the distance XY and a previously computed distance.(package private) static class
A set of tests to determine which of two points is closer to a reference point.(package private) static class
A test to compare whether two edges are closer to proceeding in the same direction or in opposite directions around the sphere, essentially signum((AxB)x(CxD)).(package private) static class
A test to compare the distance from point X to edge A with a previously computed distance.(package private) static class
A predicate for whether an edge PQ passes to the left, to the right, or through the center of the circumcircle of triangle ABC.static enum
Given two sites A and B that form the center of caps of radius 'r', this indicates which sites are irrelevant to the Voronoi diagram relative to an edge PQ.static class
Tests of whether three points represent a left turn (+1), right turn (-1), or neither (0).(package private) static class
A test for which (if any) of two Voronoi sites within R of an edge PQ are covered by the other. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate static final double
Maximum rounding error of a 64 bit double.private static final S1ChordAngle
A predefined S1ChordAngle representing (approximately) 45 degrees.private static final BigDecimal
private static final BigDecimal
private static final BigDecimal
private static final double
Rounding error of numeric type used for computation.private static final BigDecimal
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate static BigDecimal
big
(double v) Returns a BigDecimal-based representation of 'v'.private static BigPoint
Returns a BigDecimal-based representation of 'p'.private static S2Point
circumcenter
(S2Point a, S2Point b, S2Point c, double[] error) If triangle ABC has positive sign, returns its circumcenter.private static S2Point
closestVertex
(S2Point x, S2Point a, S2Point b, double[] dx2) Returns "a" or "b", whichever is closer to "x".private static int
compare
(double a, double aError, double b, double bError) Returns the same result asDouble.compare(double, double)
, or 0 if 'a' and 'b' are within their measurement errors of each other.(package private) static int
compareDistance
(S2Point x, S2Point y, double r2) Returns -1, 0, or +1 according to whether the distance XY is less than, equal to, or greater than the squared chord distance "r2" respectively.static int
compareDistances
(S2Point x, S2Point a, S2Point b) Returns -1, 0, or +1 according to whether AX invalid input: '<' BX, A == B, or AX > BX respectively.(package private) static int
compareEdgeDirections
(S2Point a, S2Point b, S2Point c, S2Point d) Returns -1, 0, or +1 according to whether the normal of edge AB has negative, zero, or positive dot product with the normal of edge CD.static int
compareEdgeDistance
(S2Point x, S2Point a, S2Point b, double r2) Returns -1, 0, or +1 according to whether the distance from the point X to the edge AB is less than, equal to, or greater than the squared chord distance "r2" respectively.private static double
cosDistance
(S2Point x, S2Point y) Returns cos(XY).private static double
cosDistanceError
(double x) Returns the error in a value returned fromcosDistance(com.google.common.geometry.S2Point, com.google.common.geometry.S2Point)
.static int
Returns sign(P, Q, Z) where Z is the circumcenter of triangle ABC.static S2Predicates.Excluded
getVoronoiSiteExclusion
(S2Point a, S2Point b, S2Point p, S2Point q, double r2) This is a specialized method that is used to compute the intersection of an edge PQ with the Voronoi diagram of a set of points, where each Voronoi region is intersected with a disc of fixed radius "r".private static S2Point
Returns (a-b).crossProd(a+b), which eliminates almost all of the error due to "x" and "y" being not quite unit length.static boolean
orderedCCW
(S2Point a, S2Point b, S2Point c, S2Point o) Return true if the edges OA, OB, and OC are encountered in that order while sweeping CCW around the point O.static int
Returns +1 if the points A, B, C are counterclockwise, -1 if the points are clockwise, and 0 if any two points are the same.private static int
signum
(double value, double error) Returns the same result asMath.signum(double)
, or 0 if 'value' is within 'error' of 0.private static double
sin2Distance
(S2Point x, S2Point y) Returns sin^2(XY), where XY=x.angle(y).private static double
sin2DistanceError
(double x) Returns the error in a value returned fromsin2Distance(com.google.common.geometry.S2Point, com.google.common.geometry.S2Point)
.private static BigDecimal
square
(BigDecimal v) Returns v*v.
-
Field Details
-
DBL_ERR
private static final double DBL_ERRMaximum rounding error of a 64 bit double. -
T_ERR
private static final double T_ERRRounding error of numeric type used for computation. This is a distinct value fromDBL_ERR
to avoid recomputing the error bounds when we may later use higher precision (but inexact) types for computations. -
DEG_45
A predefined S1ChordAngle representing (approximately) 45 degrees. -
QUARTER
-
HALF
-
TWO
-
FOUR
-
-
Constructor Details
-
S2Predicates
private S2Predicates()
-
-
Method Details
-
sign
Returns +1 if the points A, B, C are counterclockwise, -1 if the points are clockwise, and 0 if any two points are the same. This function is essentially like taking the sign of the determinant of ABC, except that it has additional logic to make sure that the above properties hold even when the three points are coplanar, and to deal with the limitations of floating-point arithmetic.Sign satisfies the following conditions:
sign(a,b,c) == 0
iffa.equals(b) || b.equals(c) || c.equals(a)
sign(b,c,a) == sign(a,b,c)
, for all a,b,csign(c,b,a) == -sign(a,b,c)
, for all a,b,c
In other words:
- The result is zero if and only if two points are the same.
- Rotating the order of the arguments does not affect the result.
- Exchanging any two arguments inverts the result.
On the other hand, note that it is not true in general that
sign(-a,b,c) == -sign(a,b,c)
, or any similar identities involving antipodal points. -
orderedCCW
Return true if the edges OA, OB, and OC are encountered in that order while sweeping CCW around the point O. You can think of this as testing whether A invalid input: '<'= B invalid input: '<'= C with respect to a continuous CCW ordering around O.Properties:
- If orderedCCW(a,b,c,o) invalid input: '&'invalid input: '&' orderedCCW(b,a,c,o), then a == b
- If orderedCCW(a,b,c,o) invalid input: '&'invalid input: '&' orderedCCW(a,c,b,o), then b == c
- If orderedCCW(a,b,c,o) invalid input: '&'invalid input: '&' orderedCCW(c,b,a,o), then a == b == c
- If a == b or b == c, then orderedCCW(a,b,c,o) is true
- Otherwise if a == c, then orderedCCW(a,b,c,o) is false
-
compareDistances
Returns -1, 0, or +1 according to whether AX invalid input: '<' BX, A == B, or AX > BX respectively. Distances are measured with respect to the positions of X, A, and B as though they were reprojected to lie exactly on the surface of the unit sphere. Furthermore, this method uses symbolic perturbations to ensure that the result is non-zero whenever A != B, even when AX == BX exactly, or even when A and B project to the same point on the sphere. Such results are guaranteed to be self-consistent, i.e. if AB invalid input: '<' BC and BC invalid input: '<' AC, then AB invalid input: '<' AC. -
compareDistance
Returns -1, 0, or +1 according to whether the distance XY is less than, equal to, or greater than the squared chord distance "r2" respectively. Distances are measured with respect the positions of all points as though they are projected to lie exactly on the surface of the unit sphere. -
compareEdgeDistance
Returns -1, 0, or +1 according to whether the distance from the point X to the edge AB is less than, equal to, or greater than the squared chord distance "r2" respectively.Distances are measured with respect to the positions of all points as though they were projected to lie exactly on the surface of the unit sphere.
Requires that A and B do not project to antipodal points (e.g., A != -B). This can occur if for example A == S * B, for some constant S invalid input: '<' 0.
Note all of the predicates defined here could be extended to handle edges consisting of antipodal points by implementing additional symbolic perturbation logic (similar to
sign(com.google.common.geometry.S2Point, com.google.common.geometry.S2Point, com.google.common.geometry.S2Point)
) in order to rigorously define the direction of such edges. -
compareEdgeDirections
Returns -1, 0, or +1 according to whether the normal of edge AB has negative, zero, or positive dot product with the normal of edge CD. This essentially measures whether the edges AB and CD are closer to proceeding in the same direction or in opposite directions around the sphere.This method returns an exact result, i.e. the result is zero if and only if the two edges are exactly perpendicular or at least one edge is degenerate. (i.e., both edge endpoints project to the same point on the sphere).
However, this method does not use symbolic perturbations. Therefore it can return zero even when A != B and C != D, e.g. if A == S * B exactly for some constant S > 0 (which is possible even when both points are considered "normalized").
Edges may not consist of antipodal points (e.g., A != -B). See
compareEdgeDistance(com.google.common.geometry.S2Point, com.google.common.geometry.S2Point, com.google.common.geometry.S2Point, double)
. -
edgeCircumcenterSign
Returns sign(P, Q, Z) where Z is the circumcenter of triangle ABC. The return value is -1 if Z is to the left of edge PQ, and +1 if Z is to the right of edge PQ. The return value is zero if A == B, B == C, or C == A (exactly), and also if P and Q project to identical points on the sphere (e.g., P == Q).The result is determined with respect to the positions of all points as though they were projected to lie exactly on the surface of the unit sphere. Furthermore this method uses symbolic perturbations to compute a consistent non-zero result even when Z lies exactly on edge PQ.
Requires that P and Q do not project to antipodal points (e.g., P == -Q) (see comments in compareEdgeDistance).
-
getVoronoiSiteExclusion
public static S2Predicates.Excluded getVoronoiSiteExclusion(S2Point a, S2Point b, S2Point p, S2Point q, double r2) This is a specialized method that is used to compute the intersection of an edge PQ with the Voronoi diagram of a set of points, where each Voronoi region is intersected with a disc of fixed radius "r".Given two sites A and B and an edge (P, Q) such that
d(A,P) < d(B,P)
, and both sites are within the given distance "r" of edge PQ, this method intersects the Voronoi region of each site with a disc of radius r and determines whether either region has an empty intersection with edge PQ. It returns FIRST if site A has an empty intersection, SECOND if site B has an empty intersection, NEITHER if neither site has an empty intersection, or UNCERTAIN if A == B exactly. Note that it is not possible for both intersections to be empty because of the requirement that both sites are within distance r of edge PQ. (For example, the only reason that Voronoi region A can have an empty intersection with PQ is that site B is closer to all points on PQ that are within radius r of site A.)The result is determined with respect to the positions of all points as though they were projected to lie exactly on the surface of the unit sphere. Furthermore this method uses symbolic perturbations to compute a consistent non-zero result even when A and B lie on opposite sides of PQ such that the Voronoi edge between them exactly coincides with edge PQ, or when A and B are distinct but project to the same point on the sphere (i.e., they are linearly dependent).
Requires that
r < S1ChordAngle.RIGHT
(90 degrees)compareDistances(p, a, b) < 0
compareEdgeDistance(a, p, q, r) <= 0
compareEdgeDistance(b, p, q, r) <= 0
- P and Q do not project to antipodal points (e.g., P != -Q), see
S2Predicates.CompareEdgeDistance
for details.
-
ndCross
Returns (a-b).crossProd(a+b), which eliminates almost all of the error due to "x" and "y" being not quite unit length. This method is extremely accurate for small distances; the *relative* error in the result is O(DBL_ERR) for distances as small as DBL_ERR. -
cosDistance
Returns cos(XY). Requires that "x" and "y" areS2.isUnitLength(com.google.common.geometry.S2Point)
. -
cosDistanceError
private static double cosDistanceError(double x) Returns the error in a value returned fromcosDistance(com.google.common.geometry.S2Point, com.google.common.geometry.S2Point)
. -
sin2Distance
Returns sin^2(XY), where XY=x.angle(y). Requires "x" and "y" to beS2.isUnitLength(com.google.common.geometry.S2Point)
. -
sin2DistanceError
private static double sin2DistanceError(double x) Returns the error in a value returned fromsin2Distance(com.google.common.geometry.S2Point, com.google.common.geometry.S2Point)
. -
signum
private static int signum(double value, double error) Returns the same result asMath.signum(double)
, or 0 if 'value' is within 'error' of 0. -
compare
private static int compare(double a, double aError, double b, double bError) Returns the same result asDouble.compare(double, double)
, or 0 if 'a' and 'b' are within their measurement errors of each other.- Parameters:
a
- the first valueaError
- the true value of 'a' must be at least a-aError and at most a+aErrorb
- the second valuebError
- the true value of 'b' must be at least b-bError and at most b+bError
-
closestVertex
Returns "a" or "b", whichever is closer to "x". Also returns the squared distance from the returned point to "x" in "d". -
circumcenter
If triangle ABC has positive sign, returns its circumcenter. If ABC has negative sign, returns the negated circumcenter. -
big
Returns a BigDecimal-based representation of 'p'. -
big
Returns a BigDecimal-based representation of 'v'. -
square
Returns v*v.
-