How to quickly fit a circle by given random arc points?

Question

Could you suggest a method to quickly fit the parameters of a circle (center and radius), if I have a small set of random points (for example, 64), covering only a part of the circle (arc)?

[Clarification] The points are noisy, so the exact formulation is how fit the circle parameters to to minimize the sum of squared distances from the points to the circle (L2 metric, L1 is also ok).

I look for a fast algorithm, because I need to do it in real time with rather high FPS.

Additionally, there is information to compute an approximate initial guess of the circle.

Answer 1

Perhaps try Bullock to see if it works in your situation. Then consult Gander et al (1994) and Chernov & Lesort (2008) for discussion on why the problem isn't trivial and possible remedies.

Answer 2

This was to be a comment on Sau001's comment to the approved solution, but i have no reputation, so i post it as a solution, if allowed.

I tried the link Sau001 posted in his comment

http://www.dtcenter.org/sites/default/files/community-code/met/docs/write-ups/circle_fit.pdf

where he was asking if this was the Bullock implementation...

I needed a way to infer the circle parameters from data around a limited arc of a circle, as illustrated in the linked document circle_fit.pdf, and found that it does not work as intended in my cases, which contain a lot of noise.

Details: used python3 and numpy library imported as np. The circle_fit.pdf implementation went into a

def fit_circle(xs, ys, jf=True, vb=1):
    ...
returns: xc, yc, rc, err_stdev, res

function which takes the x's and their y's and two options and returns the fitted circle's x, y, r + the stdev of the residuals (signed diff btwn each point's radius and the circle radius, see 3rd line from the last in py-code, where i show how the residuals are computed, 'errs = ...') and the residuals themselves.

It gave the same output as the paper indicates for the listed input with 7 points on a parabola, so i assume the coding is okay (could share it...), but when tested with a band of points around the model circle xc, yc, rc = 0, -100, 121 it succeeded when the whole circle was filled with data [green points], but failed badly when only an arc on top was fitted [blue ones].

Here is the testing code, with output:

print("--- test with paper's values: fitted x,y,r all match:")
xs = np.arange(0, 3.1, 0.5)
ys = xs**2
xf, yf, rf, err_stdev, res = fit_circle(xs, ys, jf=0, vb=0)
print('xf, yf, rf = %.3f, %.3f, %.3f     res_std: %.3f' % (xf, yf, rf, err_stdev))

print('=' * 10 + ' two more cases: full circle data [green] and only top arc [blue]')
np.random.seed(101)
xc, yc, rc = 0, -100, 121  # model a circle of these parms
n2 = 10000 # num pts around the circle
idxs = range(n2) # will filter out some, below
rs = np.random.normal(rc, scale=4, size=n2) # radii around true r=121 radius w stdev=4
phs = np.random.uniform(0, 2*np.pi, size=n2) # phi values

xs2 = xc + rs * np.cos(phs)
ys2 = yc + rs * np.sin(phs)

xf, yf, rf, err_stdev, res = fit_circle(xs2, ys2, jf=0, vb=0)
print('xf, yf, rf = %.2f, %.2f, %.2f     res_std: %.3f' % (xf, yf, rf, err_stdev))

print('now with the cut slice of the points [blue] from the top only...')
cutt = 50 # cut-threshold for upper slice...
xs2b = [xs2[i] for i in idxs if (-cutt < xs2[i] < cutt and -cutt < ys2[i])]
ys2b = [ys2[i] for i in idxs if (-cutt < xs2[i] < cutt and -cutt < ys2[i])]
n2b = len(xs2b) # how many left in the cut

xf, yf, rf, err_stdev, res = fit_circle(xs2b, ys2b, jf=0, vb=0)
print('xf, yf, rf = %.2f, %.2f, %.2f     res_std: %.3f    n=%dpts'
% (xf, yf, rf, err_stdev, n2b))

# calculate stdev for the same sum of distances squared to true modeling circle:
print('true model has: xc, yc, rc = %s, %s, %s' % (xc, yc, rc))
xs2q, ys2q = np.array(xs2b), np.array(ys2b)
errs = np.sqrt((xs2q - xc)**2 + (ys2q - yc)**2) - rc  # the true residuals
true_stdev = np.sqrt(np.sum(errs*errs)/(n2b-3)) # 3 deg of freedom lost
print('true-stdev: %.3f    [fitted was: %.3f]' % (true_stdev, err_stdev))

---------------------------------------- output below:

--- test with paper's values ---
xf, yf, rf = -11.839, 8.446, 14.686     res_std: 0.189
========== two more cases: full circle data [green] and only top arc [blue]
xf, yf, rf = 0.01, -100.03, 121.13     res_std: 4.052
now with the cut slice of the points [blue] from the top only...
xf, yf, rf = 0.03, -25.38, 52.00     res_std: 5.841    n=1376pts
true model has: xc, yc, rc = 0, -100, 121
true-stdev: 4.135    [fitted was: 5.841]

---

Including a plot of the dataset created below, with the green and blue points. enter image description here

Answer 3

I've had a decent amount of success with Ian Coope's method: http://hdl.handle.net/10092/11104

I've implemented the algorithm in python in scikit-guess in skg.nsphere_fit.

Answer 4

No need for complicated computer algorithm. A straightaway formula comes from pp. 11-13 in https://fr.scribd.com/doc/14819165/Regressions-coniques-quadriques-circulaire-spherique