Class S2EdgeUtil
- java.lang.Object
-
- com.google.common.geometry.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.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) static class
S2EdgeUtil.CloserResult
private static class
S2EdgeUtil.ClosestPoint
Used to denote which point should be used when finding distances/points.static class
S2EdgeUtil.EdgeCrosser
Used to efficiently test a fixed edge AB against an edge chain.(package private) static class
S2EdgeUtil.FaceSegment
FaceSegment represents an edge AB clipped to an S2 cube face.static class
S2EdgeUtil.LongitudePruner
The purpose of this class is to find edges that intersect a given longitude interval.static class
S2EdgeUtil.RectBounder
This class computes a bounding rectangle that contains all edges defined by a vertex chain v0, v1, v2, ...(package private) static class
S2EdgeUtil.ResultError
Encapsulation of a mutable error value.static class
S2EdgeUtil.WedgeContains
Returns true if wedge A contains wedge B.static class
S2EdgeUtil.WedgeContainsOrCrosses
static class
S2EdgeUtil.WedgeContainsOrIntersects
static class
S2EdgeUtil.WedgeIntersects
Returns true if wedge A intersects wedge B.static interface
S2EdgeUtil.WedgeProcessor
Wedge processors are used to determine the local relationship between two polygons that share a common vertex.(package private) static class
S2EdgeUtil.WedgeRelation
Spatial containment relationships between a wedge A to another wedge B.static class
S2EdgeUtil.XYZPruner
The purpose of this class is to find edges that intersect a given XYZ bounding box.
-
Field Summary
Fields Modifier and Type Field Description static S1Angle
DEFAULT_INTERSECTION_TOLERANCE
IEEE floating-point operations have a maximum error of 0.5 ULPS (units in the last place).static 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).static double
EDGE_CLIP_ERROR_UV_DIST
The maximum error between a clipped edge or boundary point and the corresponding exact result.static double
FACE_CLIP_ERROR_RADIANS
The maximum angle between a returned vertex and the nearest point on the exact edge AB.static double
FACE_CLIP_ERROR_UV_COORD
The same angle asFACE_CLIP_ERROR_RADIANS
, expressed as the maximum error in an individual u- or v-coordinate.static double
FACE_CLIP_ERROR_UV_DIST
The same angle asFACE_CLIP_ERROR_RADIANS
, expressed as a maximum distance in (u,v)-space.static 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.static double
INTERSECTS_RECT_ERROR_UV_DIST
The maximum error in IntersectRect.static double
MAX_CELL_EDGE_ERROR
Max error allowed when checking if a loop boundary approximately intersects a target cellprivate static double
MAX_DET_ERROR
Threshold for small angles, that help lenientCrossing to determine whether two edges are likely to intersect.
-
Constructor Summary
Constructors Modifier Constructor Description private
S2EdgeUtil()
Constructor is private so that this class is never instantiated.
-
Method Summary
All Methods Static Methods Concrete Methods Deprecated Methods Modifier and Type Method Description private static boolean
ccw(S2Point a, S2Point b, S2Point c)
Deprecated.Temporary bridge for refactoring(package private) 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".(package private) static int
clipDestination(S2Point a, S2Point b, S2Point nScaled, S2Point aTangent, S2Point bTangent, double uvScale, R2Vector uv)
This helper function does two things.(package private) 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.(package private) 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.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.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).(package private) 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.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.(package private) static S2Point
correctIntersectionSign(S2Point a0, S2Point a1, S2Point b0, S2Point b1, S2Point intersectionResult)
Returns intersection result with sign corrected (if necessary).private static double
diffMag2(S2Point a, S2Point b)
Returns the squared distance froma
tob
.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.(package private) 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".static S2Point
getClosestPoint(S2Point x, S2Point a, S2Point b)
Returns the point on edge AB closest to X.static S2Point
getClosestPoint(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 S1ChordAngle
getDistance(S2Point p, S2Edge e)
Gets the distance fromp
toe
.static S1Angle
getDistance(S2Point x, S2Point a, S2Point b)
Return the minimum distance from X to any point on the edge AB.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.static double
getDistanceFraction(S2Point x, S2Point a0, S2Point a1)
Given a point X and an edge AB, return the distance ratio AX / (AX + BX).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.(package private) static void
getEdgePairClosestPoints(S2Point a0, S2Point a1, S2Point b0, S2Point b1, S2Point[] result)
Updates theresults
with points that achieve the minimum distance between edges a0a1 and b0b1, wherea
is a point on a0a1 andb
is a point on b0b1.static S1ChordAngle
getEdgePairDistance(S2Point a0, S2Point a1, S2Point b0, S2Point b1)
Gets distance between edges with no minimum distance.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.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.(package private) 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.(package private) 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 ofgetExitAxis(S2Point)
, setresult
to the (u,v) coordinates of the point where L exits the cube face.(package private) 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).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.(package private) 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.(package private) 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.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.(package private) static S2Point
getIntersectionExact(S2Point a0, S2Point a1, S2Point b0, S2Point b1)
Compute the intersection point of (a0, a1) and (b0, b1) using exact arithmetic.(package private) static double
getMinDistanceMaxError(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 double
getMinInteriorDistanceMaxError(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 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).(package private) 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)
.static S2EdgeUtil.WedgeRelation
getWedgeRelation(S2Point a0, S2Point ab1, S2Point a2, S2Point b0, S2Point b2)
Returns the relation from wedge A to B.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.static S2Point
interpolateAtDistance(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 S2Point
interpolateAtDistance(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 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.(package private) static boolean
intersectsFace(S2Point n)
Returns true if a given directed line L intersects the cube face F.(package private) 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).(package private) 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.static boolean
lenientCrossing(S2Point a, S2Point b, S2Point c, S2Point d)
Returns true if ab possibly crosses cd, by clipping tiny angles to zero.(package private) 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.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).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.(package private) static boolean
sumEquals(double u, double v, double w)
Returns true if u + v == w exactly.(package private) static boolean
updateEndpoint(R1Interval bound, boolean slopeNegative, double value)
Moves an endpoint of the given bound to the given value.static S1ChordAngle
updateMaxDistance(S2Point x, S2Point a, S2Point b, S1ChordAngle maxDistance)
Returns the maximum of the distance fromx
to any point on edge AB and the givenmaxDistance
.static S1ChordAngle
updateMinDistance(S2Point p, S2Edge e, S1ChordAngle minDistance)
Gets the minimum of the distance froma
toe
andminDistance
.static S1ChordAngle
updateMinDistance(S2Point x, S2Point a, S2Point b, S1ChordAngle minDistance)
Return the minimum of the distance fromx
to any point on edge ab and the givenminDistance
.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.
-
-
-
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_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 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_DIST
The 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_COORD
The 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_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.
-
-
Method Detail
-
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 ofgetExitAxis(S2Point)
, setresult
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)
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
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:- If x == a, then x1 = a1 (exactly).
- If x == b, then x1 = b1 (exactly).
- 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)
-
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
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.
-
getDistance
public static S1ChordAngle getDistance(S2Point p, S2Edge e)
Gets the distance fromp
toe
.
-
updateMinDistance
public static S1ChordAngle updateMinDistance(S2Point p, S2Edge e, S1ChordAngle minDistance)
Gets the minimum of the distance froma
toe
andminDistance
.
-
updateMinDistance
public static S1ChordAngle updateMinDistance(S2Point x, S2Point a, S2Point b, S1ChordAngle minDistance)
Return the minimum of the distance fromx
to any point on edge ab and the givenminDistance
. The casea.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 fromx
to 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
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 theresults
with points that achieve the minimum distance between edges a0a1 and b0b1, wherea
is a point on a0a1 andb
is a point on b0b1. If the two edges intersect,a
andb
are 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
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 froma
tob
.
-
getClosestPoint
public static S2Point getClosestPoint(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. 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 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
public static S2Point interpolateAtDistance(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. Requires thata
andb
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 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
static double getMinDistanceMaxError(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()
. 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
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 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.
-
-