CGAL  Bounding Volumes

#include <CGAL/Min_sphere_of_spheres_d.h>
An object of the class Min_sphere_of_spheres_d
is a data structure that represents the unique sphere of smallest volume enclosing a finite set of spheres in \( d\)dimensional Euclidean space \( \E^d\).
For a set \( S\) of spheres we denote by \( ms(S)\) the smallest sphere that contains all spheres of \( S\); we call \( ms(S)\) the minsphere of \( S\). \( ms(S)\) can be degenerate, i.e., \( ms(S)=\emptyset\), if \( S=\emptyset\) and \( ms(S)=\{s\}\), if \( S=\{s\}\). Any sphere in \( S\) may be degenerate, too, i.e., any sphere from \( S\) may be a point. Also, \( S\) may contain several copies of the same sphere.
An inclusionminimal subset \( R\) of \( S\) with \( ms(R)=ms(S)\) is called a support set for \( ms(S)\); the spheres in \( R\) are the support spheres. A support set has size at most \( d+1\), and all its spheres lie on the boundary of \( ms(S)\). (A sphere \( s'\) is said to lie on the boundary of a sphere \( s\), if \( s'\) is contained in \( s\) and if their boundaries intersect.) In general, the support set is not unique.
The algorithm computes the center and the radius of \( ms(S)\), and finds a support set \( R\) (which remains fixed until the next insert()
, clear()
or set()
operation). We also provide a specialization of the algorithm for the case when the center coordinates and radii of the input spheres are floatingpoint numbers. This specialized algorithm uses floatingpoint arithmetic only, is very fast and especially tuned for stability and robustness. Still, it's output may be incorrect in some (rare) cases; termination is guaranteed.
When default constructed, an instance of type Min_sphere_of_spheres_d<Traits>
represents the set \( S=\emptyset\), together with its minsphere \( ms(S)=\emptyset\). You can add spheres to the set \( S\) by calling insert()
. Querying the minsphere is done by calling the routines is_empty()
, radius()
and center_cartesian_begin()
, among others.
In general, the radius and the Euclidean center coordinates of \( ms(S)\) need not be rational. Consequently, the algorithm computing the exact minsphere will have to deal with algebraic numbers. Fortunately, both the radius and the coordinates of the minsphere are numbers of the form \( a_i+b_i\sqrt{t}\), where \( a_i,b_i,t\in \Q\) and where \( t\ge 0\) is the same for all coordinates and the radius. Thus, the exact minsphere can be described by the number \( t\), which is called the sphere's discriminant, and by \( d+1\) pairs \( (a_i,b_i)\in\Q^2\) (one for the radius and \( d\) for the center coordinates).
Note: This class (almost) replaces CGAL::Min_sphere_d<Traits>
, which solves the less general problem of finding the smallest enclosing ball of a set of points. Min_sphere_of_spheres_d
is faster than CGAL::Min_sphere_d<Traits>
, and in contrast to the latter provides a specialized implementation for floatingpoint arithmetic which ensures correct results in a large number of cases (including highly degenerate ones). The only advantage of CGAL::Min_sphere_d<Traits>
over Min_sphere_of_spheres_d
is that the former can deal with points in homogeneous coordinates, in which case the algorithm is divisionfree. Thus, CGAL::Min_sphere_d<Traits>
might still be an option in case your input number type cannot (efficiently) divide.
Traits  must be a model of the concept MinSphereOfSpheresTraits as its template argument. 
CGAL::Min_sphere_d<Traits>
CGAL::Min_circle_2<Traits>
Implementation
We implement two algorithms, the LPalgorithm and a heuristic [11]. As described in the documentation of concept MinSphereOfSpheresTraits
, each has its advantages and disadvantages: Our implementation of the LPalgorithm has maximal expected running time \( O(2^d n)\), while the heuristic comes without any complexity guarantee. In particular, the LPalgorithm runs in linear time for fixed dimension \( d\). (These running times hold for the arithmetic model, so they count the number of operations on the number type FT
.)
On the other hand, the LPalgorithm is, for inexact number types FT
, much worse at handling degeneracies and should therefore not be used in such a case. (For exact number types FT
, both methods handle all kinds of degeneracies.)
Currently, we require Traits::FT
to be either an exact number type or double
or float
; other inexact number types are not supported at this time. Also, the current implementation only handles spheres with Cartesian coordinates; homogenous representation is not supported yet.
Example
File Min_sphere_of_spheres_d/min_sphere_of_spheres_d_d.cpp
Types  
typedef unspecified_type  Sphere 
is a typedef to Traits::Sphere .  
typedef unspecified_type  FT 
is a typedef to Traits::FT .  
typedef unspecified_type  Result 
is the type of the radius and of the center coordinates of the computed minsphere: When FT is an inexact number type (double , for instance), then Result is simply FT . More...  
typedef unspecified_type  Algorithm 
is either CGAL::LP_algorithm or CGAL::Farthest_first_heuristic . More...  
typedef unspecified_type  Support_iterator 
nonmutable model of the STL concept BidirectionalIterator with value type Sphere . More...  
typedef unspecified_type  Cartesian_const_iterator 
nonmutable model of the STL concept BidirectionalIterator to access the center coordinates of the minsphere.  
Creation  
Min_sphere_of_spheres_d (const Traits &traits=Traits())  
creates a variable of type Min_sphere_of_spheres_d and initializes it to \( ms(\emptyset)\). More...  
template<typename InputIterator >  
Min_sphere_of_spheres_d (InputIterator first, InputIterator last, const Traits &traits=Traits())  
creates a variable minsphere of type Min_sphere_of_spheres_d and inserts (cf. More...  
Access Functions  
Support_iterator  support_begin () const 
returns an iterator referring to the first support sphere of minsphere .  
Support_iterator  support_end () const 
returns the corresponding pasttheend iterator.  
const FT &  discriminant () const 
returns the discriminant of minsphere . More...  
Result  radius () const 
returns the radius of minsphere . More...  
Cartesian_const_iterator  center_cartesian_begin () const 
returns a constiterator to the first of the Traits::D center coordinates of minsphere . More...  
Cartesian_const_iterator  center_cartesian_end () const 
returns the corresponding pasttheend iterator, i.e. center_cartesian_begin()+Traits::D . More...  
Predicates  
bool  is_empty () const 
returns true , iff minsphere is empty, i.e. iff \( ms(S)=\emptyset\).  
Modifiers  
void  clear () 
resets minsphere to \( ms(\emptyset)\), with \( S:= \emptyset\).  
template<class InputIterator >  
void  set (InputIterator first, InputIterator last) 
sets minsphere to the \( ms(S)\), where \( S\) is the set of spheres in the range [first ,last ). More...  
void  insert (const Sphere &s) 
inserts the sphere s into the set \( S\) of instance minsphere .  
template<class InputIterator >  
void  insert (InputIterator first, InputIterator last) 
inserts the spheres in the range [first ,last ) into the set \( S\) of instance minsphere . More...  
Validity Check  
An object
 
bool  is_valid () const 
returns true , iff minsphere is valid. More...  
Miscellaneous  
const Traits &  traits () const 
returns a const reference to the traits class object.  
typedef unspecified_type CGAL::Min_sphere_of_spheres_d< Traits >::Algorithm 
is either CGAL::LP_algorithm
or CGAL::Farthest_first_heuristic
.
As is described in the documentation of concept MinSphereOfSpheresTraits
, the type Algorithm
reflects the method which is used to compute the minsphere. (Normally, Algorithm
coincides with Traits::Algorithm
. However, if the method Traits::Algorithm
should not be supported anymore in a future release, then Algorithm
will have another type.)
typedef unspecified_type CGAL::Min_sphere_of_spheres_d< Traits >::Result 
is the type of the radius and of the center coordinates of the computed minsphere: When FT
is an inexact number type (double
, for instance), then Result
is simply FT
.
However, when FT
is an exact number type, then Result
is a typedef to a derived class of std::pair<FT,FT>
; an instance of this type represents the number \( a+b\sqrt{t}\), where \( a\) is the first and \( b\) the second element of the pair and where the number \( t\) is accessed using the member function discriminant()
of class Min_sphere_of_spheres_d<Traits>
.
typedef unspecified_type CGAL::Min_sphere_of_spheres_d< Traits >::Support_iterator 
nonmutable model of the STL concept BidirectionalIterator
with value type Sphere
.
Used to access the support spheres defining the smallest enclosing sphere.
CGAL::Min_sphere_of_spheres_d< Traits >::Min_sphere_of_spheres_d  (  const Traits &  traits = Traits() ) 
creates a variable of type Min_sphere_of_spheres_d
and initializes it to \( ms(\emptyset)\).
If the traits parameter is not supplied, the class Traits
must provide a default constructor.
CGAL::Min_sphere_of_spheres_d< Traits >::Min_sphere_of_spheres_d  (  InputIterator  first, 
InputIterator  last,  
const Traits &  traits = Traits() 

) 
creates a variable minsphere
of type Min_sphere_of_spheres_d
and inserts (cf.
insert()
) the spheres from the range [first
,last
).
InputIterator  is a model of InputIterator with Sphere as value type. If the traits parameter is not supplied, the class Traits must provide a default constructor. 
Cartesian_const_iterator CGAL::Min_sphere_of_spheres_d< Traits >::center_cartesian_begin  (  )  const 
returns a constiterator to the first of the Traits::D
center coordinates of minsphere
.
The iterator returns objects of type Result
. If FT
is an exact number type, then a center coordinate is represented by a pair \( (a,b)\) describing the real number \( a+b\sqrt{t}\), where \( t\) is the minsphere's discriminant (cf. discriminant()
).
minsphere
is not empty. Cartesian_const_iterator CGAL::Min_sphere_of_spheres_d< Traits >::center_cartesian_end  (  )  const 
returns the corresponding pasttheend iterator, i.e. center_cartesian_begin()+Traits::D
.
minsphere
is not empty. const FT& CGAL::Min_sphere_of_spheres_d< Traits >::discriminant  (  )  const 
returns the discriminant of minsphere
.
This number is undefined when FT
is an inexact number type. When FT
is exact, the center coordinates and the radius of the minsphere are numbers of the form \( a+b\sqrt{t}\), where \( t\) is the discriminant of the minsphere as returned by this function.
minsphere
is not empty, and FT
is an exact number type. void CGAL::Min_sphere_of_spheres_d< Traits >::insert  (  InputIterator  first, 
InputIterator  last  
) 
inserts the spheres in the range [first
,last
) into the set \( S\) of instance minsphere
.
InputIterator  is a model of InputIterator with Sphere as value type. 
bool CGAL::Min_sphere_of_spheres_d< Traits >::is_valid  (  )  const 
returns true
, iff minsphere
is valid.
When FT
is inexact, this routine always returns true
.
Result CGAL::Min_sphere_of_spheres_d< Traits >::radius  (  )  const 
returns the radius of minsphere
.
If FT
is an exact number type then the radius of the minsphere is the real number \( a+b\sqrt{t}\), where \( t\) is the minsphere's discriminant, \( a\) is the first and \( b\) the second component of the pair returned by radius()
.
minsphere
is not empty. void CGAL::Min_sphere_of_spheres_d< Traits >::set  (  InputIterator  first, 
InputIterator  last  
) 
sets minsphere
to the \( ms(S)\), where \( S\) is the set of spheres in the range [first
,last
).
InputIterator  is a model of InputIterator with Sphere as value type. 