Class S2EdgeUtil
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescription(package private) static classprivate static enumUsed to denote which point should be used when finding distances/points.static final classUsed to efficiently test a fixed edge AB against an edge chain.(package private) static final classFaceSegment represents an edge AB clipped to an S2 cube face.static classThe purpose of this class is to find edges that intersect a given longitude interval.static classThis class computes a bounding rectangle that contains all edges defined by a vertex chain v0, v1, v2, ...(package private) static final classEncapsulation of a mutable error value.static classReturns true if wedge A contains wedge B.static classstatic classstatic classReturns true if wedge A intersects wedge B.static interfaceWedge processors are used to determine the local relationship between two polygons that share a common vertex.(package private) static enumSpatial containment relationships between a wedge A to another wedge B.static classThe purpose of this class is to find edges that intersect a given XYZ bounding box. -
Field Summary
FieldsModifier and TypeFieldDescriptionstatic final S1AngleIEEE floating-point operations have a maximum error of 0.5 ULPS (units in the last place).static final doubleThe 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).static final doubleThe maximum error between a clipped edge or boundary point and the corresponding exact result.static final doubleThe maximum angle between a returned vertex and the nearest point on the exact edge AB.static final doubleThe same angle asFACE_CLIP_ERROR_RADIANS, expressed as the maximum error in an individual u- or v-coordinate.static final doubleThe same angle asFACE_CLIP_ERROR_RADIANS, expressed as a maximum distance in (u,v)-space.static final doubleINTERSECTION_ERROR can be set somewhat arbitrarily, because the algorithm uses more precision than necessary in order to achieve the specified error.static final doubleThe maximum error in IntersectRect.static final doubleMax error allowed when checking if a loop boundary approximately intersects a target cellprivate static final doubleThreshold for small angles, that help lenientCrossing to determine whether two edges are likely to intersect. -
Constructor Summary
ConstructorsModifierConstructorDescriptionprivateConstructor is private so that this class is never instantiated. -
Method Summary
Modifier and TypeMethodDescriptionprivate static booleanDeprecated.Temporary bridge for refactoring(package private) static booleanclipBoundAxis(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".(package private) static intclipDestination(S2Point a, S2Point b, S2Point nScaled, S2Point aTangent, S2Point bTangent, double uvScale, R2Vector uv) This helper function does two things.(package private) static booleanGiven 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.(package private) static booleanclipEdgeBound(R2Vector a, R2Vector b, R2Rect clip, R2Rect bound) This function can be used to clip an edge AB to sequence of rectangles efficiently.static booleanclipToFace(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.static booleanclipToPaddedFace(S2Point aXyz, S2Point bXyz, int face, double padding, R2Vector aUv, R2Vector bUv) AsclipToFace(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).(package private) static S2PointclosestAcceptableEndpoint(S2Point a0, S2Point a1, S2Point aNorm, S2Point b0, S2Point b1, S2Point bNorm, S2Point x) Finds the closest acceptable endpoint to a given point.private static booleancompareEdges(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.(package private) static S2PointReturns intersection result with sign corrected (if necessary).private static final doubleReturns the squared distance fromatob.static booleanedgeOrVertexCrossing(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.(package private) static R2RectgetClippedEdgeBound(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".static S2PointgetClosestPoint(S2Point x, S2Point a, S2Point b) Returns the point on edge AB closest to X.static S2PointgetClosestPoint(S2Point x, S2Point a, S2Point b, S2Point aCrossB) AsgetClosestPoint(S2Point, S2Point, S2Point), but faster if the cross product between a and b has already been computed.static S1ChordAnglegetDistance(S2Point p, S2Edge e) Gets the distance fromptoe.static S1AnglegetDistance(S2Point x, S2Point a, S2Point b) Return the minimum distance from X to any point on the edge AB.static S1AnglegetDistance(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.static doublegetDistanceFraction(S2Point x, S2Point a0, S2Point a1) Given a point X and an edge AB, return the distance ratio AX / (AX + BX).static doublegetDistanceRadians(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.(package private) static voidUpdates theresultswith points that achieve the minimum distance between edges a0a1 and b0b1, whereais a point on a0a1 andbis a point on b0b1.static S1ChordAnglegetEdgePairDistance(S2Point a0, S2Point a1, S2Point b0, S2Point b1) Gets distance between edges with no minimum distance.static S1ChordAnglegetEdgePairMaxDistance(S2Point a0, S2Point a1, S2Point b0, S2Point b1, S1ChordAngle maxDist) LikeupdateMaxDistance(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.static S1ChordAnglegetEdgePairMinDistance(S2Point a0, S2Point a1, S2Point b0, S2Point b1, S1ChordAngle minDist) LikeupdateMinDistance(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.(package private) static intGiven 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.(package private) static voidgetExitPoint(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 ofgetExitAxis(S2Point), setresultto the (u,v) coordinates of the point where L exits the cube face.(package private) static intgetFaceSegments(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).static S2PointgetIntersection(S2Point a0, S2Point a1, S2Point b0, S2Point b1) Given two edges AB and CD such that robustCrossing() is true, return their intersection point.(package private) static S2PointgetIntersection(S2Point a0, S2Point a1, S2Point b0, S2Point b1, S2EdgeUtil.ResultError resultError) Helper forgetIntersection(com.google.common.geometry.S2Point,com.google.common.geometry.S2Point,com.google.common.geometry.S2Point,com.google.common.geometry.S2Point)with provided result error parameter for testing and benchmarking purposes.(package private) static S2PointgetIntersectionApprox(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.private static S2PointgetIntersectionApproxSorted(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.(package private) static S2PointgetIntersectionExact(S2Point a0, S2Point a1, S2Point b0, S2Point b1) Compute the intersection point of (a0, a1) and (b0, b1) using exact arithmetic.(package private) static doublegetMinDistanceMaxError(S1ChordAngle distance) Returns the maximum error in the result ofupdateMinDistance(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 byS2Point.normalize().(package private) static doublegetMinInteriorDistanceMaxError(S1ChordAngle distance) Returns the maximum error in the result ofupdateMinDistance(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 byS2Point.normalize().(package private) static intgetNextFace(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).(package private) static doublegetProjection(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 usingS2.robustCrossProd(com.google.common.geometry.S2Point, com.google.common.geometry.S2Point).static S2EdgeUtil.WedgeRelationReturns the relation from wedge A to B.static S2Pointinterpolate(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.static S2PointinterpolateAtDistance(S1Angle ax, S2Point a, S2Point b) Likeinterpolate(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.static S2PointinterpolateAtDistance(S1Angle ax, S2Point a, S2Point b, S1Angle ab) A slightly more efficient version ofinterpolateAtDistance(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.(package private) static doubleinterpolateDouble(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.(package private) static booleanReturns true if a given directed line L intersects the cube face F.(package private) static booleanGiven 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).(package private) static booleanintersectsRect(R2Vector a, R2Vector b, R2Rect rect) Returns true if the edge AB intersects the given (closed) rectangle to within the error bound below.static final booleanlenientCrossing(S2Point a, S2Point b, S2Point c, S2Point d) Returns true if ab possibly crosses cd, by clipping tiny angles to zero.(package private) static intmoveOriginToValidFace(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.static introbustCrossing(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).static booleansimpleCrossing(S2Point a, S2Point b, S2Point c, S2Point d) Return true if edge AB crosses CD at a point that is interior to both edges.(package private) static booleansumEquals(double u, double v, double w) Returns true if u + v == w exactly.(package private) static booleanupdateEndpoint(R1Interval bound, boolean slopeNegative, double value) Moves an endpoint of the given bound to the given value.static S1ChordAngleupdateMaxDistance(S2Point x, S2Point a, S2Point b, S1ChordAngle maxDistance) Returns the maximum of the distance fromxto any point on edge AB and the givenmaxDistance.static S1ChordAngleupdateMinDistance(S2Point p, S2Edge e, S1ChordAngle minDistance) Gets the minimum of the distance fromatoeandminDistance.static S1ChordAngleupdateMinDistance(S2Point x, S2Point a, S2Point b, S1ChordAngle minDistance) Return the minimum of the distance fromxto any point on edge ab and the givenminDistance.static booleanvertexCrossing(S2Point a, S2Point b, S2Point c, S2Point d) Given two edges AB and CD where at least two vertices are identical (i.e.
-
Field Details
-
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_ERRORThreshold 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_RADIANSThe maximum angle between a returned vertex and the nearest point on the exact edge AB. It is equal to the maximum directional error inS2.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_DISTThe same angle asFACE_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_COORDThe same angle asFACE_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_DISTThe 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_COORDThe 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_DISTThe 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_ERRORMax error allowed when checking if a loop boundary approximately intersects a target cell -
INTERSECTION_ERROR
public static final double INTERSECTION_ERRORINTERSECTION_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
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
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
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
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 ofgetExitAxis(S2Point), setresultto the (u,v) coordinates of the point where L exits the cube face. -
moveOriginToValidFace
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
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
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) AsclipToFace(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
Returns true if the edge AB intersects the given (closed) rectangle to within the error bound below. -
updateEndpoint
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
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
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
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:- If x == a, then x1 = a1 (exactly).
- If x == b, then x1 = b1 (exactly).
- 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
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
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
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
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
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
Returns true if ab possibly crosses cd, by clipping tiny angles to zero. -
getIntersection
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)
-
getIntersection
static S2Point getIntersection(S2Point a0, S2Point a1, S2Point b0, S2Point b1, S2EdgeUtil.ResultError resultError) Helper forgetIntersection(com.google.common.geometry.S2Point,com.google.common.geometry.S2Point,com.google.common.geometry.S2Point,com.google.common.geometry.S2Point)with provided result error parameter for testing and benchmarking purposes. -
correctIntersectionSign
static S2Point correctIntersectionSign(S2Point a0, S2Point a1, S2Point b0, S2Point b1, S2Point intersectionResult) Returns intersection result with sign corrected (if necessary). -
getDistanceFraction
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
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
Gets the distance fromptoe. -
updateMinDistance
Gets the minimum of the distance fromatoeandminDistance. -
updateMinDistance
public static S1ChordAngle updateMinDistance(S2Point x, S2Point a, S2Point b, S1ChordAngle minDistance) Return the minimum of the distance fromxto any point on edge ab and the givenminDistance. The casea.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 fromxto any point on edge AB and the givenmaxDistance. The casea.equals(b)is handled correctly. -
getEdgePairMinDistance
public static S1ChordAngle getEdgePairMinDistance(S2Point a0, S2Point a1, S2Point b0, S2Point b1, S1ChordAngle minDist) LikeupdateMinDistance(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 casesa0.equals(a1)andb0.equals(b1)are handled correctly. -
getEdgePairDistance
Gets distance between edges with no minimum distance. -
getEdgePairClosestPoints
static void getEdgePairClosestPoints(S2Point a0, S2Point a1, S2Point b0, S2Point b1, S2Point[] result) Updates theresultswith points that achieve the minimum distance between edges a0a1 and b0b1, whereais a point on a0a1 andbis a point on b0b1. If the two edges intersect,aandbare both equal to the intersection point. Handlesa0.equals(a1)andb0.equals(b1)correctly. -
getEdgePairMaxDistance
public static S1ChordAngle getEdgePairMaxDistance(S2Point a0, S2Point a1, S2Point b0, S2Point b1, S1ChordAngle maxDist) LikeupdateMaxDistance(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 casesa0.equals(a1)andb0.equals(b1)are handled correctly. -
getDistance
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.Temporary bridge for refactoring -
getDistanceRadians
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
Returns the squared distance fromatob. -
getClosestPoint
AsgetClosestPoint(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
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
A slightly more efficient version ofinterpolateAtDistance(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
Likeinterpolate(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 thataandbare unit length. -
interpolate
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
Returns the maximum error in the result ofupdateMinDistance(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 byS2Point.normalize(). The error can be added or subtracted from an S1ChordAngle "x" usingx.plusError(error). -
getMinDistanceMaxError
Returns the maximum error in the result ofupdateMinDistance(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 byS2Point.normalize(). The error can be added or subtracted from an S1ChordAngle "x" usingx.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
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
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 usingS2.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.
-