Approximating a polygon with a circle

Question

Well, approximating a circle with a polygon and Pythagoras' story may be well known. But what about the other way around?

I have some polygons, that should be in fact circles. However, due to measurement errors they are not. So, what I'm looking for is the circle that best "approximates" the given polygon.

In the following figure we can see two different examples.

My first Ansatz was to find the maximum distance of the points to the center as well as the minimum. The circle we are looking for is maybe somewhere in between.

Is there any algorithm out there for this problem?

Answer 1

I would use scipy to best-"fit" a circle onto my points. You can get a starting point for the center and radius by a simple center-of-mass calculation. This works well if the points are uniformly distributed over the circle. If they are not, as in the example below, it is still better than nothing!

The fitting function is simple because a circle is simple. You only need to find the radial distance from your fit circle to your points as the tangent (radial) surface will always be the best fit.

import numpy as np
from scipy.spatial.distance import cdist
from scipy.optimize import fmin
import scipy

# Draw a fuzzy circle to test
N = 15
THETA = np.random.random(15)*2*np.pi
R     = 1.5 + (.1*np.random.random(15) - .05)
X = R*np.cos(THETA) + 5
Y = R*np.sin(THETA) - 2

# Choose the inital center of fit circle as the CM
xm = X.mean()
ym = Y.mean()

# Choose the inital radius as the average distance to the CM
cm = np.array([xm,ym]).reshape(1,2)
rm = cdist(cm, np.array([X,Y]).T).mean()

# Best fit a circle to these points
def err((w,v,r)):
    pts = [np.linalg.norm([x-w,y-v])-r for x,y in zip(X,Y)]
    return (np.array(pts)**2).sum()

xf,yf,rf = scipy.optimize.fmin(err,[xm,ym,rm])  

# Viszualize the results
import pylab as plt
fig = plt.figure()
ax = fig.add_subplot(1, 1, 1)

# Show the inital guess circle
circ = plt.Circle((xm, ym), radius=rm, color='y',lw=2,alpha=.5)
ax.add_patch(circ)

# Show the fit circle
circ = plt.Circle((xf, yf), radius=rf, color='b',lw=2,alpha=.5)
ax.add_patch(circ)

plt.axis('equal')
plt.scatter(X,Y)
plt.show()

Answer 2

Perhaps a simple algorithm would be firstly to calculate the centroid of the points (providing they are usually roughly regularly spaced). This is the circle centre. Once you have that you can calculate the mean radius of the points, giving the radius of the circle.

A more sophisticated answer might be to do a simple minimisation, where you minimise the sum of the distances of the points to the edge of the circle (or distance squared).