Find Minimum area ellipse enclosing a set of points in c++
An answer to this question on Stack Overflow.
Question
I have a set of 2D points. I need to find a minimum area ellipse enclosing all the points. Could someone give an idea of how the problem has to be tackled. For a circle it was simple. The largest distance between the center and the point. But for an ellipse its quite complicated which I do not know. I have to implement this in c++.
Answer
The other answers here give approximation schemes or only provide links. We can do better.
Your question is addressed by the paper "Smallest Enclosing Ellipses -- Fast and Exact" by Gärtner and Schönherr (1997). The same authors provide a C++ implementation in their 1998 paper "Smallest Enclosing Ellipses -- An Exact and Generic Implementation in C++". This algorithm is implemented in a more usable form in CGAL here.
However, CGAL only provides the general equation for the ellipse, so we use a few transforms to get a parametric equation suitable for plotting.
All this is included in the implementation below.
Using WebPlotDigitizer to extract your data while choosing arbitrary values for the lengths of the axes, but preserving their aspect ratio, gives:
-1.1314123177813773 4.316368664322679
1.345680085331649 5.1848164974519015
2.2148682495160603 3.9139687117291504
0.9938150357523803 3.2732678860664475
-0.24524315569075128 3.0455750009876343
-1.4493153715482157 2.4049282977126376
0.356472958558844 0.0699802473037554
2.8166270295895384 0.9211630387547896
3.7889384901038987 -0.8484766720657362
1.3457654169794182 -1.6996053411290646
2.9287101489353287 -3.1919219373444463
0.8080480385572635 -3.990389523169913
0.46847074625686425 -4.008682890214516
-1.6521060324734327 -4.8415723146209455
Fitting this using the program below gives:
a = 3.36286
b = 5.51152
cx = 0.474112
cy = -0.239756
theta = -0.0979706
We can then plot this with gnuplot
set parametric
plot "points" pt 7 ps 2, [0:2*pi] a*cos(t)*cos(theta) - b*sin(t)*sin(theta) + cx, a*cos(t)*sin(theta) + b*sin(t)*cos(theta) +
cy lw 2
to get
Implementation
The code below does this:
// Compile with clang++ -DBOOST_ALL_NO_LIB -DCGAL_USE_GMPXX=1 -O2 -g -DNDEBUG -Wall -Wextra -pedantic -march=native -frounding-math main.cpp -lgmpxx -lmpfr -lgmp
#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>
#include <cmath>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
typedef CGAL::Exact_rational 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;
struct EllipseCanonicalEquation {
double semimajor; // Length of semi-major axis
double semiminor; // Length of semi-minor axis
double cx; // x-coordinate of center
double cy; // y-coordinate of center
double theta; // Rotation angle
};
std::vector<Point> read_points_from_file(const std::string &filename){
std::vector<Point> ret;
std::ifstream fin(filename);
float x,y;
while(fin>>x>>y){
std::cout<<x<<" "<<y<<std::endl;
ret.emplace_back(x, y);
}
return ret;
}
// Uses "Smallest Enclosing Ellipses -- An Exact and Generic Implementation in C++"
// under the hood.
EllipseCanonicalEquation get_min_area_ellipse_from_points(const std::vector<Point> &pts){
// Compute minimum ellipse using randomization for speed
Min_ellipse me2(pts.data(), pts.data()+pts.size(), true);
std::cout << "done." << std::endl;
// If it's degenerate, the ellipse is a line or a point
assert(!me2.is_degenerate());
// Get coefficients for the equation
// r*x^2 + s*y^2 + t*x*y + u*x + v*y + w = 0
double r, s, t, u, v, w;
me2.ellipse().double_coefficients(r, s, t, u, v, w);
// Convert from CGAL's coefficients to Wikipedia's coefficients
// A*x^2 + B*x*y + C*y^2 + D*x + E*y + F = 0
const double A = r;
const double B = t;
const double C = s;
const double D = u;
const double E = v;
const double F = w;
// Get the canonical form parameters
// Using equations from https://en.wikipedia.org/wiki/Ellipse#General_ellipse
const auto a = -std::sqrt(2*(A*E*E+C*D*D-B*D*E+(B*B-4*A*C)*F)*((A+C)+std::sqrt((A-C)*(A-C)+B*B)))/(B*B-4*A*C);
const auto b = -std::sqrt(2*(A*E*E+C*D*D-B*D*E+(B*B-4*A*C)*F)*((A+C)-std::sqrt((A-C)*(A-C)+B*B)))/(B*B-4*A*C);
const auto cx = (2*C*D-B*E)/(B*B-4*A*C);
const auto cy = (2*A*E-B*D)/(B*B-4*A*C);
double theta;
if(B!=0){
theta = std::atan(1/B*(C-A-std::sqrt((A-C)*(A-C)+B*B)));
} else if(A<C){
theta = 0;
} else { //A>C
theta = M_PI;
}
return EllipseCanonicalEquation{a, b, cx, cy, theta};
}
int main(int argc, char** argv){
if(argc!=2){
std::cerr<<"Provide name of input containing a list of x,y points"<<std::endl;
std::cerr<<"Syntax: "<<argv[0]<<" <Filename>"<<std::endl;
return -1;
}
const auto pts = read_points_from_file(argv[1]);
const auto eq = get_min_area_ellipse_from_points(pts);
// Convert canonical equation for rotated ellipse to parametric based on:
// https://math.stackexchange.com/a/2647450/14493
std::cout << "Ellipse has the parametric equation " << std::endl;
std::cout << "x(t) = a*cos(t)*cos(theta) - b*sin(t)*sin(theta) + cx"<<std::endl;
std::cout << "y(t) = a*cos(t)*sin(theta) + b*sin(t)*cos(theta) + cy"<<std::endl;
std::cout << "with" << std::endl;
std::cout << "a = " << eq.semimajor << std::endl;
std::cout << "b = " << eq.semiminor << std::endl;
std::cout << "cx = " << eq.cx << std::endl;
std::cout << "cy = " << eq.cy << std::endl;
std::cout << "theta = " << eq.theta << std::endl;
return 0;
}