BetaBetaReturns a new RegionCoverer with the appropriate defaults.
RegionCoverer options
BetalevelBetamaxBetamaxBetaminBetaReturns a normalized CellUnion 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 CellUnion constructor does in fact satisfy all the given restrictions.)
BetaReturns a CellUnion that covers the given region similar to Covering, except that this method is much faster and the coverings are not as tight. All of the usual parameters are respected (MaxCells, MinLevel, MaxLevel, and LevelMod), 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.
BetaReturns a normalized CellUnion that is contained within 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 CellUnion constructor does in fact satisfy all the given restrictions.)
BetaReports whether the given CellUnion represents a valid covering that conforms to the current covering parameters. In particular:
All CellIDs must be valid.
CellIDs must be sorted and non-overlapping.
CellID levels must satisfy MinLevel, MaxLevel, and LevelMod.
If the covering has more than MaxCells, there must be no two cells with a common ancestor at MinLevel or higher.
There must be no sequence of cells that could be replaced by an ancestor (i.e. with LevelMod == 1, the 4 child cells of a parent).
RegionCoverer allows arbitrary regions to be approximated as unions of cells (CellUnion). This is useful for implementing various sorts of search and precomputation operations.
Typical usage:
This yields a CellUnion of at most 5 cells that is guaranteed to cover the given region (a disc-shaped region on the sphere).
For covering, only cells where (level - MinLevel) is a multiple of LevelMod will be used. This effectively allows the branching factor of the S2 CellID hierarchy to be increased. Currently the only parameter values allowed are 1, 2, or 3, corresponding to branching factors of 4, 16, and 64 respectively.
Note the following:
MinLevel takes priority over MaxCells, i.e. cells below the given level will never be used even if this causes a large number of cells to be returned.
For any setting of MaxCells, up to 6 cells may be returned if that is the minimum number of cells required (e.g. if the region intersects all six face cells). Up to 3 cells may be returned even for very tiny convex regions if they happen to be located at the intersection of three cube faces.
For any setting of MaxCells, an arbitrary number of cells may be returned if MinLevel is too high for the region being approximated.
If MaxCells is less than 4, the area of the covering may be arbitrarily large compared to the area of the original region even if the region is convex (e.g. a Cap or Rect).
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.
Because it is an approximation algorithm, one should not rely on the stability of the output. In particular, the output of the covering algorithm may change across different versions of the library.
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.