Class S2

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

@GwtCompatible public final class S2 extends Object
  • Field Details

    • M_PI

      public static final double M_PI
      See Also:
    • M_1_PI

      public static final double M_1_PI
      See Also:
    • M_PI_2

      public static final double M_PI_2
      See Also:
    • M_PI_4

      public static final double M_PI_4
      See Also:
    • 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:
    • DBL_EPSILON

      public static final double DBL_EPSILON
      The smallest floating-point value x such that (1 + x != 1).
    • ORIGIN

      private static final S2Point ORIGIN
    • SWAP_MASK

      public static final int SWAP_MASK
      See Also:
    • INVERT_MASK

      public static final int INVERT_MASK
      See Also:
    • 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
  • Constructor Details

    • S2

      private S2()
  • Method Details

    • 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 and INVERT_MASK.
      Throws:
      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 of ijToPos(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:
      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 of posToIJ(int, int).
      Parameters:
      orientation - the subcell orientation, in the range [0,3].
      ijIndex - the subcell index where 0->(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:
      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 to a. Satisfies ortho(-a) = -ortho(a) for all a.
    • 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.
    • planarOrderedCCW

      public static int planarOrderedCCW(R2Vector a, R2Vector b, R2Vector c)
    • 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 in turnAngle(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 copy p after rotating it by the rotation matrix r.
    • 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(S2Point a, S2Point b)
    • approxEquals

      public static boolean approxEquals(double a, double b, double maxError)
    • approxEquals

      public static boolean approxEquals(double a, double b)