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

ConvexPolygon is a closed convex polygon on the unit sphere. More...

#include <ConvexPolygon.h>

Inheritance diagram for lsst::sphgeom::ConvexPolygon:
lsst::sphgeom::Region

Public Member Functions

 ConvexPolygon (std::vector< UnitVector3d > const &points)
 This constructor creates a convex polygon that is the convex hull of the given set of points. More...
 
 ConvexPolygon (UnitVector3d const &v0, UnitVector3d const &v1, UnitVector3d const &v2)
 This constructor creates a triangle with the given vertices. More...
 
 ConvexPolygon (UnitVector3d const &v0, UnitVector3d const &v1, UnitVector3d const &v2, UnitVector3d const &v3)
 This constructor creates a quadrilateral with the given vertices. More...
 
bool operator== (ConvexPolygon const &p) const
 Two convex polygons are equal iff they contain the same points. More...
 
bool operator!= (ConvexPolygon const &p) const
 
std::vector< UnitVector3d > const & getVertices () const
 
UnitVector3d getCentroid () const
 The centroid of a polygon is its center of mass projected onto S², assuming a uniform mass distribution over the polygon surface. More...
 
std::unique_ptr< Regionclone () const override
 clone returns a deep copy of this region. More...
 
Box getBoundingBox () const override
 getBoundingBox returns a bounding-box for this region. More...
 
Box3d getBoundingBox3d () const override
 getBoundingBox3d returns a 3-dimensional bounding-box for this region. More...
 
Circle getBoundingCircle () const override
 getBoundingCircle returns a bounding-circle for this region. More...
 
Relationship relate (Region const &r) const override
 
Relationship relate (Box const &) const override
 
Relationship relate (Circle const &) const override
 
Relationship relate (ConvexPolygon const &) const override
 
Relationship relate (Ellipse const &) const override
 
std::vector< uint8_t > encode () const override
 encode serializes this region into an opaque byte string. More...
 
virtual bool contains (UnitVector3d const &) const=0
 contains tests whether the given unit vector is inside this region. More...
 
bool contains (double x, double y, double z) const
 contains tests whether the unit vector defined by the given (not necessarily normalized) coordinates is inside this region. More...
 
bool contains (double lon, double lat) const
 contains tests whether the unit vector defined by the given longitude and latitude coordinates (in radians) is inside this region. More...
 
bool contains (double x, double y, double z) const
 contains tests whether the unit vector defined by the given (not necessarily normalized) coordinates is inside this region. More...
 
bool contains (double lon, double lat) const
 contains tests whether the unit vector defined by the given longitude and latitude coordinates (in radians) is inside this region. More...
 
bool contains (UnitVector3d const &v) const override
 
bool contains (Region const &r) const
 
bool isDisjointFrom (Region const &r) const
 
bool intersects (Region const &r) const
 
bool isWithin (Region const &r) const
 

Static Public Member Functions

static ConvexPolygon convexHull (std::vector< UnitVector3d > const &points)
 convexHull returns the convex hull of the given set of points if it exists and throws an exception otherwise. More...
 
static std::unique_ptr< ConvexPolygondecode (std::vector< uint8_t > const &s)
 
static std::unique_ptr< ConvexPolygondecode (uint8_t const *buffer, size_t n)
 

Static Public Attributes

static constexpr uint8_t TYPE_CODE = 'p'
 

Detailed Description

ConvexPolygon is a closed convex polygon on the unit sphere.

Its edges are great circles (geodesics), and the shorter of the two great circle segments between any two points on the polygon boundary is contained in the polygon.

The vertices of a convex polygon are distinct and have counter-clockwise orientation when viewed from outside the unit sphere. No three consecutive vertices are coplanar and edges do not intersect except at vertices.

Furthermore, if a convex polygon contains a point p of S², then we require that it be disjoint from point -p. This guarantees the existence of a unique shortest great circle segment between any 2 points contained in the polygon, but means e.g. that hemispheres and lunes cannot be represented by convex polygons.

Currently, the only way to construct a convex polygon is to compute the convex hull of a point set.

Definition at line 57 of file ConvexPolygon.h.

Constructor & Destructor Documentation

◆ ConvexPolygon() [1/3]

lsst::sphgeom::ConvexPolygon::ConvexPolygon ( std::vector< UnitVector3d > const &  points)
explicit

This constructor creates a convex polygon that is the convex hull of the given set of points.

Definition at line 255 of file ConvexPolygon.cc.

255  :
256  _vertices(points)
257 {
258  computeHull(_vertices);
259 }

◆ ConvexPolygon() [2/3]

lsst::sphgeom::ConvexPolygon::ConvexPolygon ( UnitVector3d const &  v0,
UnitVector3d const &  v1,
UnitVector3d const &  v2 
)
inline

This constructor creates a triangle with the given vertices.

It is assumed that orientation(v0, v1, v2) = 1. Use with caution - for performance reasons, this is not verified!

Definition at line 77 of file ConvexPolygon.h.

79  :
80  _vertices{v0, v1, v2}
81  {}

◆ ConvexPolygon() [3/3]

lsst::sphgeom::ConvexPolygon::ConvexPolygon ( UnitVector3d const &  v0,
UnitVector3d const &  v1,
UnitVector3d const &  v2,
UnitVector3d const &  v3 
)
inline

This constructor creates a quadrilateral with the given vertices.

It is assumed that orientation(v0, v1, v2), orientation(v1, v2, v3), orientation(v2, v3, v0), and orientation (v3, v0, v1) are all 1. Use with caution - for performance reasons, this is not verified!

Definition at line 88 of file ConvexPolygon.h.

91  :
92  _vertices{v0, v1, v2, v3}
93  {}

Member Function Documentation

◆ clone()

std::unique_ptr<Region> lsst::sphgeom::ConvexPolygon::clone ( ) const
inlineoverridevirtual

clone returns a deep copy of this region.

Implements lsst::sphgeom::Region.

Definition at line 108 of file ConvexPolygon.h.

108  {
110  }
ConvexPolygon(std::vector< UnitVector3d > const &points)
This constructor creates a convex polygon that is the convex hull of the given set of points.

◆ contains() [1/7]

bool lsst::sphgeom::Region::contains

contains tests whether the unit vector defined by the given longitude and latitude coordinates (in radians) is inside this region.

Definition at line 104 of file Region.cc.

43  {
44  return contains(UnitVector3d(LonLat::fromRadians(lon, lat)));
45 }
virtual bool contains(UnitVector3d const &) const=0
contains tests whether the given unit vector is inside this region.
static LonLat fromRadians(double lon, double lat)
Definition: LonLat.h:55

◆ contains() [2/7]

bool lsst::sphgeom::Region::contains ( double  lon,
double  lat 
) const
inherited

contains tests whether the unit vector defined by the given longitude and latitude coordinates (in radians) is inside this region.

Definition at line 43 of file Region.cc.

43  {
44  return contains(UnitVector3d(LonLat::fromRadians(lon, lat)));
45 }
virtual bool contains(UnitVector3d const &) const =0
contains tests whether the given unit vector is inside this region.

◆ contains() [3/7]

bool lsst::sphgeom::Region::contains

contains tests whether the unit vector defined by the given (not necessarily normalized) coordinates is inside this region.

Definition at line 100 of file Region.cc.

39  {
40  return contains(UnitVector3d(x, y, z));
41 }
double x
double z
Definition: Match.cc:44
int y
Definition: SpanSet.cc:48

◆ contains() [4/7]

bool lsst::sphgeom::Region::contains ( double  x,
double  y,
double  z 
) const
inherited

contains tests whether the unit vector defined by the given (not necessarily normalized) coordinates is inside this region.

Definition at line 39 of file Region.cc.

39  {
40  return contains(UnitVector3d(x, y, z));
41 }

◆ contains() [5/7]

bool lsst::sphgeom::ConvexPolygon::contains ( Region const &  r) const

contains returns true if the intersection of this convex polygon and x is equal to x.

Definition at line 316 of file ConvexPolygon.cc.

316  {
317  return (relate(r) & CONTAINS) != 0;
318 }
Relationship relate(Region const &r) const override

◆ contains() [6/7]

virtual bool lsst::sphgeom::Region::contains

contains tests whether the given unit vector is inside this region.

◆ contains() [7/7]

bool lsst::sphgeom::ConvexPolygon::contains ( UnitVector3d const &  v) const
overridevirtual

contains returns true if the intersection of this convex polygon and x is equal to x.

Implements lsst::sphgeom::Region.

Definition at line 312 of file ConvexPolygon.cc.

312  {
313  return detail::contains(_vertices.begin(), _vertices.end(), v);
314 }
bool contains(VertexIterator const begin, VertexIterator const end, UnitVector3d const &v)

◆ convexHull()

static ConvexPolygon lsst::sphgeom::ConvexPolygon::convexHull ( std::vector< UnitVector3d > const &  points)
inlinestatic

convexHull returns the convex hull of the given set of points if it exists and throws an exception otherwise.

Though points are supplied in a vector, they really are conceptually a set - the ConvexPolygon returned is invariant under permutation of the input array.

Definition at line 65 of file ConvexPolygon.h.

65  {
66  return ConvexPolygon(points);
67  }

◆ decode() [1/2]

static std::unique_ptr<ConvexPolygon> lsst::sphgeom::ConvexPolygon::decode ( std::vector< uint8_t > const &  s)
inlinestatic

decode deserializes a ConvexPolygon from a byte string produced by encode.

Definition at line 157 of file ConvexPolygon.h.

157  {
158  return decode(s.data(), s.size());
159  }
static std::unique_ptr< ConvexPolygon > decode(std::vector< uint8_t > const &s)
T data(T... args)
T size(T... args)

◆ decode() [2/2]

std::unique_ptr< ConvexPolygon > lsst::sphgeom::ConvexPolygon::decode ( uint8_t const *  buffer,
size_t  n 
)
static

decode deserializes a ConvexPolygon from a byte string produced by encode.

Definition at line 361 of file ConvexPolygon.cc.

363 {
364  if (buffer == nullptr || *buffer != TYPE_CODE ||
365  n < 1 + 24*3 || (n - 1) % 24 != 0) {
366  throw std::runtime_error("Byte-string is not an encoded ConvexPolygon");
367  }
368  std::unique_ptr<ConvexPolygon> poly(new ConvexPolygon);
369  ++buffer;
370  size_t nv = (n - 1) / 24;
371  poly->_vertices.reserve(nv);
372  for (size_t i = 0; i < nv; ++i, buffer += 24) {
373  poly->_vertices.push_back(UnitVector3d::fromNormalized(
374  decodeDouble(buffer),
375  decodeDouble(buffer + 8),
376  decodeDouble(buffer + 16)
377  ));
378  }
379  return poly;
380 }
static constexpr uint8_t TYPE_CODE
Definition: ConvexPolygon.h:59
static UnitVector3d fromNormalized(Vector3d const &v)
fromNormalized returns the unit vector equal to v, which is assumed to be normalized.
Definition: UnitVector3d.h:82
Low-level polynomials (including special polynomials) in C++.
Definition: Basis1d.h:26
double decodeDouble(uint8_t const *buffer)
decode extracts an IEEE double from the 8 byte little-endian byte sequence in buffer.
Definition: codec.h:66

◆ encode()

std::vector< uint8_t > lsst::sphgeom::ConvexPolygon::encode ( ) const
overridevirtual

encode serializes this region into an opaque byte string.

Byte strings emitted by encode can be deserialized with decode.

Implements lsst::sphgeom::Region.

Definition at line 348 of file ConvexPolygon.cc.

348  {
349  std::vector<uint8_t> buffer;
350  uint8_t tc = TYPE_CODE;
351  buffer.reserve(1 + 24 * _vertices.size());
352  buffer.push_back(tc);
353  for (UnitVector3d const & v: _vertices) {
354  encodeDouble(v.x(), buffer);
355  encodeDouble(v.y(), buffer);
356  encodeDouble(v.z(), buffer);
357  }
358  return buffer;
359 }
void encodeDouble(double item, std::vector< uint8_t > &buffer)
encode appends an IEEE double in little-endian byte order to the end of buffer.
Definition: codec.h:46
T push_back(T... args)
T reserve(T... args)

◆ getBoundingBox()

Box lsst::sphgeom::ConvexPolygon::getBoundingBox ( ) const
overridevirtual

getBoundingBox returns a bounding-box for this region.

Implements lsst::sphgeom::Region.

Definition at line 304 of file ConvexPolygon.cc.

304  {
305  return detail::boundingBox(_vertices.begin(), _vertices.end());
306 }
Box boundingBox(VertexIterator const begin, VertexIterator const end)

◆ getBoundingBox3d()

Box3d lsst::sphgeom::ConvexPolygon::getBoundingBox3d ( ) const
overridevirtual

getBoundingBox3d returns a 3-dimensional bounding-box for this region.

Implements lsst::sphgeom::Region.

Definition at line 308 of file ConvexPolygon.cc.

308  {
309  return detail::boundingBox3d(_vertices.begin(), _vertices.end());
310 }
Box3d boundingBox3d(VertexIterator const begin, VertexIterator const end)

◆ getBoundingCircle()

Circle lsst::sphgeom::ConvexPolygon::getBoundingCircle ( ) const
overridevirtual

getBoundingCircle returns a bounding-circle for this region.

Implements lsst::sphgeom::Region.

Definition at line 300 of file ConvexPolygon.cc.

300  {
301  return detail::boundingCircle(_vertices.begin(), _vertices.end());
302 }
Circle boundingCircle(VertexIterator const begin, VertexIterator const end)

◆ getCentroid()

UnitVector3d lsst::sphgeom::ConvexPolygon::getCentroid ( ) const

The centroid of a polygon is its center of mass projected onto S², assuming a uniform mass distribution over the polygon surface.

Definition at line 296 of file ConvexPolygon.cc.

296  {
297  return detail::centroid(_vertices.begin(), _vertices.end());
298 }
UnitVector3d centroid(VertexIterator const begin, VertexIterator const end)

◆ getVertices()

std::vector<UnitVector3d> const& lsst::sphgeom::ConvexPolygon::getVertices ( ) const
inline

Definition at line 99 of file ConvexPolygon.h.

99  {
100  return _vertices;
101  }

◆ intersects()

bool lsst::sphgeom::ConvexPolygon::intersects ( Region const &  r) const

intersects returns true if the intersection of this convex polygon and x is non-empty.

Definition at line 324 of file ConvexPolygon.cc.

324  {
325  return !isDisjointFrom(r);
326 }
bool isDisjointFrom(Region const &r) const

◆ isDisjointFrom()

bool lsst::sphgeom::ConvexPolygon::isDisjointFrom ( Region const &  r) const

isDisjointFrom returns true if the intersection of this convex polygon and x is empty.

Definition at line 320 of file ConvexPolygon.cc.

320  {
321  return (relate(r) & DISJOINT) != 0;
322 }

◆ isWithin()

bool lsst::sphgeom::ConvexPolygon::isWithin ( Region const &  r) const

isWithin returns true if the intersection of this convex polygon and x is this convex polygon.

Definition at line 328 of file ConvexPolygon.cc.

328  {
329  return (relate(r) & WITHIN) != 0;
330 }

◆ operator!=()

bool lsst::sphgeom::ConvexPolygon::operator!= ( ConvexPolygon const &  p) const
inline

Definition at line 97 of file ConvexPolygon.h.

97 { return !(*this == p); }

◆ operator==()

bool lsst::sphgeom::ConvexPolygon::operator== ( ConvexPolygon const &  p) const

Two convex polygons are equal iff they contain the same points.

Definition at line 261 of file ConvexPolygon.cc.

261  {
262  if (this == &p) {
263  return true;
264  }
265  if (_vertices.size() != p._vertices.size()) {
266  return false;
267  }
268  VertexIterator i = _vertices.begin();
269  VertexIterator f = p._vertices.begin();
270  VertexIterator const ep = p._vertices.end();
271  // Find vertex f of p equal to the first vertex of this polygon.
272  for (; f != ep; ++f) {
273  if (*i == *f) {
274  break;
275  }
276  }
277  if (f == ep) {
278  // No vertex of p is equal to the first vertex of this polygon.
279  return false;
280  }
281  // Now, compare all vertices.
282  ++i;
283  for (VertexIterator j = f + 1; j != ep; ++i, ++j) {
284  if (*i != *j) {
285  return false;
286  }
287  }
288  for (VertexIterator j = p._vertices.begin(); j != f; ++i, ++j) {
289  if (*i != *j) {
290  return false;
291  }
292  }
293  return true;
294 }

◆ relate() [1/5]

Relationship lsst::sphgeom::ConvexPolygon::relate ( Box const &  ) const
overridevirtual

relate computes the spatial relationships between this region A and another region B. The return value S is a bitset with the following properties:

  • Bit S & DISJOINT is set only if A and B do not have any points in common.
  • Bit S & CONTAINS is set only if A contains all points in B.
  • Bit S & WITHIN is set only if B contains all points in A.

Said another way: if the CONTAINS, WITHIN or DISJOINT bit is set, then the corresponding spatial relationship between the two regions holds conclusively. If it is not set, the relationship may or may not hold.

These semantics allow for conservative relationship computations. In particular, a Region may choose to implement relate by replacing itself and/or the argument with a simplified bounding region.

Implements lsst::sphgeom::Region.

Definition at line 332 of file ConvexPolygon.cc.

332  {
333  return detail::relate(_vertices.begin(), _vertices.end(), b);
334 }
table::Key< int > b
Relationship relate(VertexIterator const begin, VertexIterator const end, Box const &b)

◆ relate() [2/5]

Relationship lsst::sphgeom::ConvexPolygon::relate ( Circle const &  ) const
overridevirtual

relate computes the spatial relationships between this region A and another region B. The return value S is a bitset with the following properties:

  • Bit S & DISJOINT is set only if A and B do not have any points in common.
  • Bit S & CONTAINS is set only if A contains all points in B.
  • Bit S & WITHIN is set only if B contains all points in A.

Said another way: if the CONTAINS, WITHIN or DISJOINT bit is set, then the corresponding spatial relationship between the two regions holds conclusively. If it is not set, the relationship may or may not hold.

These semantics allow for conservative relationship computations. In particular, a Region may choose to implement relate by replacing itself and/or the argument with a simplified bounding region.

Implements lsst::sphgeom::Region.

Definition at line 336 of file ConvexPolygon.cc.

336  {
337  return detail::relate(_vertices.begin(), _vertices.end(), c);
338 }

◆ relate() [3/5]

Relationship lsst::sphgeom::ConvexPolygon::relate ( ConvexPolygon const &  ) const
overridevirtual

relate computes the spatial relationships between this region A and another region B. The return value S is a bitset with the following properties:

  • Bit S & DISJOINT is set only if A and B do not have any points in common.
  • Bit S & CONTAINS is set only if A contains all points in B.
  • Bit S & WITHIN is set only if B contains all points in A.

Said another way: if the CONTAINS, WITHIN or DISJOINT bit is set, then the corresponding spatial relationship between the two regions holds conclusively. If it is not set, the relationship may or may not hold.

These semantics allow for conservative relationship computations. In particular, a Region may choose to implement relate by replacing itself and/or the argument with a simplified bounding region.

Implements lsst::sphgeom::Region.

Definition at line 340 of file ConvexPolygon.cc.

340  {
341  return detail::relate(_vertices.begin(), _vertices.end(), p);
342 }

◆ relate() [4/5]

Relationship lsst::sphgeom::ConvexPolygon::relate ( Ellipse const &  ) const
overridevirtual

relate computes the spatial relationships between this region A and another region B. The return value S is a bitset with the following properties:

  • Bit S & DISJOINT is set only if A and B do not have any points in common.
  • Bit S & CONTAINS is set only if A contains all points in B.
  • Bit S & WITHIN is set only if B contains all points in A.

Said another way: if the CONTAINS, WITHIN or DISJOINT bit is set, then the corresponding spatial relationship between the two regions holds conclusively. If it is not set, the relationship may or may not hold.

These semantics allow for conservative relationship computations. In particular, a Region may choose to implement relate by replacing itself and/or the argument with a simplified bounding region.

Implements lsst::sphgeom::Region.

Definition at line 344 of file ConvexPolygon.cc.

344  {
345  return detail::relate(_vertices.begin(), _vertices.end(), e);
346 }

◆ relate() [5/5]

Relationship lsst::sphgeom::ConvexPolygon::relate ( Region const &  ) const
inlineoverridevirtual

relate computes the spatial relationships between this region A and another region B. The return value S is a bitset with the following properties:

  • Bit S & DISJOINT is set only if A and B do not have any points in common.
  • Bit S & CONTAINS is set only if A contains all points in B.
  • Bit S & WITHIN is set only if B contains all points in A.

Said another way: if the CONTAINS, WITHIN or DISJOINT bit is set, then the corresponding spatial relationship between the two regions holds conclusively. If it is not set, the relationship may or may not hold.

These semantics allow for conservative relationship computations. In particular, a Region may choose to implement relate by replacing itself and/or the argument with a simplified bounding region.

Implements lsst::sphgeom::Region.

Definition at line 143 of file ConvexPolygon.h.

143  {
144  // Dispatch on the type of r.
145  return invert(r.relate(*this));
146  }
Relationship invert(Relationship r)
Given the relationship between two sets A and B (i.e.
Definition: Relationship.h:55

Member Data Documentation

◆ TYPE_CODE

constexpr uint8_t lsst::sphgeom::ConvexPolygon::TYPE_CODE = 'p'
staticconstexpr

Definition at line 59 of file ConvexPolygon.h.


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