CGAL 5.1.3 - Bounding Volumes
CGAL::Min_ellipse_2< Traits > Class Template Reference

#include <CGAL/Min_ellipse_2.h>

## Definition

An object of the class Min_ellipse_2 is the unique ellipse of smallest area enclosing a finite (multi)set of points in two-dimensional euclidean space $$\E^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)=\emptyset$$ if $$P=\emptyset$$, $$me(P)=\{p\}$$ if $$P=\{p\}$$, and $$me(P) = \{ (1-\lambda)p + \lambda q \mid 0 \leq \lambda \leq 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)$$. 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.

Template Parameters
 Traits must be a model for MinEllipse2Traits.

We provide the model CGAL::Min_ellipse_2_traits_2<K> using the two-dimensional CGAL kernel.

CGAL::Min_circle_2<Traits>
CGAL::Min_ellipse_2_traits_2<K>
MinEllipse2Traits

Implementation

We implement the incremental algorithm of Welzl, with move-to-front heuristic [16], using the primitives as described in [4], [3]. The whole implementation is described in [6].

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 usage of Min_ellipse_2 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.

#include <CGAL/Cartesian.h>
#include <CGAL/Min_ellipse_2.h>
#include <CGAL/Min_ellipse_2_traits_2.h>
#include <CGAL/Exact_rational.h>
#include <cassert>
typedef CGAL::Exact_rational NT;
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;
}
Examples:
Min_ellipse_2/min_ellipse_2.cpp.

## Related Functions

(Note that these are not member functions.)

std::ostream & operator<< (std::ostream &os, const Min_ellipse_2< Traits > &min_ellipse)
writes min_ellipse to output stream os. More...

std::istream & operator>> (std::istream &is, Min_ellipse_2< Traits > min_ellipse &)
reads min_ellipse from input stream is. More...

## Types

typedef unspecified_type Point
Typedef to Traits::Point.

typedef unspecified_type Ellipse
Typedef to Traits::Ellipse. More...

typedef unspecified_type Point_iterator
Non-mutable model of the STL concept BidirectionalIterator with value type Point. More...

typedef unspecified_type Support_point_iterator
Non-mutable model of the STL concept RandomAccessIterator with value type Point. More...

## Creation

A Min_ellipse_2 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 (InputIterator first, InputIterator last, bool randomize, Random &random=get_default_random(), const Traits &traits=Traits())
initializes min_ellipse to $$me(P)$$ with $$P$$ being the set of points in the range [first,last). More...

Min_ellipse_2 (const Traits &traits=Traits())
creates a variable min_ellipse of type Min_ellipse_2. More...

Min_ellipse_2 (const Point &p, const Traits &traits=Traits())
initializes min_ellipse to $$me(\{p\})$$, the set $$\{p\}$$. More...

Min_ellipse_2 (const Point &p, const Point &q, const Traits &traits=Traits())
initializes min_ellipse to $$me(\{p,q\})$$, the set $$\{ (1-\lambda) p + \lambda q \mid 0 \leq \lambda \leq 1 \}$$ More...

Min_ellipse_2 (const Point &p1, const Point &p2, const Point &p3, const Traits &traits=Traits())
initializes min_ellipse to $$me(\{p1,p2,p3\})$$.

Min_ellipse_2 (const Point &p1, const Point &p2, const Point &p3, const Point &p4, const Traits &traits=Traits())
initializes min_ellipse to $$me(\{p1,p2,p3,p4\})$$.

Min_ellipse_2 (const Point &p1, const Point &p2, const Point &p3, const Point &p4, const Point &p5, const Traits &traits=Traits())
initializes min_ellipse to $$me(\{p1,p2,p3,p4,p5\})$$.

## Access Functions

int number_of_points () const
returns the number of points of min_ellipse, i.e. $$|P|$$.

int number_of_support_points () const
returns the number of support points of min_ellipse, i.e. $$|S|$$.

Point_iterator points_begin () const
returns an iterator referring to the first point of min_ellipse.

Point_iterator points_end () const
returns the corresponding past-the-end iterator.

Support_point_iterator support_points_begin () const
returns an iterator referring to the first support point of min_ellipse.

Support_point_iterator support_points_end () const
returns the corresponding past-the-end iterator.

const Pointsupport_point (int i) const
returns the i-th support point of min_ellipse. More...

const Ellipseellipse () const
returns the current ellipse of min_ellipse.

## Predicates

By definition, an empty Min_ellipse_2 has no boundary and no bounded side, i.e. its unbounded side equals the whole space $$\E^2$$.

CGAL::Bounded_side bounded_side (const 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 has_on_bounded_side (const Point &p) const
returns true, iff p lies properly inside min_ellipse.

bool has_on_boundary (const Point &p) const
returns true, iff p lies on the boundary of min_ellipse.

bool has_on_unbounded_side (const Point &p) const
returns true, iff p lies properly outside of min_ellipse.

bool is_empty () const
returns true, iff min_ellipse is empty (this implies degeneracy).

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

## 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 insert (const Point &p)
inserts p into min_ellipse and recomputes the smallest enclosing ellipse.

template<class InputIterator >
void 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). More...

void clear ()
deletes all points in min_ellipse and sets min_ellipse to the empty set. More...

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

Note: In this release only the first item is considered by the validity check.

bool is_valid (bool verbose=false, int level=0) const
returns true, iff min_ellipse contains all points of its defining set $$P$$. More...

## Miscellaneous

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

## ◆ Ellipse

template<typename Traits>
 typedef unspecified_type CGAL::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.

## ◆ Point_iterator

template<typename Traits>
 typedef unspecified_type CGAL::Min_ellipse_2< Traits >::Point_iterator

Non-mutable model of the STL concept BidirectionalIterator with value type Point.

Used to access the points of the smallest enclosing ellipse.

## ◆ Support_point_iterator

template<typename Traits>
 typedef unspecified_type CGAL::Min_ellipse_2< Traits >::Support_point_iterator

Non-mutable model of the STL concept RandomAccessIterator with value type Point.

Used to access the support points of the smallest enclosing ellipse.

## ◆ Min_ellipse_2() [1/3]

template<typename Traits>
 CGAL::Min_ellipse_2< Traits >::Min_ellipse_2 ( const Traits & traits = Traits() )

creates a variable min_ellipse of type Min_ellipse_2.

It is initialized to $$me(\emptyset)$$, the empty set.

Postcondition
min_ellipse.is_empty() = true.

## ◆ Min_ellipse_2() [2/3]

template<typename Traits>
 CGAL::Min_ellipse_2< Traits >::Min_ellipse_2 ( const Point & p, const Traits & traits = Traits() )

initializes min_ellipse to $$me(\{p\})$$, the set $$\{p\}$$.

Postcondition
min_ellipse.is_degenerate() = true.

## ◆ Min_ellipse_2() [3/3]

template<typename Traits>
 CGAL::Min_ellipse_2< Traits >::Min_ellipse_2 ( const Point & p, const Point & q, const Traits & traits = Traits() )

initializes min_ellipse to $$me(\{p,q\})$$, the set $$\{ (1-\lambda) p + \lambda q \mid 0 \leq \lambda \leq 1 \}$$

Postcondition
min_ellipse.is_degenerate() = true.

## ◆ clear()

template<typename Traits>
 void CGAL::Min_ellipse_2< Traits >::clear ( )

deletes all points in min_ellipse and sets min_ellipse to the empty set.

Postcondition
min_ellipse.is_empty() = true.

## ◆ insert()

template<typename Traits>
template<class InputIterator >
 void CGAL::Min_ellipse_2< Traits >::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).

Template Parameters
 InputIterator is a model of InputIterator with Point as value type.

## ◆ is_valid()

template<typename Traits>
 bool CGAL::Min_ellipse_2< Traits >::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.

## ◆ Min_Ellipse_2()

template<typename Traits>
template<class InputIterator >
 CGAL::Min_ellipse_2< Traits >::Min_Ellipse_2 ( InputIterator first, InputIterator last, bool randomize, Random & random = get_default_random(), const Traits & traits = Traits() )

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

Template Parameters
 InputIterator is a model of InputIterator with Point as value type.

## ◆ support_point()

template<typename Traits>
 const Point& CGAL::Min_ellipse_2< Traits >::support_point ( int i ) const

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 \leq i<$$ min_ellipse.number_of_support_points().

## ◆ operator>>()

template<typename Traits>
 std::istream & operator>> ( std::istream & is, Min_ellipse_2< Traits > min_ellipse & )
related

reads min_ellipse from input stream is.

An overload of operator>> must be defined for Point.