用圆形近似多边形

Question

大家都知道，可以用多边形来近似一个圆，这个道理很简单。可是，反过来呢？

我有一些多边形，它们其实应该是圆形的。但是因为测量误差，它们并不是完美的圆。所以，我想找出一个最能“接近”这些多边形的圆。

在下面的图中，我们可以看到两个不同的例子。

我最开始的想法是找出这些点到中心的最大距离和最小距离。我们要找的圆可能就在这两者之间。

有没有什么算法可以解决这个问题呢？

Answer 1

在维基百科的 最小圆问题 页面上，有两种不同的 O(n) 算法可以用来找出一个包含一系列点的最小圆。接下来，画第二个圆就比较简单了，只需要确定你之前找到的圆心，然后找出离这个圆心最近的那个点。第二个圆的半径就是这个距离。

这可能不是你想要的完全答案，但这就是我开始的方式。

Answer 2

也许一个简单的方法是先计算这些点的中心点（假设这些点通常是大致均匀分布的）。这个中心点就是圆心。一旦你找到了圆心，就可以计算这些点到圆心的平均距离，这个距离就是圆的半径。

一个更复杂的做法可能是进行简单的最小化计算，也就是尽量让这些点到圆边的距离之和（或者距离的平方）最小化。

Answer 3

我会用 scipy 来把一个圆形“拟合”到我的点上。你可以通过简单的质心计算来得到圆心和半径的起始点。如果这些点在圆周上分布得比较均匀，这个方法效果很好。如果分布不均匀，比如下面的例子，这个方法仍然比什么都不做要好！

拟合的过程很简单，因为圆形本身就很简单。你只需要找出拟合的圆到你的点的距离，因为切线（径向）表面总是最适合的。

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()