Class S2CellUnion

  • All Implemented Interfaces:
    S2Region, java.io.Serializable, java.lang.Iterable<S2CellId>

    @GwtCompatible(serializable=true)
    public class S2CellUnion
    extends java.lang.Object
    implements S2Region, java.lang.Iterable<S2CellId>, java.io.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:
    Serialized Form
    • Constructor Summary

      Constructors 
      Constructor Description
      S2CellUnion()  
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      double approxArea()
      Calculates this cell union's area by summing the approximate area for each contained cell, using S2Cell.approxArea().
      private static boolean areSiblings​(S2CellId a, S2CellId b, S2CellId c, S2CellId d)
      Returns true if the given four cells have a common parent.
      double averageBasedArea()
      Approximate this cell union's area by summing the average area of each contained cell's average area, using S2Cell.averageArea().
      S2CellId cellId​(int i)
      Convenience methods for accessing the individual cell ids.
      java.util.ArrayList<S2CellId> cellIds()
      Direct access to the underlying vector for iteration .
      S2Region clone()  
      boolean contains​(S2Cell cell)
      This is a fast operation (logarithmic in the size of the cell union).
      boolean contains​(S2CellId id)
      Return true if the cell union contains the given cell id.
      boolean contains​(S2CellUnion that)
      Returns true if this cell union contains that.
      boolean contains​(S2Point p)
      The point 'p' does not need to be normalized.
      static S2CellUnion decode​(LittleEndianInput input)
      As decode(InputStream), but avoids creating a little endian input helper.
      static S2CellUnion decode​(java.io.InputStream input)
      Decodes an S2CellUnion encoded with Encode().
      void denormalize​(int minLevel, int levelMod, java.util.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.
      void encode​(LittleEndianOutput output)
      As encode(OutputStream), but avoids creating a little endian output helper.
      void encode​(java.io.OutputStream output)
      Writes a simple lossless encoding of this cell union to the given output stream.
      boolean equals​(java.lang.Object that)
      Return true if two cell unions are identical.
      double exactArea()
      Calculates this cell union's area by summing the exact area for each contained cell, using the S2Cell.exactArea().
      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.
      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.
      S2Cap getCapBound()
      Return a bounding spherical cap.
      void getDifference​(S2CellUnion x, S2CellUnion y)
      Initiaizes this cell union to the difference of the two given cell unions.
      private void getDifferenceInternal​(S2CellId cell, S2CellUnion y)  
      void getIntersection​(S2CellUnion x, S2CellId id)
      Specialized version of GetIntersection() that gets the intersection of a cell union with the given cell id.
      void getIntersection​(S2CellUnion x, S2CellUnion y)
      Initializes this cell union to the intersection of the two given cell unions.
      static void getIntersection​(java.util.List<S2CellId> x, java.util.List<S2CellId> y, java.util.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.
      S2LatLngRect getRectBound()
      Return a bounding latitude-longitude rectangle.
      void getUnion​(S2CellUnion x, S2CellUnion y)
      Sets this cell union to the union of x and y.
      int hashCode()  
      private static int indexedBinarySearch​(java.util.List<S2CellId> l, S2CellId key, int low)
      Just as normal binary search, except that it allows specifying the starting value for the lower bound.
      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.
      void initFromCellIds​(java.util.ArrayList<S2CellId> cellIds)
      Populates a cell union with the given S2CellIds, and then calls normalize().
      void initFromIds​(java.util.List<java.lang.Long> cellIds)
      Populates a cell union with the given 64-bit cell ids, and then calls normalize().
      void initFromMinMax​(S2CellId minId, S2CellId maxId)
      Create a cell union that corresponds to a continuous range of cell ids.
      void initRawCellIds​(java.util.ArrayList<S2CellId> cellIds)
      Populates a cell union with the given S2CellIds.
      void initRawIds​(java.util.List<java.lang.Long> cellIds)
      Populates a cell union with the given 64 bit cell ids.
      void initRawSwap​(java.util.List<S2CellId> cellIds)
      Like the initFrom*() constructors, but does not call normalize().
      void initSwap​(java.util.List<S2CellId> cellIds)
      Populates a cell union with the given S2CellIds.
      boolean intersects​(S2CellId id)
      Return true if the cell union intersects the given cell id.
      boolean intersects​(S2CellUnion union)
      Return true if this cell union intersects union.
      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.
      boolean isValid()
      Returns true if the cell union is valid, meaning that the S2CellIds are non-overlapping and sorted in increasing order.
      java.util.Iterator<S2CellId> iterator()
      Enable iteration over the union's cells.
      long leafCellsCovered()
      The number of leaf cells covered by the union.
      boolean mayIntersect​(S2Cell cell)
      This is a fast operation (logarithmic in the size of the cell union).
      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.
      static boolean normalize​(java.util.List<S2CellId> ids)
      Like normalize(), but works directly with a vector of S2CellIds.
      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.
      int size()  
      • Methods inherited from class java.lang.Object

        finalize, getClass, notify, notifyAll, toString, wait, wait, wait
      • Methods inherited from interface java.lang.Iterable

        forEach, spliterator
    • Field Detail

      • LOSSLESS_ENCODING_VERSION

        private static final byte LOSSLESS_ENCODING_VERSION
        See Also:
        Constant Field Values
      • cellIds

        private java.util.ArrayList<S2CellId> cellIds
        The CellIds that form the Union
    • Constructor Detail

      • S2CellUnion

        public S2CellUnion()
    • Method Detail

      • initFromCellIds

        public void initFromCellIds​(java.util.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​(java.util.List<java.lang.Long> cellIds)
        Populates a cell union with the given 64-bit cell ids, and then calls normalize().
      • initSwap

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

        public void initRawSwap​(java.util.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 <= 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 <= end.

      • size

        public int size()
      • cellId

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

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

        public java.util.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,
                                java.util.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​(java.util.List<S2CellId> x,
                                           java.util.List<S2CellId> y,
                                           java.util.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​(java.util.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 java.lang.Object
      • getCapBound

        public S2Cap getCapBound()
        Description copied from interface: S2Region
        Return a bounding spherical cap.
        Specified by:
        getCapBound 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​(java.lang.Object that)
        Return true if two cell unions are identical.
        Overrides:
        equals in class java.lang.Object
      • hashCode

        public int hashCode()
        Overrides:
        hashCode in class java.lang.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​(java.util.List<S2CellId> ids)
        Like normalize(), but works directly with a vector of S2CellIds.
      • encode

        public void encode​(java.io.OutputStream output)
                    throws java.io.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:
        java.io.IOException - there is a problem writing to the underlying stream
      • encode

        public void encode​(LittleEndianOutput output)
                    throws java.io.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:
        java.io.IOException
      • decode

        public static S2CellUnion decode​(java.io.InputStream input)
                                  throws java.io.IOException
        Decodes an S2CellUnion encoded with Encode(). Returns true on success.
        Throws:
        java.io.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 java.io.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:
        java.io.IOException