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

 

[Corsa88]

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.

GooberTron,

What you said makes sense, let me do a quick check

 

[Corsa88]

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

shg,

Your fit looks ideal for my purpose. Could i summarise your approach so that i could try it out :

1) For the table you attached, i would fill in the columns x and y with the original scatter data. On the right side on column y, i would populate the column with 1.

2) Create variable r to be varied in the rotation matrix

3) For each pair of scatter data, compute x', y' by performing matrix multiplication on the original x, y points with translation, rotation and scaling matrices, in that order.

4) Use Solver to minimise varp(xi^2 + yi^2) while changing deltax deltay r scaleY. Am i right to say that xi, yi refer to x', y'?

5) To find inverse, i would multiply the x', y' points by inverse of scaling, rotation and translation, in that order

6) The result of the inverse multiplication would yield the data points corresponding to points on the ellipse.

Any idea if it's possible to set the constraint on the ellipse pivot point?

Thank you in advance for your advice.

 

[shg]

The workbook is at https://app.box.com/s/1iqesr1osikoj1acacb2472w4jylmz0p

 

[shg]

Any idea if it's possible to set the constraint on the ellipse pivot point?

You mean specify where the center is? Yes: Change the order of operations to perform the translation first, enter the translation values manually, then solve for the best-fit rotation and scale.

 

[shg]

Solving repeatedly, there are many solutions. I think I have the wrong objective function ...

EDIT: I know I have the wrong objective function.

 

[Corsa88]

Solving repeatedly, there are many solutions. I think I have the wrong objective function ...

EDIT: I know I have the wrong objective function.

yep, that was what happened in my original fit as well. Different starting values for the ellipse equation yielded different solutions. The correct objective function is elusive indeed!

For the pivot point, I actually meant to refer to this:

From what I've tried so far, it seems like this constraint is very tough to implement. Perhaps you have an insight to its implementation?

 

[Corsa88]

shg,

By the way, how do you come up with the ranges in Solver for dX,dY and sy?

 

[shg]

For the pivot point, I actually meant ...

Same answer, I think.

Rotation is (by definition) about the origin. So to rotate about that point, you first translate that point to the origin, then rotate, then translate again, then rotate, then scale. The current order is rotate/translate/scale.

 

[shg]

... how do you come up with the ranges in Solver for dX,dY and sy?

Flailing to find something that worked.

I changed it to set instead the minimum angle subtended by the outboard points on the circle, and removed the other constraints, other than sy >= 0.

I think you need another (compeletely different) constraint that bounds the solution space.

 

[shg]

I'll put the current workbook up at the same link in a minute, and let you soldier on.

EDIT: Done.