Class S2RegionCoverer

java.lang.Object
com.google.common.geometry.S2RegionCoverer
All Implemented Interfaces:
Serializable

@GwtCompatible(serializable=true) public final class S2RegionCoverer extends Object implements Serializable
An S2RegionCoverer is a class that allows arbitrary regions to be approximated as unions of cells (S2CellUnion). This is useful for implementing various sorts of search and precomputation operations.

Typical usage: S2RegionCoverer coverer = S2RegionCoverer.builder().setMaxCells(5).build(); S2Cap cap = S2Cap.fromAxisAngle(...); S2CellUnion covering; coverer.getCovering(cap, covering);

This yields a cell union of at most 5 cells that is guaranteed to cover the given cap (a disc-shaped region on the sphere).

The approximation algorithm is not optimal but does a pretty good job in practice. The output does not always use the maximum number of cells allowed, both because this would not always yield a better approximation, and because maxCells() is a limit on how much work is done exploring the possible covering as well as a limit on the final output size.

One can also generate interior coverings, which are sets of cells which are entirely contained within a region. Interior coverings can be empty, even for non-empty regions, if there are no cells that satisfy the provided constraints and are contained by the region. Note that for performance reasons, it is wise to specify a maxLevel when computing interior coverings - otherwise for regions with small or zero area, the algorithm may spend a lot of time subdividing cells all the way to leaf level to try to find contained cells.

See Also:
  • Field Details

    • DEFAULT

      public static final S2RegionCoverer DEFAULT
      A S2RegionCoverer configured with the default options. The min level, max level, and level mod are unrestricted, and maxCells is S2RegionCoverer.Builder.DEFAULT_MAX_CELLS. See S2RegionCoverer.Builder for details.
    • FACE_CELLS

      private static final List<S2Cell> FACE_CELLS
    • minLevel

      private final int minLevel
    • maxLevel

      private final int maxLevel
    • levelMod

      private final int levelMod
    • maxCells

      private final int maxCells
  • Constructor Details

  • Method Details

    • builder

      public static S2RegionCoverer.Builder builder()
      Returns a new Builder with default values, which can be used to construct an S2RegionCoverer instance.
    • equals

      public boolean equals(Object obj)
      Overrides:
      equals in class Object
    • hashCode

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

      public int minLevel()
    • maxLevel

      public int maxLevel()
    • maxCells

      public int maxCells()
    • levelMod

      public int levelMod()
    • getCovering

      public void getCovering(S2Region region, ArrayList<S2CellId> covering)
      Computes a list of cell ids that covers the given region and satisfies the various restrictions specified above.
      Parameters:
      region - The region to cover
      covering - The list filled in by this method
    • getInteriorCovering

      public void getInteriorCovering(S2Region region, ArrayList<S2CellId> interior)
      Computes a list of cell ids that is contained within the given region and satisfies the various restrictions specified above; note that if the max cell level is not specified very carefully this method can try to create an enormous number of cells, wasting a lot of time and memory, so care should be taken to set a max level suitable for the scale of the region being covered.
      Parameters:
      region - The region to fill
      interior - The list filled in by this method
    • getCovering

      public S2CellUnion getCovering(S2Region region)
      Return a normalized cell union that covers the given region and satisfies the restrictions *EXCEPT* for minLevel() and levelMod(). These criteria cannot be satisfied using a cell union because cell unions are automatically normalized by replacing four child cells with their parent whenever possible. (Note that the list of cell ids passed to the cell union constructor does in fact satisfy all the given restrictions.)
    • getCovering

      public void getCovering(S2Region region, S2CellUnion covering)
    • getInteriorCovering

      public S2CellUnion getInteriorCovering(S2Region region)
      Return a normalized cell union that is contained within the given region and satisfies the restrictions *EXCEPT* for minLevel() and levelMod().
    • getInteriorCovering

      public void getInteriorCovering(S2Region region, S2CellUnion covering)
    • getSimpleCovering

      public static void getSimpleCovering(S2Region region, S2Point start, int level, ArrayList<S2CellId> output)
      Given a connected region and a starting point, return a set of cells at the given level that cover the region.
    • getFastCovering

      public void getFastCovering(S2Cap cap, ArrayList<S2CellId> results)
      Like GetCovering(), except that this method is much faster and the coverings are not as tight.

      All of the usual parameters are respected (max_cells, min_level, max_level, and level_mod), except that the implementation makes no attempt to take advantage of large values of maxCells. (A small number of cells will always be returned.)

      This function is useful as a starting point for algorithms that recursively subdivide cells.

    • getRawFastCovering

      private static void getRawFastCovering(S2Cap cap, int maxCellsHint, List<S2CellId> covering)
      Compute a covering of the given cap. In general the covering consists of at most 4 cells (except for very large caps, which may need up to 6 cells). The output is not sorted.

      max_cells_hint can be used to request a more accurate covering (but is currently ignored).

    • normalizeCovering

      public void normalizeCovering(ArrayList<S2CellId> covering)
      Normalize "covering" so that it conforms to the current covering parameters (maxCells, minLevel, maxLevel, and levelMod).
    • adjustLevel

      private int adjustLevel(int level)
      If level > minLevel(), then reduce level if necessary so that it also satisfies levelMod(). Levels smaller than minLevel() are not affected (since cells at these levels are eventually expanded).
    • floodFill

      private static void floodFill(S2Region region, S2CellId start, ArrayList<S2CellId> output)
      Given a region and a starting cell, return the set of all the edge-connected cells at the same level that intersect "region". The output cells are returned in arbitrary order.