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::HtmPixelization Class Reference

HtmPixelization provides HTM indexing of points and regions. More...

#include <HtmPixelization.h>

Inheritance diagram for lsst::sphgeom::HtmPixelization:
lsst::sphgeom::Pixelization

Public Member Functions

 HtmPixelization (int level)
 This constructor creates an HTM 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 &) 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 HTM index. More...
 
static ConvexPolygon triangle (uint64_t i)
 triangle returns the triangle corresponding to the given HTM index. More...
 
static std::string asString (uint64_t i)
 asString converts the given HTM index to a human readable string. More...
 

Static Public Attributes

static constexpr int MAX_LEVEL = 24
 MAX_LEVEL is the maximum supported HTM subdivision level. More...
 

Detailed Description

HtmPixelization provides HTM 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 6 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 a hemisphere or the entire unit sphere, even as its radius tends to 0.

Definition at line 50 of file HtmPixelization.h.

Constructor & Destructor Documentation

◆ HtmPixelization()

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

This constructor creates an HTM pixelization of the sphere with the given subdivision level.

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

Definition at line 164 of file HtmPixelization.cc.

164  : _level(level) {
165  if (level < 0 || level > MAX_LEVEL) {
166  throw std::invalid_argument("Invalid HTM subdivision level");
167  }
168 }
static constexpr int MAX_LEVEL
MAX_LEVEL is the maximum supported HTM subdivision level.
static int level(uint64_t i)
level returns the subdivision level of the given HTM index.

Member Function Documentation

◆ asString()

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

asString converts the given HTM index to a human readable string.

The first character in the return value is always 'N' or 'S', indicating whether the root triangle containing i is in the northern or southern hemisphere. The second character is the index of the root triangle within that hemisphere (a digit in [0-3]). Each subsequent character is a digit in [0-3] corresponding to a child trixel index, so that reading the string from left to right corresponds to descent of the HTM triangle-tree.

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

Definition at line 148 of file HtmPixelization.cc.

148  {
149  char s[MAX_LEVEL + 2];
150  int l = level(i);
151  if (l < 0 || l > MAX_LEVEL) {
152  throw std::invalid_argument("Invalid HTM index");
153  }
154  // Print in base-4, from least to most significant digit.
155  char * p = s + (sizeof(s) - 1);
156  for (; l >= 0; --l, --p, i >>= 2) {
157  *p = '0' + (i & 3);
158  }
159  // The remaining bit corresponds to the hemisphere.
160  *p = (i & 1) == 0 ? 'S' : 'N';
161  return std::string(p, sizeof(s) - static_cast<size_t>(p - s));
162 }

◆ 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::HtmPixelization::getLevel ( ) const
inline

getLevel returns the subdivision level of this pixelization.

Definition at line 84 of file HtmPixelization.h.

84 { return _level; }

◆ index()

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

index computes the index of the pixel for v.

Implements lsst::sphgeom::Pixelization.

Definition at line 170 of file HtmPixelization.cc.

170  {
171  // Find the root triangle containing v.
172  uint64_t r;
173  if (v.z() < 0.0) {
174  // v is in the southern hemisphere (root triangle 0, 1, 2, or 3).
175  if (v.y() > 0.0) {
176  r = (v.x() > 0.0) ? 0 : 1;
177  } else if (v.y() == 0.0) {
178  r = (v.x() >= 0.0) ? 0 : 2;
179  } else {
180  r = (v.x() < 0.0) ? 2 : 3;
181  }
182  } else {
183  // v is in the northern hemisphere (root triangle 4, 5, 6, or 7).
184  if (v.y() > 0.0) {
185  r = (v.x() > 0.0) ? 7 : 6;
186  } else if (v.y() == 0.0) {
187  r = (v.x() >= 0.0) ? 7 : 5;
188  } else {
189  r = (v.x() < 0.0) ? 5 : 4;
190  }
191  }
192  UnitVector3d v0 = rootVertex(r, 0);
193  UnitVector3d v1 = rootVertex(r, 1);
194  UnitVector3d v2 = rootVertex(r, 2);
195  uint64_t i = r + 8;
196  for (int l = 0; l < _level; ++l) {
197  UnitVector3d m01 = UnitVector3d(v0 + v1);
198  UnitVector3d m20 = UnitVector3d(v2 + v0);
199  i <<= 2;
200  if (orientation(v, m01, m20) >= 0) {
201  v1 = m01; v2 = m20;
202  continue;
203  }
204  UnitVector3d m12 = UnitVector3d(v1 + v2);
205  if (orientation(v, m12, m01) >= 0) {
206  v0 = v1; v1 = m12; v2 = m01;
207  i += 1;
208  } else if (orientation(v, m20, m12) >= 0) {
209  v0 = v2; v1 = m20; v2 = m12;
210  i += 2;
211  } else {
212  v0 = m12; v1 = m20; v2 = m01;
213  i += 3;
214  }
215  }
216  return i;
217 }
int orientation(UnitVector3d const &a, UnitVector3d const &b, UnitVector3d const &c)
orientation computes and returns the orientations of 3 unit vectors a, b and c.
Definition: orientation.cc:135

◆ 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::HtmPixelization::level ( uint64_t  i)
static

level returns the subdivision level of the given HTM index.

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

Definition at line 110 of file HtmPixelization.cc.

110  {
111  // An HTM index consists of 4 bits encoding the root triangle
112  // number (8 - 15), followed by 2l bits, where each of the l bit pairs
113  // encodes a child triangle number (0-3), and l is the desired level.
114  int j = log2(i);
115  // The level l is derivable from the index j of the MSB of i.
116  // For i to be valid, j must be an odd integer > 1.
117  if ((j & 1) == 0 || (j == 1)) {
118  return -1;
119  }
120  return (j - 3) >> 1;
121 }
uint8_t log2(uint64_t x)
Definition: curve.h:98

◆ pixel()

std::unique_ptr<Region> lsst::sphgeom::HtmPixelization::pixel ( uint64_t  i) const
inlineoverridevirtual

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 91 of file HtmPixelization.h.

91  {
92  return std::unique_ptr<Region>(new ConvexPolygon(triangle(i)));
93  }
static ConvexPolygon triangle(uint64_t i)
triangle returns the triangle corresponding to the given HTM index.

◆ toString()

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

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

Implements lsst::sphgeom::Pixelization.

Definition at line 97 of file HtmPixelization.h.

97 { return asString(i); }
static std::string asString(uint64_t i)
asString converts the given HTM index to a human readable string.

◆ triangle()

ConvexPolygon lsst::sphgeom::HtmPixelization::triangle ( uint64_t  i)
static

triangle returns the triangle corresponding to the given HTM index.

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

Definition at line 123 of file HtmPixelization.cc.

123  {
124  int l = level(i);
125  if (l < 0 || l > MAX_LEVEL) {
126  throw std::invalid_argument("Invalid HTM index");
127  }
128  l *= 2;
129  uint64_t r = (i >> l) & 7;
130  UnitVector3d v0 = rootVertex(r, 0);
131  UnitVector3d v1 = rootVertex(r, 1);
132  UnitVector3d v2 = rootVertex(r, 2);
133  for (l -= 2; l >= 0; l -= 2) {
134  int child = (i >> l) & 3;
135  UnitVector3d m12 = UnitVector3d(v1 + v2);
136  UnitVector3d m20 = UnitVector3d(v2 + v0);
137  UnitVector3d m01 = UnitVector3d(v0 + v1);
138  switch (child) {
139  case 0: v1 = m01; v2 = m20; break;
140  case 1: v0 = v1; v1 = m12; v2 = m01; break;
141  case 2: v0 = v2; v1 = m20; v2 = m12; break;
142  case 3: v0 = m12; v1 = m20; v2 = m01; break;
143  }
144  }
145  return ConvexPolygon(v0, v1, v2);
146 }

◆ universe()

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

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

Implements lsst::sphgeom::Pixelization.

Definition at line 86 of file HtmPixelization.h.

86  {
87  return RangeSet(static_cast<uint64_t>(8) << 2 * _level,
88  static_cast<uint64_t>(16) << 2 * _level);
89  }

Member Data Documentation

◆ MAX_LEVEL

constexpr int lsst::sphgeom::HtmPixelization::MAX_LEVEL = 24
staticconstexpr

MAX_LEVEL is the maximum supported HTM subdivision level.

Definition at line 53 of file HtmPixelization.h.


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