Struct s2::region::RegionCoverer

pub struct RegionCoverer {
    pub min_level: u8,
    pub max_level: u8,
    pub level_mod: u8,
    pub max_cells: usize,
}

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:

rc := &s2.RegionCoverer{MaxLevel: 30, MaxCells: 5} r := s2.Region(CapFromCenterArea(center, area)) covering := rc.Covering(r)

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 0/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.

Fields

min_level: u8

the minimum cell level to be used.

max_level: u8

the maximum cell level to be used.

level_mod: u8

the level_mod to be used.

max_cells: usize

the maximum desired number of cells in the approximation.

Implementations

impl RegionCoverer

pub fn covering<R>(&self, region: &R) -> CellUnionwhere
    R: Region + 'static,

covering returns a CellUnion that covers the given region and satisfies the various restrictions.

pub fn interior_covering<R>(&self, region: &R) -> CellUnionwhere
    R: Region + 'static,

interior_covering returns a CellUnion that is contained within the given region and satisfies the various restrictions.

pub fn interior_cellunion<'a, R>(&self, region: &'a R) -> CellUnionwhere
    R: Region + 'static,

interior_cellunion returns 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.)

pub fn fast_covering<'a, R>(&self, region: &'a R) -> CellUnionwhere
    R: Region,

FastCovering returns 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.

Trait Implementations

impl Clone for RegionCoverer

fn clone(&self) -> RegionCoverer

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for RegionCoverer

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for RegionCoverer

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>where
    __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Serialize for RegionCoverer

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>where
    __S: Serializer,

Serialize this value into the given Serde serializer.