Class S2CellIndex

java.lang.Object
com.google.common.geometry.S2CellIndex

@GwtCompatible public class S2CellIndex extends 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:

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) and getIntersectingLabels(com.google.common.geometry.S2CellUnion).

  • Field Details

    • cellNodes

      private final 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 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 Details

    • S2CellIndex

      public S2CellIndex()
  • Method Details

    • 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 until build() 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(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 if S2CellIndex.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.