Approximieren eines Polygons mit einem Kreis

Question

Nun, die Annäherung eines Kreises mit einem Polygon und die Geschichte von Pythagoras sind wohlbekannt. Aber was ist umgekehrt?

Ich habe einige Polygone, die eigentlich Kreise sein sollten. Dies ist jedoch aufgrund von Messfehlern nicht der Fall. Also, was ich suche, ist der Kreis, der das gegebene Polygon am besten "approximiert".

In der folgenden Abbildung sehen wir zwei verschiedene Beispiele.

Mein erster Ansatz war die maximale Entfernung der Punkte zum Zentrum sowie das Minimum zu finden. Der Kreis, nach dem wir suchen, liegt vielleicht irgendwo dazwischen.

Gibt es einen Algorithmus für dieses Problem?

Answer 1

Ich würde scipy verwenden, um Best- „fit“ einen Kreis auf meine Punkte. Sie können einen Ausgangspunkt für den Mittelpunkt und den Radius durch eine einfache Schwerpunktsberechnung erhalten. Dies funktioniert gut, wenn die Punkte gleichmäßig über den Kreis verteilt sind. Wenn nicht, wie im Beispiel unten, ist es immer noch besser als nichts!

Die Anpassungsfunktion ist einfach, weil ein Kreis einfach ist. Sie müssen nur den radialen Abstand von Ihrem Fit-Kreis zu Ihren Punkten finden, da die tangentiale (radiale) Fläche immer die beste Anpassung ist.

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

Es gibt zwei verschiedene O (n) -Algorithmen zur Bestimmung des kleinsten gezeichneten Kreises, der eine Reihe von Punkten auf der Wikipedia-Seite smallest-circle problem umfasst. Von hier aus sollte es ziemlich einfach sein, den zweiten Kreis zu zeichnen, einfach den Mittelpunkt des zuvor gefundenen Kreises zu bestimmen und den Punkt zu finden, der diesem Punkt am nächsten liegt. Der Radius des zweiten Kreises ist der.

Dies kann nicht genau, was Sie wollen, aber das ist, wie ich anfangen würde.

Answer 3

Das Problem könnte die gleiche wie die Smallest-circle problem sein.

Aber da Sie Messfehler haben die Ausreißer enthalten könnte, dann ist RANSAC eine gute Option, statt. Einen Überblick über die Methode (auch andere grundlegende Techniken) finden Sie unter http://cs.gmu.edu/~kosecka/cs482/lect-fitting.pdf, in http://www.asl.ethz.ch/education/master/info-process-rob/Hough-Ransac.pdf gibt es weitere Informationen zur Kreisanpassung.

Answer 4

Vielleicht ein einfacher Algorithmus wäre zunächst den Schwerpunkt der Punkte zu berechnen (vorausgesetzt, sie sind in der Regel grob regelmäßigen Abstand). Dies ist das Kreiszentrum. Sobald Sie das haben, können Sie den mittleren Radius der Punkte berechnen, indem Sie den Radius des Kreises angeben.

Eine anspruchsvollere Antwort wäre eine einfache Minimierung zu tun, in dem Sie die Summe der Abstände der Punkte an den Rand des Kreises (oder Abstand zum Quadrat) minimieren.

Answer 5

Es ist ganz einfach eine gewisse Annäherung zu finden:

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 

Erklärt: die Mitte des Kreises auf den Mittelwert x gesetzt und y Ihrer Punkte bedeuten. Bestimmen Sie dann für jeden Punkt den Abstand zum Mittelpunkt und nehmen Sie den Mittelwert über alle Punkte. Das ist dein Radius.

Das komplette Skript:

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

produziert dieses Grundstück:

Diese gute Arbeit, wie Sie Polygone mit Messfehler haben. Wenn Ihre Punkte nicht annähernd gleichmäßig über die Winkel [0,2pi[ verteilt sind, wird die Leistung schlecht.

Allgemeiner könnten Sie Optimierung verwenden.