Class S2CellUnion

java.lang.Object
com.google.common.geometry.S2CellUnion
All Implemented Interfaces:
S2Region, Serializable, Iterable<S2CellId>

@GwtCompatible(serializable=true) public class S2CellUnion extends Object implements S2Region, Iterable<S2CellId>, Serializable
An S2CellUnion is a region consisting of cells of various sizes. Typically a cell union is used to approximate some other shape. There is a tradeoff between the accuracy of the approximation and how many cells are used. Unlike polygons, cells have a fixed hierarchical structure. This makes them more suitable for optimizations based on preprocessing.

An S2CellUnion is represented as a vector of sorted, non-overlapping S2CellIds. By default the vector is also "normalized", meaning that groups of 4 child cells have been replaced by their parent cell whenever possible. S2CellUnions are not required to be normalized, but certain operations will return different results if they are not, e.g. contains(S2CellUnion).

See Also:
  • Field Details

  • Constructor Details

    • S2CellUnion

      public S2CellUnion()
  • Method Details

    • initFromCellIds

      public void initFromCellIds(ArrayList<S2CellId> cellIds)
      Populates a cell union with the given S2CellIds, and then calls normalize(). This directly uses the input list, without copying it.
    • initFromIds

      public void initFromIds(List<Long> cellIds)
      Populates a cell union with the given 64-bit cell ids, and then calls normalize().
    • initSwap

      public void initSwap(List<S2CellId> cellIds)
      Populates a cell union with the given S2CellIds. The input list is copied, and then cleared.
    • initRawCellIds

      public void initRawCellIds(ArrayList<S2CellId> cellIds)
      Populates a cell union with the given S2CellIds. This does not call normalize, see initRawSwap(java.util.List<com.google.common.geometry.S2CellId>) for details. This directly uses the input list, without copying it.
    • initRawIds

      public void initRawIds(List<Long> cellIds)
      Populates a cell union with the given 64 bit cell ids. This does not call normalize, see initRawSwap(java.util.List<com.google.common.geometry.S2CellId>) for details. The input list is copied.
    • initRawSwap

      public void initRawSwap(List<S2CellId> cellIds)
      Like the initFrom*() constructors, but does not call normalize(). The cell union *must* be normalized before doing any calculations with it, so it is the caller's * responsibility to make sure that the input is normalized. This method is useful when converting cell unions to another representation and back.

      The input list is copied, and then cleared.

    • initFromMinMax

      public void initFromMinMax(S2CellId minId, S2CellId maxId)
      Create a cell union that corresponds to a continuous range of cell ids. The output is a normalized collection of cell ids that covers the leaf cells between "minId" and "maxId" inclusive.

      Requires that minId.isLeaf(), maxId.isLeaf(), and minId invalid input: '<'= maxId.

    • initFromBeginEnd

      public void initFromBeginEnd(S2CellId begin, S2CellId end)
      As initFromMinMax(S2CellId, S2CellId), except that the union covers the range of leaf cells from "begin" (inclusive) to "end" (exclusive.) If begin.equals(end), the result is empty.

      Requires that begin.isLeaf(), end.isLeaf(), and begin invalid input: '<'= end.

    • size

      public int size()
    • cellId

      public S2CellId cellId(int i)
      Convenience methods for accessing the individual cell ids.
    • iterator

      public Iterator<S2CellId> iterator()
      Enable iteration over the union's cells.
      Specified by:
      iterator in interface Iterable<S2CellId>
    • cellIds

      public ArrayList<S2CellId> cellIds()
      Direct access to the underlying vector for iteration .
    • isValid

      public boolean isValid()
      Returns true if the cell union is valid, meaning that the S2CellIds are non-overlapping and sorted in increasing order.
    • isNormalized

      public boolean isNormalized()
      Returns true if the cell union is normalized, meaning that it isValid() is true and that no four cells have a common parent.

      Certain operations such as contains(S2CellUnion) may return a different result if the cell union is not normalized.

    • areSiblings

      private static boolean areSiblings(S2CellId a, S2CellId b, S2CellId c, S2CellId d)
      Returns true if the given four cells have a common parent.

      Requires the four cells are distinct.

    • denormalize

      public void denormalize(int minLevel, int levelMod, ArrayList<S2CellId> output)
      Replaces "output" with an expanded version of the cell union where any cells whose level is less than "min_level" or where (level - min_level) is not a multiple of "level_mod" are replaced by their children, until either both of these conditions are satisfied or the maximum level is reached.

      This method allows a covering generated by S2RegionCoverer using min_level() or level_mod() constraints to be stored as a normalized cell union (which allows various geometric computations to be done) and then converted back to the original list of cell ids that satisfies the desired constraints.

    • pack

      public void pack()
      If there are more than "excess" elements of the cell_ids() vector that are allocated but unused, reallocate the array to eliminate the excess space. This reduces memory usage when many cell unions need to be held in memory at once.
    • contains

      public boolean contains(S2CellId id)
      Return true if the cell union contains the given cell id. Containment is defined with respect to regions, e.g. a cell contains its 4 children. This is a fast operation (logarithmic in the size of the cell union).

      CAVEAT: If you have constructed a valid but non-normalized S2CellUnion, note that groups of 4 child cells are not considered to contain their parent cell. To get this behavior you must construct a normalized cell union, or call normalize() prior to this method.

    • intersects

      public boolean intersects(S2CellId id)
      Return true if the cell union intersects the given cell id. This is a fast operation (logarithmic in the size of the cell union).
    • contains

      public boolean contains(S2CellUnion that)
      Returns true if this cell union contains that.

      CAVEAT: If you have constructed a valid but non-normalized S2CellUnion, note that groups of 4 child cells are not considered to contain their parent cell. To get this behavior you must construct a normalized cell union, or call normalize() prior to this method.

    • contains

      public boolean contains(S2Cell cell)
      This is a fast operation (logarithmic in the size of the cell union).
      Specified by:
      contains in interface S2Region
    • intersects

      public boolean intersects(S2CellUnion union)
      Return true if this cell union intersects union.
    • getUnion

      public void getUnion(S2CellUnion x, S2CellUnion y)
      Sets this cell union to the union of x and y.
    • getIntersection

      public void getIntersection(S2CellUnion x, S2CellId id)
      Specialized version of GetIntersection() that gets the intersection of a cell union with the given cell id. This can be useful for "splitting" a cell union into chunks.

      Note: x and y must be normalized.

    • getIntersection

      public void getIntersection(S2CellUnion x, S2CellUnion y)
      Initializes this cell union to the intersection of the two given cell unions. Requires: x != this and y != this.

      Note: x and y must be normalized.

    • getIntersection

      public static void getIntersection(List<S2CellId> x, List<S2CellId> y, List<S2CellId> results)
      Like #getIntersection(S2CellUnion, S2CellUnion), but works directly with lists of S2CellIds, and this method has slightly more relaxed normalization requirements: the input vectors may contain groups of 4 child cells that all have the same parent. (In a normalized S2CellUnion, such groups are always replaced by the parent cell.)

      Note: x and y must be sorted.

    • getDifference

      public void getDifference(S2CellUnion x, S2CellUnion y)
      Initiaizes this cell union to the difference of the two given cell unions.
    • getDifferenceInternal

      private void getDifferenceInternal(S2CellId cell, S2CellUnion y)
    • indexedBinarySearch

      private static int indexedBinarySearch(List<S2CellId> l, S2CellId key, int low)
      Just as normal binary search, except that it allows specifying the starting value for the lower bound.
      Returns:
      The position of the searched element in the list (if found), or the position where the element could be inserted without violating the order.
    • expand

      public void expand(int level)
      Expands the cell union such that it contains all cells of the given level that are adjacent to any cell of the original union. Two cells are defined as adjacent if their boundaries have any points in common, i.e. most cells have 8 adjacent cells (not counting the cell itself).

      Note that the size of the output is exponential in "level". For example, if level == 20 and the input has a cell at level 10, there will be on the order of 4000 adjacent cells in the output. For most applications the Expand(min_fraction, min_distance) method below is easier to use.

    • expand

      public void expand(S1Angle minRadius, int maxLevelDiff)
      Expand the cell union such that it contains all points whose distance to the cell union is at most minRadius, but do not use cells that are more than maxLevelDiff levels higher than the largest cell in the input. The second parameter controls the tradeoff between accuracy and output size when a large region is being expanded by a small amount (e.g. expanding Canada by 1km).

      For example, if maxLevelDiff == 4, the region will always be expanded by approximately 1/16 the width of its largest cell. Note that in the worst case, the number of cells in the output can be up to 4 * (1 + 2 ** maxLevelDiff) times larger than the number of cells in the input.

    • clone

      public S2Region clone()
      Overrides:
      clone in class Object
    • getCapBound

      public S2Cap getCapBound()
      Description copied from interface: S2Region
      Return a bounding spherical cap.
      Specified by:
      getCapBound in interface S2Region
    • getRectBound

      public S2LatLngRect getRectBound()
      Description copied from interface: S2Region
      Return a bounding latitude-longitude rectangle.
      Specified by:
      getRectBound in interface S2Region
    • mayIntersect

      public boolean mayIntersect(S2Cell cell)
      This is a fast operation (logarithmic in the size of the cell union).
      Specified by:
      mayIntersect in interface S2Region
    • contains

      public boolean contains(S2Point p)
      The point 'p' does not need to be normalized. This is a fast operation (logarithmic in the size of the cell union).
      Specified by:
      contains in interface S2Region
    • leafCellsCovered

      public long leafCellsCovered()
      The number of leaf cells covered by the union. This will be no more than 6*2^60 for the whole sphere.
      Returns:
      the number of leaf cells covered by the union
    • averageBasedArea

      public double averageBasedArea()
      Approximate this cell union's area by summing the average area of each contained cell's average area, using S2Cell.averageArea(). This is equivalent to the number of leaves covered, multiplied by the average area of a leaf.

      Note that S2Cell.averageArea() does not take into account distortion of cell, and thus may be off by up to a factor of 1.7. NOTE: Since this is proportional to LeafCellsCovered(), it is always better to use the other function if all you care about is the relative average area between objects.

      Returns:
      the sum of the average area of each contained cell's average area
    • approxArea

      public double approxArea()
      Calculates this cell union's area by summing the approximate area for each contained cell, using S2Cell.approxArea().
      Returns:
      approximate area of the cell union
    • exactArea

      public double exactArea()
      Calculates this cell union's area by summing the exact area for each contained cell, using the S2Cell.exactArea().
      Returns:
      the exact area of the cell union
    • equals

      public boolean equals(Object that)
      Return true if two cell unions are identical.
      Overrides:
      equals in class Object
    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object
    • normalize

      public boolean normalize()
      Normalizes the cell union by discarding cells that are contained by other cells, replacing groups of 4 child cells by their parent cell whenever possible, and sorting all the cell ids in increasing order. Returns true if the number of cells was reduced.

      This method *must* be called before doing any calculations on the cell union, such as Intersects() or Contains().

      Returns:
      true if the normalize operation had any effect on the cell union, false if the union was already normalized
    • normalize

      public static boolean normalize(List<S2CellId> ids)
      Like normalize(), but works directly with a vector of S2CellIds.
    • encode

      public void encode(OutputStream output) throws IOException
      Writes a simple lossless encoding of this cell union to the given output stream. This encoding uses 1 byte for a version number, and N+1 64-bit longs where the first is the number of longs that follow.
      Throws:
      IOException - there is a problem writing to the underlying stream
    • encode

      public void encode(LittleEndianOutput output) throws IOException
      As encode(OutputStream), but avoids creating a little endian output helper.

      Use this method if a number of S2 objects will be encoded to the same underlying stream.

      Throws:
      IOException
    • decode

      public static S2CellUnion decode(InputStream input) throws IOException
      Decodes an S2CellUnion encoded with Encode(). Returns true on success.
      Throws:
      IOException - there is a problem reading from the underlying stream, the version number doesn't match, or the number of elements to read is not between 0 and 2^31-1.
    • decode

      public static S2CellUnion decode(LittleEndianInput input) throws IOException
      As decode(InputStream), but avoids creating a little endian input helper.

      Use this method if a number of S2 objects will be decoded from the same underlying stream.

      Throws:
      IOException