Class S2
- java.lang.Object
-
- com.google.common.geometry.S2
-
@GwtCompatible public final class S2 extends java.lang.Object
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
S2.Metric
Defines an area or a length cell metric.
-
Field Summary
Fields Modifier and Type Field Description static double
DBL_EPSILON
The smallest floating-point valuex
such that(1 + x != 1)
.private static int[][]
IJ_TO_POS
Mapping from Hilbert traversal order + cell orientation to IJ-index.static int
INVERT_MASK
static double
M_1_PI
static double
M_E
static double
M_PI
static double
M_PI_2
static double
M_PI_4
static double
M_SQRT1_2
Inverse of the root of 2.static double
M_SQRT2
private static S2Point
ORIGIN
private static S2Point[]
ORTHO_BASES
private static int[][]
posToIj
Mapping from cell orientation + Hilbert traversal to IJ-index.private static int[]
posToOrientation
Mapping Hilbert traversal order to orientation adjustment mask.static int
SWAP_MASK
-
Constructor Summary
Constructors Modifier Constructor Description private
S2()
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static double
angle(S2Point a, S2Point b, S2Point c)
Return the angle at the vertex B in the triangle ABC.static boolean
approxEquals(double a, double b)
static boolean
approxEquals(double a, double b, double maxError)
static boolean
approxEquals(S2Point a, S2Point b)
static boolean
approxEquals(S2Point a, S2Point b, double maxError)
Return true if two points are within the given distance of each other (mainly useful for testing).static double
area(S2Point a, S2Point b, S2Point c)
Returns the area of triangle ABC.(package private) static S2Point
fromFrame(Matrix3x3 frame, S2Point q)
Converts 'p' from the basis given in 'frame'.static Matrix3x3
getFrame(S2Point p0)
Returns a right-handed coordinate frame (three orthonormal vectors) based on a single point, which will become the third axis.static double
getTurningAngleMaxError(int numVertices)
Returns the maximum error inturnAngle(com.google.common.geometry.S2Point, com.google.common.geometry.S2Point, com.google.common.geometry.S2Point)
.static double
girardArea(S2Point a, S2Point b, S2Point c)
Returns the area of the triangle computed using Girard's formula.static int
ijToPos(int orientation, int ijIndex)
Returns the order in which a specified subcell is visited by the Hilbert curve.static boolean
isUnitLength(S2Point p)
Return true if the given point is approximately unit length (this is mainly useful for assertions).static S2Point
origin()
Return a unique "origin" on the sphere for operations that need a fixed reference point.static S2Point
ortho(S2Point a)
Returns a unit-length vector that is orthogonal toa
.static int
planarCCW(R2Vector a, R2Vector b)
Returns +1 if the edge AB is CCW around the origin, -1 if its clockwise, and 0 if the result is indeterminate.static S2Point
planarCentroid(S2Point a, S2Point b, S2Point c)
Return the centroid of the planar triangle ABC.static int
planarOrderedCCW(R2Vector a, R2Vector b, R2Vector c)
static int
posToIJ(int orientation, int position)
Return the IJ-index of the subcell at the given position in the Hilbert curve traversal with the given orientation.static int
posToOrientation(int position)
Returns an XOR bit mask indicating how the orientation of a child subcell is related to the orientation of its parent cell.static S2Point
robustCrossProd(S2Point a, S2Point b)
Return a vector "c" that is orthogonal to the given unit-length vectors "a" and "b".(package private) static S2Point
rotate(S2Point p, Matrix3x3 r)
Returns a normalized copyp
after rotating it by the rotation matrixr
.static double
signedArea(S2Point a, S2Point b, S2Point c)
Like area(), but returns a positive value for counterclockwise triangles and a negative value otherwise.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 S2Point
toFrame(Matrix3x3 frame, S2Point p)
Converts 'p' to the basis given in 'frame'.static S2Point
trueCentroid(S2Point a, S2Point b)
Returns the true centroid of the spherical geodesic edge AB multiplied by the length of the edge AB.static S2Point
trueCentroid(S2Point a, S2Point b, S2Point c)
Returns the true centroid of the spherical triangle ABC multiplied by the signed area of spherical triangle ABC.static double
turnAngle(S2Point a, S2Point b, S2Point c)
Returns the exterior angle at the vertex B in the triangle ABC.
-
-
-
Field Detail
-
M_PI
public static final double M_PI
- See Also:
- Constant Field Values
-
M_1_PI
public static final double M_1_PI
- See Also:
- Constant Field Values
-
M_PI_2
public static final double M_PI_2
- See Also:
- Constant Field Values
-
M_PI_4
public static final double M_PI_4
- See Also:
- Constant Field Values
-
M_SQRT1_2
public static final double M_SQRT1_2
Inverse of the root of 2.
-
M_SQRT2
public static final double M_SQRT2
-
M_E
public static final double M_E
- See Also:
- Constant Field Values
-
DBL_EPSILON
public static final double DBL_EPSILON
The smallest floating-point valuex
such that(1 + x != 1)
.
-
ORIGIN
private static final S2Point ORIGIN
-
SWAP_MASK
public static final int SWAP_MASK
- See Also:
- Constant Field Values
-
INVERT_MASK
public static final int INVERT_MASK
- See Also:
- Constant Field Values
-
posToOrientation
private static final int[] posToOrientation
Mapping Hilbert traversal order to orientation adjustment mask.
-
posToIj
private static final int[][] posToIj
Mapping from cell orientation + Hilbert traversal to IJ-index.
-
IJ_TO_POS
private static final int[][] IJ_TO_POS
Mapping from Hilbert traversal order + cell orientation to IJ-index.
-
ORTHO_BASES
private static final S2Point[] ORTHO_BASES
-
-
Method Detail
-
posToOrientation
public static int posToOrientation(int position)
Returns an XOR bit mask indicating how the orientation of a child subcell is related to the orientation of its parent cell. The returned value can be XOR'd with the parent cell's orientation to give the orientation of the child cell.- Parameters:
position
- the position of the subcell in the Hilbert traversal, in the range [0,3].- Returns:
- a bit mask containing some combination of
SWAP_MASK
andINVERT_MASK
. - Throws:
java.lang.IllegalArgumentException
- if position is out of bounds.
-
posToIJ
public static int posToIJ(int orientation, int position)
Return the IJ-index of the subcell at the given position in the Hilbert curve traversal with the given orientation. This is the inverse ofijToPos(int, int)
.- Parameters:
orientation
- the subcell orientation, in the range [0,3].position
- the position of the subcell in the Hilbert traversal, in the range [0,3].- Returns:
- the IJ-index where
0->(0,0), 1->(0,1), 2->(1,0), 3->(1,1)
. - Throws:
java.lang.IllegalArgumentException
- if either parameter is out of bounds.
-
ijToPos
public static final int ijToPos(int orientation, int ijIndex)
Returns the order in which a specified subcell is visited by the Hilbert curve. This is the inverse ofposToIJ(int, int)
.- Parameters:
orientation
- the subcell orientation, in the range [0,3].ijIndex
- the subcell index where0->(0,0), 1->(0,1), 2->(1,0), 3->(1,1)
.- Returns:
- the position of the subcell in the Hilbert traversal, in the range [0,3].
- Throws:
java.lang.IllegalArgumentException
- if either parameter is out of bounds.
-
origin
public static S2Point origin()
Return a unique "origin" on the sphere for operations that need a fixed reference point. It should *not* be a point that is commonly used in edge tests in order to avoid triggering code to handle degenerate cases. (This rules out the north and south poles.)
-
isUnitLength
public static boolean isUnitLength(S2Point p)
Return true if the given point is approximately unit length (this is mainly useful for assertions).
-
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:(1) SimpleCrossing(b,a,c,d) == SimpleCrossing(a,b,c,d) (2) SimpleCrossing(c,d,a,b) == SimpleCrossing(a,b,c,d)
-
robustCrossProd
public static S2Point robustCrossProd(S2Point a, S2Point b)
Return a vector "c" that is orthogonal to the given unit-length vectors "a" and "b". This function is similar to a.CrossProd(b) except that it does a better job of ensuring orthogonality when "a" is nearly parallel to "b", and it returns a non-zero result even when a == b or a == -b.It satisfies the following properties (RCP == robustCrossProd):
(1) RCP(a,b) != 0 for all a, b (2) RCP(b,a) == -RCP(a,b) unless a == b or a == -b (3) RCP(-a,b) == -RCP(a,b) unless a == b or a == -b (4) RCP(a,-b) == -RCP(a,b) unless a == b or a == -b
-
ortho
public static S2Point ortho(S2Point a)
Returns a unit-length vector that is orthogonal toa
. Satisfiesortho(-a) = -ortho(a)
for alla
.
-
area
public static double area(S2Point a, S2Point b, S2Point c)
Returns the area of triangle ABC. This method combines two different algorithms to get accurate results for both large and small triangles. The maximum error is about 5e-15 (about 0.25 square meters on the Earth's surface), the same as girardArea() below, but unlike that method it is also accurate for small triangles. Example: when the true area is 100 square meters, area() yields an error about 1 trillion times smaller than girardArea().All points should be unit length, and no two points should be antipodal. The area is always positive.
-
girardArea
public static double girardArea(S2Point a, S2Point b, S2Point c)
Returns the area of the triangle computed using Girard's formula. All points should be unit length, and no two points should be antipodal.This method is about twice as fast as area() but has poor relative accuracy for small triangles. The maximum error is about 5e-15 (about 0.25 square meters on the Earth's surface) and the average error is about 1e-15. These bounds apply to triangles of any size, even as the maximum edge length of the triangle approaches 180 degrees. But note that for such triangles, tiny perturbations of the input points can change the true mathematical area dramatically.
-
signedArea
public static double signedArea(S2Point a, S2Point b, S2Point c)
Like area(), but returns a positive value for counterclockwise triangles and a negative value otherwise.
-
planarCentroid
public static S2Point planarCentroid(S2Point a, S2Point b, S2Point c)
Return the centroid of the planar triangle ABC. This can be normalized to unit length to obtain the "surface centroid" of the corresponding spherical triangle, i.e. the intersection of the three medians. However, note that for large spherical triangles the surface centroid may be nowhere near the intuitive "center" (see example above).
-
trueCentroid
public static S2Point trueCentroid(S2Point a, S2Point b)
Returns the true centroid of the spherical geodesic edge AB multiplied by the length of the edge AB. As with triangles, the true centroid of a collection of edges may be computed simply by summing the result of this method for each edge.Note that the planar centroid of a geodesic edge is simply 0.5 * (a + b), while the surface centroid is (a + b).normalize(). However neither of these values is appropriate for computing the centroid of a collection of edges (such as a polyline).
Also note that the result of this function is defined to be
S2Point.ORIGIN
if the edge is degenerate (and that this is intended behavior).
-
trueCentroid
public static S2Point trueCentroid(S2Point a, S2Point b, S2Point c)
Returns the true centroid of the spherical triangle ABC multiplied by the signed area of spherical triangle ABC. The reasons for multiplying by the signed area are (1) this is the quantity that needs to be summed to compute the centroid of a union or difference of triangles, and (2) it's actually easier to calculate this way.
-
planarCCW
public static int planarCCW(R2Vector a, R2Vector b)
Returns +1 if the edge AB is CCW around the origin, -1 if its clockwise, and 0 if the result is indeterminate.
-
angle
public static double angle(S2Point a, S2Point b, S2Point c)
Return the angle at the vertex B in the triangle ABC. The return value is always in the range [0, Pi]. The points do not need to be normalized. Ensures that Angle(a,b,c) == Angle(c,b,a) for all a,b,c.The angle is undefined if A or C is diametrically opposite from B, and becomes numerically unstable as the length of edge AB or BC approaches 180 degrees.
-
turnAngle
public static double turnAngle(S2Point a, S2Point b, S2Point c)
Returns the exterior angle at the vertex B in the triangle ABC. The return value is positive if ABC is counterclockwise and negative otherwise. If you imagine an ant walking from A to B to C, this is the angle that the ant turns at vertex B (positive = left, negative = right).Ensures that turnAngle(a,b,c) == -turnAngle(c,b,a) for all distinct a,b,c. The result is undefined if (a == b || b == c), but is either -Pi or Pi if (a == c). All points should be normalized.
-
getTurningAngleMaxError
public static double getTurningAngleMaxError(int numVertices)
Returns the maximum error inturnAngle(com.google.common.geometry.S2Point, com.google.common.geometry.S2Point, com.google.common.geometry.S2Point)
. The returned value is proportional to the number of vertices and the machine epsilon.
-
getFrame
public static Matrix3x3 getFrame(S2Point p0)
Returns a right-handed coordinate frame (three orthonormal vectors) based on a single point, which will become the third axis.
-
rotate
static S2Point rotate(S2Point p, Matrix3x3 r)
Returns a normalized copyp
after rotating it by the rotation matrixr
.
-
toFrame
static S2Point toFrame(Matrix3x3 frame, S2Point p)
Converts 'p' to the basis given in 'frame'.
-
fromFrame
static S2Point fromFrame(Matrix3x3 frame, S2Point q)
Converts 'p' from the basis given in 'frame'.
-
approxEquals
public static boolean approxEquals(S2Point a, S2Point b, double maxError)
Return true if two points are within the given distance of each other (mainly useful for testing).
-
approxEquals
public static boolean approxEquals(double a, double b, double maxError)
-
approxEquals
public static boolean approxEquals(double a, double b)
-
-