Class S2EdgeUtil

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

@GwtCompatible(serializable=false) public class S2EdgeUtil extends 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 Details

    • 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:
    • FACE_CLIP_ERROR_RADIANS

      public static final double FACE_CLIP_ERROR_RADIANS
      The maximum angle between a returned vertex and the nearest point on the exact edge AB. It is equal to the maximum directional error in S2.robustCrossProd(com.google.common.geometry.S2Point, com.google.common.geometry.S2Point), plus the error when projecting points onto a cube face.
    • 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 Details

    • S2EdgeUtil

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

    • getWedgeRelation

      public static S2EdgeUtil.WedgeRelation getWedgeRelation(S2Point a0, S2Point ab1, S2Point a2, S2Point b0, S2Point b2)
      Returns the relation from wedge A to B.
    • 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.
    • getFaceSegments

      static int getFaceSegments(S2Point a, S2Point b, S2EdgeUtil.FaceSegment[] segments)
      Subdivide the given edge AB at every point where it crosses the boundary between two S2 cube faces, returning the number of FaceSegments entries used (all entries must be prefilled). The segments are returned in order from A toward B. The input points must be unit length.

      This method guarantees that the returned segments form a continuous path from A to B, and that all vertices are within kFaceClipErrorUVDist of the line AB. All vertices lie within the [-1,1]x[-1,1] cube face rectangles. The results are consistent with S2Predicates.Sign.expensive(com.google.common.geometry.S2Point, com.google.common.geometry.S2Point, com.google.common.geometry.S2Point, boolean), i.e. the edge is well-defined even if its endpoints are antipodal.

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

      public static boolean clipToPaddedFace(S2Point aXyz, S2Point bXyz, int face, double padding, R2Vector aUv, R2Vector bUv)
      As clipToFace(S2Point, S2Point, int, R2Vector, R2Vector), but rather than clipping to the square [-1,1]x[-1,1] in (u,v) space, this method clips to [-R,R]x[-R,R] where R=(1+padding).
    • 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 invalid input: '<'= x invalid input: '<'= b, then a1 invalid input: '<'= x1 invalid input: '<'= 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) invalid input: '<'= 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.
    • getIntersection

      static S2Point getIntersection(S2Point a0, S2Point a1, S2Point b0, S2Point b1, S2EdgeUtil.ResultError resultError)
    • 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:
      IllegalArgumentException - Thrown if the parameters are not all unit length.
    • getDistance

      public static S1ChordAngle getDistance(S2Point p, S2Edge e)
      Gets the distance from p to e.
    • updateMinDistance

      public static S1ChordAngle updateMinDistance(S2Point p, S2Edge e, S1ChordAngle minDistance)
      Gets the minimum of the distance from a to e and minDistance.
    • 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:
      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.
    • getEdgePairMinDistance

      public static S1ChordAngle getEdgePairMinDistance(S2Point a0, S2Point a1, S2Point b0, S2Point b1, S1ChordAngle minDist)
      Like updateMinDistance(com.google.common.geometry.S2Point, com.google.common.geometry.S2Edge, com.google.common.geometry.S1ChordAngle), but computes the minimum distance between the given pair of edges. (If the two edges cross, the distance is zero.) The cases a0.equals(a1) and b0.equals(b1) are handled correctly.
    • getEdgePairDistance

      public static S1ChordAngle getEdgePairDistance(S2Point a0, S2Point a1, S2Point b0, S2Point b1)
      Gets distance between edges with no minimum distance.
    • 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.
    • getEdgePairMaxDistance

      public static S1ChordAngle getEdgePairMaxDistance(S2Point a0, S2Point a1, S2Point b0, S2Point b1, S1ChordAngle maxDist)
      Like updateMaxDistance(com.google.common.geometry.S2Point, com.google.common.geometry.S2Point, com.google.common.geometry.S2Point, com.google.common.geometry.S1ChordAngle), but computes the maximum distance between the given pair of edges. If the two edges cross, the distance is zero. The cases a0.equals(a1) and b0.equals(b1) are handled 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:
      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, S2Point aCrossB)
      As getClosestPoint(S2Point, S2Point, S2Point), but faster if the cross product between a and b has already been computed. All points must be unit length; results are undefined if that is not the case.
    • 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.
    • interpolateAtDistance

      public static S2Point interpolateAtDistance(S1Angle ax, S2Point a, S2Point b, S1Angle ab)
      A slightly more efficient version of interpolateAtDistance(com.google.common.geometry.S1Angle, com.google.common.geometry.S2Point, com.google.common.geometry.S2Point, com.google.common.geometry.S1Angle) that can be used when the distance AB is already known. Requires that all vectors have unit length.
    • interpolateAtDistance

      public static S2Point interpolateAtDistance(S1Angle ax, S2Point a, S2Point b)
      Like interpolate(double, com.google.common.geometry.S2Point, com.google.common.geometry.S2Point), except that the parameter "ax" represents the desired distance from A to the result X rather than a fraction between 0 and 1. Requires that a and b are unit length.
    • 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.
    • getMinInteriorDistanceMaxError

      static double getMinInteriorDistanceMaxError(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), 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).
    • 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.