Class S2CellIndex
- java.lang.Object
-
- com.google.common.geometry.S2CellIndex
-
@GwtCompatible public class S2CellIndex extends java.lang.Object
A collection of (cellId, label) pairs. The S2CellIds may be overlapping or contain duplicate values. For example, an S2CellIndex could store a collection of S2CellUnions, where each S2CellUnion has its own label. Labels are 32-bit non-negative integers, and are typically used to map the results of queries back to client data structures.To build an S2CellIndex, call add() for each (cellId, label) pair, and then call the build() method. There is also a convenience method to associate a label with each cell in a union.
Note that the index is not dynamic; the contents of the index cannot be changed once it has been built. However, the same memory space can be reused by
clearing
the index.There are several options for retrieving data from the index. The simplest is to use a built-in method such as getIntersectingLabels, which returns the labels of all cells that intersect a given target S2CellUnion. Alternatively, you can access the index contents directly.
Internally, the index consists of a set of non-overlapping leaf cell ranges that subdivide the sphere and such that each range intersects a particular set of (cellId, label) pairs. Data is accessed using the following iterator types:
S2CellIndex.RangeIterator
: used to seek and iterate over the non-overlapping leaf cell ranges.S2CellIndex.NonEmptyRangeIterator
: like RangeIterator, but skips ranges whose contents are empty.S2CellIndex.ContentsIterator
: iterates over the (cellId, label) pairs that intersect a given range.S2CellIndex.CellIterator
: iterates over the entire set of (cellId, label) pairs.
Note that these are low-level, efficient types intended mainly for implementing new query classes. Most clients should use either the built-in methods such as
visitIntersectingCells(com.google.common.geometry.S2CellUnion, com.google.common.geometry.S2CellIndex.CellVisitor)
andgetIntersectingLabels(com.google.common.geometry.S2CellUnion)
.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description class
S2CellIndex.CellIterator
An iterator over all (cellId, label) pairs in an unspecified order.private static class
S2CellIndex.CellNode
Represents a node in the (cellId, label) tree.static interface
S2CellIndex.CellVisitor
A function that is called with each (cellId, label) pair to be visited.class
S2CellIndex.ContentsIterator
An iterator that visits the (cellId, label) pairs that cover a set of leaf cell ranges (see RangeIterator).private static class
S2CellIndex.Delta
To build the cell tree and leaf cell ranges, we maintain a stack of (cellId, label) pairs that contain the current leaf cell.static class
S2CellIndex.Labels
A set of labels that can be grown bygetIntersectingLabels(S2CellUnion, Labels)
and shrunk viaS2CellIndex.Labels.clear()
orS2CellIndex.Labels.normalize()
.class
S2CellIndex.NonEmptyRangeIterator
AsS2CellIndex.RangeIterator
but only visits range nodes that overlap (cellId, label) pairs.class
S2CellIndex.RangeIterator
An iterator that seeks and iterates over a set of non-overlapping leaf cell ranges that cover the entire sphere.private static class
S2CellIndex.RangeNode
A range of leaf S2CellIds, from the level 30 leaf cell of this range to the next range.
-
Field Summary
Fields Modifier and Type Field Description private java.util.List<S2CellIndex.CellNode>
cellNodes
A tree of (cellId, label) pairs such that if X is an ancestor of Y, then X.cellId contains Y.cellId.private java.util.ArrayList<S2CellIndex.RangeNode>
rangeNodes
The last element of nodes is a sentinel value, which is necessary in order to represent the range covered by the previous element.
-
Constructor Summary
Constructors Constructor Description S2CellIndex()
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
add(S2CellId cellId, int label)
Adds the given (cellId, label) pair to the index.void
add(java.lang.Iterable<S2CellId> cellIds, int label)
Convenience function that adds a collection of cells with the same label.void
build()
Builds the index.S2CellIndex.CellIterator
cells()
Returns an iterator over the cells of this index.void
clear()
Clears the index so that it can be re-used.S2CellIndex.ContentsIterator
contents()
Returns an iterator over the contents of this index.S2CellIndex.Labels
getIntersectingLabels(S2CellUnion target)
Returns the distinct sorted labels that intersect the given target.void
getIntersectingLabels(S2CellUnion target, S2CellIndex.Labels results)
Appends labels intersecting 'target', in unspecified order, with possible duplicates.S2CellIndex.NonEmptyRangeIterator
nonEmptyRanges()
Returns an iterator over the non-empty ranges of this index.int
numCells()
Returns the number of (cellId, label) pairs in the index.S2CellIndex.RangeIterator
ranges()
Returns an iterator over the ranges of this index.boolean
visitIntersectingCells(S2CellUnion target, S2CellIndex.CellVisitor visitor)
Visits all (cellId, label) pairs in the given index that intersect the given S2CellUnion "target" and returns true, or terminates early and returns false ifS2CellIndex.CellVisitor.visit(com.google.common.geometry.S2CellId, int)
ever returns false.
-
-
-
Field Detail
-
cellNodes
private final java.util.List<S2CellIndex.CellNode> cellNodes
A tree of (cellId, label) pairs such that if X is an ancestor of Y, then X.cellId contains Y.cellId. The contents of a given range of leaf cells can be represented by pointing to a node of this tree.
-
rangeNodes
private final java.util.ArrayList<S2CellIndex.RangeNode> rangeNodes
The last element of nodes is a sentinel value, which is necessary in order to represent the range covered by the previous element.
-
-
Method Detail
-
numCells
public int numCells()
Returns the number of (cellId, label) pairs in the index.
-
add
public void add(S2CellId cellId, int label)
Adds the given (cellId, label) pair to the index. Note that the index is not valid untilbuild()
is called.The S2CellIds in the index may overlap (including duplicate values). Duplicate (cellId, label) pairs are also allowed, although query tools often remove duplicates.
Results are undefined unless all cells are
valid
.
-
add
public void add(java.lang.Iterable<S2CellId> cellIds, int label)
Convenience function that adds a collection of cells with the same label.
-
build
public void build()
Builds the index. This method may only be called once. No iterators may be used until the index is built.
-
cells
public S2CellIndex.CellIterator cells()
Returns an iterator over the cells of this index.
-
ranges
public S2CellIndex.RangeIterator ranges()
Returns an iterator over the ranges of this index.
-
nonEmptyRanges
public S2CellIndex.NonEmptyRangeIterator nonEmptyRanges()
Returns an iterator over the non-empty ranges of this index.
-
contents
public S2CellIndex.ContentsIterator contents()
Returns an iterator over the contents of this index.
-
clear
public void clear()
Clears the index so that it can be re-used.
-
visitIntersectingCells
public boolean visitIntersectingCells(S2CellUnion target, S2CellIndex.CellVisitor visitor)
Visits all (cellId, label) pairs in the given index that intersect the given S2CellUnion "target" and returns true, or terminates early and returns false ifS2CellIndex.CellVisitor.visit(com.google.common.geometry.S2CellId, int)
ever returns false.Each (cellId, label) pair in the index is visited at most once. If the index contains duplicates, then each copy is visited.
-
getIntersectingLabels
public S2CellIndex.Labels getIntersectingLabels(S2CellUnion target)
Returns the distinct sorted labels that intersect the given target.
-
getIntersectingLabels
public void getIntersectingLabels(S2CellUnion target, S2CellIndex.Labels results)
Appends labels intersecting 'target', in unspecified order, with possible duplicates.
-
-