Class S2CellId

java.lang.Object

com.google.common.geometry.S2CellId

All Implemented Interfaces:

Serializable, Comparable<S2CellId>

@Immutable
@GwtCompatible(emulated=true,
               serializable=true)
public final class S2CellId
extends Object
implements Comparable<S2CellId>, 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 final int	FACE_BITS
static final S2CellId[]	FACE_CELLS
static final int	MAX_LEVEL
static final int	MAX_SIZE
static final long	MAX_UNSIGNED
static final int	NUM_FACES
static final int	POS_BITS

Constructor Summary

Constructors

Constructor	Description
S2CellId()
S2CellId(long id)

Method Summary

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.
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.
int	childPosition(int level)	Return the child position (0..3) of this cell's ancestor at the given level, relative to its parent.
Iterable<S2CellId>	children()
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(Object that)
int	face()	Which cube face this cell belongs to, in the range 0..5.
static S2CellId	fromFace(int face)	Returns the cell corresponding to a given S2 cube 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.
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 with POS_BITS bits), and level (range 0..MAX_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(String token)	Decodes the cell id from a compact text string suitable for display or indexing.
void	getAllNeighbors(int nbrLevel, 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.
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.
int	getJ()	Returns the "j" coordinate of this S2 cell ID.
int	getOrientation()	Returns the orientation of this S2 cell ID.
int	getSizeIJ()	As getSizeIJ(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()	As getSizeST(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.
void	getVertexNeighbors(int level, 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.
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).
long	lowestOnBit()	Returns the lowest-numbered bit that is on for this cell id, which is equal to 1L << (2 * (MAX_LEVEL - level)).
static long	lowestOnBitForLevel(int level)	Return the lowest-numbered bit that is on for cells at the given level.
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).
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.)
S2CellId	rangeMin()	Returns the start of the range of cell ids that are contained within this cell (including itself.)
static S2CellId	sentinel()	Returns an invalid cell id guaranteed to be larger than any valid cell id.
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 at level.
S2Point	toPoint()
S2Point	toPointRaw()	Return the direction vector corresponding to the center of the given cell.
String	toString()
String	toToken()	Encodes the cell id to compact text strings suitable for display or indexing.
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 invalid input: '<'= x2, when both values are treated as unsigned.
static boolean	unsignedLongLessThan(long x1, long x2)	Returns true if x1 invalid input: '<' x2, when both values are treated as unsigned.

Methods inherited from class Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Details

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

MAX_UNSIGNED

public static final long MAX_UNSIGNED

See Also:

• Constant Field Values

FACE_CELLS

public static final S2CellId[] FACE_CELLS

Constructor Details

S2CellId

public S2CellId(long id)

S2CellId

public S2CellId()

Method Details

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 with POS_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 at level. Equivalent to the union of new S2Polygon(new S2Cell(child)), for each child in childrenAtLevel(int) for the given level, but radically faster.

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()

As getSizeIJ(int), using the level of this cell.

getSizeST

public double getSizeST()

As getSizeST(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 invalid input: '<'=) and the return values of both this method and rangeMax() 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 invalid input: '<'=) and the return values of both this method and rangeMin() 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()) invalid input: '<'= 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" as rangeMax.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 Iterable<S2CellId> children()

childrenAtLevel

public 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 past end(int) or before begin(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(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:

NumberFormatException - if the token is not formatted correctly

toToken

public 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 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,
 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 invalid input: '<' 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,
 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).

getI

public int getI()

Returns the "i" coordinate of this S2 cell ID.

getJ

public int getJ()

Returns the "j" coordinate of this S2 cell ID.

getOrientation

public int getOrientation()

Returns the orientation of this S2 cell ID.

lowestOnBit

public long lowestOnBit()

Returns the lowest-numbered bit that is on for this cell id, which is equal to 1L << (2 * (MAX_LEVEL - level)). So for example, a.lsb() invalid input: '<'= 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.

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(Object that)

Overrides:

equals in class Object

unsignedLongLessThan

public static boolean unsignedLongLessThan(long x1,
 long x2)

Returns true if x1 invalid input: '<' x2, when both values are treated as unsigned.

unsignedLongLessOrEquals

public static boolean unsignedLongLessOrEquals(long x1,
 long x2)

Returns true if x1 invalid input: '<'= 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 class Object

toString

public String toString()

Overrides:

toString in class Object

compareTo

public int compareTo(S2CellId that)

Specified by:

compareTo in interface Comparable<S2CellId>