\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.14 - Bounding Volumes
List of all members | Related Functions
CGAL::Min_circle_2< Traits > Class Template Reference
Bounding Volumes Reference

#include <CGAL/Min_circle_2.h>

Definition

An object of the class Min_circle_2 is the unique circle of smallest area enclosing a finite (multi)set of points in two-dimensional 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 inclusion-minimal 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.

Please note: This class is (almost) obsolete. The class CGAL::Min_sphere_of_spheres_d<Traits> solves a more general problem and is faster then 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 floating-point arithmetic which ensures correct results in a large number of cases (including highly degenerate ones). In contrast, Min_circle_2 is not tuned for floating-point 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 division-free. Thus, Min_circle_2 might still be an option in case your input number type cannot (efficiently) divide.

Template Parameters
Traitsmust be a model for MinCircle2Traits.

We provide the model CGAL::Min_circle_2_traits_2 using the two-dimensional CGAL kernel.

See also
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 move-to-front 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

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Min_circle_2.h>
#include <CGAL/Min_circle_2_traits_2.h>
#include <iostream>
// typedefs
typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef CGAL::Min_circle_2_traits_2<K> Traits;
typedef CGAL::Min_circle_2<Traits> Min_circle;
typedef K::Point_2 Point;
int
main( int, char**)
{
const int n = 100;
Point P[n];
for ( int i = 0; i < n; ++i)
P[ i] = Point( (i%2 == 0 ? i : -i), 0);
// (0,0), (-1,0), (2,0), (-3,0), ...
Min_circle mc1( P, P+n, false); // very slow
Min_circle mc2( P, P+n, true); // fast
CGAL::set_pretty_mode( std::cout);
std::cout << mc2;
return 0;
}
Examples:
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
 non-mutable model of the STL concept BidirectionalIterator with value type Point. More...
 
typedef unspecified_type Support_point_iterator
 non-mutable model of the STL concept RandomAccessIterator with value type Point. More...
 

Creation

A Min_circle_2 object can be created from an arbitrary point set \( P\) and by specialized construction methods expecting no, one, two or three points as arguments.

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 past-the-end 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 past-the-end 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 Min_circle_2 has no boundary and no bounded side, i.e. its unbounded side equals the whole space \( \E^2\).

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 min_circle, allowing to build \( mc(P)\) incrementally, e.g.

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 min_circle is valid, iff

  • min_circle contains all points of its defining set \( P\),
  • min_circle is the smallest circle spanned by its support set \( S\), and
  • \( S\) is minimal, i.e. no support point is redundant.
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.
 

Member Typedef Documentation

◆ Point_iterator

template<typename Traits>
typedef unspecified_type CGAL::Min_circle_2< Traits >::Point_iterator

non-mutable model of the STL concept BidirectionalIterator with value type Point.

Used to access the points of the smallest enclosing circle.

◆ Support_point_iterator

template<typename Traits>
typedef unspecified_type CGAL::Min_circle_2< Traits >::Support_point_iterator

non-mutable model of the STL concept RandomAccessIterator with value type Point.

Used to access the support points of the smallest enclosing circle.

Constructor & Destructor Documentation

◆ Min_circle_2() [1/3]

template<typename Traits>
template<class InputIterator >
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).

Template Parameters
InputIteratormust be a model of InputIterator with Point as value type.

◆ Min_circle_2() [2/3]

template<typename Traits>
CGAL::Min_circle_2< Traits >::Min_circle_2 ( const Traits &  traits = Traits())

initializes min_circle to \( mc(\emptyset)\), the empty set.

Postcondition
min_circle.is_empty() = true.

◆ Min_circle_2() [3/3]

template<typename Traits>
CGAL::Min_circle_2< Traits >::Min_circle_2 ( const Point &  p,
const Traits &  traits = Traits() 
)

initializes min_circle to \( mc(\{p\})\), the set \( \{p\}\).

Postcondition
min_circle.is_degenerate() = true.

Member Function Documentation

◆ clear()

template<typename Traits>
void CGAL::Min_circle_2< Traits >::clear ( )

deletes all points in min_circle and sets min_circle to the empty set.

Postcondition
min_circle.is_empty() = true.

◆ insert()

template<typename Traits>
template<class InputIterator >
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).

Template Parameters
InputIteratormust be a model of InputIterator with Point as value type.

◆ is_valid()

template<typename Traits>
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.

◆ support_point()

template<typename Traits>
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.

Precondition
\( 0 \leq i< \) min_circle.number_of_support_points().

Friends And Related Function Documentation

◆ operator
template<typename Traits>
std::ostream & operator<< ( std::ostream &  os,
const Min_circle_2< Traits > &  min_circle 
)
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).

◆ operator>>()

template<typename Traits>
std::istream & operator>> ( std::istream &  is,
Min_circle_2< Traits > min_circle &   
)
related

reads min_circle from input stream is.

An overload of operator>> must be defined for Point.