CGAL::Min_ellipse_2<Traits>

Definition

An object of the class Min_ellipse_2<Traits> is the unique ellipse of smallest area enclosing a finite (multi)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-λ)p + λq | 0 ≤ λ ≤ 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.

#include <CGAL/Min_ellipse_2.h>

Requirements

The template parameter Traits is a model for MinEllipse2Traits.

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

Types

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.

Access Functions

Predicates

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

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.

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.

Miscellaneous

I/O

See Also

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