Class S2RegionCoverer

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.

class S2RegionCoverer ;

Typical usage: 

auto options = new S2RegionCoverer.Options();
options.setMaxCells(5);
auto coverer = new S2RegionCoverer(options);
auto cap = new S2Cap(center, radius);
S2CellUnion covering = coverer.getCovering(cap);

This yields a vector 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 max_cells() 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 max_level 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.

Constructors

NameDescription
this (options) Constructs an S2RegionCoverer with the given options.

Methods

NameDescription
canonicalizeCovering (covering) Modify "covering" if necessary so that it conforms to the current covering parameters (max_cells, min_level, max_level, and level_mod). There are no restrictions on the input S2CellIds (they may be unsorted, overlapping, etc).
floodFill (region, start, output) Given a region and a starting cell, returns the set of all the edge-connected cells at the same level that intersect "region". The output cells are returned in arbitrary order.
getCovering (region) Returns an S2CellUnion that covers (GetCovering) or is contained within (GetInteriorCovering) the given region and satisfies the current options.
getCovering (region, covering) Like the methods above, but works directly with a vector of S2CellIds. This version can be more efficient when this method is called many times, since it does not require allocating a new vector on each call.
getFastCovering (region, covering) 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 max_cells(). (A small number of cells will always be returned.)
getSimpleCovering (region, start, level, output) Given a connected region and a starting point, return a set of cells at the given level that cover the region.
isCanonical (covering) Returns true if the given S2CellId vector represents a valid covering that conforms to the current covering parameters. In particular:
options () Returns the current options. Options can be modifed between calls.

Inner classes

NameDescription
Options Options for the S2RegionCoverer.