Class S2EdgeUtil


  • @GwtCompatible(serializable=false)
    public class S2EdgeUtil
    extends java.lang.Object
    This class contains various utility functions related to edges. It collects together common code that is needed to implement polygonal geometry such as polylines, loops, and general polygons.
    • Field Detail

      • DEFAULT_INTERSECTION_TOLERANCE

        public static final S1Angle DEFAULT_INTERSECTION_TOLERANCE
        IEEE floating-point operations have a maximum error of 0.5 ULPS (units in the last place). For double-precision numbers, this works out to 2**-53 (about 1.11e-16) times the magnitude of the result. It is possible to analyze the calculation done by getIntersection() and work out the worst-case rounding error. I have done a rough version of this, and my estimate is that the worst case distance from the intersection point X to the great circle through (a0, a1) is about 12 ULPS, or about 1.3e-15. This needs to be increased by a factor of (1/0.866) to account for the edgeSpliceFraction() in S2PolygonBuilder. Note that the maximum error measured by the unittest in 1,000,000 trials is less than 3e-16.
      • MAX_DET_ERROR

        private static final double MAX_DET_ERROR
        Threshold for small angles, that help lenientCrossing to determine whether two edges are likely to intersect.
        See Also:
        Constant Field Values
      • FACE_CLIP_ERROR_UV_DIST

        public static final double FACE_CLIP_ERROR_UV_DIST
        The same angle as FACE_CLIP_ERROR_RADIANS, expressed as a maximum distance in (u,v)-space. In other words, a returned vertex is at most this far from the exact edge AB projected into (u,v)-space.
      • FACE_CLIP_ERROR_UV_COORD

        public static final double FACE_CLIP_ERROR_UV_COORD
        The same angle as FACE_CLIP_ERROR_RADIANS, expressed as the maximum error in an individual u- or v-coordinate. In other words, for each returned vertex there is a point on the exact edge AB whose u- and v-coordinates differ from the vertex by at most this amount.
      • INTERSECTS_RECT_ERROR_UV_DIST

        public static final double INTERSECTS_RECT_ERROR_UV_DIST
        The maximum error in IntersectRect. If some point of AB is inside the rectangle by at least this distance, the result is guaranteed to be true; if all points of AB are outside the rectangle by at least this distance, the result is guaranteed to be false. This bound assumes that "rect" is a subset of the rectangle [-1,1]x[-1,1] or extends slightly outside it (e.g., by 1e-10 or less).
      • EDGE_CLIP_ERROR_UV_COORD

        public static final double EDGE_CLIP_ERROR_UV_COORD
        The maximum error in a clipped point's u- or v-coordinate compared to the exact result, assuming that the points A and B are in the rectangle [-1,1]x[1,1] or slightly outside it (by 1e-10 or less).
      • EDGE_CLIP_ERROR_UV_DIST

        public static final double EDGE_CLIP_ERROR_UV_DIST
        The maximum error between a clipped edge or boundary point and the corresponding exact result. It is equal to the error in a single coordinate because at most one coordinate is subject to error.
      • MAX_CELL_EDGE_ERROR

        public static final double MAX_CELL_EDGE_ERROR
        Max error allowed when checking if a loop boundary approximately intersects a target cell
      • INTERSECTION_ERROR

        public static final double INTERSECTION_ERROR
        INTERSECTION_ERROR can be set somewhat arbitrarily, because the algorithm uses more precision than necessary in order to achieve the specified error. The only strict requirement is that INTERSECTION_ERROR >= 2 * S2.DBL_EPSILON radians. However, using a larger error tolerance makes the algorithm more efficient because it reduces the number of cases where exact arithmetic is needed.
    • Constructor Detail

      • S2EdgeUtil

        private S2EdgeUtil()
        Constructor is private so that this class is never instantiated.
    • Method Detail

      • sumEquals

        static boolean sumEquals​(double u,
                                 double v,
                                 double w)
        Returns true if u + v == w exactly.
      • intersectsFace

        static boolean intersectsFace​(S2Point n)
        Returns true if a given directed line L intersects the cube face F. The line L is defined by its normal N in the (u,v,w) coordinates of F.
      • intersectsOppositeEdges

        static boolean intersectsOppositeEdges​(S2Point n)
        Given a directed line L intersecting a cube face F, return true if L intersects two opposite edges of F (including the case where L passes exactly through a corner vertex of F). The line L is defined by its normal N in the (u,v,w) coordinates of F.
      • getExitAxis

        static int getExitAxis​(S2Point n)
        Given cube face F and a directed line L (represented by its CCW normal N in the (u,v,w) coordinates of F), compute the axis of the cube face edge where L exits the face: return 0 if L exits through the u=-1 or u=+1 edge, and 1 if L exits through the v=-1 or v=+1 edge. Either result is acceptable if L exits exactly through a corner vertex of the cube face.
      • getExitPoint

        static void getExitPoint​(S2Point n,
                                 int axis,
                                 R2Vector result)
        Given a cube face F, a directed line L (represented by its CCW normal N in the (u,v,w) coordinates of F), and result of getExitAxis(S2Point), set result to the (u,v) coordinates of the point where L exits the cube face.
      • moveOriginToValidFace

        static int moveOriginToValidFace​(int face,
                                         S2Point a,
                                         S2Point ab,
                                         R2Vector aUv)
        Given a line segment AB whose origin A has been projected onto a given cube face, determine whether it is necessary to project A onto a different face instead. This can happen because the normal of the line AB is not computed exactly, so that the line AB (defined as the set of points perpendicular to the normal) may not intersect the cube face containing A. Even if it does intersect the face, the "exit point" of the line from that face may be on the wrong side of A (i.e., in the direction away from B). If this happens, we reproject A onto the adjacent face where the line AB approaches A most closely. This moves the origin by a small amount, but never more than the error tolerances documented in the header file.
      • getNextFace

        static int getNextFace​(int face,
                               R2Vector exit,
                               int axis,
                               S2Point n,
                               int targetFace)
        Return the next face that should be visited by getFaceSegments, given that we have just visited "face" and we are following the line AB (represented by its normal N in the (u,v,w) coordinates of that face). The other arguments include the point where AB exits "face", the corresponding exit axis, and the "target face" containing the destination point B.
      • clipDestination

        static int clipDestination​(S2Point a,
                                   S2Point b,
                                   S2Point nScaled,
                                   S2Point aTangent,
                                   S2Point bTangent,
                                   double uvScale,
                                   R2Vector uv)
        This helper function does two things. First, it clips the line segment AB to find the clipped destination B' on a given face. (The face is specified implicitly by expressing *all arguments* in the (u,v,w) coordinates of that face.) Second, it partially computes whether the segment AB intersects this face at all. The actual condition is fairly complicated, but it turns out that it can be expressed as a "score" that can be computed independently when clipping the two endpoints A and B. This function returns the score for the given endpoint, which is an integer ranging from 0 to 3. If the sum of the two scores is 3 or more, then AB does not intersect this face. See the calling function for the meaning of the various parameters.
      • intersectsRect

        static boolean intersectsRect​(R2Vector a,
                                      R2Vector b,
                                      R2Rect rect)
        Returns true if the edge AB intersects the given (closed) rectangle to within the error bound below.
      • updateEndpoint

        static boolean updateEndpoint​(R1Interval bound,
                                      boolean slopeNegative,
                                      double value)
        Moves an endpoint of the given bound to the given value.
      • clipBoundAxis

        static boolean clipBoundAxis​(double a0,
                                     double b0,
                                     R1Interval bound0,
                                     double a1,
                                     double b1,
                                     R1Interval bound1,
                                     boolean slopeNegative,
                                     R1Interval clip0)
        Given a line segment from (a0,a1) to (b0,b1) and a bounding interval for each axis, clip the segment further if necessary so that "bound0" does not extend outside the given interval "clip". "diag" is a a precomputed helper variable that indicates which diagonal of the bounding box is spanned by AB: it is 0 if AB has positive slope, and 1 if AB has negative slope.
      • getClippedEdgeBound

        static R2Rect getClippedEdgeBound​(R2Vector a,
                                          R2Vector b,
                                          R2Rect clip)
        Given an edge AB and a rectangle "clip", return the bounding rectangle of the portion of AB intersected by "clip". The resulting bound may be empty. This is a convenience function built on top of clipEdgeBound.
      • clipEdgeBound

        static boolean clipEdgeBound​(R2Vector a,
                                     R2Vector b,
                                     R2Rect clip,
                                     R2Rect bound)
        This function can be used to clip an edge AB to sequence of rectangles efficiently. It represents the clipped edges by their bounding boxes rather than as a pair of endpoints. Specifically, let A'B' be some portion of an edge AB, and let "bound" be a tight bound of A'B'. This function updates "bound" (in place) to be a tight bound of A'B' intersected with a given rectangle "clip". If A'B' does not intersect "clip", returns false and does not necessarily update "bound".

        The given bound must be a tight bounding rectangle for some portion of AB. (This condition is automatically satisfied if you start with the bounding box of AB and clip to a sequence of rectangles, stopping when the method returns false.)

      • clipEdge

        static boolean clipEdge​(R2Vector a,
                                R2Vector b,
                                R2Rect clip,
                                R2Vector aClipped,
                                R2Vector bClipped)
        Given an edge AB, assigns the portion of AB that is contained by the given rectangle "clip" to the aClipped and bClipped arguments, and returns true if there is an intersection.
      • interpolateDouble

        static double interpolateDouble​(double x,
                                        double a,
                                        double b,
                                        double a1,
                                        double b1)
        Given a value x that is some linear combination of a and b, return the value x1 that is the same linear combination of a1 and b1. This function makes the following guarantees:
        1. If x == a, then x1 = a1 (exactly).
        2. If x == b, then x1 = b1 (exactly).
        3. If a <= x <= b, then a1 <= x1 <= b1 (even if a1 == b1).

        Results are undefined if a==b.

      • clipToFace

        public static boolean clipToFace​(S2Point a,
                                         S2Point b,
                                         int face,
                                         R2Vector aUv,
                                         R2Vector bUv)
        Given an edge AB and a face, return the (u,v) coordinates for the portion of AB that intersects that face. This method guarantees that the clipped vertices lie within the [-1,1]x[-1,1] cube face rectangle and are within kFaceClipErrorUVDist of the line AB, but the results may differ from those produced by getFaceSegments. Returns false if AB does not intersect the given face.
      • simpleCrossing

        public static boolean simpleCrossing​(S2Point a,
                                             S2Point b,
                                             S2Point c,
                                             S2Point d)
        Return true if edge AB crosses CD at a point that is interior to both edges. Properties:
        • simpleCrossing(b,a,c,d) == simpleCrossing(a,b,c,d)
        • simpleCrossing(c,d,a,b) == simpleCrossing(a,b,c,d)
      • robustCrossing

        public static int robustCrossing​(S2Point a,
                                         S2Point b,
                                         S2Point c,
                                         S2Point d)
        Like SimpleCrossing, except that points that lie exactly on a line are arbitrarily classified as being on one side or the other (according to the rules of sign). It returns +1 if there is a crossing, -1 if there is no crossing, and 0 if any two vertices from different edges are the same. Returns 0 or -1 if either edge is degenerate. Properties of robustCrossing:
        • robustCrossing(b,a,c,d) == robustCrossing(a,b,c,d)
        • robustCrossing(c,d,a,b) == robustCrossing(a,b,c,d)
        • robustCrossing(a,b,c,d) == 0 if a==c, a==d, b==c, b==d
        • robustCrossing(a,b,c,d) <= 0 if a==b or c==d

        Note that if you want to check an edge against a *chain* of other edges, it is much more efficient to use an EdgeCrosser (above).

      • vertexCrossing

        public static boolean vertexCrossing​(S2Point a,
                                             S2Point b,
                                             S2Point c,
                                             S2Point d)
        Given two edges AB and CD where at least two vertices are identical (i.e. robustCrossing(a,b,c,d) == 0), this function defines whether the two edges "cross" in a such a way that point-in-polygon containment tests can be implemented by counting the number of edge crossings. The basic rule is that a "crossing" occurs if AB is encountered after CD during a CCW sweep around the shared vertex starting from a fixed reference point.

        Note that according to this rule, if AB crosses CD then in general CD does not cross AB. However, this leads to the correct result when counting polygon edge crossings. For example, suppose that A,B,C are three consecutive vertices of a CCW polygon. If we now consider the edge crossings of a segment BP as P sweeps around B, the crossing number changes parity exactly when BP crosses BA or BC.

        Useful properties of VertexCrossing (VC):

        • VC(a,a,c,d) == VC(a,b,c,c) == false
        • VC(a,b,a,b) == VC(a,b,b,a) == true
        • VC(a,b,c,d) == VC(a,b,d,c) == VC(b,a,c,d) == VC(b,a,d,c)
        • If exactly one of a,b equals one of c,d, then exactly one of VC(a,b,c,d) and VC(c,d,a,b) is true

        It is an error to call this method with 4 distinct vertices.

      • edgeOrVertexCrossing

        public static boolean edgeOrVertexCrossing​(S2Point a,
                                                   S2Point b,
                                                   S2Point c,
                                                   S2Point d)
        A convenience function that calls robustCrossing() to handle cases where all four vertices are distinct, and VertexCrossing() to handle cases where two or more vertices are the same. This defines a crossing function such that point-in-polygon containment tests can be implemented by simply counting edge crossings.
      • closestAcceptableEndpoint

        static S2Point closestAcceptableEndpoint​(S2Point a0,
                                                 S2Point a1,
                                                 S2Point aNorm,
                                                 S2Point b0,
                                                 S2Point b1,
                                                 S2Point bNorm,
                                                 S2Point x)
        Finds the closest acceptable endpoint to a given point. An endpoint is acceptable if it lies between the endpoints of the other line segment.
      • lenientCrossing

        public static final boolean lenientCrossing​(S2Point a,
                                                    S2Point b,
                                                    S2Point c,
                                                    S2Point d)
        Returns true if ab possibly crosses cd, by clipping tiny angles to zero.
      • getIntersection

        public static S2Point getIntersection​(S2Point a0,
                                              S2Point a1,
                                              S2Point b0,
                                              S2Point b1)
        Given two edges AB and CD such that robustCrossing() is true, return their intersection point. Useful properties of getIntersection (GI):
        • GI(b,a,c,d) == GI(a,b,d,c) == GI(a,b,c,d)
        • GI(c,d,a,b) == GI(a,b,c,d)
        The returned intersection point X is guaranteed to be very close to the true intersection point of AB and CD, even if the edges intersect at a very small angle. See "INTERSECTION_ERROR" above for details.
      • correctIntersectionSign

        static S2Point correctIntersectionSign​(S2Point a0,
                                               S2Point a1,
                                               S2Point b0,
                                               S2Point b1,
                                               S2Point intersectionResult)
        Returns intersection result with sign corrected (if necessary).
      • getDistanceFraction

        public static double getDistanceFraction​(S2Point x,
                                                 S2Point a0,
                                                 S2Point a1)
        Given a point X and an edge AB, return the distance ratio AX / (AX + BX). If X happens to be on the line segment AB, this is the fraction "t" such that X == Interpolate(A, B, t). Requires that A and B are distinct.
      • getDistance

        public static S1Angle getDistance​(S2Point x,
                                          S2Point a,
                                          S2Point b)
        Return the minimum distance from X to any point on the edge AB. The result is very accurate for small distances but may have some numerical error if the distance is large (approximately Pi/2 or greater). The case A == B is handled correctly.
        Throws:
        java.lang.IllegalArgumentException - Thrown if the parameters are not all unit length.
      • updateMinDistance

        public static S1ChordAngle updateMinDistance​(S2Point x,
                                                     S2Point a,
                                                     S2Point b,
                                                     S1ChordAngle minDistance)
        Return the minimum of the distance from x to any point on edge ab and the given minDistance. The case a.equals(b) is handled correctly.
        Throws:
        java.lang.IllegalArgumentException - Thrown if the parameters are not all unit length.
      • updateMaxDistance

        public static S1ChordAngle updateMaxDistance​(S2Point x,
                                                     S2Point a,
                                                     S2Point b,
                                                     S1ChordAngle maxDistance)
        Returns the maximum of the distance from x to any point on edge AB and the given maxDistance. The case a.equals(b) is handled correctly.
      • getEdgePairClosestPoints

        static void getEdgePairClosestPoints​(S2Point a0,
                                             S2Point a1,
                                             S2Point b0,
                                             S2Point b1,
                                             S2Point[] result)
        Updates the results with points that achieve the minimum distance between edges a0a1 and b0b1, where a is a point on a0a1 and b is a point on b0b1. If the two edges intersect, a and b are both equal to the intersection point. Handles a0.equals(a1) and b0.equals(b1) correctly.
      • getDistance

        public static S1Angle getDistance​(S2Point x,
                                          S2Point a,
                                          S2Point b,
                                          S2Point aCrossB)
        A slightly more efficient version of getDistance() where the cross product of the two endpoints has been precomputed. The cross product does not need to be normalized, but should be computed using S2.robustCrossProd() for the most accurate results.
        Throws:
        java.lang.IllegalArgumentException - Thrown if the parameters are not all unit length.
      • ccw

        @Deprecated
        private static boolean ccw​(S2Point a,
                                   S2Point b,
                                   S2Point c)
        Deprecated.
        Temporary bridge for refactoring
      • getDistanceRadians

        public static double getDistanceRadians​(S2Point x,
                                                S2Point a,
                                                S2Point b,
                                                S2Point aCrossB)
        A more efficient version of getDistance() where the cross product of the endpoints has been precomputed and the result is returned as a direct radian measure rather than wrapping it in an S1Angle. This is the recommended method for making large numbers of back-to-back edge distance tests, since it allocates no objects. The inputs are assumed to be unit length; results are undefined if they are not.
      • diffMag2

        private static final double diffMag2​(S2Point a,
                                             S2Point b)
        Returns the squared distance from a to b.
      • getClosestPoint

        public static S2Point getClosestPoint​(S2Point x,
                                              S2Point a,
                                              S2Point b)
        Returns the point on edge AB closest to X. All points must be unit length; results are undefined if that is not the case.
      • interpolate

        public static S2Point interpolate​(double t,
                                          S2Point a,
                                          S2Point b)
        Return the point X along the line segment AB whose distance from A is the given fraction "t" of the distance AB. Does NOT require that "t" be between 0 and 1. Note that all distances are measured on the surface of the sphere, so this is more complicated than just computing (1-t)*a + t*b and normalizing the result.
      • getMinDistanceMaxError

        static double getMinDistanceMaxError​(S1ChordAngle distance)
        Returns the maximum error in the result of updateMinDistance(com.google.common.geometry.S2Point, com.google.common.geometry.S2Edge, com.google.common.geometry.S1ChordAngle) (and associated functions), assuming that all input points are normalized to within the bounds guaranteed by S2Point.normalize(). The error can be added or subtracted from an S1ChordAngle "x" using x.plusError(error).

        Note that accuracy goes down as the distance approaches 0 degrees or 180 degrees (for different reasons). Near 0 degrees the error is acceptable for all practical purposes (about 1.2e-15 radians ~= 8 nanometers). For exactly antipodal points the maximum error is quite high (0.5 meters), but this error drops rapidly as the points move away from antipodality (approximately 1 millimeter for points that are 50 meters from antipodal, and 1 micrometer for points that are 50km from antipodal).

      • getIntersectionExact

        static S2Point getIntersectionExact​(S2Point a0,
                                            S2Point a1,
                                            S2Point b0,
                                            S2Point b1)
        Compute the intersection point of (a0, a1) and (b0, b1) using exact arithmetic. Note that the result is not exact because it is rounded to double precision. Also, the intersection point is not guaranteed to have the correct sign (i.e., the return value may need to be negated).
      • getIntersectionApprox

        static S2Point getIntersectionApprox​(S2Point a0,
                                             S2Point a1,
                                             S2Point b0,
                                             S2Point b1,
                                             S2EdgeUtil.ResultError resultError)
        Returns the approximate intersection point of the edges (a0,a1) and (b0,b1), and writes to resultError a bound on its error.

        The intersection point is not guaranteed to have the correct sign, i.e., it may need to be negated.

      • compareEdges

        private static boolean compareEdges​(S2Point a0,
                                            S2Point a1,
                                            S2Point b0,
                                            S2Point b1)
        Returns true if (a0,a1) is less than (b0,b1) with respect to a total ordering on edges that is invariant under edge reversals.
      • getIntersectionApproxSorted

        private static S2Point getIntersectionApproxSorted​(S2Point a0,
                                                           S2Point a1,
                                                           S2Point b0,
                                                           S2Point b1,
                                                           S2EdgeUtil.ResultError resultError)
        Returns the approximate intersection point of the edges (a0,a1) and (b0,b1), and writes to resultError a bound on its error.

        Expects that the edges (a0,a1) and (b0,b1) have been sorted so that the first edge is longer.

        The intersection point is not guaranteed to have the correct sign, i.e., it may need to be negated.

      • getProjection

        static double getProjection​(S2Point x,
                                    S2Point aNormal,
                                    double aNormalLen,
                                    S2Point a0,
                                    S2Point a1,
                                    S2EdgeUtil.ResultError resultError)
        Returns 2x the dot product of x and aNormal, and writes to resultError a bound on the error given that aNormal was calculated using S2.robustCrossProd(com.google.common.geometry.S2Point, com.google.common.geometry.S2Point).

        The remaining parameters allow this calculation to be computed more accurately and efficiently. They include the length of aNormal (aNormalLen) and the edge endpoints a0 and a1.

        Note that the 2x factor mentioned above is the result of an error reducing step. Rescaling the result would result in a loss of accuracy and efficiency, and thus is not performed.