用ci逼近多边形

Question

好吧，用多边形近似一个圆和毕达哥拉斯的故事可能是众所周知的。 但反过来呢？在

我有一些多边形，实际上应该是圆。但是，由于测量误差，它们不是。所以，我要找的是最接近给定多边形的圆。在

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

我的第一个安萨兹是找出点到中心的最大距离和最小距离。我们要找的圆圈可能介于两者之间。在

有什么算法可以解决这个问题吗？在

Answer 1

也许一个简单的算法是首先计算点的质心（前提是它们通常是大致规则间隔的）。这是圆心。一旦你有了它，你就可以计算出这些点的平均半径，给出圆的半径。在

一个更复杂的答案可能是做一个简单的最小化，即最小化点到圆边缘的距离之和（或距离平方）。在

Answer 2

有两种不同的O（n）算法来确定你画的包含维基百科页面smallest-circle problem上一系列点的最小圆。从这里画第二个圆应该很容易，只需确定之前找到的圆的中心，然后找到最接近该点的点。第二个圆的半径是。在

这也许不是你想要的，但这就是我开始的方式。在

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