From: eberly@cs.unc.edu (David Eberly) Newsgroups: sci.math,comp.graphics.algorithms Subject: Re: Fitting an ellipse given by... Date: 30 Mar 1998 23:39:46 -0500 In article <351B7F99.3A58@wxs.nl>, JP wrote: > >I have an ellipse given by the following function: > > A( x^2 + c^2 * y^2) + Bx + Cx + D = 0 > >I have a set of data points (Xi,Yi) 10 < i < 200 >Where 'c' is an constant that is given. > >How do i solve this problem. I try solving it with the least square >method but i unable to get a solution. An analytical (closed-form) solution is not tractable. An implementation which uses (1) an eigensolver to get an initial guess for the ellipse, (2) a minimizer in 5D for the energy function and (3) a quartic root finder for finding distance from point to ellipse is at my web site http://www.cs.unc.edu/~eberly/gr_appr.htm. The links to all the necessary files are on that page. The file ellp2fit.cpp contains a Windows95 driver which draws the computed ellipse and the data points. The code is not extremely fast, but when you are searching in 5D and having to compute roots of a quartic for each point in the data set per energy evaluation, its about the best you can do. Your problem is a slight variation in that you have specified the eccentricity of the ellipse. You should be able to make minor modifications to my code to handle this specialization. Dave Eberly eberly@cs.unc.edu ============================================================================== Date: Thu, 2 Apr 1998 00:45:52 -0600 (CST) From: Dave Rusin To: jp.jeanp@wxs.nl Subject: Re: Fitting an ellipse given by... Newsgroups: sci.math,comp.graphics.algorithms In article <351B7F99.3A58@wxs.nl> you write: >I have an ellipse given by the following function: > > A( x^2 + c^2 * y^2) + Bx + Cx + D = 0 > >I have a set of data points (Xi,Yi) 10 < i < 200 >Where 'c' is an constant that is given. > >How do i solve this problem. I try solving it with the least square >method but i unable to get a solution. By "solve this problem" do you mean, "find the best choices of A B C D so as to make the equation almost hold for all the datapoints"? That _should indeed_ be a least-squares problem. What do you mean when you say you were unable to get a solution? (If you mean "...to make the equation _hold_ for all the datapoints", then of course there is no solution unless the points really do lie on such an ellipse!) By the way, I assume you meant for the "Cx" term to be "Cy" ? dave ============================================================================== Date: Thu, 2 Apr 1998 01:04:33 -0600 (CST) From: Dave Rusin To: jp.jeanp@wxs.nl Subject: Re: Fitting an ellipse given by... Newsgroups: sci.math,comp.graphics.algorithms Let me clarify my previous remark: I guess I am assuming you're not really particular about the sense in which "best ellipse" is going to be decided; and I'm assuming the ellipse doesn't pass through the origin, for simplicity. Then when you normalize the equation to, say, D=-1, you have a problem of choosing good A, B, C to make A Z_i + B X_i + C Y_i ~= 1 for all i. That is a least-squares problem. (If you tried it without normalizing, you'll be told the best A B C D are all zero, of course!) The decision to scale to D=-1 actually introduces some distortion, which will be noticeable when the "correct" ellipse passes near the origin. If that's a problem, you can take advantage of the known eccentricity and the known orientation of the axes: in that case, you can scale the problem along one axis and change the question into the search for a _circle_ through a number of points. That's simpler and faster (as the other poster suggested). Even here there is some distortion if you are committed to selecting the absolute best ellipse in the least-squares sense, and the eccentricity is high, and the points are not really close to the optimal ellipse. If this distortion is a problem for you I think you may have to return to Eberly's general iterative ellise-fitter. I think there's a discussion of the topic in the FAQ for the newsgroup comp.graphics.algorithms. dave