Class S2RegionCoverer
- java.lang.Object
-
- com.google.common.geometry.S2RegionCoverer
-
- All Implemented Interfaces:
java.io.Serializable
@GwtCompatible(serializable=true) public final class S2RegionCoverer extends java.lang.Object implements java.io.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:
- Serialized Form
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) class
S2RegionCoverer.ActiveCovering
This class tracks the state of a covering while it is underway.static class
S2RegionCoverer.Builder
A Build to construct aS2RegionCoverer
with options.(package private) static class
S2RegionCoverer.Candidate
(package private) static class
S2RegionCoverer.QueueEntriesComparator
We define our own comparison function on QueueEntries in order to make the results deterministic.(package private) static class
S2RegionCoverer.QueueEntry
-
Field Summary
Fields Modifier and Type Field Description static S2RegionCoverer
DEFAULT
A S2RegionCoverer configured with the default options.private static java.util.List<S2Cell>
FACE_CELLS
private int
levelMod
private int
maxCells
private int
maxLevel
private int
minLevel
-
Constructor Summary
Constructors Modifier Constructor Description private
S2RegionCoverer(S2RegionCoverer.Builder builder)
Construct from aS2RegionCoverer.Builder
.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private int
adjustLevel(int level)
If level > minLevel(), then reducelevel
if necessary so that it also satisfies levelMod().static S2RegionCoverer.Builder
builder()
Returns a new Builder with default values, which can be used to construct an S2RegionCoverer instance.boolean
equals(java.lang.Object obj)
private static void
floodFill(S2Region region, S2CellId start, java.util.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".S2CellUnion
getCovering(S2Region region)
Return a normalized cell union that covers the given region and satisfies the restrictions *EXCEPT* for minLevel() and levelMod().void
getCovering(S2Region region, S2CellUnion covering)
void
getCovering(S2Region region, java.util.ArrayList<S2CellId> covering)
Computes a list of cell ids that covers the given region and satisfies the various restrictions specified above.void
getFastCovering(S2Cap cap, java.util.ArrayList<S2CellId> results)
Like GetCovering(), except that this method is much faster and the coverings are not as tight.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().void
getInteriorCovering(S2Region region, S2CellUnion covering)
void
getInteriorCovering(S2Region region, java.util.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.private static void
getRawFastCovering(S2Cap cap, int maxCellsHint, java.util.List<S2CellId> covering)
Compute a covering of the given cap.static void
getSimpleCovering(S2Region region, S2Point start, int level, java.util.ArrayList<S2CellId> output)
Given a connected region and a starting point, return a set of cells at the given level that cover the region.int
hashCode()
int
levelMod()
int
maxCells()
int
maxLevel()
int
minLevel()
void
normalizeCovering(java.util.ArrayList<S2CellId> covering)
Normalize "covering" so that it conforms to the current covering parameters (maxCells, minLevel, maxLevel, and levelMod).
-
-
-
Field Detail
-
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 isS2RegionCoverer.Builder.DEFAULT_MAX_CELLS
. SeeS2RegionCoverer.Builder
for details.
-
FACE_CELLS
private static final java.util.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 Detail
-
S2RegionCoverer
private S2RegionCoverer(S2RegionCoverer.Builder builder)
Construct from aS2RegionCoverer.Builder
. Users should construct with S2RegionCoverer.builder().build(), or use the DEFAULT instance.
-
-
Method Detail
-
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(java.lang.Object obj)
- Overrides:
equals
in classjava.lang.Object
-
hashCode
public int hashCode()
- Overrides:
hashCode
in classjava.lang.Object
-
minLevel
public int minLevel()
-
maxLevel
public int maxLevel()
-
maxCells
public int maxCells()
-
levelMod
public int levelMod()
-
getCovering
public void getCovering(S2Region region, java.util.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 covercovering
- The list filled in by this method
-
getInteriorCovering
public void getInteriorCovering(S2Region region, java.util.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 fillinterior
- 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, java.util.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, java.util.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, java.util.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(java.util.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 reducelevel
if necessary so that it also satisfies levelMod(). Levels smaller than minLevel() are not affected (since cells at these levels are eventually expanded).
-
-