Fitting an ellipse to a quadratic curve

[Unrest]

Hello. This is 2D with arbitrary orientations.

I have a quadratic curve segment defined by 2 end points and another one in between. I can find lots of other points along this curve.

I want to find a close-enough elliptic spline. It is defined by 2 end points and the point of intersection between the tangents through these end points.

The 2 end points must match exactly.One thought I had was to take 6 points on the curve, then solve the equation of the ellipse (Ax²+Bxy+Cy²+Dx+Ey+F=0) with them. But since these points aren't actually on an ellipse, could it be there is no ellipse that passes through all of them?? I heard you need 5 points to uniquely define an ellipse, but don't see how this equation can be solved for just 5.

Even if I can find this parametric equation for the ellipse, how would I find the point of intersection of the two tangents in a numerically stable way? It should also work for the special case of a straight line.

 

[Office_Shredder]

$$Ax^2+Bxy+Cy^2+Dx+Ey+F=0$$ looks like it should have six unknowns in it, but the equals zero part is key. If you divide everything by A for example
$$x^2 + B'xy + C'y^2 + D'x+E'y +F'=0$$
and now you only have five unknowns.

 

[Unrest]

$$Ax^2+Bxy+Cy^2+Dx+Ey+F=0$$ looks like it should have six unknowns in it, but the equals zero part is key. If you divide everything by A for example
$$x^2 + B'xy + C'y^2 + D'x+E'y +F'=0$$
and now you only have five unknowns.

Oh, excellent. Thanks. So with 5 arbitrary points, I should be able to find an ellipse that passes through them?

I have a strong feeling that it can't work when the points are collinear. This the other part of my problem. I don't actually need the ellipse's equation, so it would be great if I could bypass that and go directly to the intersection of the tangents, which can be defined for collinear points (tho not uniquely).

 

[Unrest]

$$Ax^2+Bxy+Cy^2+Dx+Ey+F=0$$ looks like it should have six unknowns in it, but the equals zero part is key. If you divide everything by A for example

This doesn't seem to work in all cases. For example, with these five points:
(0,1)
(0.375, 0.75)
(0.5, 0.5)
(0.375, 0.25)
(0, 0)

The ellipse equation with A divided out can't seem to be solved using them. Excel says:
x² + 2xy + E15y² + E15x + E15y = 0

I tried another way, dividing by F instead of A:
A'x² + B'xy + C'y² + D'x + E'y = -1

Doing it this way makes it solvable for some cases, but sometimes produces parabolas instead of ellipses. It also doesn't work for the example above - the point (0,0) leads to an equation like 0=-1.

Maybe I have to decide which coefficient to divide out of the equation on a case-by-case basis?

Maybe the exact approach is impossible? There seem to be some arrangements of 5 points that lie on a parabola but not on any ellipse.

 

[hotvette]

The trouble with using the general quadratic form of a conic is that you have an ellipse only if B²-4AC<0. Though I haven't tried it, I think the problem can be solved by using the standard form of an ellipse with an assumed translation and rotation of the points. This should result in a set of 5 (non-linear) equations in 5 unknowns (coordinates of center, a & b of the standard ellipse equation, and rotation angle). I don't know if an analytic solution is possible, but it should be possible to solve numerically. Also, depending on the points, there might be more than one solution.

 

[Unrest]

The trouble with using the general quadratic form of a conic is that you have an ellipse only if B²-4AC<0.

Yea I was just starting to realize that.

Though I haven't tried it, I think the problem can be solved by using the standard form of an ellipse with an assumed translation and rotation of the points. This should result in a set
..
Also, depending on the points, there might be more than one solution.

Or no solution - I don't think restricting it to an ellipse could work. The reason is that if you have 5 abritrary points, they should define a unique conic section. Since my 5 points lie on a parabola, they must define a parabola, and therefore cannot define an ellipse.

Another idea was to simplify the problem by rotating the points so the ellipse becomes a translated standard ellipse. Then I should be able to use 4 points to find the ellipse according to
Ax² + Cy² + Dx + Ey + F = 0
and rotate it back again.

But that still seems to have the same problem. When the 4 points are on a parabola, the equations can't seem to be solved.

 

[hotvette]

Oops, I hadn't read your original post carefully. If I understand correctly:

- You are fitting an ellipse to a series of points that don't necessarily define an ellipse
- The ellipse has to match the end points of the segment exactly
- You can generate as many points as you need in the segment

If all of the above is true, then I think you have a least squares problem (to fit an ellipse to a series of points that don't define an ellipse) with equality constraints (to fit the segment end points exactly). The approach I suggested should still work, but you need to add constraints and make it a least squares problem (orthogonal / total least squares probably makes sense vs ordinary least squares). Re the number of points needed, I'm not convinced that more than 5 would be needed, but I'm guessing the solution would vary somewhat with the number of points used.

In summary, I see this as an orthogonal least squares problem using parametric equations (since the rotation angle affects both x and y) with equality contraints (on the end points). Intriguing problem.

 

[Unrest]

Ah! The whole problem is unsolvable!

There's no such thing as the ellipse which best approximates a segment of a parabola! You can get a better approximation by making the ellipse bigger, but there's no upper limit.

So I tried slightly adjusting one point to make the parabola a little more ellipse-shaped, now the equations can be solved and do produce ellipses.

Maybe least squares would work as you suggested, but I can't imagine how it could possibly decide what ellipse to choose.

 

[hotvette]

Ah! The whole problem is unsolvable!

There's no such thing as the ellipse which best approximates a segment of a parabola! You can get a better approximation by making the ellipse bigger, but there's no upper limit.

So I tried slightly adjusting one point to make the parabola a little more ellipse-shaped, now the equations can be solved and do produce ellipses.

Maybe least squares would work as you suggested, but I can't imagine how it could possibly decide what ellipse to choose.

I don't think it is unsolvable. I'd like to play around with this, but probably won't have a chance until this weekend.

 

[hotvette]

There's no such thing as the ellipse which best approximates a segment of a parabola! You can get a better approximation by making the ellipse bigger, but there's no upper limit.

If you only use 5 points I agree. But, I think you'll find that using greater than 5 points will result in a solveable problem. I made up a problem choosing 6 points of an arbitrarily rotated parabola and was able to get a converged solution using total least squares. See attached showing starting point and converged solution.

 

[Unrest]

If you only use 5 points I agree. But, I think you'll find that using greater than 5 points will result in a solveable problem. I made up a problem choosing 6 points of an arbitrarily rotated parabola and was able to get a converged solution using total least squares. See attached showing starting point and converged solution.

Thanks for going to so much effort! But are you sure your solution is really an ellipse, not a parabola? Do you happen to have the equation available?

There's also bad news. I discovered that I don't just need any old ellipse, it has to have some other constraints, and I'm not sure what they are. So it's basically a dead end for now

 

[hotvette]

But are you sure your solution is really an ellipse, not a parabola? Do you happen to have the equation available?

Crud, I found an error. I had offset one of the points. Solution isn't converging even with 6 points. At this point I'd have to agree that an ellipse can't be fit to points that lie on a parabola, even in a least squares sense.

 

[Unrest]

Crud, I found an error. I had offset one of the points. Solution isn't converging even with 6 points. At this point I'd have to agree that an ellipse can't be fit to points that lie on a parabola, even in a least squares sense.

Ah. I was going to try working through that myself. Thanks for solving it for me! At least we've confirmed this thing. I was thinking about it a conic sections. If you rotate an ellipse to a steeper angle, you get something closer to a parabola, if you rotate it so it's nearly parallel to the side of the cone you get something that's nearly a parabola around its vertex. So you can get a better and better approximation by getting closer and closer to a parabola until it actually is a parabola.

 

[iLIKEstuff]

This is kind of old topic but FYI check out a paper on this exact subject in IEEE by Fitzgibbon et al titled "Direct least squares fitting of ellipses" from 1999

 

[Unrest]

Interesting, particularly being ellipse-specific. But the paper doesn't seem to say what happens with perfectly parabolic data. They only fit hand-drawn and noisy parabolas.

I think there can be no general purpose technique for fitting an ellipse to parabolic data.

 

[iLIKEstuff]

Oops. I had so many papers up I picked the wrong one to post... I meant to cite

Zhengyou Zhang, "Parameter estimation techniques: a tutorial with application to conic fitting"
Image and Vision Computing, Vol 15, No 1, 1997, pg 59-76.

It talks about conic fitting. With those two papers, you should be able to fit any conic section... albeit with some math involved

At least the first paper highlighted how tough the problem is...

 

[Unrest]

Zhengyou Zhang, "Parameter estimation techniques: a tutorial with application to conic fitting"
Image and Vision Computing, Vol 15, No 1, 1997, pg 59-76.

I just looked at the abstract. It's also about noisy data. My problem was perfectly clean data, and I'm still fairly sure there's no solution. The best fitting ellipse would be one with a huge aspect ratio, huge without limit. Which ends up being a parabola.

Anyway I managed to solve the problem by not requiring an ellipse at all.

 

[iLIKEstuff]

Oh. Maybe I dont' understand your problem. What about quadratic bezier curve?

 

[Unrest]

Oh. Maybe I dont' understand your problem. What about quadratic bezier curve?

If one section of a quadratic bezier curve is a parabola, then yes, that's what I ended up doing - fitting a parabola to a parabola. (very easy! :P). The only reason for the ellipse was I had a 3rd party library which required ellipses, so I worked around that to use parabolas instead.