Solve for a circle given more than 3 points.

Question

The problem is; given a set of 3 or more point in $\mathbb{R}^2$ that are assumed to approximate some portion of a circular arc, find the "best" center and radius of the circle.

The solution I'm considering is:

Start with the definition of a circle:

• $(x_i-X_c)^2 + (y_i-Y_c)^2 = R^2$

Rearrange it as a polynomial:

• $x_i^2 - 2x_iX_c + X_c^2 + y_i^2 - 2y_iY_c + Y_c^2 = R^2$
• $x_i(-2X_c) + y_i(-2Y_c) + 1(X_c^2 + Y_c^2 - R^2) = (x_i^2 + y_i^2)$

Use a least square regression to solve for $-2X_c$, $-2Y_c$ and $X_c^2 + Y_c^2 - R^2$ and then from there solve for $X_c$, $Y_c$ and $R$.

(This other question mentions using least squares but none of the answers that actually get into details describe solutions that looks like this and this has the advantage of being very easy to describe and understand.)

My actual questions:

• Is this a reasonable solution? Empirically it seems to work, but that is a rather weak claim.
• Should this be stable under translation, rotation and scaling? If not, are there similarly simple solutions that are?
• Is this a known solution?

Answer 1

As far as I know, this method was first described in 1982 in the document referenced $[2]$, p.15, in the paper cited below. Several further publications can be found in bibliographic resources.

You can find all details on this method in section 7, pages 11-13, paper : https://fr.scribd.com/doc/14819165/Regressions-coniques-quadriques-circulaire-spherique , with numerical example.

The method is extended to conics in general and to spherical regression, to quadratics, etc.

Note : The paper is in French, but comprehensive equations make it understandable by everyone.

Answer 2

There is a very simple method to get an approximate answer.

Consider $n$ equations $$f_i=(x_i-a)^2+(y_i-b)^2-r^2=0$$ Now, build $\color{red}{\frac{n(n-1)}2}$ equations $$g_{ij}=f_i-f_j=2(x_j-x_i)\,\color{red}{a}+2(y_j-y_i)\,\color{red}{b}+[(x_i^2+y_i^2)-(x_j^2+y_j^2)]$$ This is a linear system very easy to solve using matrices or linear regression to get $a,b$ and later $r^2$.

For example, using the data (equation $(2.3)$) of this paper $$\left( \begin{array}{cc} x_i & y_i \\ 1 & 7 \\ 2 & 6 \\ 5 & 8 \\ 7 & 7 \\ 9 & 5 \\ 3 & 7 \end{array} \right)$$ the above method gives $$a=\frac{773}{163}\approx 4.74233\qquad \text{and} \qquad b=\frac{5001}{1304}\approx 3.83512$$ which is close to the one called best fit in the paper.

Now, consider the simple objective function to be minimized $$SSQ=\sum_{i=1}^n \left[ (x_i-a)^2+(y_i-b)^2-r^2\right]^2$$ Differentiate with respect to $r$ and set the result equal to $0$ to get $$r^2=\frac 1n \sum_{i=1}^n [(x_i-a)^2+(y_i-b)^2]\implies r\approx 4.10876$$