円でポリゴンを近似する

Question

ポリゴンとピタゴラスの物語で円​​を近似することはよく知られているかもしれません。 しかし、それ以外の方法はどうですか？

私はいくつかのポリゴンを持っていますが、実際には円でなければなりません。しかし、測定誤差のためにそうではありません。だから、私が探しているのは、与えられたポリゴンを最も近似するサークルです。

次の図では、2つの異なる例を見ることができます。

私の最初Ansatzは、中心に点の最大距離、ならびに最小値を見出すことでした。私たちが探しているサークルは、おそらくその中間にあります。

この問題のアルゴリズムはありますか？

Answer 1

を使用して、円を自分のポイントに最適にフィットさせます。簡単な質量中心計算によって、中心と半径の出発点を得ることができます。点が円の上に均一に分布している場合は、これがうまくいきます。下の例のようにそうでない場合、それは何もないよりも優れています！

円が簡単なのでフィッティング機能は簡単です。接線（放射状）サーフェスが常に最適になるので、フィットサークルからポイントまでの半径距離を求める必要があります。

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

wikipediaページsmallest-circle problemの一連の点を含む、描く最小円を決定するための2つの異なるO（n）アルゴリズムがあります。ここから、2番目の円を描き、以前に見つかった円の中心を決定し、その点に最も近い点を見つけることはかなり簡単です。 2番目の円の半径はそれです。

これはまさにあなたが望むものではないかもしれませんが、これが私のやり方です。

Answer 3

この問題はSmallest-circle problemと同じ場合があります。

しかし、測定値に異常値が含まれている可能性があるため、代わりにRANSACは良いオプションです。方法の概要についてはhttp://cs.gmu.edu/~kosecka/cs482/lect-fitting.pdf（他の基本的な技術と同様）を参照してください。http://www.asl.ethz.ch/education/master/info-process-rob/Hough-Ransac.pdfには、円フィッティング専用の情報があります。

Answer 4

おそらく、簡単なアルゴリズムは、まず点の重心を計算することです（通常は、ほぼ規則的に間隔を置いています）。これは円の中心です。いったんそれを持っていれば、円の半径を与えて、点の平均半径を計算することができます。

もっと洗練された答えは、点の円の端までの距離の和（または距離の二乗）を最小にする簡単な最小化を行うことです。

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に円の中心を置き、あなたのポイントのy座標を意味します。次に、各点について、中心までの距離を決定し、すべての点にわたって平均をとる。それはあなたの半径です。

この完全なスクリプト：

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

はこのプロットを生成します。

あなたは測定誤差とポリゴンを持っているので、これは良い動作します。あなたのポイントが角度[0,2pi[にほぼ均等に分配されていないと、パフォーマンスが悪くなります。

さらに一般的には、最適化を使用できます。