An object of the class Min_ellipse_2<Traits> is the unique ellipse of smallest area enclosing a finite set of points in twodimensional euclidean space $$ _{2}. For a point set $$P we denote by $$me(P) the smallest ellipse that contains all points of $$P. Note that $$me(P) can be degenerate, i.e. $$me(P)=Ø$$ if $$P=Ø$$, $$me(P)={p} if $$P={p}, and $$me(P) = { (1l)p + l q  0 <= l <= 1$$ } if $$P={p,q}.
An inclusionminimal subset $$S of $$P with $$me(S)=me(P) is called a support set, the points in $$S are the support points. A support set has size at most five, and all its points lie on the boundary of $$me(P). If $$me(P) 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. $$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_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 2D CGALkernel 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 .
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_ellipse_2<Traits> is of nonconstant size, copy and assignment are expensive. Use references whenever possible.

 
 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 nonmutable and their value type is Point. The iterator category is given in parentheses.
 
(bidirectional).
 
 
(random access).

A Min_ellipse_2<Traits> object can be created from an arbitrary point set $$P and by specialized construction methods expecting no, one, two, three, four or five points as arguments. The latter methods can be useful for reconstructing $$me(P) from a given support set $$S of $$P.
 
 
creates a variable min_ellipse of type Min_ellipse_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.

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 Min_ellipse_2<Traits>.
It is initialized to
$$me(Ø$$), the empty set. Postcondition: min_ellipse.is_empty() = true.
 
 
creates a variable min_ellipse of type Min_ellipse_2<Traits>.
It is initialized to $$me({p}), the set $${p}. Postcondition: min_ellipse.is_degenerate() = true.
 
 
creates a variable min_ellipse of type Min_ellipse_2<Traits>.
It is initialized to $$me({p,q}), the set
$${ (1l)p + l q  0 <= l <= 1$$ }. Postcondition: min_ellipse.is_degenerate() = true.
 
 
creates a variable min_ellipse of type Min_ellipse_2<Traits>.
It is initialized to $$me({p1,p2,p3}).
 
 
creates a variable min_ellipse of type Min_ellipse_2<Traits>.
It is initialized to $$me({p1,p2,p3,p4}).
 
 
creates a variable min_ellipse of type Min_ellipse_2<Traits>.
It is initialized to $$me({p1,p2,p3,p4,p5}).


 
returns the number of points of min_ellipse, i.e. $$P.  

 
returns the number of support points of min_ellipse, i.e. $$S.  

 
returns an iterator referring to the first point of min_ellipse.  

 
returns the corresponding pasttheend iterator.  
 
 
returns an iterator referring to the first support point of min_ellipse.  
 
 
returns the corresponding pasttheend iterator.  

 
returns the ith 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: $$0 i< min_ellipse.number_of_support_points()$$.  

 
returns the current ellipse of min_ellipse. 
By definition, an empty Min_ellipse_2<Traits> has no boundary and no bounded side, i.e. its unbounded side equals the whole plane $$ _{2}.

 
returns ON_BOUNDED_SIDE, ON_BOUNDARY, or ON_UNBOUNDED_SIDE iff p lies properly inside, on the boundary of, 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 properly 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. 
New points can be added to an existing min_ellipse, allowing to build $$me(P) incrementally, e.g. if $$P is not known in advance. Compared to the direct creation of $$me(P), this is not much slower, because the construction method is incremental itself.

 
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 2D CGALkernel 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 $$P. 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. 
Min_circle_2 , Min_ellipse_2_traits_2 , Min_ellipse_2_adapterC2 , Min_ellipse_2_adapterH2 .
We implement the algorithm of Welzl, with movetofront heuristic [Wel91], using the primitives as described in [GS97a, GS97b]. The whole implementation is described in [GS98b]. 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 ellipse from scratch. The clear operation and the check for validity each takes linear time.
To illustrate the creation of Min_ellipse_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_ellipse_2_traits_2.h> #include <CGAL/Min_ellipse_2.h> using namespace CGAL; typedef Gmpz NT; typedef Homogeneous<NT> R; typedef Point_2<R> Point; typedef Min_ellipse_2_traits_2<R> Traits; typedef 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); }