8

さて、円を多角形で近似することとピタゴラスの話は有名かもしれません。しかし、その逆はどうでしょうか。

実際には円であるはずのポリゴンがいくつかあります。ただし、測定誤差のため、そうではありません。だから、私が探しているのは、与えられた多角形を最も「近似」する円です。

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

ここに画像の説明を入力

私の最初の Ansatz は、点から中心までの最大距離と最小距離を見つけることでした。私たちが探している円は、おそらくその中間のどこかにあるでしょう。

この問題に対応するアルゴリズムはありますか?

4

5 に答える 5

6

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

ここに画像の説明を入力

于 2013-02-12T15:08:13.763 に答える
1

おそらく、単純なアルゴリズムは、最初に点の重心を計算することです (通常、点がほぼ等間隔に配置されている場合)。これがサークルセンターです。それができたら、点の平均半径を計算して、円の半径を得ることができます。

より洗練された答えは、円の端までの点の距離の合計 (または距離の 2 乗) を最小化する単純な最小化を行うことです。

于 2013-02-12T14:38:57.830 に答える
0

ウィキペディア ページの最小円問題で、一連の点を含む、描画する最小の円を決定するための 2 つの異なる O(n) アルゴリズムがあります。ここから 2 番目の円を描くのはかなり簡単です。前に見つけた円の中心を特定し、その点に最も近い点を見つけるだけです。2 番目の円の半径はそれです。

これはまさにあなたが望むものではないかもしれませんが、これが私が始める方法です.

于 2013-02-12T14:32:05.577 に答える
0

その問題は、最小円問題と同じかもしれません。

ただし、外れ値を含む可能性のある測定誤差があるため、RANSAC は代わりに適切なオプションです。http://www.asl.ethz.ch/education/で、メソッドの概要 (およびその他の基本的な手法) については、http ://cs.gmu.edu/~kosecka/cs482/lect-fitting.pdf を参照してください。 master/info-process-rob/Hough-Ransac.pdfサークル フィッティング専用の詳細情報があります。

于 2013-02-12T14:32:11.637 に答える
-1

近似値を見つけるのは非常に簡単です。

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[パフォーマンスが低下します。

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

于 2013-02-12T15:20:05.283 に答える