用圆形逼近多边形 [英] Approximating a polygon with a circle

问题描述

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

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.

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

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?

推荐答案

我会使用 scipy 来最好地拟合圆到我的点上。您可以通过简单的质量中心计算来获得中心和半径的起​​点。如果点在圆上均匀分布，则效果很好。如果不是这样，则如下所示，它总比没有好！

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

这篇关于用圆形逼近多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！