Struct S2CellId

An S2CellId is a 64-bit unsigned integer that uniquely identifies a cell in the S2 cell decomposition.

struct S2CellId ;

It has the following format:

id = [face][face_pos]

Constructors

NameDescription
this (id) Construct a cell from a raw numerical S2 Cell ID.
this (p) Construct a leaf cell containing the given point "p". Usually there is is exactly one such cell, but for points along the edge of a cell, any adjacent cell may be (deterministically) chosen. This is because S2CellIds are considered to be closed sets. The returned cell will always contain the given point, i.e.
this (ll) Constructs a cell from a latitude-longitude coordinate.

Properties

NameTypeDescription
id[get] ulongThe 64-bit unique identifier for this cell.

Methods

NameDescription
advance (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 is never advanced past End() or before Begin().
advanceWrap (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.
appendAllNeighbors (nbr_level, 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. Note that for cells adjacent to a face vertex, the same neighbor may be appended more than once.
appendVertexNeighbors (level, output) Returns 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.
begin (level) Iterator-style methods for traversing all the cells along the Hilbert curve at a given level (across all 6 faces of the cube). Note that the end value is exclusive (just like standard STL iterators), and is not a valid cell id.
child (position) Returns the immediate child of this cell at the given traversal order position (in the range 0 to 3). This cell must not be a leaf cell.
childBegin () Iterator-style methods for traversing the immediate children of a cell or all of the children at a given level (greater than or equal to the current level). Note that the end value is exclusive, just like standard STL iterators, and may not even be a valid cell id. You should iterate using code like this:
childPosition () Return the child position (0..3) of this cell within its parent.
childPosition (level) Return the child position (0..3) of this cell's ancestor at the given level within its parent. For example, child_position(1) returns the position of this cell's level-1 ancestor within its top-level face cell.
contains (other) Returns true if the given cell is contained within this one.
decode (decoder) Decodes an S2CellId encoded by Encode(). Returns true on success.
distanceFromBegin () Returns the number of steps that this cell is from Begin(level()). The return value is always non-negative.
encode (encoder) Use encoder to generate a serialized representation of this cell id. Can also encode an invalid cell.
expandedByDistanceUV (uv, distance) Expands a rectangle in (u,v)-space so that it contains all points within the given distance of the boundary, and return the smallest such rectangle. If the distance is negative, then instead shrink this rectangle so that it excludes all points within the given absolute distance of the boundary.
face () Which cube face this cell belongs to, in the range 0..5.
fromDebugString (str) Converts a string in the format returned by ToString() to an S2CellId. Returns S2CellId::None() if the string could not be parsed.
fromFace (face) Return the cell corresponding to a given S2 cube face.
fromFaceIJ (face, i, j) Returns a leaf cell given its cube face (range 0..5) and i- and j-coordinates (see s2coords.h).
fromFacePosLevel (face, pos, level) Returns a cell given its face \(range 0..5\), Hilbert curve position within that face \(an unsigned integer with S2CellId::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.
getBoundST () Returns the bounds of this cell in (s,t)-space.
getBoundUV () Returns the bounds of this cell in (u,v)-space.
getCenterSiTi (psi, pti) Returns the (face, si, ti) coordinates of the center of the cell. 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.
getCenterST () Returns the center of the cell in (s,t) coordinates (see s2coords.d).
getCenterUV () Returns the center of the cell in (u,v) coordinates (see s2coords.h). 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.
getCommonAncestorLevel (other) Returns the level of the lowest common ancestor of this cell and "other", that is, the maximum level such that parent(level) == other.parent(level). Returns -1 if the two cells do not have any common ancestor (i.e., they are from different faces).
getEdgeNeighbors (neighbors) Returns 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.
getSizeIJ () Returns the edge length of this cell in (i,j)-space.
getSizeIJ (level) Like getSizeIJ(), but returns the size of cells at the given level.
getSizeST () Returns the edge length of this cell in (s,t)-space.
getSizeST (level) Returns the edge length in (s,t)-space of cells at the given level.
IJLevelToBoundUV (ij, 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.
intersects (other) Returns true if the given cell intersects this one.
isFace () Return true if this is a top-level face cell (more efficient than checking whether level() == 0).
isLeaf () Returns true if this is a leaf cell (more efficient than checking whether level() == MAX_LEVEL).
isValid () Returns true if id() represents a valid cell.
level () Returns the subdivision level of the cell (range 0..MAX_LEVEL).
lsb () Returns the lowest-numbered bit that is on for this cell id, which is equal to (uint64(1) << (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.
lsbForLevel (level) Returns the lowest-numbered bit that is on for cells at the given level.
maximumTile (limit) Returns the largest cell with the same range_min() and such that range_max() < limit.range_min().
next () Returns the next/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 () Like next() and prev(), but these methods wrap around from the last face to the first and vice versa. They should *not* be used for iteration in conjunction with child_begin(), child_end(), Begin(), or End(). The input must be a valid cell id.
none () Returns an representative empty cell smaller than any valid cell..
opCmp (v) Supports <, <=, >, and >= operators.
opEquals (v) Supports the == and != operators.
parent () Returns the cell at the previous level or at the given level (which must be less than or equal to the current level).
pos () The position of the cell center along the Hilbert curve over this face, in the range 0..(2**POS_BITS-1).
rangeMin () These methods return the range of cell ids that are contained within this cell \(including itself\).
sentinel () Returns an invalid cell id guaranteed to be larger than any valid cell id. Useful for creating indexes.
toFaceIJOrientation (pi, pj) Return the (face, i, j) coordinates for the leaf cell corresponding to this cell id. 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. If "orientation" is non-nullptr, also return the Hilbert curve orientation for the current cell.
toHash () The ID serves as a good hash for associative arrays.
toLatLng () Returns the S2LatLng corresponding to the center of the given cell.
toS2Point () Returns the direction vector corresponding to the center of the given cell. The vector returned by ToPointRaw is not necessarily unit length. This method returns the same result as S2Cell.getCenter().
toString () Creates a human readable debug string. Used for << and available for direct usage as well. The format is "f/dd..d" where "f" is a digit in the range [0-5] representing the S2CellId face, and "dd..d" is a string of digits in the range [0-3] representing each child's position with respect to its parent. (Note that the latter string may be empty.)
toToken () Methods to encode and decode cell ids 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.

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.

This class is intended to be copied by value as desired. It uses the default copy constructor and assignment operator.