Detailed Description

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

Definition at line 17 of file MinimalBoundingSphere.h.

#include <MinimalBoundingSphere.h>

Collaboration diagram for GeoLib::MinimalBoundingSphere:

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.
double	getRadius () const
	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
double	_radius {-1}
MathLib::Point3d	_center

Constructor & Destructor Documentation

◆ MinimalBoundingSphere() [1/6]

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

explicit

Point-Sphere.

Definition at line 17 of file MinimalBoundingSphere.cpp.

    : _radius(radius), _center(p)
{
}

References _center, and _radius.

Referenced by MinimalBoundingSphere(), MinimalBoundingSphere(), MinimalBoundingSphere(), MinimalBoundingSphere(), and recurseCalculation().

◆ MinimalBoundingSphere() [2/6]

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

Bounding sphere using two points.

Definition at line 23 of file MinimalBoundingSphere.cpp.

    : _radius(std::numeric_limits<double>::epsilon()), _center(p)
{
    Eigen::Vector3d const a = q.asEigenVector3d() - p.asEigenVector3d();
 
    Eigen::Vector3d o = a / 2;
    _radius = o.norm() + std::numeric_limits<double>::epsilon();
    o += p.asEigenVector3d();
    _center = MathLib::Point3d{{o[0], o[1], o[2]}};
}

References _center, _radius, and MathLib::Point3d::asEigenVector3d().

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

{
    auto const& vp = p.asEigenVector3d();
    Eigen::Vector3d const a = r.asEigenVector3d() - vp;
    Eigen::Vector3d const b = q.asEigenVector3d() - vp;
    Eigen::Vector3d const axb = a.cross(b);
 
    if (axb.squaredNorm() > 0)
    {
        double const denom = 2.0 * axb.dot(axb);
        Eigen::Vector3d o =
            (b.dot(b) * axb.cross(a) + a.dot(a) * b.cross(axb)) / denom;
        _radius = o.norm() + std::numeric_limits<double>::epsilon();
        o += vp;
        _center = MathLib::Point3d{{o[0], o[1], o[2]}};
    }
    else
    {
        MinimalBoundingSphere two_pnts_sphere;
        if (a.squaredNorm() > b.squaredNorm())
        {
            two_pnts_sphere = MinimalBoundingSphere(p, r);
        }
        else
        {
            two_pnts_sphere = MinimalBoundingSphere(p, q);
        }
        _radius = two_pnts_sphere.getRadius();
        _center = two_pnts_sphere.getCenter();
    }
}

References MinimalBoundingSphere(), _center, _radius, MathLib::Point3d::asEigenVector3d(), getCenter(), and getRadius().

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

{
    Eigen::Vector3d const va = q.asEigenVector3d() - p.asEigenVector3d();
    Eigen::Vector3d const vb = r.asEigenVector3d() - p.asEigenVector3d();
    Eigen::Vector3d const vc = s.asEigenVector3d() - p.asEigenVector3d();
 
    if (!MathLib::isCoplanar(p, q, r, s))
    {
        double const denom = 2.0 * va.cross(vb).dot(vc);
        Eigen::Vector3d o =
            (vc.dot(vc) * va.cross(vb) + vb.dot(vb) * vc.cross(va) +
             va.dot(va) * vb.cross(vc)) /
            denom;
 
        _radius = o.norm() + std::numeric_limits<double>::epsilon();
        o += p.asEigenVector3d();
        _center = MathLib::Point3d({o[0], o[1], o[2]});
    }
    else
    {
        MinimalBoundingSphere const pqr(p, q, r);
        MinimalBoundingSphere const pqs(p, q, s);
        MinimalBoundingSphere const prs(p, r, s);
        MinimalBoundingSphere const qrs(q, r, s);
        _radius = pqr.getRadius();
        _center = pqr.getCenter();
        if (_radius < pqs.getRadius())
        {
            _radius = pqs.getRadius();
            _center = pqs.getCenter();
        }
        if (_radius < prs.getRadius())
        {
            _radius = prs.getRadius();
            _center = prs.getCenter();
        }
        if (_radius < qrs.getRadius())
        {
            _radius = qrs.getRadius();
            _center = qrs.getCenter();
        }
    }
}

References MinimalBoundingSphere(), _center, _radius, MathLib::Point3d::asEigenVector3d(), getCenter(), getRadius(), and MathLib::isCoplanar().

◆ MinimalBoundingSphere() [5/6]

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

explicit

Bounding sphere of n points.

Definition at line 116 of file MinimalBoundingSphere.cpp.

    : _radius(-1), _center({0, 0, 0})
{
    const std::vector<MathLib::Point3d*>& sphere_points(points);
    MinimalBoundingSphere const bounding_sphere =
        recurseCalculation(sphere_points, 0, sphere_points.size(), 0);
    _center = bounding_sphere.getCenter();
    _radius = bounding_sphere.getRadius();
}

References MinimalBoundingSphere(), _center, and _radius.

◆ MinimalBoundingSphere() [6/6]

GeoLib::MinimalBoundingSphere::MinimalBoundingSphere ( )

privatedefault

Constructor using no points.

References MinimalBoundingSphere().

Referenced by recurseCalculation().

Member Function Documentation

◆ getCenter()

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

inline

Returns the center point of the sphere.

Definition at line 39 of file MinimalBoundingSphere.h.

39{ return _center; }

References _center.

Referenced by MinimalBoundingSphere(), and MinimalBoundingSphere().

◆ getRadius()

double GeoLib::MinimalBoundingSphere::getRadius ( ) const

inline

Returns the radius of the sphere.

Definition at line 42 of file MinimalBoundingSphere.h.

42{ return _radius; }

References _radius.

Referenced by MinimalBoundingSphere(), MinimalBoundingSphere(), and MeshToolsLib::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 183 of file MinimalBoundingSphere.cpp.

{
    return MathLib::sqrDist(_center, pnt) - (_radius * _radius);
}

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

{
    MinimalBoundingSphere sphere;
    switch (n_boundary_points)
    {
        case 0:
            sphere = MinimalBoundingSphere();
            break;
        case 1:
            sphere = MinimalBoundingSphere(*sphere_points[start_idx - 1]);
            break;
        case 2:
            sphere = MinimalBoundingSphere(*sphere_points[start_idx - 1],
                                           *sphere_points[start_idx - 2]);
            break;
        case 3:
            sphere = MinimalBoundingSphere(*sphere_points[start_idx - 1],
                                           *sphere_points[start_idx - 2],
                                           *sphere_points[start_idx - 3]);
            break;
        case 4:
            sphere = MinimalBoundingSphere(
                *sphere_points[start_idx - 1], *sphere_points[start_idx - 2],
                *sphere_points[start_idx - 3], *sphere_points[start_idx - 4]);
            return sphere;
    }
 
    for (std::size_t i = 0; i < length; ++i)
    {
        // current point is located outside of sphere
        if (sphere.pointDistanceSquared(*sphere_points[start_idx + i]) > 0)
        {
            if (i > start_idx)
            {
                using DiffType =
                    std::vector<MathLib::Point3d*>::iterator::difference_type;
                std::vector<MathLib::Point3d*> const tmp_ps(
                    sphere_points.cbegin() + static_cast<DiffType>(start_idx),
                    sphere_points.cbegin() +
                        static_cast<DiffType>(start_idx + i + 1));
                std::copy(tmp_ps.cbegin(), --tmp_ps.cend(),
                          sphere_points.begin() +
                              static_cast<DiffType>(start_idx + 1));
                sphere_points[start_idx] = tmp_ps.back();
            }
            sphere = recurseCalculation(sphere_points, start_idx + 1, i,
                                        n_boundary_points + 1);
        }
    }
    return sphere;
}

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

Referenced by recurseCalculation().

Member Data Documentation

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

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

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

◆ _radius

double GeoLib::MinimalBoundingSphere::_radius {-1}

private

Definition at line 75 of file MinimalBoundingSphere.h.

75{-1};

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

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

Detailed Description

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Constructor & Destructor Documentation

◆ MinimalBoundingSphere() [1/6]

◆ MinimalBoundingSphere() [2/6]

◆ MinimalBoundingSphere() [3/6]

◆ MinimalBoundingSphere() [4/6]

◆ MinimalBoundingSphere() [5/6]

◆ MinimalBoundingSphere() [6/6]

Member Function Documentation

◆ getCenter()

◆ getRadius()

◆ pointDistanceSquared()

◆ recurseCalculation()

Member Data Documentation

◆ _center

◆ _radius