Xref: utzoo comp.graphics:6186 sci.math:7053
Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!uunet!seismo!esosun!cogen!celerity!celit!hutch
From: hutch@celerity.uucp (Jim Hutchison)
Newsgroups: comp.graphics,sci.math
Subject: Re: Need to fit a circle to some points
Keywords: least squares
Message-ID: <339@celit.UUCP>
Date: 16 Jun 89 17:55:52 GMT
References: <573@lehi3b15.csee.Lehigh.EDU> <221@obs.unige.ch> <1241@cadillac.CAD.MCC.COM>
Sender: news@celerity
Reply-To: hutch%celerity.UUCP@ucsd.ucsd.edu (Jim Hutchison)
Organization: FPS Computing
Lines: 40

finn@MCC.COM (Chris Finn) writes:
>pfenniger@obs.unige.ch writes:
>>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. 
...
>>The problem can be stated as follow :
>>You have a set of points in cartesian coordinates {Xi, Yi} i = 1, ..., n (n>2). 
[math problem/?simple case explanation? deleted]

>>The problem is therefore suited to *linear* least squares, since the unknowns
>>a, b, c in Z enter in a linear way.

There is atleast 1 other possibility.  It could be reduced to a simpler
problem.  If the problem where instead fitting a circle around an arbitrary
polygon, it'd be much simpler right?

    1) Take the first three arbitrary points, construct a triangle.
    2) Any points which when added to the polygon make a concave
       edge, are not added to the polygon.  Just drop them on the floor.
       By concave edge, I mean an edge formed by adding a point inside
       the convex polygon.
    3) Repeat step 2 for all points in your set.
    4) Fit a circle to the polygon.

This may not be the ideal algorithm.  For a large number of points it
should atleast reduces the size of the problem with no loss of precision.

>[...] I followed Mr. 
>Pfenniger's suggestion for linearizing the problem. However, I did not use 
>orthogonal decomposition but rather inverted the square normal matrix ( by
>Cramer's Rule no less, well it's only 3x3). I think it should be fairly
>robust if a large number of angles are present in the data.

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

/*    Jim Hutchison   		{dcdwest,ucbvax}!ucsd!celerity!hutch  */
/*    Disclaimor:  I am not an official spokesman for FPS computing   */