Xref: utzoo comp.graphics:6196 sci.math:7060
Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!milano!cadillac!sunshine!finn
From: finn@sunshine.cad.mcc.com (Chris Finn)
Newsgroups: comp.graphics,sci.math
Subject: Re: Need to fit a circle to some points
Keywords: least squares
Message-ID: <1311@cadillac.CAD.MCC.COM>
Date: 19 Jun 89 21:24:20 GMT
References: <573@lehi3b15.csee.Lehigh.EDU> <221@obs.unige.ch> <1241@cadillac.CAD.MCC.COM> <339@celit.UUCP>
Sender: news@cadillac.CAD.MCC.COM
Reply-To: finn@MCC.COM (Chris Finn)
Organization: MCC CAD Program, Austin, TX
Lines: 34

> Good job Chris!  How accurate are the results?  The reason I ask is because
> of the inversion step.

Running the example I posted outputs

   Estimated circle center (x0,y0) =   149.9992  -299.9999
   Estimated circle radius         =   2000.001
 
The values used to generate the circle were (x0,y0) = 150.0 -300.0
and radius = 2000.0. The results are accurate to within the precision
of the machine ( approximately six or seven decimal places ). These results 
are for a set of 500 data points which are an "exact" circle evenly sampled
along its circumference. 
	As with any inverse problem the quality of the results are highly
dependent on the quality of the data input. Data which lie along a circle 
but contain noise will be fit in the least squares  sense (i.e. the summed
squared distance between the predicted circle and the  data will be minimized).
For reasonable data sets the matrix inversion should be stable.
	A more fundamental problem is fitting data which do not fully determine 
the parameters of the circle. An example which comes to mind is to fit a circle
to a point. As a more likely example consider a small data set which covers a
very small segment of the circles arc ( say five degrees ) and contains 
some noise. Such a data set could be appear as a straight line requiring
a circle of infinite radius with a center at infinity. 
	For those of you out there in netland who solve a lot of 
inverse problems I highly recommend "Inverse Problem Theory: Methods
for Data Fitting and Model Parameter Estiation" by Albert Tarantola,	
Elsevier Science Publishers. It is very complete and contains lots of 
examples for special cases.

Chris Finn
MCC CAD Program, P.O. Box 200195, Austin, TX 78720 [512] 343-0978
ARPA: finn@mcc.com
UUCP: {uunet,harvard,gatech,pyramid}!cs.utexas.edu!milano!cadillac!finn