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.

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.

class S2RegionCoverer {

class Options;

this();

this(Options options);

const(Options) options();

Options mutableOptions();

S2CellUnion getCovering(S2Region region);

S2CellUnion getInteriorCovering(S2Region region);

void getCovering(S2Region region, S2CellId[] covering);

void getInteriorCovering(S2Region region, S2CellId[] interior);

void getFastCovering(S2Region region, S2CellId[] covering);

static void getSimpleCovering(S2Region region, S2Point start, int level, S2CellId[] output);

static void floodFill(S2Region region, S2CellId start, S2CellId[] output);

bool isCanonical(S2CellUnion covering);

bool isCanonical(S2CellId[] covering);

S2CellUnion canonicalizeCovering(S2CellUnion covering);

void canonicalizeCovering(S2CellId[] covering);

}

Constructors

this this(): Undocumented in source.
this this(Options options): Constructs an S2RegionCoverer with the given options.

Members

Classes

Options class Options: Options for the S2RegionCoverer.

Functions

canonicalizeCovering S2CellUnion canonicalizeCovering(S2CellUnion 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).
canonicalizeCovering void canonicalizeCovering(S2CellId[] covering): Undocumented in source.
getCovering S2CellUnion getCovering(S2Region region): Returns an S2CellUnion that covers (GetCovering) or is contained within (GetInteriorCovering) the given region and satisfies the current options.
getCovering void getCovering(S2Region region, S2CellId[] 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 void getFastCovering(S2Region region, S2CellId[] 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.)
getInteriorCovering S2CellUnion getInteriorCovering(S2Region region): Undocumented in source. Be warned that the author may not have intended to support it.
getInteriorCovering void getInteriorCovering(S2Region region, S2CellId[] interior): Undocumented in source. Be warned that the author may not have intended to support it.
isCanonical bool isCanonical(S2CellUnion covering): Returns true if the given S2CellId vector represents a valid covering that conforms to the current covering parameters. In particular:
isCanonical bool isCanonical(S2CellId[] covering): Undocumented in source. Be warned that the author may not have intended to support it.
mutableOptions Options mutableOptions(): Undocumented in source. Be warned that the author may not have intended to support it.
options const(Options) options(): Returns the current options. Options can be modifed between calls.

Static functions

floodFill void floodFill(S2Region region, S2CellId start, S2CellId[] 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.
getSimpleCovering void getSimpleCovering(S2Region region, S2Point start, int level, S2CellId[] output): Given a connected region and a starting point, return a set of cells at the given level that cover the region.