 OGS
GeoLib::MinimalBoundingSphere Class Referencefinal

## Detailed Description

Calculated center and radius of a minimal bounding sphere for a given number of geometric points.

Definition at line 27 of file MinimalBoundingSphere.h.

#include <MinimalBoundingSphere.h>

Collaboration diagram for GeoLib::MinimalBoundingSphere:
[legend]

## Public Member Functions

MinimalBoundingSphere (MathLib::Point3d const &p, double radius=std::numeric_limits< double >::epsilon())
Point-Sphere. More...

MinimalBoundingSphere (MathLib::Point3d const &p, MathLib::Point3d const &q)
Bounding sphere using two points. More...

MinimalBoundingSphere (MathLib::Point3d const &p, MathLib::Point3d const &q, MathLib::Point3d const &r)
Bounding sphere using three points. More...

MinimalBoundingSphere (MathLib::Point3d const &p, MathLib::Point3d const &q, MathLib::Point3d const &r, MathLib::Point3d const &s)
Bounding sphere using four points. More...

MinimalBoundingSphere (std::vector< MathLib::Point3d * > const &points)
Bounding sphere of n points. More...

MathLib::Point3d getCenter () const
Returns the center point of the sphere. More...

double getRadius () const
Returns the radius of the sphere. More...

double pointDistanceSquared (MathLib::Point3d const &pnt) const
Returns the squared euclidean distance of a point from the sphere (for points within the sphere distance is negative) More...

## Private Member Functions

MinimalBoundingSphere ()
Constructor using no points. More...

## Static Private Member Functions

static MinimalBoundingSphere recurseCalculation (std::vector< MathLib::Point3d * > sphere_points, std::size_t start_idx, std::size_t length, std::size_t n_boundary_points)

## Private Attributes

MathLib::Point3d _center

## ◆ MinimalBoundingSphere() [1/6]

 GeoLib::MinimalBoundingSphere::MinimalBoundingSphere ( MathLib::Point3d const & p, double radius = std::numeric_limits::epsilon() )
explicit

Point-Sphere.

Definition at line 27 of file MinimalBoundingSphere.cpp.

30 {
31 }

## ◆ MinimalBoundingSphere() [2/6]

 GeoLib::MinimalBoundingSphere::MinimalBoundingSphere ( MathLib::Point3d const & p, MathLib::Point3d const & q )

Bounding sphere using two points.

Definition at line 33 of file MinimalBoundingSphere.cpp.

35  : _radius(std::numeric_limits<double>::epsilon()), _center(p)
36 {
37  auto const vp = Eigen::Map<Eigen::Vector3d const>(p.getCoords());
38  auto const vq = Eigen::Map<Eigen::Vector3d const>(q.getCoords());
39  Eigen::Vector3d const a = vq - vp;
40
41  Eigen::Vector3d o = a / 2;
42  _radius = o.norm() + std::numeric_limits<double>::epsilon();
43  o += vp;
44  _center = MathLib::Point3d{{o, o, o}};
45 }
static const double q

References _center, _radius, and MathLib::q.

## ◆ MinimalBoundingSphere() [3/6]

 GeoLib::MinimalBoundingSphere::MinimalBoundingSphere ( MathLib::Point3d const & p, MathLib::Point3d const & q, MathLib::Point3d const & r )

Bounding sphere using three points.

Definition at line 47 of file MinimalBoundingSphere.cpp.

50 {
51  auto const vp = Eigen::Map<Eigen::Vector3d const>(p.getCoords());
52  auto const vq = Eigen::Map<Eigen::Vector3d const>(q.getCoords());
53  auto const vr = Eigen::Map<Eigen::Vector3d const>(r.getCoords());
54  Eigen::Vector3d const a = vr - vp;
55  Eigen::Vector3d const b = vq - vp;
56  Eigen::Vector3d const axb = a.cross(b);
57
58  if (axb.squaredNorm() > 0)
59  {
60  double const denom = 2.0 * axb.dot(axb);
61  Eigen::Vector3d o =
62  (b.dot(b) * axb.cross(a) + a.dot(a) * b.cross(axb)) / denom;
63  _radius = o.norm() + std::numeric_limits<double>::epsilon();
64  o += vp;
65  _center = MathLib::Point3d{{o, o, o}};
66  }
67  else
68  {
69  MinimalBoundingSphere two_pnts_sphere;
70  if (a.squaredNorm() > b.squaredNorm())
71  {
72  two_pnts_sphere = MinimalBoundingSphere(p, r);
73  }
74  else
75  {
76  two_pnts_sphere = MinimalBoundingSphere(p, q);
77  }
79  _center = two_pnts_sphere.getCenter();
80  }
81 }
MinimalBoundingSphere()
Constructor using no points.
static const double r

References MinimalBoundingSphere(), _center, _radius, getCenter(), getRadius(), MathLib::q, and MathLib::r.

## ◆ MinimalBoundingSphere() [4/6]

 GeoLib::MinimalBoundingSphere::MinimalBoundingSphere ( MathLib::Point3d const & p, MathLib::Point3d const & q, MathLib::Point3d const & r, MathLib::Point3d const & s )

Bounding sphere using four points.

Definition at line 83 of file MinimalBoundingSphere.cpp.

87 {
88  auto const vp = Eigen::Map<Eigen::Vector3d const>(p.getCoords());
89  auto const vq = Eigen::Map<Eigen::Vector3d const>(q.getCoords());
90  auto const vr = Eigen::Map<Eigen::Vector3d const>(r.getCoords());
91  auto const vs = Eigen::Map<Eigen::Vector3d const>(s.getCoords());
92
93  Eigen::Vector3d const va = vq - vp;
94  Eigen::Vector3d const vb = vr - vp;
95  Eigen::Vector3d const vc = vs - vp;
96
97  if (!MathLib::isCoplanar(p, q, r, s))
98  {
99  double const denom = 2.0 * va.cross(vb).dot(vc);
100  Eigen::Vector3d o =
101  (vc.dot(vc) * va.cross(vb) + vb.dot(vb) * vc.cross(va) +
102  va.dot(va) * vb.cross(vc)) /
103  denom;
104
105  _radius = o.norm() + std::numeric_limits<double>::epsilon();
106  o += vp;
107  _center = MathLib::Point3d({o, o, o});
108  }
109  else
110  {
111  MinimalBoundingSphere const pqr(p, q, r);
112  MinimalBoundingSphere const pqs(p, q, s);
113  MinimalBoundingSphere const prs(p, r, s);
114  MinimalBoundingSphere const qrs(q, r, s);
116  _center = pqr.getCenter();
118  {
120  _center = pqs.getCenter();
121  }
123  {
125  _center = prs.getCenter();
126  }
128  {
130  _center = qrs.getCenter();
131  }
132  }
133 }
bool isCoplanar(const MathLib::Point3d &a, const MathLib::Point3d &b, const MathLib::Point3d &c, const MathLib::Point3d &d)
Checks if the four given points are located on a plane.
MathLib::TemplatePoint< double, 3 > Point3d

## ◆ MinimalBoundingSphere() [5/6]

 GeoLib::MinimalBoundingSphere::MinimalBoundingSphere ( std::vector< MathLib::Point3d * > const & points )
explicit

Bounding sphere of n points.

Definition at line 135 of file MinimalBoundingSphere.cpp.

137  : _radius(-1), _center({0, 0, 0})
138 {
139  const std::vector<MathLib::Point3d*>& sphere_points(points);
140  MinimalBoundingSphere const bounding_sphere =
141  recurseCalculation(sphere_points, 0, sphere_points.size(), 0);
142  _center = bounding_sphere.getCenter();
144 }
static MinimalBoundingSphere recurseCalculation(std::vector< MathLib::Point3d * > sphere_points, std::size_t start_idx, std::size_t length, std::size_t n_boundary_points)

## ◆ MinimalBoundingSphere() [6/6]

 GeoLib::MinimalBoundingSphere::MinimalBoundingSphere ( )
privatedefault

Constructor using no points.

Referenced by MinimalBoundingSphere(), and recurseCalculation().

## ◆ getCenter()

 MathLib::Point3d GeoLib::MinimalBoundingSphere::getCenter ( ) const
inline

Returns the center point of the sphere.

Definition at line 49 of file MinimalBoundingSphere.h.

49 { return _center; }

References _center.

Referenced by MinimalBoundingSphere().

 double GeoLib::MinimalBoundingSphere::getRadius ( ) const
inline

Returns the radius of the sphere.

Definition at line 52 of file MinimalBoundingSphere.h.

52 {return _radius; }

Referenced by MinimalBoundingSphere(), and MeshLib::RadiusEdgeRatioMetric::calculateQuality().

## ◆ pointDistanceSquared()

 double GeoLib::MinimalBoundingSphere::pointDistanceSquared ( MathLib::Point3d const & pnt ) const

Returns the squared euclidean distance of a point from the sphere (for points within the sphere distance is negative)

Definition at line 202 of file MinimalBoundingSphere.cpp.

204 {
205  return MathLib::sqrDist(_center, pnt) - (_radius * _radius);
206 }
double sqrDist(MathLib::Point3d const &p0, MathLib::Point3d const &p1)
Definition: Point3d.h:48

References _center, _radius, and MathLib::sqrDist().

Referenced by recurseCalculation().

## ◆ recurseCalculation()

 MinimalBoundingSphere GeoLib::MinimalBoundingSphere::recurseCalculation ( std::vector< MathLib::Point3d * > sphere_points, std::size_t start_idx, std::size_t length, std::size_t n_boundary_points )
staticprivate

Recursive method for calculating a minimal bounding sphere for an arbitrary number of points. Note: This method will change the order of elements in the vector sphere_points.

Parameters
 sphere_points The vector of points for which the smallest enclosing sphere is calculated start_idx Start index of the vector subrange analysed in the current recursive step length Length of the vector subrange analysed in the current recursive step n_boundary_points Number of found boundary points in the current recursive step

Algorithm based the following two papers: Emo Welzl: Smallest enclosing disks (balls and ellipsoids). New Results and New Trends in Computer Science, pp. 359–370, 1991 Bernd Gaertner: Fast and Robust Smallest Enclosing Balls. ESA99, pp. 325–338, 1999. Code based on "Smallest Enclosing Spheres" implementation by Nicolas Capens on flipcode's Developer Toolbox (www.flipcode.com)

Definition at line 146 of file MinimalBoundingSphere.cpp.

151 {
152  MinimalBoundingSphere sphere;
153  switch (n_boundary_points)
154  {
155  case 0:
156  sphere = MinimalBoundingSphere();
157  break;
158  case 1:
159  sphere = MinimalBoundingSphere(*sphere_points[start_idx - 1]);
160  break;
161  case 2:
162  sphere = MinimalBoundingSphere(*sphere_points[start_idx - 1],
163  *sphere_points[start_idx - 2]);
164  break;
165  case 3:
166  sphere = MinimalBoundingSphere(*sphere_points[start_idx - 1],
167  *sphere_points[start_idx - 2],
168  *sphere_points[start_idx - 3]);
169  break;
170  case 4:
171  sphere = MinimalBoundingSphere(
172  *sphere_points[start_idx - 1], *sphere_points[start_idx - 2],
173  *sphere_points[start_idx - 3], *sphere_points[start_idx - 4]);
174  return sphere;
175  }
176
177  for (std::size_t i = 0; i < length; ++i)
178  {
179  // current point is located outside of sphere
180  if (sphere.pointDistanceSquared(*sphere_points[start_idx + i]) > 0)
181  {
182  if (i > start_idx)
183  {
184  using DiffType =
185  std::vector<MathLib::Point3d*>::iterator::difference_type;
186  std::vector<MathLib::Point3d*> const tmp_ps(
187  sphere_points.cbegin() + static_cast<DiffType>(start_idx),
188  sphere_points.cbegin() +
189  static_cast<DiffType>(start_idx + i + 1));
190  std::copy(tmp_ps.cbegin(), --tmp_ps.cend(),
191  sphere_points.begin() +
192  static_cast<DiffType>(start_idx + 1));
193  sphere_points[start_idx] = tmp_ps.back();
194  }
195  sphere = recurseCalculation(sphere_points, start_idx + 1, i,
196  n_boundary_points + 1);
197  }
198  }
199  return sphere;
200 }
void copy(PETScVector const &x, PETScVector &y)
Definition: LinAlg.cpp:37

References MinimalBoundingSphere(), MathLib::LinAlg::copy(), and pointDistanceSquared().

## ◆ _center

 MathLib::Point3d GeoLib::MinimalBoundingSphere::_center
private
Initial value:
{{std::numeric_limits<double>::max(),
std::numeric_limits<double>::max(),
std::numeric_limits<double>::max()}}

Definition at line 81 of file MinimalBoundingSphere.h.

Referenced by MinimalBoundingSphere(), getCenter(), and pointDistanceSquared().