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 28 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.

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

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

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

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

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

Returns the radius of the sphere.

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

## Private Member Functions

MinimalBoundingSphere ()
Constructor using no points.

## 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 28 of file MinimalBoundingSphere.cpp.

## ◆ MinimalBoundingSphere() [2/6]

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

Bounding sphere using two points.

Definition at line 34 of file MinimalBoundingSphere.cpp.

37{
38 Eigen::Vector3d const a = q.asEigenVector3d() - p.asEigenVector3d();
39
40 Eigen::Vector3d o = a / 2;
41 _radius = o.norm() + std::numeric_limits<double>::epsilon();
42 o += p.asEigenVector3d();
43 _center = MathLib::Point3d{{o[0], o[1], o[2]}};
44}
Eigen::Vector3d const & asEigenVector3d() const
Definition Point3d.h:64

## ◆ 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 46 of file MinimalBoundingSphere.cpp.

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

## ◆ 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 80 of file MinimalBoundingSphere.cpp.

84{
85 Eigen::Vector3d const va = q.asEigenVector3d() - p.asEigenVector3d();
86 Eigen::Vector3d const vb = r.asEigenVector3d() - p.asEigenVector3d();
87 Eigen::Vector3d const vc = s.asEigenVector3d() - p.asEigenVector3d();
88
89 if (!MathLib::isCoplanar(p, q, r, s))
90 {
91 double const denom = 2.0 * va.cross(vb).dot(vc);
92 Eigen::Vector3d o =
93 (vc.dot(vc) * va.cross(vb) + vb.dot(vb) * vc.cross(va) +
94 va.dot(va) * vb.cross(vc)) /
95 denom;
96
97 _radius = o.norm() + std::numeric_limits<double>::epsilon();
98 o += p.asEigenVector3d();
99 _center = MathLib::Point3d({o[0], o[1], o[2]});
100 }
101 else
102 {
103 MinimalBoundingSphere const pqr(p, q, r);
104 MinimalBoundingSphere const pqs(p, q, s);
105 MinimalBoundingSphere const prs(p, r, s);
106 MinimalBoundingSphere const qrs(q, r, s);
108 _center = pqr.getCenter();
110 {
112 _center = pqs.getCenter();
113 }
115 {
117 _center = prs.getCenter();
118 }
120 {
122 _center = qrs.getCenter();
123 }
124 }
125}
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.

## ◆ MinimalBoundingSphere() [5/6]

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

Bounding sphere of n points.

Definition at line 127 of file MinimalBoundingSphere.cpp.

129 : _radius(-1), _center({0, 0, 0})
130{
131 const std::vector<MathLib::Point3d*>& sphere_points(points);
132 MinimalBoundingSphere const bounding_sphere =
133 recurseCalculation(sphere_points, 0, sphere_points.size(), 0);
134 _center = bounding_sphere.getCenter();
136}
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 50 of file MinimalBoundingSphere.h.

50{ return _center; }

References _center.

Referenced by MinimalBoundingSphere(), and MinimalBoundingSphere().

inline

Returns the radius of the sphere.

Definition at line 53 of file MinimalBoundingSphere.h.

## ◆ 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 194 of file MinimalBoundingSphere.cpp.

196{
198}
double sqrDist(MathLib::Point3d const &p0, MathLib::Point3d const &p1)
Definition Point3d.cpp:26

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 138 of file MinimalBoundingSphere.cpp.

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

References MinimalBoundingSphere(), pointDistanceSquared(), and recurseCalculation().

Referenced by recurseCalculation().

## ◆ _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 87 of file MinimalBoundingSphere.h.

87 {{std::numeric_limits<double>::max(),
88 std::numeric_limits<double>::max(),
89 std::numeric_limits<double>::max()}};