Class S2Predicates

java.lang.Object
com.google.common.geometry.S2Predicates

@GwtCompatible public final class S2Predicates extends 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).
  • Field Details

    • 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 BigDecimal QUARTER
    • HALF

      private static final BigDecimal HALF
    • TWO

      private static final BigDecimal TWO
    • FOUR

      private static final BigDecimal FOUR
  • Constructor Details

    • S2Predicates

      private S2Predicates()
  • Method Details

    • 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 invalid input: '<'= B invalid input: '<'= C with respect to a continuous CCW ordering around O.

      Properties:

      1. If orderedCCW(a,b,c,o) invalid input: '&'invalid input: '&' orderedCCW(b,a,c,o), then a == b
      2. If orderedCCW(a,b,c,o) invalid input: '&'invalid input: '&' orderedCCW(a,c,b,o), then b == c
      3. If orderedCCW(a,b,c,o) invalid input: '&'invalid input: '&' 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 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

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

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

      private static double cosDistance(S2Point x, S2Point y)
      Returns cos(XY). Requires that "x" and "y" are S2.isUnitLength(com.google.common.geometry.S2Point).
    • cosDistanceError

      private static double cosDistanceError(double x)
    • sin2Distance

      private static double sin2Distance(S2Point x, S2Point y)
      Returns sin^2(XY), where XY=x.angle(y). Requires "x" and "y" to be S2.isUnitLength(com.google.common.geometry.S2Point).
    • sin2DistanceError

      private static double sin2DistanceError(double x)
    • 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 BigDecimal big(double v)
      Returns a BigDecimal-based representation of 'v'.
    • square

      private static BigDecimal square(BigDecimal v)
      Returns v*v.