CGAL 6.1.1 - Bounding Volumes

Loading...
Searching...
No Matches
List of all members | Related Functions
CGAL::Min_circle_2< Traits > Class Template Reference
Reference Manual

`#include <CGAL/Min_circle_2.h>`

## Definition

template<typename Traits>
class CGAL::Min_circle_2< Traits >

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.

Note
  This class is (almost) obsolete. The class `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 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

  Traits | must 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/Simple_cartesian.h>
#include <CGAL/Min_sphere_of_spheres_d.h>
#include <CGAL/Min_sphere_of_points_d_traits_2.h>
#include <CGAL/Random.h>
#include <iostream>
#include <array>
typedef CGAL::Simple_cartesian<double> K;
typedef CGAL::Min_sphere_of_points_d_traits_2<K,double> Traits;
typedef CGAL::Min_sphere_of_spheres_d<Traits> Min_circle;
typedef K::Point_2 Point;
int
main( int, char**)
{
const int n = 100;
std::array<Point, n> P;
CGAL::Random r; // random number generator
for ( int i = 0; i < n; ++i){
P.at(i) = Point(r.get_double(), r.get_double());
}
Min_circle mc( P.begin(), P.end());
Min_circle::Cartesian_const_iterator ccib = mc.center_cartesian_begin(), ccie = mc.center_cartesian_end();
std::cout << "center:";
for( ; ccib != ccie; ++ccib){
std::cout << " " << *ccib;
}
std::cout << std::endl << "radius: " << mc.radius() << std::endl;
return 0;
}
CGAL::Min_circle_2::Point
unspecified_type Point
typedef to Traits::Point.
Definition: Min_circle_2.h:84
CGAL::Min_sphere_of_points_d_traits_2
The class Min_sphere_of_points_d_traits_2<K,FT,UseSqrt,Algorithm> is a model for concept MinSphereOfS...
Definition: Min_sphere_of_points_d_traits_2.h:33
CGAL::Min_sphere_of_spheres_d
An object of the class Min_sphere_of_spheres_d is a data structure that represents the unique sphere ...
Definition: Min_sphere_of_spheres_d.h:102
CGAL::Simple_cartesian

Examples
  Min_circle_2/min_circle_homogeneous_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`.
std::istream & | operator>> (std::istream &is, Min_circle_2< Traits > min_circle &)
| reads `min_circle` from input stream `is`.

## 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`.
typedef unspecified_type | Support_point_iterator
| non-mutable model of the STL concept RandomAccessIterator with value type `Point`.

## 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`).
| Min_circle_2 (const Traits &traits=Traits())
| initializes `min_circle` to \( mc(\emptyset)\), the empty set.
| Min_circle_2 (const Point &p, const Traits &traits=Traits())
| initializes `min_circle` to \( mc(\{p\})\), the set \( \{p\}\).
| 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`.
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`).
void | clear ()
| deletes all points in `min_circle` and sets `min_circle` to the empty set.

## 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.

## 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

  InputIterator | must 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

  InputIterator | must 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`.