用圆圈近似多边形

Question

好吧,近似一个带有多边形的圆圈和毕达哥拉斯的故事可能是众所周知的.但另一种方式呢？

我有一些多边形,实际上应该是圆圈.但是,由于测量误差,它们不是.所以,我正在寻找的是最能"近似"给定多边形的圆.

在下图中,我们可以看到两个不同的例子.

我的第一个Ansatz是找到点到中心的最大距离以及最小值.我们正在寻找的圈子可能介于两者之间.

这个问题有没有算法？

Answer 1

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