Enum S2Projections
- All Implemented Interfaces:
Serializable
,Comparable<S2Projections>
,java.lang.constant.Constable
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 ClassesModifier and TypeClassDescription(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 ConstantsEnum ConstantDescriptionThis 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
FieldsModifier and TypeFieldDescriptionfinal 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
ConstructorsModifierConstructorDescriptionprivate
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 TypeMethodDescriptionfaceSiTiToXyz
(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 theS2Projections.UvTransform
for the specified face.(package private) static S2Projections.XyzTransform
faceToXyzTransform
(int face) Returns theS2Projections.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 ofstToUV(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) AsvalidFaceXyzToUv(int, S2Point)
, exceptresult
is updated, instead of a being returned in a new instance.static S2Projections
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) AsxyzToFace(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.
-
Enum Constant Details
-
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
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
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_SITIThe maximum value of an si- or ti-coordinate. The range of valid (si,ti) values is [0..MAX_SiTi].- See Also:
-
FACE_UVW_AXES
The U,V,W axes for each face. -
FACE_UVW_FACES
private static final int[][][] FACE_UVW_FACESThe precomputed neighbors of each face. SeegetUVWFace(int, int, int)
. -
UV_TRANSFORMS
The transforms to convert (x, y, z) coordinates to u and v coordinates on a specific face, indexed by face. -
XYZ_TRANSFORMS
The transforms to convert (u, v) coordinates on a specific face to x-, y-, and z- coordinates, indexed by face. -
minArea
Minimum area of a cell at level k. -
maxArea
Maximum area of a cell at level k. -
avgArea
Average area of a cell at level k. -
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
Maximum angular separation between opposite edges of a cell at level k. -
avgAngleSpan
Average angular separation between opposite edges of a cell at level k. -
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
Maximum perpendicular angular separation between opposite edges of a cell at level k. -
avgWidth
Average perpendicular angular separation between opposite edges of a cell at level k. -
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
Maximum angular length of any cell edge at level k. -
avgEdge
Average angular length of any cell edge at level k. -
minDiag
Minimum diagonal size of cells at level k. -
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
Average diagonal size of cells at level k. -
maxEdgeAspect
public final double maxEdgeAspectMaximum 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 maxDiagAspectThis 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
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
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
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 nameNullPointerException
- 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 ofstToUV(double)
. Note that it is not always true thatuvToST(stToUV(x)) == x
due to numerical errors. -
faceUvToXyz
Convert (face, u, v) coordinates to a direction vector (not necessarily unit length).Requires that the face is between 0 and 5, inclusive.
-
faceUvToXyz
Convert (face, u, v) coordinates to a direction vector (not necessarily unit length).Requires that the face is between 0 and 5, inclusive.
-
faceToXyzTransform
Returns theS2Projections.XyzTransform
for the specified face. -
faceXyzToUv
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
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
AsvalidFaceXyzToUv(int, S2Point)
, exceptresult
is updated, instead of a being returned in a new instance. Package-private because non-S2 classes should not be mutating R2Vectors. -
faceToUvTransform
Returns theS2Projections.UvTransform
for the specified face. -
faceXyzToUvw
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
Convert (face, si, ti) coordinates to a direction vector (not necessarily unit length.) -
xyzToFaceSiTi
Convert a direction vector (not necessarily unit length) to (face, si, ti) coordinates. -
levelIfCenter
If p is exactly a cell center, returns the level of the cell, -1 otherwise. -
xyzToFace
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) AsxyzToFace(S2Point)
, but accepts the coordinates as primitive doubles instead. Useful when the caller has coordinates and doesn't want to allocate an S2Point. -
getUNorm
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
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
Returns the u-axis for the given face. -
getVAxis
Returns the v-axis for the given face. -
getNorm
Returns the unit-length normal for the given face. -
getUVWAxis
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.
-