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 five, and all its points lie on the boundary of . If has more than five 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_ellipse_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. | |
| ||
| Ellipse type. |
The following types denote iterators that allow to traverse all points and support points of the smallest enclosing ellipse, 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_ellipse_2<Traits> object can be created from an arbitrary point set and by specialized construction methods expecting no, one, two, three, four or five points as arguments. The latter methods can be useful for reconstructing from a given support set of .
| |||
| |||
creates a variable min_ellipse of type
CGAL_Min_ellipse_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_ellipse of type
CGAL_Min_ellipse_2<Traits>. It is initialized to
Ø, the empty set.
Postcondition: min_ellipse .is_empty() = true.
| |||
| |||
creates a variable min_ellipse of type
CGAL_Min_ellipse_2<Traits>. It is initialized to
, the set .
Postcondition: min_ellipse .is_degenerate() = true.
| |||
| |||
creates a variable min_ellipse of type
CGAL_Min_ellipse_2<Traits>. It is initialized to
, the set
(1-l)p + l q | 0 <= l <= 1.
Postcondition: min_ellipse .is_degenerate() = true.
| |||
| |||
creates a variable min_ellipse of type
CGAL_Min_ellipse_2<Traits>. It is initialized to
.
| |||
| |||
creates a variable min_ellipse of type
CGAL_Min_ellipse_2<Traits>. It is initialized to
.
| |||
| |||
creates a variable min_ellipse of type
CGAL_Min_ellipse_2<Traits>. It is initialized to
.
|
|
| |
returns the number of points of min_ellipse, i.e. . | ||
|
| |
returns the number of support points of min_ellipse, i.e. . | ||
|
| |
returns an iterator referring to the first point of min_ellipse. | ||
|
| |
returns the corresponding past-the-end iterator. | ||
| ||
| ||
returns an iterator referring to the first support point of min_ellipse. | ||
| ||
| ||
returns the corresponding past-the-end iterator. | ||
|
| |
returns the i-th support point of min_ellipse.
Between two modifying operations (see below) any call to
min_ellipse.support_point(i) with the same i
returns the same point.
Precondition: min_ellipse.number_of_support_points(). | ||
|
| |
returns the current ellipse of min_ellipse. |
|
| |
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_ellipse, resp. | ||
|
| |
returns true, iff p lies properly inside min_ellipse. | ||
|
| |
returns true, iff p lies on the boundary of min_ellipse. | ||
|
| |
returns true, iff p lies outside of min_ellipse. | ||
|
| |
returns true, iff min_ellipse is empty (this implies degeneracy). | ||
|
| |
returns true, iff min_ellipse is degenerate, i.e. if min_ellipse is empty, equal to a single point or equal to a segment, equivalently if the number of support points is less than 3. |
|
| |||
inserts p into min_ellipse and recomputes the smallest enclosing ellipse. | ||||
| ||||
|
| |||
inserts the points in the range [first,last) into
min_ellipse and recomputes the smallest enclosing ellipse 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_ellipse and sets
min_ellipse to the empty set.
Postcondition: min_ellipse .is_empty() = true. |
An object min_ellipse is valid, iff
Using the traits class implementation for the CGAL kernel with exact arithmetic as described in Section guarantees validity of min_ellipse. The following function is mainly intended for debugging user supplied traits classes but also for convincing the anxious user that the traits class implementation is correct.
|
| |||
returns true, iff min_ellipse contains all points of its defining set . 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_ellipse to window stream ws.
Precondition: The window stream output operator is defined for Point and Ellipse. |
#include <CGAL/Gmpz.h> #include <CGAL/Homogeneous.h> #include <CGAL/Point_2.h> #include <CGAL/Min_ellipse_2_traits_2.h> #include <CGAL/Min_ellipse_2.h> typedef CGAL_Gmpz NT; typedef CGAL_Homogeneous<NT> R; typedef CGAL_Point_2<R> Point; typedef CGAL_Min_ellipse_2_traits_2<R> Traits; typedef CGAL_Min_ellipse_2<Traits> Min_ellipse; 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_ellipse me1( P, P+n); // very slow Min_ellipse me2( P, P+n, true); // fast delete[] P; return( 0); }