Class S2CellId
- java.lang.Object
-
- com.google.common.geometry.S2CellId
-
- All Implemented Interfaces:
java.io.Serializable
,java.lang.Comparable<S2CellId>
@Immutable @GwtCompatible(emulated=true, serializable=true) public final class S2CellId extends java.lang.Object implements java.lang.Comparable<S2CellId>, java.io.Serializable
An S2CellId is a 64-bit unsigned integer that uniquely identifies a cell in the S2 cell decomposition. It has the following format:id = [face][face_pos]
face: a 3-bit number (range 0..5) encoding the cube face.
face_pos: a 61-bit number encoding the position of the center of this cell along the Hilbert curve over this face (see the Wiki pages for details).
Sequentially increasing cell ids follow a continuous space-filling curve over the entire sphere. They have the following properties:
- The id of a cell at level k consists of a 3-bit face number followed by k bit pairs that recursively select one of the four children of each cell. The next bit is always 1, and all other bits are 0. Therefore, the level of a cell is determined by the position of its lowest-numbered bit that is turned on (for a cell at level k, this position is 2 * (MAX_LEVEL - k).)
- The id of a parent cell is at the midpoint of the range of ids spanned by its children (or by its descendants at any level).
Leaf cells are often used to represent points on the unit sphere, and this class provides methods for converting directly between these two representations. For cells that represent 2D regions rather than discrete point, it is better to use the S2Cell class.
- See Also:
- Serialized Form
-
-
Field Summary
Fields Modifier and Type Field Description static int
FACE_BITS
static S2CellId[]
FACE_CELLS
private static int
I_SHIFT
private long
id
The id of the cell.private static double
IJ_TO_ST
The change in ST coordinates for each unit change in IJ coordinates.private static int
INVERT_MASK
private static long
J_MASK
private static int
J_SHIFT
private static int
LOOKUP_BITS
private static int[]
LOOKUP_IJ
private static int
LOOKUP_MASK
private static int[]
LOOKUP_POS
private static com.google.common.base.CharMatcher
MATCHES_ZERO
Matches literal '0' characters.static int
MAX_LEVEL
static int
MAX_SIZE
static long
MAX_UNSIGNED
private static S2CellId
NONE
static int
NUM_FACES
private static long
ORIENTATION_MASK
static int
POS_BITS
private static S2CellId
SENTINEL
private static int
SI_SHIFT
private static int
SWAP_MASK
private static long
TI_MASK
private static long
WRAP_OFFSET
This is the offset required to wrap around from the beginning of the Hilbert curve to the end or vice versa; see nextWrap() and prevWrap().
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description S2CellId
advance(long steps)
This method advances or retreats the indicated number of steps along the Hilbert curve at the current level, and returns the new position.S2CellId
advanceWrap(long steps)
This method advances or retreats the indicated number of steps along the Hilbert curve at the current level, and returns the new position.static S2CellId
begin(int level)
Returns the first cell in an ordered traversal along the Hilbert curve at a given level (across all 6 faces of the cube).S2CellId
child(int position)
Returns the immediate child of this cell at the given traversal order position (in the range 0 to 3).S2CellId
childBegin()
Returns the first child in a traversal of the children of this cell, in Hilbert curve order.S2CellId
childBegin(int level)
Returns the first cell in a traversal of children a given level deeper than this cell, in Hilbert curve order.private static long
childBeginAsLong(long id)
private static long
childBeginAsLong(long id, int level)
S2CellId
childEnd()
Returns the first cell after a traversal of the children of this cell in Hilbert curve order.S2CellId
childEnd(int level)
Returns the first cell after the last child in a traversal of children a given level deeper than this cell, in Hilbert curve order.private static long
childEndAsLong(long id)
private static long
childEndAsLong(long id, int level)
int
childPosition(int level)
Return the child position (0..3) of this cell's ancestor at the given level, relative to its parent.java.lang.Iterable<S2CellId>
children()
java.lang.Iterable<S2CellId>
childrenAtLevel(int level)
int
compareTo(S2CellId that)
boolean
contains(S2CellId other)
Return true if the given cell is contained within this one.static S2CellId
end(int level)
Returns the first cell after an ordered traversal along the Hilbert curve at a given level (across all 6 faces of the cube).boolean
equals(java.lang.Object that)
int
face()
Which cube face this cell belongs to, in the range 0..5.(package private) static S2CellId
fromDebugString(java.lang.String str)
Returns a cell id decoded from a simple debug format.static S2CellId
fromFace(int face)
Returns the cell corresponding to a given S2 cube face.private static long
fromFaceAsLong(int face)
static S2CellId
fromFaceIJ(int face, int i, int j)
Return a leaf cell given its cube face (range 0..5) and i- and j-coordinates (see s2.h).static S2CellId
fromFaceIJSame(int face, int i, int j, boolean sameFace)
Public helper function that calls FromFaceIJ if sameFace is true, or FromFaceIJWrap if sameFace is false.private static S2CellId
fromFaceIJWrap(int face, int i, int j)
Given a face and a point (i,j) where either i or j is outside the valid range [0..MAX_SIZE-1], this function first determines which neighboring face "contains" (i,j), and then returns the leaf cell on that face which is adjacent to the given face and whose distance from (i,j) is minimal.static S2CellId
fromFacePosLevel(int face, long pos, int level)
Returns a cell given its face (range 0..5), Hilbert curve position within that face (an unsigned integer withPOS_BITS
bits), and level (range 0..MAX_LEVEL).private static long
fromFacePosLevelAsLong(int face, long pos, int level)
static S2CellId
fromLatLng(S2LatLng ll)
Return the leaf cell containing the given S2LatLng.static S2CellId
fromPoint(S2Point p)
Return the leaf cell containing the given point (a direction vector, not necessarily unit length).static S2CellId
fromToken(java.lang.String token)
Decodes the cell id from a compact text string suitable for display or indexing.private static S2CellId
fromTokenImpl(java.lang.String token, boolean implicitZeroes)
Returns the cell id for the given token, which will be implicitly zero-right-padded to length 16 if 'implicitZeroes' is true.void
getAllNeighbors(int nbrLevel, java.util.List<S2CellId> output)
Append all neighbors of this cell at the given level to "output".R2Rect
getBoundST()
Returns the bounds of this cell in (s,t)-space.R2Rect
getBoundUV()
Returns the bounds of this cell in (u,v)-space.(package private) long
getCenterSiTi()
Returns the (si, ti) coordinates of the center of the cell.R2Vector
getCenterST()
Returns the center of the cell in (s,t) coordinates.R2Vector
getCenterUV()
Returns the center of the cell in (u,v) coordinates.int
getCommonAncestorLevel(S2CellId other)
Returns the level of the "lowest common ancestor" of this cell and "other".void
getEdgeNeighbors(S2CellId[] neighbors)
Return the four cells that are adjacent across the cell's four edges.int
getI()
Returns the "i" coordinate of this S2 cell ID.(package private) static int
getI(long ijo)
Returns the "i" coordinate from bits 33-63 in the givenijo
primitive long returned bytoIJOrientation()
.int
getJ()
Returns the "j" coordinate of this S2 cell ID.(package private) static int
getJ(long ijo)
Returns the "j" coordinate from bits 2-32 in the givenijo
primitive long returned bytoIJOrientation()
.int
getOrientation()
Returns the orientation of this S2 cell ID.(package private) static int
getOrientation(long ijo)
Returns the orientation from bits 0-1 in the givenijo
primitive long returned bytoIJOrientation()
.(package private) static int
getSi(long center)
Returns the "si" coordinate from bits 32-63 in the givencenter
primitive long returned bygetCenterSiTi()
.int
getSizeIJ()
AsgetSizeIJ(int)
, using the level of this cell.static int
getSizeIJ(int level)
Returns the edge length of cells at the given level in (i,j)-space.double
getSizeST()
AsgetSizeST(int)
, using the level of this cell.static double
getSizeST(int level)
Returns the edge length of cells at the given level in (s,t)-space.(package private) static int
getTi(long center)
Returns the "ti" coordinate from bits 0-31 in the givencenter
primitive long returned bygetCenterSiTi()
.void
getVertexNeighbors(int level, java.util.Collection<S2CellId> output)
Return the neighbors of closest vertex to this cell at the given level, by appending them to "output".boolean
greaterOrEquals(S2CellId x)
boolean
greaterThan(S2CellId x)
int
hashCode()
long
id()
The 64-bit unique identifier for this cell.(package private) static R2Rect
ijLevelToBoundUv(int i, int j, int level)
Returns the bound in (u,v)-space for the cell at the given level containing the leaf cell with the given (i,j)-coordinates.private static void
initLookupCell(int level, int i, int j, int origOrientation, int pos, int orientation)
boolean
intersects(S2CellId other)
Return true if the given cell intersects this one.boolean
isFace()
Return true if this is a top-level face cell (more efficient than checking whether level() == 0).boolean
isLeaf()
Return true if this is a leaf cell (more efficient than checking whether level() == MAX_LEVEL).boolean
isValid()
Return true if id() represents a valid cell.boolean
lessOrEquals(S2CellId x)
boolean
lessThan(S2CellId x)
int
level()
Return the subdivision level of the cell (range 0..MAX_LEVEL).private static int
lookupBits(int i, int j, int k, int bits)
long
lowestOnBit()
Returns the lowest-numbered bit that is on for this cell id, which is equal to1L << (2 * (MAX_LEVEL - level))
.private static long
lowestOnBit(long id)
static long
lowestOnBitForLevel(int level)
Return the lowest-numbered bit that is on for cells at the given level.private static int
maskBits(int bits)
S2CellId
next()
Return the next cell at the same level along the Hilbert curve.S2CellId
nextWrap()
Like next(), but wraps around from the last face to the first and vice versa.static S2CellId
none()
The default constructor returns an invalid cell id.S2CellId
parent()
S2CellId
parent(int level)
Return the cell at the previous level or at the given level (which must be less than or equal to the current level).private static long
parentAsLong(long id)
private static long
parentAsLong(long id, int level)
long
pos()
The position of the cell center along the Hilbert curve over this face, in the range 0..(2**kPosBits-1).S2CellId
prev()
Return the previous cell at the same level along the Hilbert curve.S2CellId
prevWrap()
Like prev(), but wraps around from the last face to the first and vice versa.S2CellId
rangeMax()
Returns the end of the range of cell ids that are contained within this cell (including itself.) The range is *inclusive* (i.e.private static long
rangeMaxAsLong(long id)
S2CellId
rangeMin()
Returns the start of the range of cell ids that are contained within this cell (including itself.) The range is *inclusive* (i.e.private static long
rangeMinAsLong(long id)
static S2CellId
sentinel()
Returns an invalid cell id guaranteed to be larger than any valid cell id.private static void
setAxisRange(int ij, int cellSize, R1Interval interval)
(package private) long
toIJOrientation()
Returns the (i, j) coordinates for the leaf cell corresponding to this cell id, and the orientation the i- and j-axes follow at that level.S2LatLng
toLatLng()
Return the S2LatLng corresponding to the center of the given cell.S2Loop
toLoop(int level)
Returns a loop along the boundary of this cell, with vertices at intersections with the cell grid atlevel
.S2Point
toPoint()
S2Point
toPointRaw()
Return the direction vector corresponding to the center of the given cell.java.lang.String
toString()
java.lang.String
toToken()
Encodes the cell id to compact text strings suitable for display or indexing.java.lang.String
toTokenOld()
static boolean
unsignedLongGreaterOrEquals(long x1, long x2)
Returns true if x1 >= x2, when both values are treated as unsigned.static boolean
unsignedLongGreaterThan(long x1, long x2)
Returns true if x1 > x2, when both values are treated as unsigned.static boolean
unsignedLongLessOrEquals(long x1, long x2)
Returns true if x1 <= x2, when both values are treated as unsigned.static boolean
unsignedLongLessThan(long x1, long x2)
Returns true if x1 < x2, when both values are treated as unsigned.private static long
updateBits(long sb, int k, int bits)
-
-
-
Field Detail
-
FACE_BITS
public static final int FACE_BITS
- See Also:
- Constant Field Values
-
NUM_FACES
public static final int NUM_FACES
- See Also:
- Constant Field Values
-
MAX_LEVEL
public static final int MAX_LEVEL
- See Also:
- Constant Field Values
-
POS_BITS
public static final int POS_BITS
- See Also:
- Constant Field Values
-
MAX_SIZE
public static final int MAX_SIZE
- See Also:
- Constant Field Values
-
IJ_TO_ST
private static final double IJ_TO_ST
The change in ST coordinates for each unit change in IJ coordinates.- See Also:
- Constant Field Values
-
MAX_UNSIGNED
public static final long MAX_UNSIGNED
- See Also:
- Constant Field Values
-
I_SHIFT
private static final int I_SHIFT
- See Also:
- Constant Field Values
-
J_SHIFT
private static final int J_SHIFT
- See Also:
- Constant Field Values
-
J_MASK
private static final long J_MASK
- See Also:
- Constant Field Values
-
ORIENTATION_MASK
private static final long ORIENTATION_MASK
- See Also:
- Constant Field Values
-
SI_SHIFT
private static final int SI_SHIFT
- See Also:
- Constant Field Values
-
TI_MASK
private static final long TI_MASK
- See Also:
- Constant Field Values
-
LOOKUP_BITS
private static final int LOOKUP_BITS
- See Also:
- Constant Field Values
-
SWAP_MASK
private static final int SWAP_MASK
- See Also:
- Constant Field Values
-
INVERT_MASK
private static final int INVERT_MASK
- See Also:
- Constant Field Values
-
LOOKUP_MASK
private static final int LOOKUP_MASK
- See Also:
- Constant Field Values
-
LOOKUP_POS
private static final int[] LOOKUP_POS
-
LOOKUP_IJ
private static final int[] LOOKUP_IJ
-
NONE
private static final S2CellId NONE
-
SENTINEL
private static final S2CellId SENTINEL
-
WRAP_OFFSET
private static final long WRAP_OFFSET
This is the offset required to wrap around from the beginning of the Hilbert curve to the end or vice versa; see nextWrap() and prevWrap().- See Also:
- Constant Field Values
-
FACE_CELLS
public static final S2CellId[] FACE_CELLS
-
id
private final long id
The id of the cell.
-
MATCHES_ZERO
private static final com.google.common.base.CharMatcher MATCHES_ZERO
Matches literal '0' characters.
-
-
Method Detail
-
none
public static S2CellId none()
The default constructor returns an invalid cell id.
-
sentinel
public static S2CellId sentinel()
Returns an invalid cell id guaranteed to be larger than any valid cell id. Useful for creating indexes.
-
fromFace
public static S2CellId fromFace(int face)
Returns the cell corresponding to a given S2 cube face.
-
fromFacePosLevel
public static S2CellId fromFacePosLevel(int face, long pos, int level)
Returns a cell given its face (range 0..5), Hilbert curve position within that face (an unsigned integer withPOS_BITS
bits), and level (range 0..MAX_LEVEL). The given position will be modified to correspond to the Hilbert curve position at the center of the returned cell. This is a static function rather than a constructor in order to indicate what the arguments represent.
-
fromPoint
public static S2CellId fromPoint(S2Point p)
Return the leaf cell containing the given point (a direction vector, not necessarily unit length).
-
fromLatLng
public static S2CellId fromLatLng(S2LatLng ll)
Return the leaf cell containing the given S2LatLng.
-
getCenterUV
public R2Vector getCenterUV()
Returns the center of the cell in (u,v) coordinates. Note that the center of the cell is defined as the point at which it is recursively subdivided into four children; in general, it is not at the midpoint of the (u,v) rectangle covered by the cell.
-
getCenterST
public R2Vector getCenterST()
Returns the center of the cell in (s,t) coordinates.
-
getBoundST
public R2Rect getBoundST()
Returns the bounds of this cell in (s,t)-space.
-
getBoundUV
public R2Rect getBoundUV()
Returns the bounds of this cell in (u,v)-space.
-
toPoint
public S2Point toPoint()
-
toPointRaw
public S2Point toPointRaw()
Return the direction vector corresponding to the center of the given cell. The vector returned by toPointRaw is not necessarily unit length.
-
toLoop
public S2Loop toLoop(int level)
Returns a loop along the boundary of this cell, with vertices at intersections with the cell grid atlevel
. Equivalent to the union of new S2Polygon(new S2Cell(child)), for each child inchildrenAtLevel(int)
for the given level, but radically faster.
-
getCenterSiTi
long getCenterSiTi()
Returns the (si, ti) coordinates of the center of the cell. The returned long packs the values into one long, such that bits 32-63 contain si, and bits 0-31 contain ti.Note that although (si, ti) coordinates span the range [0,2**31] in general, the cell center coordinates are always in the range [1,2**31-1] and therefore can be represented using a signed 32-bit integer.
Use
getSi(long)
andgetTi(long)
to extract integer values for si and ti, respectively.
-
getSi
static int getSi(long center)
Returns the "si" coordinate from bits 32-63 in the givencenter
primitive long returned bygetCenterSiTi()
.
-
getTi
static int getTi(long center)
Returns the "ti" coordinate from bits 0-31 in the givencenter
primitive long returned bygetCenterSiTi()
.
-
toLatLng
public S2LatLng toLatLng()
Return the S2LatLng corresponding to the center of the given cell.
-
id
public long id()
The 64-bit unique identifier for this cell.
-
isValid
public boolean isValid()
Return true if id() represents a valid cell.
-
face
public int face()
Which cube face this cell belongs to, in the range 0..5.
-
pos
public long pos()
The position of the cell center along the Hilbert curve over this face, in the range 0..(2**kPosBits-1).
-
level
public int level()
Return the subdivision level of the cell (range 0..MAX_LEVEL).
-
getSizeIJ
public int getSizeIJ()
AsgetSizeIJ(int)
, using the level of this cell.
-
getSizeST
public double getSizeST()
AsgetSizeST(int)
, using the level of this cell.
-
getSizeIJ
public static int getSizeIJ(int level)
Returns the edge length of cells at the given level in (i,j)-space.
-
getSizeST
public static double getSizeST(int level)
Returns the edge length of cells at the given level in (s,t)-space.
-
isLeaf
public boolean isLeaf()
Return true if this is a leaf cell (more efficient than checking whether level() == MAX_LEVEL).
-
isFace
public boolean isFace()
Return true if this is a top-level face cell (more efficient than checking whether level() == 0).
-
childPosition
public int childPosition(int level)
Return the child position (0..3) of this cell's ancestor at the given level, relative to its parent. The argument should be in the range 1..MAX_LEVEL. For example, childPosition(1) returns the position of this cell's level-1 ancestor within its top-level face cell.
-
rangeMin
public S2CellId rangeMin()
Returns the start of the range of cell ids that are contained within this cell (including itself.) The range is *inclusive* (i.e. test using >= and <=) and the return values of both this method andrangeMax()
are valid leaf cell ids.
-
rangeMax
public S2CellId rangeMax()
Returns the end of the range of cell ids that are contained within this cell (including itself.) The range is *inclusive* (i.e. test using >= and <=) and the return values of both this method andrangeMin()
are valid leaf cell ids.Note that because the range max is inclusive, care should be taken to iterate accordingly, for example:
for (S2CellId min = x.rangeMin(); min.compareTo(x.rangeMax()) <= 0; min = min.next()) {...}
If you need to convert the range to a semi-open interval [min, limit), for example to use a key-value store that only supports semi-open range queries, then do not attempt to define "limit" as rangeMax.next(). The problem is that leaf S2CellIds are 2 units apart, so the semi-open interval [min, limit) includes an additional value (rangeMax.id() + 1) which happens to be a valid S2CellId about one-third of the time and is never contained by this cell. (It always corresponds to a cell ID larger than this ID). You can define "limit" asrangeMax.id() + 1
if necessary; this is not always a valid S2CellId but can still be used with fromToken/toToken. You may also convert rangeMax() to the key space of your key- value store and define "limit" as the next larger key.Note that sentinel().rangeMin(), sentinel.rangeMax(), and sentinel() are all equal.
- See Also:
rangeMin()
,childBegin(int)
,childEnd(int)
,childrenAtLevel(int)
-
contains
public boolean contains(S2CellId other)
Return true if the given cell is contained within this one.
-
intersects
public boolean intersects(S2CellId other)
Return true if the given cell intersects this one.
-
parent
public S2CellId parent()
-
parent
public S2CellId parent(int level)
Return the cell at the previous level or at the given level (which must be less than or equal to the current level).
-
child
public S2CellId child(int position)
Returns the immediate child of this cell at the given traversal order position (in the range 0 to 3). Results are undefined if this is a leaf cell.
-
children
public java.lang.Iterable<S2CellId> children()
-
childrenAtLevel
public java.lang.Iterable<S2CellId> childrenAtLevel(int level)
-
childBegin
public S2CellId childBegin()
Returns the first child in a traversal of the children of this cell, in Hilbert curve order.
-
childBegin
public S2CellId childBegin(int level)
Returns the first cell in a traversal of children a given level deeper than this cell, in Hilbert curve order. Requires that the given level be greater or equal to this cell level.
-
childEnd
public S2CellId childEnd()
Returns the first cell after a traversal of the children of this cell in Hilbert curve order. This cell can be invalid.
-
childEnd
public S2CellId childEnd(int level)
Returns the first cell after the last child in a traversal of children a given level deeper than this cell, in Hilbert curve order. This cell can be invalid.
-
next
public S2CellId next()
Return the next cell at the same level along the Hilbert curve. Works correctly when advancing from one face to the next, but does *not* wrap around from the last face to the first or vice versa.
-
prev
public S2CellId prev()
Return the previous cell at the same level along the Hilbert curve. Works correctly when advancing from one face to the next, but does *not* wrap around from the last face to the first or vice versa.
-
nextWrap
public S2CellId nextWrap()
Like next(), but wraps around from the last face to the first and vice versa. Should *not* be used for iteration in conjunction with childBegin(), childEnd(), Begin(), or End().
-
prevWrap
public S2CellId prevWrap()
Like prev(), but wraps around from the last face to the first and vice versa. Should *not* be used for iteration in conjunction with childBegin(), childEnd(), Begin(), or End().
-
begin
public static S2CellId begin(int level)
Returns the first cell in an ordered traversal along the Hilbert curve at a given level (across all 6 faces of the cube).
-
end
public static S2CellId end(int level)
Returns the first cell after an ordered traversal along the Hilbert curve at a given level (across all 6 faces of the cube). The end value is exclusive, and is not a valid cell id.
-
advance
public S2CellId advance(long steps)
This method advances or retreats the indicated number of steps along the Hilbert curve at the current level, and returns the new position. The position never advances pastend(int)
or beforebegin(int)
, and remains at the current level.
-
advanceWrap
public S2CellId advanceWrap(long steps)
This method advances or retreats the indicated number of steps along the Hilbert curve at the current level, and returns the new position. The position wraps between the first and last faces as necessary. The input must be a valid cell id.
-
getCommonAncestorLevel
public int getCommonAncestorLevel(S2CellId other)
Returns the level of the "lowest common ancestor" of this cell and "other". Note that because of the way that cell levels are numbered, this is actually the *highest* level of any shared ancestor. Returns -1 if the two cells do not have any common ancestor (i.e., they are from different faces).
-
fromToken
public static S2CellId fromToken(java.lang.String token)
Decodes the cell id from a compact text string suitable for display or indexing. Cells at lower levels (i.e. larger cells) are encoded into fewer characters. The maximum token length is 16.- Parameters:
token
- the token to decode- Returns:
- the S2CellId for that token
- Throws:
java.lang.NumberFormatException
- if the token is not formatted correctly
-
fromTokenImpl
private static S2CellId fromTokenImpl(java.lang.String token, boolean implicitZeroes)
Returns the cell id for the given token, which will be implicitly zero-right-padded to length 16 if 'implicitZeroes' is true.
-
toToken
public java.lang.String toToken()
Encodes the cell id to compact text strings suitable for display or indexing. Cells at lower levels (i.e. larger cells) are encoded into fewer characters. The maximum token length is 16.Simple implementation: convert the id to hex and strip trailing zeros. We could use base-32 or base-64, but assuming the cells used for indexing regions are at least 100 meters across (level 16 or less), the savings would be at most 3 bytes (9 bytes hex vs. 6 bytes base-64).
- Returns:
- the encoded cell id
-
toTokenOld
public java.lang.String toTokenOld()
-
getEdgeNeighbors
public void getEdgeNeighbors(S2CellId[] neighbors)
Return the four cells that are adjacent across the cell's four edges. Neighbors are returned in the order defined by S2Cell::GetEdge. All neighbors are guaranteed to be distinct.Requires that this cell is valid.
-
getVertexNeighbors
public void getVertexNeighbors(int level, java.util.Collection<S2CellId> output)
Return the neighbors of closest vertex to this cell at the given level, by appending them to "output". Normally there are four neighbors, but the closest vertex may only have three neighbors if it is one of the 8 cube vertices.Requires that level < this.level(), so that we can determine which vertex is closest (in particular, level == MAX_LEVEL is not allowed). Also requires that this cell is valid.
-
getAllNeighbors
public void getAllNeighbors(int nbrLevel, java.util.List<S2CellId> output)
Append all neighbors of this cell at the given level to "output". Two cells X and Y are neighbors if their boundaries intersect but their interiors do not. In particular, two cells that intersect at a single point are neighbors.Requires that nbrLevel >= this->level(). Note that for cells adjacent to a face vertex, the same neighbor may be appended more than once. Also requires that this cell is valid.
-
fromFaceIJ
public static S2CellId fromFaceIJ(int face, int i, int j)
Return a leaf cell given its cube face (range 0..5) and i- and j-coordinates (see s2.h).
-
lookupBits
private static final int lookupBits(int i, int j, int k, int bits)
-
updateBits
private static final long updateBits(long sb, int k, int bits)
-
maskBits
private static final int maskBits(int bits)
-
toIJOrientation
long toIJOrientation()
Returns the (i, j) coordinates for the leaf cell corresponding to this cell id, and the orientation the i- and j-axes follow at that level. The returned long packs the values into one long, such that bits 33-63 contain i, bits 2-32 contain j, and bits 0-1 contain the orientation.Since cells are represented by the Hilbert curve position at the center of the cell, the returned (i, j) for non-leaf cells will be a leaf cell adjacent to the cell center.
Use
getI(long)
,getJ(long)
, andgetOrientation(long)
to extract integer values for i, j, and orientation, respectively.
-
getI
public int getI()
Returns the "i" coordinate of this S2 cell ID.
-
getI
static int getI(long ijo)
Returns the "i" coordinate from bits 33-63 in the givenijo
primitive long returned bytoIJOrientation()
.
-
getJ
public int getJ()
Returns the "j" coordinate of this S2 cell ID.
-
getJ
static int getJ(long ijo)
Returns the "j" coordinate from bits 2-32 in the givenijo
primitive long returned bytoIJOrientation()
.
-
getOrientation
public int getOrientation()
Returns the orientation of this S2 cell ID.
-
getOrientation
static int getOrientation(long ijo)
Returns the orientation from bits 0-1 in the givenijo
primitive long returned bytoIJOrientation()
.
-
lowestOnBit
public long lowestOnBit()
Returns the lowest-numbered bit that is on for this cell id, which is equal to1L << (2 * (MAX_LEVEL - level))
. So for example, a.lsb() <= b.lsb() if and only if a.level() >= b.level(), but the first test is more efficient.
-
lowestOnBitForLevel
public static long lowestOnBitForLevel(int level)
Return the lowest-numbered bit that is on for cells at the given level.
-
ijLevelToBoundUv
static R2Rect ijLevelToBoundUv(int i, int j, int level)
Returns the bound in (u,v)-space for the cell at the given level containing the leaf cell with the given (i,j)-coordinates.
-
setAxisRange
private static void setAxisRange(int ij, int cellSize, R1Interval interval)
-
fromFaceIJWrap
private static S2CellId fromFaceIJWrap(int face, int i, int j)
Given a face and a point (i,j) where either i or j is outside the valid range [0..MAX_SIZE-1], this function first determines which neighboring face "contains" (i,j), and then returns the leaf cell on that face which is adjacent to the given face and whose distance from (i,j) is minimal.
-
fromFaceIJSame
public static S2CellId fromFaceIJSame(int face, int i, int j, boolean sameFace)
Public helper function that calls FromFaceIJ if sameFace is true, or FromFaceIJWrap if sameFace is false.
-
equals
public boolean equals(java.lang.Object that)
- Overrides:
equals
in classjava.lang.Object
-
unsignedLongLessThan
public static boolean unsignedLongLessThan(long x1, long x2)
Returns true if x1 < x2, when both values are treated as unsigned.
-
unsignedLongLessOrEquals
public static boolean unsignedLongLessOrEquals(long x1, long x2)
Returns true if x1 <= x2, when both values are treated as unsigned.
-
unsignedLongGreaterThan
public static boolean unsignedLongGreaterThan(long x1, long x2)
Returns true if x1 > x2, when both values are treated as unsigned.
-
unsignedLongGreaterOrEquals
public static boolean unsignedLongGreaterOrEquals(long x1, long x2)
Returns true if x1 >= x2, when both values are treated as unsigned.
-
lessThan
public boolean lessThan(S2CellId x)
-
greaterThan
public boolean greaterThan(S2CellId x)
-
lessOrEquals
public boolean lessOrEquals(S2CellId x)
-
greaterOrEquals
public boolean greaterOrEquals(S2CellId x)
-
hashCode
public int hashCode()
- Overrides:
hashCode
in classjava.lang.Object
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
initLookupCell
private static void initLookupCell(int level, int i, int j, int origOrientation, int pos, int orientation)
-
compareTo
public int compareTo(S2CellId that)
- Specified by:
compareTo
in interfacejava.lang.Comparable<S2CellId>
-
fromFaceAsLong
private static long fromFaceAsLong(int face)
-
childBeginAsLong
private static long childBeginAsLong(long id)
-
childBeginAsLong
private static long childBeginAsLong(long id, int level)
-
childEndAsLong
private static long childEndAsLong(long id)
-
childEndAsLong
private static long childEndAsLong(long id, int level)
-
rangeMinAsLong
private static long rangeMinAsLong(long id)
-
rangeMaxAsLong
private static long rangeMaxAsLong(long id)
-
lowestOnBit
private static long lowestOnBit(long id)
-
parentAsLong
private static long parentAsLong(long id)
-
parentAsLong
private static long parentAsLong(long id, int level)
-
fromFacePosLevelAsLong
private static long fromFacePosLevelAsLong(int face, long pos, int level)
-
fromDebugString
static S2CellId fromDebugString(java.lang.String str)
Returns a cell id decoded from a simple debug format. This function is reasonably efficient, but is only intended for use in tests; no promises are made about the durability of the encoding over time.
-
-