近似多边形圆(Approximating a polygon with a circle)

那么，近似与多边形的圆圈和毕达哥拉斯的故事可能是众所周知的。但是，我们周围的其他方式？

我有一些多边形，这应该是事实上的圈子。但是，由于测量误差他们不是。所以，我正在寻找的是最“接近”给定的多边形圆。

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

我的第一个拟设是要找到点到中心的最大距离和最小。我们正在寻找的圈子之间可能的某个地方。

是否有任何算法在那里为这个问题？

Answer 1:

我会用scipy以BEST-“适合”一个圆上我的观点。您可以通过一个简单的中心的质量计算得到的圆心和半径的起点。这种运作良好，如果点均匀分布在圆形分布。如果不是，在下面的例子中，它仍然是聊胜于无！

拟合函数是简单，因为一个圆是简单的。你只需要找到您的拟合的圆的径向距离你点作为切线（径向）表面永远是最合适的。

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:

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

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

Answer 3:

有两种不同的O（n）的算法来确定最小的圆你画涵盖了一系列的维基百科页面点的最小圆的问题。从这里应该很容易得出第二圈，只需确定你之前找到的圆心，并找到最接近点的点。所述第二圆的半径是。

这可能不是你想要什么，但是这是我会怎么开始。

Answer 4:

这个问题可能是一样的最小圆的问题。

但是，既然你有测量误差可能有异常，那么RANSAC是不是一个很好的选择。见http://cs.gmu.edu/~kosecka/cs482/lect-fitting.pdf用于该方法的概述（以及其它基本的技术），在http://www.asl.ethz.ch/education/主/信息过程-抢劫/霍夫Ransac.pdf有专用于圆拟合的更多信息。

Answer 5:

这是很容易找到一些近似：

def find_circle_deterministically(x,y):
    center = x.mean(), y.mean()
    radius = np.sqrt((x-center[0])**2 + (y-center[1])**2).mean()
    return center, radius

说明：把圆心的平均X和平均贵点年。然后，对于每个点，确定到中心的距离，取均值的全部点。这就是你的半径。

这个完整的脚本：

import numpy as np
import matplotlib.pyplot as plt

n_points = 10
radius = 4
noise_std = 0.3

angles = np.linspace(0,2*np.pi,n_points,False)
x = np.cos(angles) * radius
y = np.sin(angles) * radius
x += np.random.normal(0,noise_std,x.shape)
y += np.random.normal(0,noise_std,y.shape)

plt.axes(aspect="equal")
plt.plot(x,y,"bx")

def find_circle_deterministically(x,y):
    center = x.mean(), y.mean()
    radius = np.sqrt((x-center[0])**2 + (y-center[1])**2).mean()
    return center, radius

center, radius2 = find_circle_deterministically(x,y)
angles2 = np.linspace(0,2*np.pi,100,True)
x2 = center[0] + np.cos(angles2) * radius2
y2 = center[1] + np.sin(angles2) * radius2
plt.plot(x2,y2,"r-")

plt.show()

产生这个情节：