A Pixelization (or partitioning) of the sphere is a mapping between points on the sphere and a set of pixels (a.k.a. More...

#include <Pixelization.h>

Inheritance diagram for lsst::sphgeom::Pixelization:

Public Member Functions
virtual	~Pixelization ()

virtual RangeSet	universe () const =0
	`universe` returns the set of all pixel indexes for this pixelization. More...

virtual std::unique_ptr< Region >	pixel (uint64_t i) const =0
	`pixel` returns the spherical region corresponding to the pixel with index i. More...

virtual uint64_t	index (UnitVector3d const &v) const =0
	`index` computes the index of the pixel for v. More...

virtual std::string	toString (uint64_t i) const =0
	`toString` converts the given pixel index to a human-readable string. More...

RangeSet	envelope (Region const &r, size_t maxRanges=0) const
	`envelope` returns the indexes of the pixels intersecting the spherical region r. More...

RangeSet	interior (Region const &r, size_t maxRanges=0) const
	`interior` returns the indexes of the pixels within the spherical region r. More...

Detailed Description

A Pixelization (or partitioning) of the sphere is a mapping between points on the sphere and a set of pixels (a.k.a.

cells or partitions) with 64 bit integer labels (indexes), where each point is assigned to exactly one pixel.

A pixelization is capable of:

mapping a unit vector to its assigned pixel
computing the indexes of pixels intersecting a region
computing the indexes of pixels within a region
returning the set of all possible pixel indexes
returning a geometric representation of a pixel

One use case for pixelizations is spatial search in an RDBMS. Given a table of points in S² indexed by pixel, one can quickly retrieve points inside of a region r by computing the indexes of pixels intersecting r:

RangeSet pixels = pixelization.envelope(r);

and then performing range lookups on the table. The range lookup results may include points outside of r but close to its boundary, so additional filtering is necessary if one wishes to obtain exactly those points inside r.

To mitigate this cost, which can be significant for large regions with complex boundaries, one can compute the indexes of pixels completely contained in R. Only points belonging to pixels in:

RangeSet s = pixelization.envelope(r) - pixelization.interior(r);

must be tested for membership in r. Note that the indexes of pixels disjoint from r can be computed as follows:

 RangeSet exterior = pixelization.universe() -
                     pixelization.envelope(r);

Definition at line 77 of file Pixelization.h.

Constructor & Destructor Documentation

◆ ~Pixelization()

virtual lsst::sphgeom::Pixelization::~Pixelization ( )

inlinevirtual

Definition at line 79 of file Pixelization.h.

79 {}

Member Function Documentation

◆ envelope()

RangeSet lsst::sphgeom::Pixelization::envelope	(	Region const &	r,
		size_t	maxRanges = `0`
	)		const

inline

envelope returns the indexes of the pixels intersecting the spherical region r.

For hierarchical pixelizations, a good way to implement this is by top down tree traversal. Starting with the root pixels (e.g. Q3C cube faces, or HTM root triangles), a pixel P is tested for intersection with the region r. If P is already at the desired subdivision level and intersects r, its index is added to the output. If r contains P, the indexes of all children of P at the target subdivision level are output. Finally, if P intersects r, then P is subdivided and the algorithm recurses on its child pixels.

Using higher subdivision levels allows a region to be more closely approximated by smaller pixels, but for large input regions the cost of computing and storing their indexes can quickly become prohibitive.

The maxRanges parameter can be used to limit both these costs - setting it to a non-zero value sets a cap on the number of ranges returned by this method. To meet this constraint, implementations are allowed to return pixels that do not intersect r along with those that do. This allows two ranges [a, b) and [c, d), a < b < c < d, to be merged into one range [a, d) (by adding in the pixels [b, c)). Since simplification proceeds by adding pixels, the return value will always be a superset of the intersecting pixels.

In practice, the implementation of this method for a hierarchical pixelization like Q3C or HTM will lower the subdivision level when too many ranges have been found. Each coarse pixel I at level L - n corresponds to pixels [I*4ⁿ, (I + 1)*4ⁿ) at level L.

Definition at line 131 of file Pixelization.h.

                                                                     {
         return _envelope(r, maxRanges);
     }

◆ index()

virtual uint64_t lsst::sphgeom::Pixelization::index ( UnitVector3d const & v ) const

pure virtual

index computes the index of the pixel for v.

Implemented in lsst::sphgeom::Mq3cPixelization, lsst::sphgeom::Q3cPixelization, and lsst::sphgeom::HtmPixelization.

◆ interior()

RangeSet lsst::sphgeom::Pixelization::interior	(	Region const &	r,
		size_t	maxRanges = `0`
	)		const

inline

interior returns the indexes of the pixels within the spherical region r.

The maxRanges argument is analogous to the identically named envelope() argument. The only difference is that implementations must remove interior pixels to keep the number of ranges at or below the maximum. The return value is therefore always a subset of the interior pixels.

Definition at line 143 of file Pixelization.h.

                                                                     {
         return _interior(r, maxRanges);
     }

◆ pixel()

virtual std::unique_ptr<Region> lsst::sphgeom::Pixelization::pixel ( uint64_t i ) const

pure virtual

pixel returns the spherical region corresponding to the pixel with index i.

This region will contain all unit vectors v with index(v) == i. But it may also contain points with index not equal to i. To see why, consider a point that lies on the edge of a polygonal pixel - it is inside the polygons for both pixels sharing the edge, but must be assigned to exactly one pixel by the pixelization.

If i is not a valid pixel index, a std::invalid_argument is thrown.

Implemented in lsst::sphgeom::Mq3cPixelization, lsst::sphgeom::HtmPixelization, and lsst::sphgeom::Q3cPixelization.