Least Squares Circle

Approximation without constraints

We want to find a circle that fits the given set of points best in a sense of least squares approximation. Let a circle be represented as

x2+y2+2Ax+2By+C=0.

Then, the center of the circle is (-A,-B) and the radius is

r=   _______ ÖA2+B2- C   .

Assume this circle is used to approximate the given set of points p_i (i=1,2,¼,n). Then, the squared error with respect to p_i=(x_i,y_i) is (x_i²+y_i²+2Ax_i+2By_i+C)². Accordingly, the total squared error is given by

f = å (xi2+yi2+2Axi+2Byi+C)2.

We thus want to find A,B,C such that f is minimized, which is equivalent to solving the following system of linear equations:

¶f ¶A ,    ¶f ¶B ,    ¶f ¶C .

Explicitly, we need to solve

       2åx_i² A+2åx_iy_i B+åx_i C+å(x_i²+y_i²)x_i=0

       2åx_iy_i A+2åy_i² B+åy_i C+å(x_i²+y_i²)y_i=0

       2åx_i A+2åy_i B+n C+å(x_i²+y_i²)=0

Approximation with two constraints

We want to find a circle

x2+y2+2Ax+2By+C=0

(2-1)

such that it interpolates two points (x₁, y₁) and (x₂, y₂) and approximates the remaining given points in a sense of least squares approximation. By substituting (x₁, y₁) and (x₂, y₂) into the above equation, we have

x12+y12+2x1A+2y1B+C=0

x22+y22+2x2A+2y2B+C=0

Subtracting the first from the second equation gives

2(x1-x2)A+2(y1-y2)B+x12+y12-x22-y22=0.

Assume that |x₁-x₂| > |y₁-y₂|. Then, we may express A in terms of B to reduce numerical noise, i.e.,

A= y1-y2 x2-x1 B+ x12+y12-x22-y22 2(x2-x1) =aB +b.

Replacing A in (2-1) gives

f(B,C,x,y)=2(xa+y)B+C+x2+y2+2xb = 0.

Let f(B,C,x_i,y_i)=åf²(B,C,x_i,y_i). We then want to find B and C such that f is minimized, which is equivalent to solving the following equations:

       [(df)/(dB)]=2å[2(x_ia+y_i)B+C+x_i²+y_i²+2x_ib]2(x_ia+y_i)=0

       [(df)/(dC)]=2å[2(x_ia+y_i)B+C+x_i²+y_i²+2x_ib]=0

Let

       a₀₀=4å(x_ia+y_i)²,

       a₀₁=a₁₀=2å(x_ia+y_i),

       a₁₁=n,

       b₀=-2å(x_i²+y_i²+2x_ib)(x_ia+y_i), and

       b₁=-å(x_i²+y_i²+2x_ib).

Then, the above system of equations can be written as

a00B+a01C=b0

a10B+a11C=b1

Solving the above equations gives a circle whose center is (-A,-B) and radius Ö[(A²+B²+C)].

In the case where |x₁-x₂| < |y₁-y₂|, we may express B in terms A and obtain the circle similarly.