CGAL 5.4  Bounding Volumes

#include <CGAL/Min_circle_2.h>
An object of the class Min_circle_2
is the unique circle of smallest area enclosing a finite (multi)set of points in twodimensional Euclidean space \( \E^2\).
For a point set \( P\) we denote by \( mc(P)\) the smallest circle that contains all points of \( P\). Note that \( mc(P)\) can be degenerate, i.e. \( mc(P)=\emptyset\) if \( P=\emptyset\) and \( mc(P)=\{p\}\) if \( P=\{p\}\).
An inclusionminimal subset \( S\) of \( P\) with \( mc(S)=mc(P)\) is called a support set, the points in \( S\) are the support points. A support set has size at most three, and all its points lie on the boundary of \( mc(P)\). In general, neither the support set nor its size are necessarily unique.
The underlying algorithm can cope with all kinds of input, e.g. \( P\) may be empty or points may occur more than once. The algorithm computes a support set \( S\) which remains fixed until the next insert or clear operation.
CGAL::Min_sphere_of_spheres_d<Traits>
solves a more general problem and is faster than Min_circle_2
even if used only for points in two dimensions as input. Most importantly, CGAL::Min_sphere_of_spheres_d<Traits>
has a specialized implementation for floatingpoint arithmetic which ensures correct results in a large number of cases (including highly degenerate ones). In contrast, Min_circle_2
is not tuned for floatingpoint computations. The only advantage of Min_circle_2
over CGAL::Min_sphere_of_spheres_d<Traits>
is that the former can deal with points in homogeneous coordinates, in which case the algorithm is divisionfree. Thus, Min_circle_2
might still be an option in case your input number type cannot (efficiently) divide.Traits  must be a model for MinCircle2Traits . 
We provide the model CGAL::Min_circle_2_traits_2
using the twodimensional CGAL kernel.
CGAL::Min_ellipse_2<Traits>
CGAL::Min_sphere_d<Traits>
CGAL::Min_sphere_of_spheres_d<Traits>
CGAL::Min_circle_2_traits_2<K>
MinCircle2Traits
Implementation
We implement the incremental algorithm of Welzl, with movetofront heuristic [16]. The whole implementation is described in [5].
If randomization is chosen, the creation time is almost always linear in the number of points. Access functions and predicates take constant time, inserting a point might take up to linear time, but substantially less than computing the new smallest enclosing circle from scratch. The clear operation and the check for validity each takes linear time.
Example
To illustrate the creation of Min_circle_2
and to show that randomization can be useful in certain cases, we give an example.
File Min_circle_2/min_circle_2.cpp
Related Functions  
(Note that these are not member functions.)  
std::ostream &  operator<< (std::ostream &os, const Min_circle_2< Traits > &min_circle) 
writes min_circle to output stream os . More...  
std::istream &  operator>> (std::istream &is, Min_circle_2< Traits > min_circle &) 
reads min_circle from input stream is . More...  
Types  
typedef unspecified_type  Point 
typedef to Traits::Point .  
typedef unspecified_type  Circle 
typedef to Traits::Circle .  
typedef unspecified_type  Point_iterator 
nonmutable model of the STL concept BidirectionalIterator with value type Point . More...  
typedef unspecified_type  Support_point_iterator 
nonmutable model of the STL concept RandomAccessIterator with value type Point . More...  
Creation  
A The latter methods can be useful for reconstructing \( mc(P)\) from a given support set \( S\) of \( P\).  
template<class InputIterator >  
Min_circle_2 (InputIterator first, InputIterator last, bool randomize, Random &random=CGAL::get_default_random(), const Traits &traits=Traits())  
initializes min_circle to \( mc(P)\) with \( P\) being the set of points in the range [first ,last ). More...  
Min_circle_2 (const Traits &traits=Traits())  
initializes min_circle to \( mc(\emptyset)\), the empty set. More...  
Min_circle_2 (const Point &p, const Traits &traits=Traits())  
initializes min_circle to \( mc(\{p\})\), the set \( \{p\}\). More...  
Min_circle_2 (const Point &p1, const Point &p2, const Traits &traits=Traits())  
initializes min_circle to \( mc(\{p1,p2\})\), the circle with diameter equal to the segment connecting \( p1\) and \( p2\).  
Min_circle_2 (const Point &p1, const Point &p2, const Point &p3, const Traits &traits=Traits())  
initializes min_circle to \( mc(\{p1,p2,p3\})\).  
Access Functions  
int  number_of_points () const 
returns the number of points of min_circle , i.e. \( P\).  
int  number_of_support_points () const 
returns the number of support points of min_circle , i.e. \( S\).  
Point_iterator  points_begin () const 
returns an iterator referring to the first point of min_circle .  
Point_iterator  points_end () const 
returns the corresponding pasttheend iterator.  
Support_point_iterator  support_points_begin () const 
returns an iterator referring to the first support point of min_circle .  
Support_point_iterator  support_points_end () const 
returns the corresponding pasttheend iterator.  
const Point &  support_point (int i) const 
returns the i th support point of min_circle . More...  
const Circle &  circle () const 
returns the current circle of min_circle .  
Predicates  
By definition, an empty  
CGAL::Bounded_side  bounded_side (const Point &p) const 
returns CGAL::ON_BOUNDED_SIDE , CGAL::ON_BOUNDARY , or CGAL::ON_UNBOUNDED_SIDE iff p lies properly inside, on the boundary of, or properly outside of min_circle , resp.  
bool  has_on_bounded_side (const Point &p) const 
returns true , iff p lies properly inside min_circle .  
bool  has_on_boundary (const Point &p) const 
returns true , iff p lies on the boundary of min_circle .  
bool  has_on_unbounded_side (const Point &p) const 
returns true , iff p lies properly outside of min_circle .  
bool  is_empty () const 
returns true , iff min_circle is empty (this implies degeneracy).  
bool  is_degenerate () const 
returns true , iff min_circle is degenerate, i.e. if min_circle is empty or equal to a single point, equivalently if the number of support points is less than 2.  
Modifiers  
New points can be added to an existing if \( P\) is not known in advance. Compared to the direct creation of \( mc(P)\), this is not much slower, because the construction method is incremental itself.  
void  insert (const Point &p) 
inserts p into min_circle and recomputes the smallest enclosing circle.  
template<class InputIterator >  
void  insert (InputIterator first, InputIterator last) 
inserts the points in the range [first ,last ) into min_circle and recomputes the smallest enclosing circle by calling insert(p) for each point p in [first ,last ). More...  
void  clear () 
deletes all points in min_circle and sets min_circle to the empty set. More...  
Validity Check  
An object
 
bool  is_valid (bool verbose=false, int level=0) const 
returns true , iff min_circle is valid. More...  
Miscellaneous  
const Traits &  traits () const 
returns a const reference to the traits class object.  
typedef unspecified_type CGAL::Min_circle_2< Traits >::Point_iterator 
nonmutable model of the STL concept BidirectionalIterator with value type Point
.
Used to access the points of the smallest enclosing circle.
typedef unspecified_type CGAL::Min_circle_2< Traits >::Support_point_iterator 
nonmutable model of the STL concept RandomAccessIterator with value type Point
.
Used to access the support points of the smallest enclosing circle.
CGAL::Min_circle_2< Traits >::Min_circle_2  (  InputIterator  first, 
InputIterator  last,  
bool  randomize,  
Random &  random = CGAL::get_default_random() , 

const Traits &  traits = Traits() 

) 
initializes min_circle
to \( mc(P)\) with \( P\) being the set of points in the range [first
,last
).
If randomize
is true
, a random permutation of \( P\) is computed in advance, using the random numbers generator random
. Usually, this will not be necessary, however, the algorithm's efficiency depends on the order in which the points are processed, and a bad order might lead to extremely poor performance (see example below).
InputIterator  must be a model of InputIterator with Point as value type. 
CGAL::Min_circle_2< Traits >::Min_circle_2  (  const Traits &  traits = Traits()  ) 
initializes min_circle
to \( mc(\emptyset)\), the empty set.
min_circle.is_empty()
= true
. CGAL::Min_circle_2< Traits >::Min_circle_2  (  const Point &  p, 
const Traits &  traits = Traits() 

) 
initializes min_circle
to \( mc(\{p\})\), the set \( \{p\}\).
min_circle.is_degenerate()
= true
. void CGAL::Min_circle_2< Traits >::clear  (  ) 
deletes all points in min_circle
and sets min_circle
to the empty set.
min_circle.is_empty()
= true
. void CGAL::Min_circle_2< Traits >::insert  (  InputIterator  first, 
InputIterator  last  
) 
inserts the points in the range [first
,last
) into min_circle
and recomputes the smallest enclosing circle by calling insert(p)
for each point p
in [first
,last
).
InputIterator  must be a model of InputIterator with Point as value type. 
bool CGAL::Min_circle_2< Traits >::is_valid  (  bool  verbose = false , 
int  level = 0 

)  const 
returns true
, iff min_circle
is valid.
If verbose
is true
, some messages concerning the performed checks are written to standard error stream. The second parameter level
is not used, we provide it only for consistency with interfaces of other classes.
const Point& CGAL::Min_circle_2< Traits >::support_point  (  int  i  )  const 
returns the i
th support point of min_circle
.
Between two modifying operations (see below) any call to min_circle.support_point(i)
with the same i
returns the same point.
min_circle.number_of_support_points()
.

related 
writes min_circle
to output stream os
.
An overload of operator<<
must be defined for Point
(and for Circle
, if pretty printing is used).

related 
reads min_circle
from input stream is
.
An overload of operator>>
must be defined for Point
.