Enum S2Projections
- java.lang.Object
-
- java.lang.Enum<S2Projections>
-
- com.google.common.geometry.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 anS2CellId
.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
, andS2_QUADRATIC_PROJECTION
. The default is inPROJ
, 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
andS2CellIdTest
.
-
-
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 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
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 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
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)
AsxyzToFace(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.
-
-
-
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. SeegetUVWFace(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 namejava.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 ofstToUV(double)
. Note that it is not always true thatuvToST(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 theS2Projections.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)
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
public static S2Projections.UvTransform faceToUvTransform(int face)
Returns theS2Projections.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)
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
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.
-
-