2D Smallest Enclosing Ellipse (Min_ellipse_2)

Definition

An object of the class Min_ellipse_2<Traits> is the unique ellipse of smallest area enclosing a finite set of points in two-dimensional euclidean space $$ ₂. 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-l)p + l q | 0 <= l <= 1$$ } if $$P={p,q}.

An inclusion-minimal 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>

Traits Class

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

Guidelines and Hints

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 non-constant size, copy and assignment are expensive. Use references whenever possible.

Types

Min_ellipse_2<Traits>::Traits

typedef Traits::Point
	Point;	Point type.
typedef Traits::Ellipse
	Ellipse;	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.

Min_ellipse_2<Traits>::Point_iterator
	(bidirectional).
Min_ellipse_2<Traits>::Support_point_iterator
	(random access).

Creation

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 >
Min_ellipse_2<Traits> min_ellipse ( InputIterator first, InputIterator last, bool randomize, Random& random = default_random, Traits traits = Traits());
	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.
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. Postcondition: min_ellipse.is_empty() = true.
Min_ellipse_2<Traits> min_ellipse ( Point p, Traits traits = Traits());
	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.
Min_ellipse_2<Traits> min_ellipse ( Point p, Point q, Traits traits = Traits());
	creates a variable min_ellipse of type Min_ellipse_2<Traits>. It is initialized to $$me({p,q}), the set $${ (1-l)p + l q | 0 <= l <= 1$$ }. Postcondition: min_ellipse.is_degenerate() = true.
Min_ellipse_2<Traits> min_ellipse ( Point p1, Point p2, Point p3, Traits traits = Traits());
	creates a variable min_ellipse of type Min_ellipse_2<Traits>. It is initialized to $$me({p1,p2,p3}).
Min_ellipse_2<Traits> min_ellipse ( Point p1, Point p2, Point p3, Point p4, Traits traits = Traits());
	creates a variable min_ellipse of type Min_ellipse_2<Traits>. It is initialized 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());
	creates a variable min_ellipse of type Min_ellipse_2<Traits>. It is initialized to $$me({p1,p2,p3,p4,p5}).

Access Functions

int	min_ellipse.number_of_points ()
		returns the number of points of min_ellipse, i.e. $$|P|.
int	min_ellipse.number_of_support_points ()
		returns the number of support points of min_ellipse, i.e. $$|S|.
Point_iterator	min_ellipse.points_begin ()
		returns an iterator referring to the first point of min_ellipse.
Point_iterator	min_ellipse.points_end ()
		returns the corresponding past-the-end iterator.
Support_point_iterator
	min_ellipse.support_points_begin ()
		returns an iterator referring to the first support point of min_ellipse.
Support_point_iterator
	min_ellipse.support_points_end ()
		returns the corresponding past-the-end iterator.
Point	min_ellipse.support_point ( int i)
		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: $$0 i< min_ellipse.number_of_support_points()$$.
Ellipse	min_ellipse.ellipse ()
		returns the current ellipse of min_ellipse.

Predicates

By definition, an empty Min_ellipse_2<Traits> has no boundary and no bounded side, i.e. its unbounded side equals the whole plane $$ ₂.

Bounded_side	min_ellipse.bounded_side ( Point p)
		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.
bool	min_ellipse.has_on_bounded_side ( Point p)
		returns true, iff p lies properly inside min_ellipse.
bool	min_ellipse.has_on_boundary ( Point p)
		returns true, iff p lies on the boundary of min_ellipse.
bool	min_ellipse.has_on_unbounded_side ( Point p)
		returns true, iff p lies properly outside of min_ellipse.
bool	min_ellipse.is_empty ()
		returns true, iff min_ellipse is empty (this implies degeneracy).
bool	min_ellipse.is_degenerate ()
		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.

Modifiers

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

void	min_ellipse.clear ()
		deletes all points in min_ellipse and sets min_ellipse to the empty set. Postcondition: min_ellipse.is_empty() = true.

Validity Check

An object min_ellipse is valid, iff

• min_ellipse contains all points of its defining set $$P,
• min_ellipse is the smallest ellipse spanned by its support set $$S, and
• $$S is minimal, i.e. no support point is redundant.

Using the traits class implementation for the 2D 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.

bool	min_ellipse.is_valid ( bool verbose = false, int level = 0)
		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.

Miscellaneous

Traits	min_ellipse.traits ()
		returns a const reference to the traits class object.

I/O

ostream&	ostream& os << min_ellipse
		writes min_ellipse to output stream os. Precondition: The output operator is defined for Point (and for Ellipse, if pretty printing is used).
istream&	istream& is >> & min_ellipse
		reads min_ellipse from input stream is. Precondition: The input operator is defined for Point.

#include <CGAL/IO/Window_stream.h>

Window_stream&	Window_stream& ws << min_ellipse
		writes min_ellipse to window stream ws. Precondition: The window stream output operator is defined for Point and Ellipse.

See Also

Min_circle_2 , Min_ellipse_2_traits_2 , Min_ellipse_2_adapterC2 , Min_ellipse_2_adapterH2 .

Implementation

We implement the algorithm of Welzl, with move-to-front 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.

Example

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);
}