Eh bien, approximation d'un cercle avec une histoire de polygone et de Pythagore peut être bien connu. Mais qu'en est-il de l'inverse?
J'ai des polygones, cela devrait être en fait des cercles. Cependant, en raison d'erreurs de mesure, elles ne le sont pas. Alors, que je cherche, c'est le cercle qui le mieux "se rapproche" du polygone donné.
Dans la figure suivante, nous pouvons voir deux exemples différents.
Mon premier ANSATZ était de trouver la distance maximale des points au centre ainsi que le minimum. Le cercle que nous recherchons est peut-être quelque part entre les deux.
Y a-t-il un algorithme pour ce problème?
5 Réponses :
Il existe deux algorithmes O (n) différents pour déterminer le plus petit cercle que vous dessinez qui englobe une série de points sur la page Wikipedia problème de plus en cercle . De là, il devrait être assez facile de dessiner le deuxième cercle, déterminez simplement le centre du cercle que vous avez trouvé précédemment et trouvez le point le plus proche de ce point. Le rayon du deuxième cercle est que.
Cela peut ne pas être exactement ce que vous voulez, mais c'est comme ça que je démarrerais.
Ce problème pourrait être identique à celui de problème de plus petit cercle .
Mais puisque vous avez des erreurs de mesure qui pourraient inclure des valeurs aberrantes, alors RANSAC est une bonne option à la place. Voir http://cs.gmu.edu/~kosecka/cs482/Lect- ajustement.pdf pour un aperçu de la méthode (ainsi que d'autres techniques de base), dans http://www.asl.ethz.ch/education/master/info-process-rob/hough-ransac.pdf Il y a plus d'informations dédiées au raccord de cercle .
Je ne suis pas sûr d'être d'accord. En supposant qu'il trouvait l'emplacement des points sur un cercle et qu'il y a une erreur dans la mesure, ce qui n'a plus de tomber sur un cercle parfait, son objectif n'est pas de trouver le plus petit cercle qui les englobe tout sauf le cercle le plus probable que le plus probable Cela entraînerait ses points particuliers.
J'aurais peut-être mal compris les exigences, oui.
+1 pour me présenter à Ransac et les beaux refs! Il semble que cela nécessite une connaissance spécifique du type d'erreurs et des valeurs aberrantes que vous pourriez rencontrer dans votre problème.
@Hooked Eh bien, oui, cela nécessite des paramètres assez nombreux. Et s'il y a trop peu de points de données, il est obligé d'échouer.
Merci pour les liens utiles. Je les ai remarqués pour les travaux futurs. Cependant, il me semble que mon problème est de cesser de fumer "trivial" d'utiliser de telles solutions sophistiquées.
Peut-être qu'un simple algorithme serait d'abord de calculer le centroïde des points (à condition qu'ils soient généralement régulièrement espacés régulièrement). C'est le centre de cercle. Une fois que vous avez que vous pouvez calculer le rayon moyen des points, donnant le rayon du cercle.
Une réponse plus sophistiquée peut être de faire une simple minimisation, où vous minimisez la somme des distances des points sur le bord du cercle (ou de la distance carrée).
J'utiliserais La fonction d'adaptation est simple car un cercle est simple. Il vous suffit de trouver la distance radiale de votre cercle d'ajustement à vos points car la surface tangente (radiale) sera toujours la meilleure solution. sciped au meilleur- "Ajuster" un cercle sur mes points. Vous pouvez obtenir un point de départ pour le centre et le rayon par un simple calcul du centre de masse. Cela fonctionne bien si les points sont uniformément distribués sur le cercle. S'ils ne sont pas, comme dans l'exemple ci-dessous, il est encore meilleur que rien! 
Cela fonctionne bien uniquement s'il n'y a pas de valeurs aberrantes réelles, voir i.imgur.com/pki3nn7.png pour un résultat après avoir ajouté une valeur aberrante. Si les erreurs de mesure n'incluent pas ce type d'erreur, cette approche est essentiellement bien.
@MMGP a accepté. Je suis allé avec l'hypothèse de l'OP: "J'ai des polygones, cela devrait être en fait des cercles" que les points sous-jacents sont des cercles perturbés. La bonne chose est que vous puissiez facilement obtenir une erreur d'ajustement, et vous pouvez répéter les convulsions en supprimant un point errant ou deux et de revérifier. Je pense aussi que vous pouvez faire des biais contre les valeurs aberrantes en augmentant la peine d'erreur de ^ 2 à dire ^ 4.
Fondamentalement, c'est exactement ce que j'ai fait. J'aime l'idée supplémentaire d'optimiser le meilleur ajustement. Merci pour ça.
Il est assez facile de trouver une approximation:
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()
Aucun manque de respect prévu, mais comment est-ce différent de ce que je fais sauf sans optimisation? Il en souffrira également, en tant que notes de MMGP, de toutes les valeurs aberrantes et , comme vous le souhaitez, si les points ne sont pas choisis uniformément sur le cercle.
En effet, juste pour faire des choses juste: i.Imgur.com/4f5IP42.png , aberrant (50, 50). Ransac trouvera le cercle approprié (oui, je vends ma réponse).
J'ai écrit ma réponse avant que votre réponse soit visible. C'était juste comme un point de départ pour l'optimisation. J'ai envisagé de mettre du code ici de mon paquet eegpy , où je fais presque la même chose, mais pour les coordonnées d'électrodes en 3D et une sphère: github.com/thorstenkranz/eegpy/blob/master/eegpy/plot/topo.p y
Et oui, les valeurs aberrantes sont un problème, mais les exemples que vous avez créés sont éloignés de la définition de l'OP.
Peut-être que vous pouvez utiliser la méthode de moindres carrés. Voici un fichier PDF d'un papier écrit sur la recherche d'un cercle en utilisant la méthode des moindres carrés. Ce pourrait être un complexe TAD pour ce que vous faites. Si les points sont à peu près un cercle, vous pouvez probablement trouver une méthode plus élémentaire qui fonctionnera très bien.
Les moindres carrés ressemblent à la voie à suivre si vous connaissez déjà le centre. Cela devient essentiellement un problème d'ajustement de courbe avec les coordonnées polaires.
Vérifiez le transformation de Hough . Cela conduit à une solution de détection de cercle simple.