Xref: utzoo comp.graphics:5976 sci.math:6872 sci.math.num-analysis:3
Path: utzoo!attcan!uunet!lll-winken!csd4.milw.wisc.edu!uxc!tank!eecae!cps3xx!flynn
From: flynn@pixel.cps.msu.edu (Patrick J. Flynn)
Newsgroups: comp.graphics,sci.math,sci.math.num-analysis
Subject: Re: Need to fit a circle to some points
Keywords: circle algorithm least-squares fit
Message-ID: <3243@cps3xx.UUCP>
Date: 1 Jun 89 23:18:14 GMT
References: <573@lehi3b15.csee.Lehigh.EDU> <1088@osf.OSF.ORG>
Sender: usenet@cps3xx.UUCP
Reply-To: flynn@pixel.cps.msu.edu (Patrick J. Flynn)
Organization: Pattern Recognition & Image Processing Lab, CS, Mich State U.
Lines: 40

In article <1088@osf.OSF.ORG> flowers@osf.org (Ken Flowers) writes:
>In article <573@lehi3b15.csee.Lehigh.EDU> flash@lehi3b15.csee.Lehigh.EDU (Stephen Corbesero) writes:
>>
>>I need an algorithm to fit a set of data points, obtained
>>experimentally, to the best-fit circle.  I have searched through many
>>book son least squares anaylsis, but can only find simple cases.  I
>>started to do the math, but it became rather involved very quickly.
>>
>It seems to me that the best fit circle can be simply found by doing
>the following:
>
>    1.  Make the center the average point of all the data points.
>
>    2.  Make the radius the average distance from the center to each
>	data point.

Unfortunately, if the points are not distributed uniformly along the *entire*
circumference, you'll get a biased estimate of the location of the center.

A least-squares error criterion to the problem is nonlinear in the `geometric'
parameters of the circle (center coordinates and radius), but if you're willing
to use iterative techniques, you can get a solution.

Minimize f^2(x,y;x0,y0,r) with respect to (x0,y0) and r, where

f(x,y;x0,y0,r) = (x-x0)^2 + (y-y0)^2 - r^2

I've used the Levenberg-Marquardt method to solve related problems in
the past (you have to watch out for local minima, though).

A second approach which avoids the nonlinear stuff:
Start choosing triples of points from your point set.  Find the circle
passing through those points; save the estimates of the center and radius.
Then average the estimates.  If the points are not very noisy, that might do;
otherwise, you might want to trim those estimates.  When choosing triples,
be careful to choose points which aren't too close together.
------------------------------------------------------------------------------
Pat Flynn, CS, Mich. State U | "Don't eat with your hands, son; use your
flynn@cps.msu.edu            |  entrenching tool." 
(517) 353-4638               |                       -Firesign Theatre