2D Smallest Enclosing Circle (Min_circle_2)

Definition

An object of the class Min_circle_2<Traits> is the unique circle of smallest area enclosing a finite set of points in the two-dimensional Euclidean plane $$ ₂. 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)=Ø$$ if $$P=Ø$$ 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). If $$mc(P) has more than three points on the boundary, 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.

Note: In this release correct results are only guaranteed if exact arithmetic is used.

#include <CGAL/Min_circle_2.h>

Traits Class

The template parameter Traits is a traits class that defines the abstract interface between the optimisation algorithm and the primitives it uses. For example Traits::Point is a mapping on a point class. Think of it as 2D points in the Euclidean plane.

We provide a traits class implementation using the 2D CGAL-kernel as described in Section . Traits class adapters to user supplied point classes are available, see Sections  and . Customizing own traits classes for optimisation algorithms can be done according to the requirements for traits classes listed in Section .

Guidelines and Hints

For ultimate speed, use the representation type Cartesian<float> or Cartesian<double>. For exact number types NT, we recommend the homogeneous representation Homogeneous<NT>, even if NT is a field type and supports divsions; the latter are usually slower than the other arithmetic operations, and it pays off to avoid them by using the homogeneous representation.

Because an object of type Min_circle_2<Traits> is of non-constant size, copy and assignment are expensive. Use references whenever possible.

Types

Min_circle_2<Traits>::Traits

typedef Traits::Point
	Point;	Point type.
typedef Traits::Circle
	Circle;	Circle type.

The following types denote iterators that allow to traverse all points and support points of the smallest enclosing circle, resp. The iterators are non-mutable and their value type is Point. The iterator category is given in parentheses.

Min_circle_2<Traits>::Point_iterator
	(bidirectional).
Min_circle_2<Traits>::Support_point_iterator
	(random access).

Creation

A Min_circle_2<Traits> 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<Traits> min_circle ( InputIterator first, InputIterator last, bool randomize, Random& random = default_random, Traits traits = Traits());
	creates a variable min_circle of type Min_circle_2<Traits>. It is initialized 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). Precondition: The value type of first and last is Point.
Min_circle_2<Traits> min_circle ( Traits traits = Traits());
	creates a variable min_circle of type Min_circle_2<Traits>. It is initialized to $$mc(Ø$$), the empty set. Postcondition: min_circle.is_empty() = true.
Min_circle_2<Traits> min_circle ( Point p, Traits traits = Traits());
	creates a variable min_circle of type Min_circle_2<Traits>. It is initialized to $$mc({p}), the set $${p}. Postcondition: min_circle.is_degenerate() = true.
Min_circle_2<Traits> min_circle ( Point p1, Point p2, Traits traits = Traits());
	creates a variable min_circle of type Min_circle_2<Traits>. It is initialized to $$mc({p1,p2}), the circle with diameter equal to the segment connecting $$p1 and $$p2.
Min_circle_2<Traits> min_circle ( Point p1, Point p2, Point p3, Traits traits = Traits());
	creates a variable min_circle of type Min_circle_2<Traits>. It is initialized to $$mc({p1,p2,p3}).

Access Functions

int	min_circle.number_of_points ()
		returns the number of points of min_circle, i.e. $$|P|.
int	min_circle.number_of_support_points ()
		returns the number of support points of min_circle, i.e. $$|S|.
Point_iterator	min_circle.points_begin ()
		returns an iterator referring to the first point of min_circle.
Point_iterator	min_circle.points_end ()
		returns the corresponding past-the-end iterator.
Support_point_iterator
	min_circle.support_points_begin ()
		returns an iterator referring to the first support point of min_circle.
Support_point_iterator
	min_circle.support_points_end ()
		returns the corresponding past-the-end iterator.
Point	min_circle.support_point ( int i)
		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 i< min_circle.number_of_support_points()$$.
Circle	min_circle.circle ()
		returns the current circle of min_circle.

Predicates

By definition, an empty Min_circle_2<Traits> has no boundary and no bounded side, i.e. its unbounded side equals the whole plane $$ ₂.

Bounded_side	min_circle.bounded_side ( Point p)
		returns ON_BOUNDED_SIDE, ON_BOUNDARY, or ON_UNBOUNDED_SIDE iff p lies properly inside, on the boundary of, or properly outside of min_circle, resp.
bool	min_circle.has_on_bounded_side ( Point p)
		returns true, iff p lies properly inside min_circle.
bool	min_circle.has_on_boundary ( Point p)
		returns true, iff p lies on the boundary of min_circle.
bool	min_circle.has_on_unbounded_side ( Point p)
		returns true, iff p lies properly outside of min_circle.
bool	min_circle.is_empty ()
		returns true, iff min_circle is empty (this implies degeneracy).
bool	min_circle.is_degenerate ()
		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	min_circle.insert ( Point p)
		inserts p into min_circle and recomputes the smallest enclosing circle.
template < class InputIterator >
void	min_circle.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). Precondition: The value type of first and last is Point.

Note: In case a compiler does not support member templates yet, we provide specialized insert functions instead. In the current release there are insert functions for C arrays (using pointers as iterators), for the STL sequence containers vector<Point> and list<Point> and for the STL input stream iterator istream_iterator<Point>.

void	min_circle.clear ()
		deletes all points in min_circle and sets min_circle to the empty set. Postcondition: min_circle.is_empty() = true.

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	min_circle.is_valid ( bool verbose = false, int level = 0)
		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.

Miscellaneous

Traits	min_circle.traits ()
		returns a const reference to the traits class object.

I/O

ostream&	ostream& os << min_circle
		writes min_circle to output stream os. Precondition: The output operator is defined for Point (and for Circle, if pretty printing is used).
istream&	istream& is >> & min_circle
		reads min_circle from input stream is. Precondition: The input operator is defined for Point.

#include <CGAL/IO/Window_stream.h>

Window_stream&	Window_stream& ws << min_circle
		writes min_circle to window stream ws. Precondition: The window stream output operator is defined for Point and Circle.

See Also

Min_circle_2_traits_2 , Min_circle_2_adapterC2 , Min_circle_2_adapterH2 , Min_ellipse_2 , Min_sphere_d .

Implementation

We implement the algorithm of Welzl, with move-to-front heuristic [Wel91]. The whole implementation is described in [GS98a]. 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<Traits> and to show that randomization can be useful in certain cases, we give an example.

#include <CGAL/Gmpz.h>
#include <CGAL/Homogeneous.h>
#include <CGAL/Point_2.h>
#include <CGAL/Min_circle_2_traits_2.h>
#include <CGAL/Min_circle_2.h>

using namespace CGAL;

typedef  Gmpz                      NT;
typedef  Homogeneous<NT>           R;
typedef  Point_2<R>                Point;
typedef  Min_circle_2_traits_2<R>  Traits;
typedef  Min_circle_2<Traits>      Min_circle;

int main()
{
    int     n = 1000;
    Point*  P = new Point[ 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);           // very slow
    Min_circle  mc2( P, P+n, true);     // fast

    delete[] P;
    return( 0);
}