Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!apple!ames!elroy!usc!venera.isi.edu!gremlin!nrtc.nrtc.northrop.com!mcohen
From: mcohen@nrtc.nrtc.northrop.com (Marty Cohen <mcohen>)
Newsgroups: comp.graphics
Subject: Re: Need to fit a circle to some points
Keywords: Least squares, circle
Message-ID: <1884@gremlin.nrtc.northrop.com>
Date: 2 Jun 89 23:01:38 GMT
Sender: news@gremlin.nrtc.northrop.com
Reply-To: mcohen@nrtc.nrtc.northrop.com (Marty Cohen <mcohen>)
Organization: Northrop Research & Technology Center, Palos Verdes, CA
Lines: 41

Date:     Thu, 1 Jun 89 15:15:43 PDT
From:     mcohen@nrtc.northrop.com
To:       flash@lehi3b15.csee.Lehigh.edu, mcohen@nrtc.northrop.com

To: flash@lehi3b15.csee.Lehigh.EDU
Subject: Re: Need to fit a circle to some points
Newsgroups: comp.graphics,sci.math,sci.math.num-analysis
In-Reply-To: <573@lehi3b15.csee.Lehigh.EDU>
Organization: Northrop Research & Technology Center, Palos Verdes, CA
Cc: mcohen

I had to do the same thing. The obvious way, given a set of
points (x_i, y_i), i = 1 to n, to fit a circle of radius r,
center (a, b) is to minimize

sum(r - sqrt((x_i-a)^2 + (y_i-b)^2)).

However, this leads to nonlinear equations, and is a mess.

What I did instead was to minimize

sum(r^2 - (x_i-a)^2 - (y_i-b)^2).

Instead of minimizing the distance of the circle to the points,
this minimizes the area between the circle and the circles
with center at (a, b) passing through the data points.

This becomes a linear least squares problem in a, b, and 
c=r^2-a^2-b^2, since the circle (x-a)^2+(y-b)^2=r^2
is the same as x^2 - 2ax + y^2 - 2by - c = 0.

Use standard linear least squares techniques to get a, b, and c,
and then get r.

If you want to actually get the best circle in the original sense,
use this modified method to get an initial estimate for a, b, and r,
and then use a non-linear least squares routine to improve them.

Good luck,

Marty Cohen (mcohen@nrtc.northrop.com, 128.99.0.1, 213-544-5373)