Class S2Predicates


  • @GwtCompatible
    public final class S2Predicates
    extends java.lang.Object
    A collection of geometric predicates core to the robustness of the S2 library. In particular,
    • 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 Classes 
      Modifier and Type Class Description
      (package private) static class  S2Predicates.CompareDistance
      A set of tests to compare the distance XY and a previously computed distance.
      (package private) static class  S2Predicates.CompareDistances
      A set of tests to determine which of two points is closer to a reference point.
      (package private) static class  S2Predicates.CompareEdgeDirections
      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  S2Predicates.CompareEdgeDistance
      A test to compare the distance from point X to edge A with a previously computed distance.
      (package private) static class  S2Predicates.EdgeCircumcenterSign
      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 class  S2Predicates.Excluded
      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  S2Predicates.Sign
      Tests of whether three points represent a left turn (+1), right turn (-1), or neither (0).
      (package private) static class  S2Predicates.VoronoiSiteExclusion
      A test for which (if any) of two Voronoi sites within R of an edge PQ are covered by the other.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private static double DBL_ERR
      Maximum rounding error of a 64 bit double.
      private static S1ChordAngle DEG_45
      A predefined S1ChordAngle representing (approximately) 45 degrees.
      private static java.math.BigDecimal FOUR  
      private static java.math.BigDecimal HALF  
      private static java.math.BigDecimal QUARTER  
      private static double T_ERR
      Rounding error of numeric type used for computation.
      private static java.math.BigDecimal TWO  
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private S2Predicates()  
    • Field Detail

      • DBL_ERR

        private static final double DBL_ERR
        Maximum rounding error of a 64 bit double.
      • T_ERR

        private static final double T_ERR
        Rounding error of numeric type used for computation. This is a distinct value from DBL_ERR to avoid recomputing the error bounds when we may later use higher precision (but inexact) types for computations.
      • DEG_45

        private static final S1ChordAngle DEG_45
        A predefined S1ChordAngle representing (approximately) 45 degrees.
      • QUARTER

        private static final java.math.BigDecimal QUARTER
      • HALF

        private static final java.math.BigDecimal HALF
      • TWO

        private static final java.math.BigDecimal TWO
      • FOUR

        private static final java.math.BigDecimal FOUR
    • Constructor Detail

      • S2Predicates

        private S2Predicates()
    • Method Detail

      • sign

        public static int sign​(S2Point a,
                               S2Point b,
                               S2Point c)
        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:

        1. sign(a,b,c) == 0 iff a.equals(b) || b.equals(c) || c.equals(a)
        2. sign(b,c,a) == sign(a,b,c), for all a,b,c
        3. sign(c,b,a) == -sign(a,b,c), for all a,b,c

        In other words:

        1. The result is zero if and only if two points are the same.
        2. Rotating the order of the arguments does not affect the result.
        3. 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

        public 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. You can think of this as testing whether A <= B <= C with respect to a continuous CCW ordering around O.

        Properties:

        1. If orderedCCW(a,b,c,o) && orderedCCW(b,a,c,o), then a == b
        2. If orderedCCW(a,b,c,o) && orderedCCW(a,c,b,o), then b == c
        3. If orderedCCW(a,b,c,o) && orderedCCW(c,b,a,o), then a == b == c
        4. If a == b or b == c, then orderedCCW(a,b,c,o) is true
        5. Otherwise if a == c, then orderedCCW(a,b,c,o) is false
      • compareDistances

        public static int compareDistances​(S2Point x,
                                           S2Point a,
                                           S2Point b)
        Returns -1, 0, or +1 according to whether AX < 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 < BC and BC < AC, then AB < AC.
      • compareDistance

        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. 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

        public 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.

        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 < 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

        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. 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

        public static int edgeCircumcenterSign​(S2Point p,
                                               S2Point q,
                                               S2Point a,
                                               S2Point b,
                                               S2Point c)
        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

        private static S2Point ndCross​(S2Point a,
                                       S2Point b)
        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.
      • signum

        private static int signum​(double value,
                                  double error)
        Returns the same result as Math.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 as Double.compare(double, double), or 0 if 'a' and 'b' are within their measurement errors of each other.
        Parameters:
        a - the first value
        aError - the true value of 'a' must be at least a-aError and at most a+aError
        b - the second value
        bError - the true value of 'b' must be at least b-bError and at most b+bError
      • closestVertex

        private static S2Point closestVertex​(S2Point x,
                                             S2Point a,
                                             S2Point b,
                                             double[] dx2)
        Returns "a" or "b", whichever is closer to "x". Also returns the squared distance from the returned point to "x" in "d".
      • circumcenter

        private static S2Point circumcenter​(S2Point a,
                                            S2Point b,
                                            S2Point c,
                                            double[] error)
        If triangle ABC has positive sign, returns its circumcenter. If ABC has negative sign, returns the negated circumcenter.
      • big

        private static BigPoint big​(S2Point p)
        Returns a BigDecimal-based representation of 'p'.
      • big

        private static java.math.BigDecimal big​(double v)
        Returns a BigDecimal-based representation of 'v'.
      • square

        private static java.math.BigDecimal square​(java.math.BigDecimal v)
        Returns v*v.