Enum S2Projections

  • All Implemented Interfaces:
    java.io.Serializable, java.lang.Comparable<S2Projections>

    @GwtCompatible
    public enum S2Projections
    extends java.lang.Enum<S2Projections>
    This class specifies the coordinate systems and transforms used to project points from the sphere to the unit cube to an S2CellId.

    In the process of converting a latitude-longitude pair to a 64-bit cell id, the following coordinate systems are used:

    • (id): An S2CellId is a 64-bit encoding of a face and a Hilbert curve position on that face. The Hilbert curve position implicitly encodes both the position of a cell and its subdivision level (see s2cellid.h).
    • (face, i, j): Leaf-cell coordinates. "i" and "j" are integers in the range [0,(2**30)-1] that identify a particular leaf cell on the given face. The (i, j) coordinate system is right-handed on each face, and the faces are oriented such that Hilbert curves connect continuously from one face to the next.
    • (face, s, t): Cell-space coordinates. "s" and "t" are real numbers in the range [0,1] that identify a point on the given face. For example, the point (s, t) = (0.5, 0.5) corresponds to the center of the top-level face cell. This point is also a vertex of exactly four cells at each subdivision level greater than zero.
    • (face, si, ti): Discrete cell-space coordinates. These are obtained by multiplying "s" and "t" by 2**31 and rounding to the nearest unsigned integer. Discrete coordinates lie in the range [0,2**31]. This coordinate system can represent the edge and center positions of all cells with no loss of precision (including non-leaf cells). In binary, each coordinate of a level-k cell center ends with a 1 followed by (30 - k) 0s. The coordinates of its edges end with (at least) (31 - k) 0s.
    • (face, u, v): Cube-space coordinates. To make the cells at each level more uniform in size after they are projected onto the sphere, we apply a nonlinear transformation of the form u=f(s), v=f(t). The (u, v) coordinates after this transformation give the actual coordinates on the cube face (modulo some 90 degree rotations) before it is projected onto the unit sphere.
    • (face, u, v, w): Per-face coordinate frame. This is an extension of the (face, u, v) cube-space coordinates that adds a third axis "w" in the direction of the face normal. It is always a right-handed 3D coordinate system. Cube-space coordinates can be converted to this frame by setting w=1, while (u,v,w) coordinates can be projected onto the cube face by dividing by w, i.e. (face, u/w, v/w).
    • (x, y, z): Direction vector (S2Point). Direction vectors are not necessarily unit length, and are often chosen to be points on the biunit cube [-1,+1]x[-1,+1]x[-1,+1]. They can be normalized to obtain the corresponding point on the unit sphere.
    • (lat, lng): Latitude and longitude (S2LatLng). Latitudes must be between -90 and 90 degrees inclusive, and longitudes must be between -180 and 180 degrees inclusive.

    Note that the (i, j), (s, t), (si, ti), and (u, v) coordinate systems are right-handed on all six faces.

    We have implemented three different projections from cell-space (s,t) to cube-space (u,v): S2_LINEAR_PROJECTION, S2_TAN_PROJECTION, and S2_QUADRATIC_PROJECTION. The default is in PROJ, and uses the quadratic projection since it has the best overall behavior.

    Here is a table comparing the cell uniformity using each projection. "Area Ratio" is the maximum ratio over all subdivision levels of the largest cell area to the smallest cell area at that level, "Edge Ratio" is the maximum ratio of the longest edge of any cell to the shortest edge of any cell at the same level, and "Diag Ratio" is the ratio of the longest diagonal of any cell to the shortest diagonal of any cell at the same level. "ToPoint" and "FromPoint" are the times in microseconds required to convert cell IDs to and from points (unit vectors) respectively. "ToPointRaw" is the time to convert to a non-unit-length vector, which is all that is needed for some purposes.

    Projection Area Ratio Edge Ratio Diag Ratio ToPointRaw (microseconds) ToPoint (microseconds) FromPoint (microseconds)
    Linear 5.200 2.117 2.959 0.020 0.087 0.085
    Tangent 1.414 1.414 1.704 0.237 0.299 0.258
    Quadratic 2.082 1.802 1.932 0.033 0.096 0.108

    The worst-case cell aspect ratios are about the same with all three projections. The maximum ratio of the longest edge to the shortest edge within the same cell is about 1.4 and the maximum ratio of the diagonals within the same cell is about 1.7.

    This data was produced using S2CellTest and S2CellIdTest.

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      (package private) static class  S2Projections.FaceSiTi
      A [face, si, ti] position.
      static class  S2Projections.UvTransform
      A transform from 3D cartesian coordinates to the 2D coordinates of a face.
      (package private) static interface  S2Projections.XyzTransform
      A transform from 2D cartesian coordinates of a face to 3D directional vectors.
    • Enum Constant Summary

      Enum Constants 
      Enum Constant Description
      S2_LINEAR_PROJECTION
      This is the fastest transformation, but also produces the least uniform cell sizes.
      S2_QUADRATIC_PROJECTION
      This is an approximation of the tangent projection that is much faster and produces cells that are almost as uniform in size.
      S2_TAN_PROJECTION
      Transforming the coordinates via atan() makes the cell sizes more uniform.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      S2.Metric avgAngleSpan
      Average angular separation between opposite edges of a cell at level k.
      S2.Metric avgArea
      Average area of a cell at level k.
      S2.Metric avgDiag
      Average diagonal size of cells at level k.
      S2.Metric avgEdge
      Average angular length of any cell edge at level k.
      S2.Metric avgWidth
      Average perpendicular angular separation between opposite edges of a cell at level k.
      private static S2Point[][] FACE_UVW_AXES
      The U,V,W axes for each face.
      private static int[][][] FACE_UVW_FACES
      The precomputed neighbors of each face.
      static long MAX_SITI
      The maximum value of an si- or ti-coordinate.
      S2.Metric maxAngleSpan
      Maximum angular separation between opposite edges of a cell at level k.
      S2.Metric maxArea
      Maximum area of a cell at level k.
      S2.Metric maxDiag
      Maximum diagonal size of cells at level k.
      double maxDiagAspect
      This is the maximum diagonal aspect ratio over all cells at any level, where the diagonal aspect ratio of a cell is defined as the ratio of its longest diagonal length to its shortest diagonal length.
      S2.Metric maxEdge
      Maximum angular length of any cell edge at level k.
      double maxEdgeAspect
      Maximum edge aspect ratio over all cells at any level, where the edge aspect ratio of a cell is defined as the ratio of its longest edge length to its shortest edge length.
      S2.Metric maxWidth
      Maximum perpendicular angular separation between opposite edges of a cell at level k.
      S2.Metric minAngleSpan
      Minimum angular separation between opposite edges of a cell at level k.
      S2.Metric minArea
      Minimum area of a cell at level k.
      S2.Metric minDiag
      Minimum diagonal size of cells at level k.
      S2.Metric minEdge
      Minimum angular length of any cell edge at level k.
      S2.Metric minWidth
      Minimum perpendicular angular separation between opposite edges of a cell at level k.
      static S2Projections PROJ
      The default transformation between ST and UV coordinates.
      private static S2Projections.UvTransform[] UV_TRANSFORMS
      The transforms to convert (x, y, z) coordinates to u and v coordinates on a specific face, indexed by face.
      private static S2Projections.XyzTransform[] XYZ_TRANSFORMS
      The transforms to convert (u, v) coordinates on a specific face to x-, y-, and z- coordinates, indexed by face.
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private S2Projections​(double minAreaDeriv, double maxAreaDeriv, double minAngleSpanDeriv, double maxAngleSpanDeriv, double minWidthDeriv, double avgWidthDeriv, double minEdgeDeriv, double avgEdgeDeriv, double minDiagDeriv, double maxDiagDeriv, double avgDiagDeriv, double maxEdgeAspect)  
    • Method Summary

      All Methods Static Methods Instance Methods Abstract Methods Concrete Methods 
      Modifier and Type Method Description
      S2Point faceSiTiToXyz​(int face, long si, long ti)
      Convert (face, si, ti) coordinates to a direction vector (not necessarily unit length.)
      static S2Projections.UvTransform faceToUvTransform​(int face)
      Returns the S2Projections.UvTransform for the specified face.
      (package private) static S2Projections.XyzTransform faceToXyzTransform​(int face)
      Returns the S2Projections.XyzTransform for the specified face.
      static S2Point faceUvToXyz​(int face, double u, double v)
      Convert (face, u, v) coordinates to a direction vector (not necessarily unit length).
      static S2Point faceUvToXyz​(int face, R2Vector uv)
      Convert (face, u, v) coordinates to a direction vector (not necessarily unit length).
      static R2Vector faceXyzToUv​(int face, S2Point p)
      If the dot product of p with the given face normal is positive, set the corresponding u and v values (which may lie outside the range [-1,1]) and return true.
      static S2Point faceXyzToUvw​(int face, S2Point p)
      Returns the given point P transformed to the (u,v,w) coordinate frame of the given face (where the w-axis represents the face normal).
      static S2Point getNorm​(int face)
      Returns the unit-length normal for the given face.
      static S2Point getUAxis​(int face)
      Returns the u-axis for the given face.
      static S2Point getUNorm​(int face, double u)
      Returns the right-handed normal (not necessarily unit length) for an edge in the direction of the positive v-axis at the given u-value on the given face.
      (package private) static S2Point getUVWAxis​(int face, int axis)
      Returns the given axis of the given face (u=0, v=1, w=2).
      (package private) static int getUVWFace​(int face, int axis, int direction)
      Returns the face that lies in the given direction (negative=0, positive=1) of the given axis (u=0, v=1, w=2) in the given face.
      static S2Point getVAxis​(int face)
      Returns the v-axis for the given face.
      static S2Point getVNorm​(int face, double v)
      Returns the right-handed normal (not necessarily unit length) for an edge in the direction of the positive u-axis at the given v-value on the given face.
      static double ijToStMin​(int i)
      Converts the i- or j-index of a leaf cell to the minimum corresponding s- or t-value contained by that cell.
      double ijToUV​(int ij, int cellSize)
      Converts the specified i- or j-coordinate into its corresponding u- or v-coordinate, respectively, for the given cell size.
      (package private) int levelIfCenter​(S2Projections.FaceSiTi fst, S2Point p)
      If p is exactly a cell center, returns the level of the cell, -1 otherwise.
      private static int siTiToLevel​(long siTi)
      Returns the level of the given si or ti coordinate.
      static double siTiToSt​(long si)
      Returns the s- or t-value corresponding to the given si- or ti-value.
      static int stToIj​(double s)
      Returns the i- or j-index of the leaf cell containing the given s- or t-value.
      static long stToSiTi​(double s)
      Returns the si- or ti-coordinate that is nearest to the given s- or t-value.
      abstract double stToUV​(double s)
      Convert an s- or t-value to the corresponding u- or v-value.
      abstract double uvToST​(double u)
      The inverse of stToUV(double).
      static R2Vector validFaceXyzToUv​(int face, S2Point p)
      Given a *valid* face for the given point p (meaning that dot product of p with the face normal is positive), return the corresponding u and v values (which may lie outside the range [-1,1]).
      (package private) static void validFaceXyzToUv​(int face, S2Point p, R2Vector result)
      As validFaceXyzToUv(int, S2Point), except result is updated, instead of a being returned in a new instance.
      static S2Projections valueOf​(java.lang.String name)
      Returns the enum constant of this type with the specified name.
      static S2Projections[] values()
      Returns an array containing the constants of this enum type, in the order they are declared.
      (package private) static int xyzToFace​(double x, double y, double z)
      As xyzToFace(S2Point), but accepts the coordinates as primitive doubles instead.
      static int xyzToFace​(S2Point p)
      Returns the face containing the given direction vector (for points on the boundary between faces, the result is arbitrary but repeatable.)
      (package private) S2Projections.FaceSiTi xyzToFaceSiTi​(S2Point p)
      Convert a direction vector (not necessarily unit length) to (face, si, ti) coordinates.
      • Methods inherited from class java.lang.Enum

        clone, compareTo, equals, finalize, getDeclaringClass, hashCode, name, ordinal, toString, valueOf
      • Methods inherited from class java.lang.Object

        getClass, notify, notifyAll, wait, wait, wait
    • Enum Constant Detail

      • S2_LINEAR_PROJECTION

        public static final S2Projections S2_LINEAR_PROJECTION
        This is the fastest transformation, but also produces the least uniform cell sizes. Cell areas vary by a factor of about 5.2, with the largest cells at the center of each face and the smallest cells in the corners.
      • S2_TAN_PROJECTION

        public static final S2Projections S2_TAN_PROJECTION
        Transforming the coordinates via atan() makes the cell sizes more uniform. The areas vary by a maximum ratio of 1.4 as opposed to a maximum ratio of 5.2. However, each call to atan() is about as expensive as all of the other calculations combined when converting from points to cell IDs, i.e. it reduces performance by a factor of 3.
      • S2_QUADRATIC_PROJECTION

        public static final S2Projections S2_QUADRATIC_PROJECTION
        This is an approximation of the tangent projection that is much faster and produces cells that are almost as uniform in size. It is about 3 times faster than the tangent projection for converting cell IDs to points or vice versa. Cell areas vary by a maximum ratio of about 2.1.
    • Field Detail

      • MAX_SITI

        public static final long MAX_SITI
        The maximum value of an si- or ti-coordinate. The range of valid (si,ti) values is [0..MAX_SiTi].
        See Also:
        Constant Field Values
      • FACE_UVW_AXES

        private static final S2Point[][] FACE_UVW_AXES
        The U,V,W axes for each face.
      • FACE_UVW_FACES

        private static final int[][][] FACE_UVW_FACES
        The precomputed neighbors of each face. See getUVWFace(int, int, int).
      • UV_TRANSFORMS

        private static final S2Projections.UvTransform[] UV_TRANSFORMS
        The transforms to convert (x, y, z) coordinates to u and v coordinates on a specific face, indexed by face.
      • XYZ_TRANSFORMS

        private static final S2Projections.XyzTransform[] XYZ_TRANSFORMS
        The transforms to convert (u, v) coordinates on a specific face to x-, y-, and z- coordinates, indexed by face.
      • minArea

        public final S2.Metric minArea
        Minimum area of a cell at level k.
      • maxArea

        public final S2.Metric maxArea
        Maximum area of a cell at level k.
      • avgArea

        public final S2.Metric avgArea
        Average area of a cell at level k.
      • minAngleSpan

        public final S2.Metric minAngleSpan
        Minimum angular separation between opposite edges of a cell at level k. Each cell is bounded by four planes passing through its four edges and the center of the sphere. The angle span metrics relate to the angle between each pair of opposite bounding planes, or equivalently, between the planes corresponding to two different s-values or two different t-values.
      • maxAngleSpan

        public final S2.Metric maxAngleSpan
        Maximum angular separation between opposite edges of a cell at level k.
      • avgAngleSpan

        public final S2.Metric avgAngleSpan
        Average angular separation between opposite edges of a cell at level k.
      • minWidth

        public final S2.Metric minWidth
        Minimum perpendicular angular separation between opposite edges of a cell at level k.

        The width of a geometric figure is defined as the distance between two parallel bounding lines in a given direction. For cells, the minimum width is always attained between two opposite edges, and the maximum width is attained between two opposite vertices. However, for our purposes we redefine the width of a cell as the perpendicular distance between a pair of opposite edges. A cell therefore has two widths, one in each direction. The minimum width according to this definition agrees with the classic geometric one, but the maximum width is different. (The maximum geometric width corresponds to maxDiag.)

        This is useful for bounding the minimum or maximum distance from a point on one edge of a cell to the closest point on the opposite edge. For example, this is useful when "growing" regions by a fixed distance.

      • maxWidth

        public final S2.Metric maxWidth
        Maximum perpendicular angular separation between opposite edges of a cell at level k.
      • avgWidth

        public final S2.Metric avgWidth
        Average perpendicular angular separation between opposite edges of a cell at level k.
      • minEdge

        public final S2.Metric minEdge
        Minimum angular length of any cell edge at level k. The edge length metrics can also be used to bound the minimum, maximum, or average distance from the center of one cell to the center of one of its edge neighbors. In particular, it can be used to bound the distance between adjacent cell centers along the space-filling Hilbert curve for cells at any given level.
      • maxEdge

        public final S2.Metric maxEdge
        Maximum angular length of any cell edge at level k.
      • avgEdge

        public final S2.Metric avgEdge
        Average angular length of any cell edge at level k.
      • minDiag

        public final S2.Metric minDiag
        Minimum diagonal size of cells at level k.
      • maxDiag

        public final S2.Metric maxDiag
        Maximum diagonal size of cells at level k. The maximum diagonal also happens to be the maximum diameter of any cell, and also the maximum geometric width. So for example, the distance from an arbitrary point to the closest cell center at a given level is at most half the maximum diagonal length.
      • avgDiag

        public final S2.Metric avgDiag
        Average diagonal size of cells at level k.
      • maxEdgeAspect

        public final double maxEdgeAspect
        Maximum edge aspect ratio over all cells at any level, where the edge aspect ratio of a cell is defined as the ratio of its longest edge length to its shortest edge length.
      • maxDiagAspect

        public final double maxDiagAspect
        This is the maximum diagonal aspect ratio over all cells at any level, where the diagonal aspect ratio of a cell is defined as the ratio of its longest diagonal length to its shortest diagonal length.
      • PROJ

        public static final S2Projections PROJ
        The default transformation between ST and UV coordinates.
    • Constructor Detail

      • S2Projections

        private S2Projections​(double minAreaDeriv,
                              double maxAreaDeriv,
                              double minAngleSpanDeriv,
                              double maxAngleSpanDeriv,
                              double minWidthDeriv,
                              double avgWidthDeriv,
                              double minEdgeDeriv,
                              double avgEdgeDeriv,
                              double minDiagDeriv,
                              double maxDiagDeriv,
                              double avgDiagDeriv,
                              double maxEdgeAspect)
    • Method Detail

      • values

        public static S2Projections[] values()
        Returns an array containing the constants of this enum type, in the order they are declared. This method may be used to iterate over the constants as follows:
        for (S2Projections c : S2Projections.values())
            System.out.println(c);
        
        Returns:
        an array containing the constants of this enum type, in the order they are declared
      • valueOf

        public static S2Projections valueOf​(java.lang.String name)
        Returns the enum constant of this type with the specified name. The string must match exactly an identifier used to declare an enum constant in this type. (Extraneous whitespace characters are not permitted.)
        Parameters:
        name - the name of the enum constant to be returned.
        Returns:
        the enum constant with the specified name
        Throws:
        java.lang.IllegalArgumentException - if this enum type has no constant with the specified name
        java.lang.NullPointerException - if the argument is null
      • stToUV

        public abstract double stToUV​(double s)
        Convert an s- or t-value to the corresponding u- or v-value. This is a non-linear transformation from [-1,1] to [-1,1] that attempts to make the cell sizes more uniform.
      • stToIj

        public static int stToIj​(double s)
        Returns the i- or j-index of the leaf cell containing the given s- or t-value. If the argument is outside the range spanned by valid leaf cell indices, return the index of the closest valid leaf cell (i.e., return values are clamped to the range of valid leaf cell indices).
      • ijToStMin

        public static double ijToStMin​(int i)
        Converts the i- or j-index of a leaf cell to the minimum corresponding s- or t-value contained by that cell. The argument must be in the range [0..2**30], i.e. up to one position beyond the normal range of valid leaf cell indices.
      • ijToUV

        public double ijToUV​(int ij,
                             int cellSize)
        Converts the specified i- or j-coordinate into its corresponding u- or v-coordinate, respectively, for the given cell size.
      • siTiToSt

        public static double siTiToSt​(long si)
        Returns the s- or t-value corresponding to the given si- or ti-value.
      • stToSiTi

        public static long stToSiTi​(double s)
        Returns the si- or ti-coordinate that is nearest to the given s- or t-value. The result may be outside the range of valid (si,ti)-values.
      • uvToST

        public abstract double uvToST​(double u)
        The inverse of stToUV(double). Note that it is not always true that uvToST(stToUV(x)) == x due to numerical errors.
      • faceUvToXyz

        public static S2Point faceUvToXyz​(int face,
                                          double u,
                                          double v)
        Convert (face, u, v) coordinates to a direction vector (not necessarily unit length).

        Requires that the face is between 0 and 5, inclusive.

      • faceUvToXyz

        public static S2Point faceUvToXyz​(int face,
                                          R2Vector uv)
        Convert (face, u, v) coordinates to a direction vector (not necessarily unit length).

        Requires that the face is between 0 and 5, inclusive.

      • faceXyzToUv

        public static R2Vector faceXyzToUv​(int face,
                                           S2Point p)
        If the dot product of p with the given face normal is positive, set the corresponding u and v values (which may lie outside the range [-1,1]) and return true. Otherwise return null.
      • validFaceXyzToUv

        public static R2Vector validFaceXyzToUv​(int face,
                                                S2Point p)
        Given a *valid* face for the given point p (meaning that dot product of p with the face normal is positive), return the corresponding u and v values (which may lie outside the range [-1,1]).

        Requires that the face is between 0 and 5, inclusive.

      • validFaceXyzToUv

        static void validFaceXyzToUv​(int face,
                                     S2Point p,
                                     R2Vector result)
        As validFaceXyzToUv(int, S2Point), except result is updated, instead of a being returned in a new instance. Package-private because non-S2 classes should not be mutating R2Vectors.
      • faceXyzToUvw

        public static S2Point faceXyzToUvw​(int face,
                                           S2Point p)
        Returns the given point P transformed to the (u,v,w) coordinate frame of the given face (where the w-axis represents the face normal).
      • siTiToLevel

        private static final int siTiToLevel​(long siTi)
        Returns the level of the given si or ti coordinate.
      • faceSiTiToXyz

        public S2Point faceSiTiToXyz​(int face,
                                     long si,
                                     long ti)
        Convert (face, si, ti) coordinates to a direction vector (not necessarily unit length.)
      • xyzToFaceSiTi

        S2Projections.FaceSiTi xyzToFaceSiTi​(S2Point p)
        Convert a direction vector (not necessarily unit length) to (face, si, ti) coordinates.
      • levelIfCenter

        int levelIfCenter​(S2Projections.FaceSiTi fst,
                          S2Point p)
        If p is exactly a cell center, returns the level of the cell, -1 otherwise.
      • xyzToFace

        public static int xyzToFace​(S2Point p)
        Returns the face containing the given direction vector (for points on the boundary between faces, the result is arbitrary but repeatable.)
      • xyzToFace

        static int xyzToFace​(double x,
                             double y,
                             double z)
        As xyzToFace(S2Point), but accepts the coordinates as primitive doubles instead. Useful when the caller has coordinates and doesn't want to allocate an S2Point.
      • getUNorm

        public static S2Point getUNorm​(int face,
                                       double u)
        Returns the right-handed normal (not necessarily unit length) for an edge in the direction of the positive v-axis at the given u-value on the given face. (This vector is perpendicular to the plane through the sphere origin that contains the given edge.)
      • getVNorm

        public static S2Point getVNorm​(int face,
                                       double v)
        Returns the right-handed normal (not necessarily unit length) for an edge in the direction of the positive u-axis at the given v-value on the given face.
      • getUAxis

        public static S2Point getUAxis​(int face)
        Returns the u-axis for the given face.
      • getVAxis

        public static S2Point getVAxis​(int face)
        Returns the v-axis for the given face.
      • getNorm

        public static S2Point getNorm​(int face)
        Returns the unit-length normal for the given face.
      • getUVWAxis

        static S2Point getUVWAxis​(int face,
                                  int axis)
        Returns the given axis of the given face (u=0, v=1, w=2).
      • getUVWFace

        static int getUVWFace​(int face,
                              int axis,
                              int direction)
        Returns the face that lies in the given direction (negative=0, positive=1) of the given axis (u=0, v=1, w=2) in the given face. For example, getUVWFace(4, 0, 1) returns the face that is adjacent to face 4 in the positive u-axis direction.