0

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?
BCS
  • 633
  • This problem has a famous solution in computer vision: The Hough transform (or Duda/Hart transform). – David G. Stork Feb 15 '18 at 23:36
  • Hough transform is an extremely inefficient solution for this problem. – mathreadler Feb 15 '18 at 23:43
  • I don't think efficiency is relevant here. The slowest, most inefficient code would likely execute in the time it takes your finger to depress Return on the keyboard. – David G. Stork Feb 15 '18 at 23:59
  • It looks like the Hough Transform is focused on the case where the majority of points are not on the circle. In the case in question, all of the points are assumed to be part of the circle. – BCS Feb 16 '18 at 00:02
  • In the case in question, if all the points are on a part of the circle, take only three points (doesn't matter the three points chosen). With only three points it is easy to compute the coordinates of the center and the radius of the circle. Any triplet of points will give the same result. The result is the same with the method of regression cited above because the method is valid for all points on the circle as well as scattered points around the circle. – JJacquelin Feb 16 '18 at 17:03
  • Well, maybe I should have said "near" the circle. Or presumed to be (and by implication aren't exactly) on the circle. I specifically want to deal with the case ware the points are noisy, either due to quantification errors, measurement errors or other losses of precision. – BCS Feb 17 '18 at 00:18

2 Answers2

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.

JJacquelin
  • 66,221
  • 3
  • 37
  • 87
  • Equations: universally understood (or not) by everyone. --- I'll take a look. – BCS Feb 16 '18 at 15:15
  • They are clearly using the same method: so it is a known solution and gives weight to it being a reasonable one, but I don't see anything that seems to be considering it's stability under transformations. – BCS Feb 16 '18 at 15:37
  • @BCS : Don't look for theoretical studies in the referenced paper : They are none. This is purely a report from practical applications in industrial labs where the regression method was successfully applied a lot of times in many different cases. – JJacquelin Feb 16 '18 at 16:51
  • Ok, my (non-existent) French wasn't good enough to get that context :0). – BCS Feb 19 '18 at 04:57
0

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$$

Claude Leibovici
  • 260,315
  • That seems reasonable to implement up until the "differentiate with respect to r and solve" part which may not be that bad. On the other hand with regards to the first steps, its not clear to me why that would work at all (which is not to say it doesn't) nor how the second equations is derived from the first. – BCS Feb 16 '18 at 15:14