# Fit ellipse to points: Algorithm in C++ or Matlab

• Feb 15th 2008, 01:51 PM
Dirlewanger
Fit ellipse to points: Algorithm in C++ or Matlab
I'm looking for an algorithm to fit an ellipse (tilted) to some given points in 2D. There are some around, but I need one that calculates and returns the error of the fit.

Some of the points might be "false" and I want to identify them by seeing how the error of the fit changes by excluding the points one at a time. Or is there a smarter way to identify points which "ruin the fit" of the other points to an ellipse?
• Feb 16th 2008, 08:38 AM
TriKri
You could look at the distance between the ponts and the elipse, every point that is further away than a certain threshold (maybe a certain amount of the elipse's circumference) is excluded, then you try to fit the elipse again. While the set of "false" points has changed from the previous time the elipse was fit to the points (which will be the empty set if the elipse hasn't been fit before), repeat and fit the elipse again.
• Feb 16th 2008, 10:54 AM
Dirlewanger
Yes! Great idea, and so simple. I don't even need a measurement of "fitness error". I can heuristically figure out good tresholds. This also seems to be computationally efficient.

Thanks!
• Mar 15th 2008, 04:52 AM
Dirlewanger
I can't make it work.

I want to calculate the distance between point P outside of the ellipse, and point E which is the point on the ellipse which is closest to point P.

C is the center of the ellipse and I use this triangle where CY is parallel to the Y-axis of the coordinate system:

Code:

```P__Y  \ | E \|   C```
I simply calculate the angle at C as atan((xP-xC)/(yP-yC)).

Then I plug this angle as "t" into the parametric equations for a tilted ellipse to get E.
xE = xC + long*cos(t)*cos(phi) - short*sin(t)*sin(phi);
yE = yC + short*sin(t)*cos(phi) + long*cos(t)*sin(phi);

While E always is on the ellipse, it is offset by a seemingly random angle from the line CP.

The tilt angle of the ellipse is phi. I thought that the point on the ellipse at angle t= -phi would give a line CE that is parallell to an axis of the coordinate system. It doesn't. Shouldn't it? Or what does the tilt angle really mean?
• Mar 15th 2008, 05:27 AM
Dirlewanger
It seems as if a certain change in the angle parameter "t" represents a larger move along the ellipse when close to the short axis, than when close to the long axis.

What a mess!
• Mar 16th 2008, 03:19 PM
TriKri
I see a couple of mistakes you make. First, the angle t isn't the angle between the y axis and the point's reative position to the center of the ellipse. First, a unit circle is created with t in its equation. Then the circle is stretched out to an ellipse, hence the angle changes. Then, the ellipse is rotated counterclockwise by the angle phi. So before you can calculate the angle, you will have to rotate it back, and then deform it back to a circle. Then you can calculate the angle.

Then I see another thing. In your formula for calculating the coordinates of the point, increasing t will rotate the point counterclockwise. But in your formula for calculating the angle from coordinates, you have assumed that the angle is measured clockwise. You must choose which and then change in one of the formulas.