Enum S2Projections

java.lang.Object
java.lang.Enum<S2Projections>
com.google.common.geometry.S2Projections
All Implemented Interfaces:
Serializable, Comparable<S2Projections>, java.lang.constant.Constable

@GwtCompatible public enum S2Projections extends 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 final class 
    A [face, si, ti] position.
    static class 
    A transform from 3D cartesian coordinates to the 2D coordinates of a face.
    (package private) static interface 
    A transform from 2D cartesian coordinates of a face to 3D directional vectors.

    Nested classes/interfaces inherited from class java.lang.Enum

    Enum.EnumDesc<E extends Enum<E>>
  • Enum Constant Summary

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

    Fields
    Modifier and Type
    Field
    Description
    final S2.Metric
    Average angular separation between opposite edges of a cell at level k.
    final S2.Metric
    Average area of a cell at level k.
    final S2.Metric
    Average diagonal size of cells at level k.
    final S2.Metric
    Average angular length of any cell edge at level k.
    final S2.Metric
    Average perpendicular angular separation between opposite edges of a cell at level k.
    private static final S2Point[][]
    The U,V,W axes for each face.
    private static final int[][][]
    The precomputed neighbors of each face.
    static final long
    The maximum value of an si- or ti-coordinate.
    final S2.Metric
    Maximum angular separation between opposite edges of a cell at level k.
    final S2.Metric
    Maximum area of a cell at level k.
    final S2.Metric
    Maximum diagonal size of cells at level k.
    final double
    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.
    final S2.Metric
    Maximum angular length of any cell edge at level k.
    final double
    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.
    final S2.Metric
    Maximum perpendicular angular separation between opposite edges of a cell at level k.
    final S2.Metric
    Minimum angular separation between opposite edges of a cell at level k.
    final S2.Metric
    Minimum area of a cell at level k.
    final S2.Metric
    Minimum diagonal size of cells at level k.
    final S2.Metric
    Minimum angular length of any cell edge at level k.
    final S2.Metric
    Minimum perpendicular angular separation between opposite edges of a cell at level k.
    static final S2Projections
    The default transformation between ST and UV coordinates.
    private static final S2Projections.UvTransform[]
    The transforms to convert (x, y, z) coordinates to u and v coordinates on a specific face, indexed by face.
    private static final S2Projections.XyzTransform[]
    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

    Modifier and Type
    Method
    Description
    faceSiTiToXyz(int face, long si, long ti)
    Convert (face, si, ti) coordinates to a direction vector (not necessarily unit length.)
    Returns the S2Projections.UvTransform for the specified face.
    (package private) static S2Projections.XyzTransform
    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
    If p is exactly a cell center, returns the level of the cell, -1 otherwise.
    private static final 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.
    Returns the enum constant of this type with the specified name.
    static S2Projections[]
    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
    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
    Convert a direction vector (not necessarily unit length) to (face, si, ti) coordinates.

    Methods inherited from class java.lang.Object

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

    • 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 Details

    • 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:
    • 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 Details

    • 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 Details

    • values

      public static S2Projections[] values()
      Returns an array containing the constants of this enum type, in the order they are declared.
      Returns:
      an array containing the constants of this enum type, in the order they are declared
    • valueOf

      public static S2Projections valueOf(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:
      IllegalArgumentException - if this enum type has no constant with the specified name
      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.

    • faceToXyzTransform

      static S2Projections.XyzTransform faceToXyzTransform(int face)
      Returns the S2Projections.XyzTransform for the specified face.
    • 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.
    • faceToUvTransform

      public static S2Projections.UvTransform faceToUvTransform(int face)
      Returns the S2Projections.UvTransform for the specified face.
    • 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.