LSST Applications  21.0.0-172-gfb10e10a+18fedfabac,22.0.0+297cba6710,22.0.0+80564b0ff1,22.0.0+8d77f4f51a,22.0.0+a28f4c53b1,22.0.0+dcf3732eb2,22.0.1-1-g7d6de66+2a20fdde0d,22.0.1-1-g8e32f31+297cba6710,22.0.1-1-geca5380+7fa3b7d9b6,22.0.1-12-g44dc1dc+2a20fdde0d,22.0.1-15-g6a90155+515f58c32b,22.0.1-16-g9282f48+790f5f2caa,22.0.1-2-g92698f7+dcf3732eb2,22.0.1-2-ga9b0f51+7fa3b7d9b6,22.0.1-2-gd1925c9+bf4f0e694f,22.0.1-24-g1ad7a390+a9625a72a8,22.0.1-25-g5bf6245+3ad8ecd50b,22.0.1-25-gb120d7b+8b5510f75f,22.0.1-27-g97737f7+2a20fdde0d,22.0.1-32-gf62ce7b1+aa4237961e,22.0.1-4-g0b3f228+2a20fdde0d,22.0.1-4-g243d05b+871c1b8305,22.0.1-4-g3a563be+32dcf1063f,22.0.1-4-g44f2e3d+9e4ab0f4fa,22.0.1-42-gca6935d93+ba5e5ca3eb,22.0.1-5-g15c806e+85460ae5f3,22.0.1-5-g58711c4+611d128589,22.0.1-5-g75bb458+99c117b92f,22.0.1-6-g1c63a23+7fa3b7d9b6,22.0.1-6-g50866e6+84ff5a128b,22.0.1-6-g8d3140d+720564cf76,22.0.1-6-gd805d02+cc5644f571,22.0.1-8-ge5750ce+85460ae5f3,master-g6e05de7fdc+babf819c66,master-g99da0e417a+8d77f4f51a,w.2021.48
LSST Data Management Base Package
Public Member Functions | Static Public Member Functions | Static Public Attributes | List of all members
lsst::sphgeom::Mq3cPixelization Class Reference

Mq3cPixelization provides modified Q3C indexing of points and regions. More...

#include <Mq3cPixelization.h>

Inheritance diagram for lsst::sphgeom::Mq3cPixelization:
lsst::sphgeom::Pixelization

Public Member Functions

 Mq3cPixelization (int level)
 This constructor creates a modified Q3C pixelization of the sphere with the given subdivision level. More...
 
int getLevel () const
 getLevel returns the subdivision level of this pixelization. More...
 
RangeSet universe () const override
 universe returns the set of all pixel indexes for this pixelization. More...
 
std::unique_ptr< Regionpixel (uint64_t i) const override
 pixel returns the spherical region corresponding to the pixel with index i. More...
 
uint64_t index (UnitVector3d const &v) const override
 index computes the index of the pixel for v. More...
 
std::string toString (uint64_t i) const override
 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...
 

Static Public Member Functions

static int level (uint64_t i)
 level returns the subdivision level of the given modified Q3C index. More...
 
static ConvexPolygon quad (uint64_t i)
 quad returns the quadrilateral corresponding to the modified Q3C pixel with index i. More...
 
static std::vector< uint64_t > neighborhood (uint64_t i)
 neighborhood returns the indexes of all pixels that share a vertex with pixel i (including i itself). More...
 
static std::string asString (uint64_t i)
 toString converts the given modified-Q3C index to a human readable string. More...
 

Static Public Attributes

static constexpr int MAX_LEVEL = 30
 The maximum supported cube-face grid resolution is 2^30 by 2^30. More...
 

Detailed Description

Mq3cPixelization provides modified Q3C indexing of points and regions.

Instances of this class are immutable and very cheap to copy.

Warning
Setting the maxRanges argument for envelope() or interior() to a non-zero value below 4 can result in very poor region pixelizations regardless of region size. For instance, if maxRanges is 1, a non-empty circle centered on an axis will be approximated by the indexes for an entire cube face, even as the circle radius tends to 0.

Definition at line 50 of file Mq3cPixelization.h.

Constructor & Destructor Documentation

◆ Mq3cPixelization()

lsst::sphgeom::Mq3cPixelization::Mq3cPixelization ( int  level)
explicit

This constructor creates a modified Q3C pixelization of the sphere with the given subdivision level.

If level ∉ [0, MAX_LEVEL], a std::invalid_argument is thrown.

Definition at line 292 of file Mq3cPixelization.cc.

292  : _level{level} {
293  if (level < 0 || level > MAX_LEVEL) {
294  throw std::invalid_argument(
295  "Modified-Q3C subdivision level not in [0, 30]");
296  }
297 }
static int level(uint64_t i)
level returns the subdivision level of the given modified Q3C index.
static constexpr int MAX_LEVEL
The maximum supported cube-face grid resolution is 2^30 by 2^30.

Member Function Documentation

◆ asString()

std::string lsst::sphgeom::Mq3cPixelization::asString ( uint64_t  i)
static

toString converts the given modified-Q3C index to a human readable string.

The first two characters in the return value are always '+X', '+Y', '+Z', '-X', '-Y', or '-Z'. They give the normal vector of the cube face F containing i. Each subsequent character is a digit in [0-3] corresponding to a child pixel index, so that reading the string from left to right corresponds to descent of the quad-tree overlaid on F.

If i is not a valid modified-Q3C index, a std::invalid_argument is thrown.

Definition at line 270 of file Mq3cPixelization.cc.

270  {
271  static char const FACE_NORM[6][2] = {
272  {'-', 'Z'}, {'+', 'X'}, {'+', 'Y'},
273  {'+', 'Z'}, {'-', 'X'}, {'-', 'Y'},
274  };
275  char s[MAX_LEVEL + 2];
276  int l = level(i);
277  if (l < 0 || l > MAX_LEVEL) {
278  throw std::invalid_argument("Invalid modified-Q3C index");
279  }
280  // Print in base-4, from least to most significant digit.
281  char * p = s + (sizeof(s) - 1);
282  for (; l > 0; --l, --p, i >>= 2) {
283  *p = '0' + (i & 3);
284  }
285  // The remaining bits correspond to the cube face.
286  --p;
287  p[0] = FACE_NORM[i - 10][0];
288  p[1] = FACE_NORM[i - 10][1];
289  return std::string(p, sizeof(s) - static_cast<size_t>(p - s));
290 }

◆ envelope()

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

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.

131  {
132  return _envelope(r, maxRanges);
133  }
virtual RangeSet _envelope(Region const &r, size_t maxRanges) const =0

◆ getLevel()

int lsst::sphgeom::Mq3cPixelization::getLevel ( ) const
inline

getLevel returns the subdivision level of this pixelization.

Definition at line 96 of file Mq3cPixelization.h.

96 { return _level; }

◆ index()

uint64_t lsst::sphgeom::Mq3cPixelization::index ( UnitVector3d const &  v) const
overridevirtual

index computes the index of the pixel for v.

Implements lsst::sphgeom::Pixelization.

Definition at line 311 of file Mq3cPixelization.cc.

311  {
312  int face = faceNumber(p, FACE_NUM);
313  double w = std::fabs(p(FACE_COMP[face][2]));
314  double u = (p(FACE_COMP[face][0]) / w) * FACE_CONST[face][0];
315  double v = (p(FACE_COMP[face][1]) / w) * FACE_CONST[face][1];
316  std::tie(u, v) = atanApprox(u, v);
317  std::tuple<int32_t, int32_t> g = faceToGrid(_level, u, v);
318  uint64_t h = hilbertIndex(static_cast<uint32_t>(std::get<0>(g)),
319  static_cast<uint32_t>(std::get<1>(g)),
320  _level);
321  return (static_cast<uint64_t>(face + 10) << (2 * _level)) | h;
322  }
T fabs(T... args)
uint64_t hilbertIndex(uint32_t x, uint32_t y, int m)
hilbertIndex returns the index of (x, y) in a 2-D Hilbert curve.
Definition: curve.h:349
double w
Definition: CoaddPsf.cc:69
T tie(T... args)

◆ interior()

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

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.

143  {
144  return _interior(r, maxRanges);
145  }
virtual RangeSet _interior(Region const &r, size_t maxRanges) const =0

◆ level()

int lsst::sphgeom::Mq3cPixelization::level ( uint64_t  i)
static

level returns the subdivision level of the given modified Q3C index.

If i is not a valid modified Q3C index, -1 is returned.

Definition at line 236 of file Mq3cPixelization.cc.

236  {
237  // A modified Q3C index consists of 4 bits encoding the root cube face
238  // (10 - 15), followed by 2l bits, where each of the l bit pairs encodes
239  // a child index (0-3), and l is the desired level.
240  int j = log2(i);
241  // The level l is derivable from the index j of the MSB of i. For i to
242  // be valid, j must be an odd integer > 1 and the upper 4 bits of i must
243  // be at least 10.
244  if ((j & 1) == 0 || (j == 1) || ((i >> (j - 3)) < 10)) {
245  return -1;
246  }
247  return (j - 3) >> 1;
248 }
uint8_t log2(uint64_t x)
Definition: curve.h:98

◆ neighborhood()

std::vector< uint64_t > lsst::sphgeom::Mq3cPixelization::neighborhood ( uint64_t  i)
static

neighborhood returns the indexes of all pixels that share a vertex with pixel i (including i itself).

A Q3C pixel has 8 - k adjacent pixels, where k is the number of vertices that are also root pixel vertices (0, 1, or 4).

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

Definition at line 260 of file Mq3cPixelization.cc.

260  {
261  int l = level(i);
262  if (l < 0 || l > MAX_LEVEL) {
263  throw std::invalid_argument("Invalid modified-Q3C index");
264  }
265  uint64_t indexes[9];
266  int n = findNeighborhood(l, i, indexes);
267  return std::vector<uint64_t>(indexes, indexes + n);
268 }

◆ pixel()

std::unique_ptr< Region > lsst::sphgeom::Mq3cPixelization::pixel ( uint64_t  i) const
overridevirtual

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.

Implements lsst::sphgeom::Pixelization.

Definition at line 299 of file Mq3cPixelization.cc.

299  {
300  uint64_t f = i >> (2 * _level);
301  if (f < 10 || f > 15) {
302  throw std::invalid_argument("Invalid modified-Q3C index");
303  }
304  UnitVector3d verts[4];
305  makeQuad(i, _level, verts);
307  new ConvexPolygon(verts[0], verts[1], verts[2], verts[3]));
308 }

◆ quad()

ConvexPolygon lsst::sphgeom::Mq3cPixelization::quad ( uint64_t  i)
static

quad returns the quadrilateral corresponding to the modified Q3C pixel with index i.

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

Definition at line 250 of file Mq3cPixelization.cc.

250  {
251  int l = level(i);
252  if (l < 0 || l > MAX_LEVEL) {
253  throw std::invalid_argument("Invalid modified-Q3C index");
254  }
255  UnitVector3d verts[4];
256  makeQuad(i, l, verts);
257  return ConvexPolygon(verts[0], verts[1], verts[2], verts[3]);
258 }

◆ toString()

std::string lsst::sphgeom::Mq3cPixelization::toString ( uint64_t  i) const
inlineoverridevirtual

toString converts the given pixel index to a human-readable string.

Implements lsst::sphgeom::Pixelization.

Definition at line 107 of file Mq3cPixelization.h.

107 { return asString(i); }
static std::string asString(uint64_t i)
toString converts the given modified-Q3C index to a human readable string.

◆ universe()

RangeSet lsst::sphgeom::Mq3cPixelization::universe ( ) const
inlineoverridevirtual

universe returns the set of all pixel indexes for this pixelization.

Implements lsst::sphgeom::Pixelization.

Definition at line 98 of file Mq3cPixelization.h.

98  {
99  return RangeSet(static_cast<uint64_t>(10) << 2 * _level,
100  static_cast<uint64_t>(16) << 2 * _level);
101  }

Member Data Documentation

◆ MAX_LEVEL

constexpr int lsst::sphgeom::Mq3cPixelization::MAX_LEVEL = 30
staticconstexpr

The maximum supported cube-face grid resolution is 2^30 by 2^30.

Definition at line 53 of file Mq3cPixelization.h.


The documentation for this class was generated from the following files: