An inclusion-minimal subset of with is called a support set, the points in are the support points. A support set has size at most three, and all its points lie on the boundary of . If 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. may be empty or points may occur more than once. The algorithm computes a support set which remains fixed until the next insert or clear operation.
Note: In this release correct results are only guaranteed if exact arithmetic is used, see Section .
#include <CGAL/Min_circle_2.h>
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 CGAL 2D 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 .
|
| ||
| Point type. | |
| ||
| 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.
| |
(bidirectional).
| |
| |
(random access).
|
A CGAL_Min_circle_2<Traits> object can be created from an arbitrary point set and by specialized construction methods expecting no, one, two or three points as arguments. The latter methods can be useful for reconstructing from a given support set of .
| |||
| |||
creates a variable min_circle of type
CGAL_Min_circle_2<Traits>. It is initialized to
with being the set of points in
the range [first,last). If randomize is
true, a random permutation of 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.
|
Note: In case a compiler does not support member templates yet, we provide specialized constructors instead. In the current release there are constructors 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>.
| |||
creates a variable min_circle of type
CGAL_Min_circle_2<Traits>. It is initialized to
Ø, the empty set.
Postcondition: min_circle .is_empty() = true.
| |||
| |||
creates a variable min_circle of type
CGAL_Min_circle_2<Traits>. It is initialized to
, the set .
Postcondition: min_circle .is_degenerate() = true.
| |||
| |||
creates a variable min_circle of type
CGAL_Min_circle_2<Traits>. It is initialized to
, the circle with diameter equal to the
segment connecting and .
| |||
| |||
creates a variable min_circle of type
CGAL_Min_circle_2<Traits>. It is initialized to
.
|
|
| |
returns the number of points of min_circle, i.e. . | ||
|
| |
returns the number of support points of min_circle, i.e. . | ||
|
| |
returns an iterator referring to the first point of min_circle. | ||
|
| |
returns the corresponding past-the-end iterator. | ||
| ||
| ||
returns an iterator referring to the first support point of min_circle. | ||
| ||
| ||
returns the corresponding past-the-end iterator. | ||
|
| |
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: min_circle.number_of_support_points(). | ||
|
| |
returns the current circle of min_circle. |
|
| |
returns CGAL_ON_BOUNDED_SIDE, CGAL_ON_BOUNDARY, or CGAL_ON_UNBOUNDED_SIDE iff p lies properly inside, on the boundary, or properly outside of min_circle, resp. | ||
|
| |
returns true, iff p lies properly inside min_circle. | ||
|
| |
returns true, iff p lies on the boundary of min_circle. | ||
|
| |
returns true, iff p lies properly outside of min_circle. | ||
|
| |
returns true, iff min_circle is empty (this implies degeneracy). | ||
|
| |
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. |
|
| |||
inserts p into min_circle and recomputes the smallest enclosing circle. | ||||
| ||||
|
| |||
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>.
|
| |
deletes all points in min_circle and sets min_circle
to the empty set.
Postcondition: min_circle .is_empty() = true. |
An object min_circle is valid, iff
|
| |||
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. |
|
| |
returns a const reference to the traits class object. |
#include <CGAL/IO/Window_stream.h>
| ||
| ||
writes min_circle to window stream ws.
Precondition: The window stream output operator is defined for Point and Circle. |
#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> typedef CGAL_Gmpz NT; typedef CGAL_Homogeneous<NT> R; typedef CGAL_Point_2<R> Point; typedef CGAL_Min_circle_2_traits_2<R> Traits; typedef CGAL_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); }