Help for Excel Solver on a ellipse fit problem [URGENT]

[Corsa88]

Greetings guys

I have a set of scatter data x and y

x	y
0	0.0947
1	0.3099
2	0.6277
3	1.0481
4	1.5711
5	2.1967
6	2.9249
7	3.7557
8	4.6891
9	5.7251

<tbody>
</tbody>

What I'm trying to do is to fit an ellipse through this data.

My approach is first to use the algebraic equation for an ellipse:

ax² + bxy + cy² + dx + ey + f = 0

I then created one additional column that allows me to compute the value of the ellipse equation for each pair of (x,y) coordinate. Also I assigned cells for the parameters in the ellipse equation: a, b, c, d, e, f

Then, to obtain the ellipse fit (which meant that I had to find the values of a,b,c,d,e,f which gave ellipse equation values = 0 for every pair of (x,y) point), what I did was to use the Solver feature in Excel:

such that:

Objective : Ellipse_equation value for first pair of (x,y) point = 0

While changing: a, b, c, d, e, f

Constraints: Ellipse_equation value for each and other pairs of (x,y) points = 0

However, the outcome of this process simply led the values of a,b,c,d,e,f = 0. I know this satisfies the condition, but it doesn't define an ellipse.

Anyone know what should I include in or edit the approach that I'm taking for this problem? Have been tearing out my hair in frustration on this one.

Thanks to everybody in advance. Would really appreciate your advice.

Thanks and regards
Corse

 

[GooberTron]

I would try treating this like an ordinary least squares problem. Have a column with the heading "zero" and just place zeroes in each cell adjacent to your x and y columns. Then have another column called "model" and use your equation in each cell referencing your coefficients and the respective x and y values in the same row. Now setup a separate single cell and use the function =SUMXMY2 with the two arrays being your zero and model columns. This returns the sum of squares of the differences between your model and target (zero) for each row. This is your objective cell to minimise in Solver. When the sum of squares is zero you have a perfect fit. Setup Solver with this as your objective cell to minimise and by changing your A, B, C, D, E cells. Set your constraints to be that A, B, C, D, E cannot be zero - this will need five separate entries in the constraints section.

 

[Corsa88]

thanks GooberTron for your advice. How would I set the constraint that the a,b,c,d,e,f cannot be zero? At least on my side, its either '>=' or '<='.

 

[GooberTron]

Does <> work? I'm not at a PC to check. In VBA at least, "<>" means "not equal to".

 

[GooberTron]

As a slightly clunky workaround you might need to setup some helper cells that test for whether your coefficients are 0, and then use these helper cells as the constraints instead.
For example, =IF(A1=0,0,1) where A1 is the cell with a coefficient in. If your coefficient is not zero it will return the value 1. You now set this as the constraint (the helper cell should be equal to 1).

 

[Corsa88]

As a slightly clunky workaround you might need to setup some helper cells that test for whether your coefficients are 0, and then use these helper cells as the constraints instead.
For example, =IF(A1=0,0,1) where A1 is the cell with a coefficient in. If your coefficient is not zero it will return the value 1. You now set this as the constraint (the helper cell should be equal to 1).

Hi GooberTron

Thank you for the suggestion, the workaround works like a charm!

Could I seek your advice on an extension to this question:

My current fit is shown below:

The orange line and diamond markers denote the scatter data points I'm trying to fit to.

I have formulated equations to compute the following parameters from a,b,c,d,e,f of the ellipse equation:

1) ellipse center (x0,y0)
2) lengths of semi-axes
3) coordinates of the pivot point (of ellipse rotation) - marked as the small yellow dot marker
4) orientation of the ellipse/ rotation

I would like to make the coordinates of the pivot point to be at (0,0) while fitting the ellipse (e.g. a special constraint).
To this end, I have tried:

1) additional constraint: the pivot points to be (0,0)
2) additional constraint: length of the semi-major axis = distance from ellipse center (x0,y0) to (0,0)

However, both approaches led me to Solver error. The figure above was the closest I could get the pivot point to (0,0), although it was pure luck.

Any ideas?

 

[GooberTron]

What I know about ellipses you could fit on a postage stamp and that is being generous. However, for the ellipse to pass through (0,0) - doesn't the algebraic form suggest that "f" should therefore be 0? Have you tried manually setting that to 0 and re-running Solver but with "f" no longer a target parameter to change?
After some googling, I don't understand how the length of the semi-major axis could ever be the same distance as that from the centre of the ellipse to (0,0) if the ellipse is pivoted at (0,0) - but I could have misunderstood the concept.

 

[shg]

Suppose you instead tried to find the transformation that maps the points to a circle around the origin?

Form a (4 x 4 homogeneous) transformation matrix that does a translation, a rotation about the origin, and a vertical scaling. The objective function to be minimized is the variance in distance of the points from the origin. So the parameters are {deltaX, deltaY, rz, and scaleY), and the objective function is =varp(xi^2 + yi^2) after the transformation is applied.

The inverse of the transformation applied to the best-fit circle gives the ellipse.

 

[shg]

This is a 2D problem, so you only need a 3 x 3 matrix:

x'​

y'​

1​

=​

x​

y​

1​

​

1​

0​

0​

​

cos(r)​

sin(r)​

0​

1​

0​

0​

*​

0​

1​

0​

*​

-sin(r)​

cos(r)​

0​

*​

0​

scaleY​

0​

​

deltaX​

deltaY​

1​

​

1​

1​

1​

1​

1​

1​

 

[shg]

I got a numerically perfect fit to your data using that approach, but the result looks nothing like yours:

https://app.box.com/s/b3o3gibroindzelexqw7xijoq6nov0s7