Class S2RegionCoverer
- All Implemented Interfaces:
Serializable
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:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescription(package private) final class
This class tracks the state of a covering while it is underway.static final class
A Build to construct aS2RegionCoverer
with options.(package private) static class
(package private) static class
We define our own comparison function on QueueEntries in order to make the results deterministic.(package private) static class
-
Field Summary
FieldsModifier and TypeFieldDescriptionstatic final S2RegionCoverer
A S2RegionCoverer configured with the default options.private final int
private final int
private final int
private final int
-
Constructor Summary
ConstructorsModifierConstructorDescriptionprivate
S2RegionCoverer
(S2RegionCoverer.Builder builder) Construct from aS2RegionCoverer.Builder
. -
Method Summary
Modifier and TypeMethodDescriptionprivate 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
private static void
Given a region and a starting cell, return the set of all the edge-connected cells at the same level that intersect "region".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, 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, ArrayList<S2CellId> results) Like GetCovering(), except that this method is much faster and the coverings are not as tight.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, 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, List<S2CellId> covering) Compute a covering of the given cap.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.int
hashCode()
int
levelMod()
int
maxCells()
int
maxLevel()
int
minLevel()
void
normalizeCovering
(ArrayList<S2CellId> covering) Normalize "covering" so that it conforms to the current covering parameters (maxCells, minLevel, maxLevel, and levelMod).
-
Field Details
-
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
-
minLevel
private final int minLevel -
maxLevel
private final int maxLevel -
levelMod
private final int levelMod -
maxCells
private final int maxCells
-
-
Constructor Details
-
S2RegionCoverer
Construct from aS2RegionCoverer.Builder
. Users should construct with S2RegionCoverer.builder().build(), or use the DEFAULT instance.
-
-
Method Details
-
builder
Returns a new Builder with default values, which can be used to construct an S2RegionCoverer instance. -
equals
-
hashCode
public int hashCode() -
minLevel
public int minLevel() -
maxLevel
public int maxLevel() -
maxCells
public int maxCells() -
levelMod
public int levelMod() -
getCovering
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
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
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
-
getInteriorCovering
Return a normalized cell union that is contained within the given region and satisfies the restrictions *EXCEPT* for minLevel() and levelMod(). -
getInteriorCovering
-
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
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
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
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). -
floodFill
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.
-