From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci)
Subject: Re: Circle fitting
Date: 29 Apr 1999 11:26:19 GMT
Newsgroups: sci.math.num-analysis

In article <7g7u0b$foo$1@wanadoo.fr>,
 "YvesRunfola" <Yves.Runfola@wanadoo.fr> writes:
|> I'am looking for the simplest method to find the center x0, Y0 and the
|> raduis R of the circle which fit the N data points Xi, Yi i=1,N. (N>3)
|> I wonder if this least square problem can be solved by solving one or more
|> linear systems ?
yes., of course.
your original problem is 

    \sum{ \sqrt((x_i-x0)^2+(y_i-y0)^2) - r }^2 = min_{x0,y0,r},
a nonlnear least squares problem. if the fit is good, i.e. the points (x_i,y_i)
lie almost on a circle, then 
           \sqrt((x_i-x0)^2+(y_i-y0)^2) almost = r ,
hence 
       \sqrt((x_i-x0)^2+(y_i-y0)^2) + r almost = constant = c (say)
multiplying the sum by "c^2" gives
     \sum  { (x_i-x0)^2+(y_i-y0)^2-r^2 }^2  = min_{x0,y0,r}
with 
       \alpha=x0^2+y0^2-r^2 
this gives the linear least squares problem
        \sum { x_i^2+y_i^2 -2*x0*x_i -2*y0*y_i +\alpha}^2 = min_{x0,y0,\alpha}
solving this gives usually a very good estimate for x0,y0,r.
(often this will be already sufficiently good, although not optimal)
some gauss-newton-steps (i.e. solving 
linear least problems with a jacobian depending on the
current guess of x0,y0,r) then will suffice to obtain the optimal solution.
software:
see http://plato.la.as.edu/guide.html
hope this helps 
peter