An object of the class Min_ellipse_2<Traits> is the unique ellipse of smallest area enclosing a finite (multi)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) = { (1λ)p + λq  0 ≤ λ ≤ 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). 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.
#include <CGAL/Min_ellipse_2.h>
The template parameter Traits is a model for MinEllipse2Traits.
We provide the model CGAL::Min_ellipse_2_traits_2<K> using the twodimensional Cgal kernel.
Min_ellipse_2<Traits>::Point  
Typedef to Traits::Point .
 
Min_ellipse_2<Traits>::Ellipse  
Typedef to Traits::Ellipse. If you
are using the predefined traits class
CGAL::Min_ellipse_2_traits_2<K>,
you can access the coefficients of the ellipse, see the
documentation of CGAL::Min_ellipse_2_traits_2<K> and
the example below.
 
Min_ellipse_2<Traits>::Point_iterator  
Nonmutable model of the STL concept BidirectionalIterator
with value type Point. Used to access the points
of the smallest enclosing ellipse.
 
Min_ellipse_2<Traits>::Support_point_iterator  
Nonmutable model of the STL concept RandomAccessIterator
with value type Point. Used to access the support points
of the smallest enclosing ellipse.

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.
template < class InputIterator >  
 
initializes min_ellipse to me(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).
 
Min_ellipse_2<Traits> min_ellipse ( Traits traits = Traits());  
creates a variable min_ellipse of type Min_ellipse_2<Traits>.
It is initialized to
me(∅), the empty set.
 
Min_ellipse_2<Traits> min_ellipse ( Point p, Traits traits = Traits());  
initializes min_ellipse to me({p}), the set {p}.
 
Min_ellipse_2<Traits> min_ellipse ( Point p, Point q, Traits traits = Traits());  
initializes min_ellipse to me({p,q}),
the set
{ (1λ) p + λq  0 ≤ λ ≤ 1 }.
 
Min_ellipse_2<Traits> min_ellipse ( Point p1, Point p2, Point p3, Traits traits = Traits());  
initializes min_ellipse to me({p1,p2,p3}).
 
Min_ellipse_2<Traits> min_ellipse ( Point p1, Point p2, Point p3, Point p4, Traits traits = Traits());  
initializes min_ellipse to me({p1,p2,p3,p4}).
 
Min_ellipse_2<Traits> min_ellipse ( Point p1, Point p2, Point p3, Point p4, Point p5, Traits traits = Traits());  
initializes min_ellipse to me({p1,p2,p3,p4,p5}).

int  min_ellipse.number_of_points () const  
returns the number of points of min_ellipse, i.e. P.  
int  min_ellipse.number_of_support_points () const  
returns the number of support points of min_ellipse, i.e. S.  
Point_iterator  min_ellipse.points_begin () const  returns an iterator referring to the first point of min_ellipse.  
Point_iterator  min_ellipse.points_end () const  returns the corresponding pasttheend iterator.  
Support_point_iterator  min_ellipse.support_points_begin () const  
returns an iterator referring to the first support point of min_ellipse.  
Support_point_iterator  min_ellipse.support_points_end () const  
returns the corresponding pasttheend iterator.  
Point  min_ellipse.support_point ( int i) const  
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.
 
Ellipse  min_ellipse.ellipse () const  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 space ^{2}.
CGAL::Bounded_side  min_ellipse.bounded_side ( 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_ellipse, resp.  
bool  min_ellipse.has_on_bounded_side ( Point p) const  
returns true, iff p lies properly inside min_ellipse.  
bool  min_ellipse.has_on_boundary ( Point p) const  
returns true, iff p lies on the boundary of min_ellipse.  
bool  min_ellipse.has_on_unbounded_side ( Point p) const  
returns true, iff p lies properly outside of min_ellipse.  
bool  min_ellipse.is_empty () const  returns true, iff min_ellipse is empty (this implies degeneracy). 
bool  min_ellipse.is_degenerate () const  
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.
void  min_ellipse.insert ( Point p)  inserts p into min_ellipse and recomputes the smallest enclosing ellipse.  
template < class InputIterator >  
void  min_ellipse.insert ( InputIterator first, InputIterator last)  
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).
 
void  min_ellipse.clear () 
deletes all points in min_ellipse and sets min_ellipse to the empty set.

An object min_ellipse is valid, iff
bool  min_ellipse.is_valid ( bool verbose = false, int level = 0) const  
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. 
const Traits&  min_ellipse.traits () const  returns a const reference to the traits class object. 
std::ostream&  std::ostream& os << min_ellipse 
writes min_ellipse to output stream os.

std::istream&  std::istream& is >> min_ellipse&  
reads min_ellipse from input stream is.

CGAL::Min_circle_2<Traits>
CGAL::Min_ellipse_2_traits_2<K>
MinEllipse2Traits
We implement the incremental 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 usage of Min_ellipse_2<Traits> and to show that randomization can be useful in certain cases, we give an example. The example also shows how the coefficents of the constructed ellipse can be accessed.
File: examples/Min_ellipse_2/min_ellipse_2.cpp
#include <CGAL/Cartesian.h> #include <CGAL/Min_ellipse_2.h> #include <CGAL/Min_ellipse_2_traits_2.h> #include <CGAL/Gmpq.h> #include <cassert> typedef CGAL::Gmpq NT; typedef CGAL::Cartesian<NT> K; typedef CGAL::Point_2<K> Point; typedef CGAL::Min_ellipse_2_traits_2<K> Traits; typedef CGAL::Min_ellipse_2<Traits> Min_ellipse; int main( int, char**) { const int n = 200; Point P[n]; for ( int i = 0; i < n; ++i) P[ i] = Point( i % 2 ? i : i , 0); // (0,0), (1,0), (2,0), (3,0) std::cout << "Computing ellipse (without randomization)..."; std::cout.flush(); Min_ellipse me1( P, P+n, false); // very slow std::cout << "done." << std::endl; std::cout << "Computing ellipse (with randomization)..."; std::cout.flush(); Min_ellipse me2( P, P+n, true); // fast std::cout << "done." << std::endl; // because all input points are collinear, the ellipse is // degenerate and equals a line segment; the ellipse has // two support points assert(me2.is_degenerate()); assert(me2.number_of_support_points()==2); // prettyprinting CGAL::set_pretty_mode( std::cout); std::cout << me2; // in general, the ellipse is not explicitly representable // over the input number type NT; when you use the default // traits class CGAL::Min_ellipse_2_traits_2<K>, you can // get double approximations for the coefficients of the // underlying conic curve. NOTE: this curve only exists // in the nondegenerate case! me2.insert(Point(0,1)); // resolves the degeneracy assert(!me2.is_degenerate()); // get the coefficients double r,s,t,u,v,w; me2.ellipse().double_coefficients( r, s, t, u, v, w); std::cout << "ellipse has the equation " << r << " x^2 + " << s << " y^2 + " << t << " xy + " << u << " x + " << v << " y + " << w << " = 0." << std::endl; return 0; }