Approximieren eines Polygons mit einem Kreis
Nun, die Annäherung eines Kreises mit einem Polygon und die Geschichte von Pythagoras mögen gut bekannt sein. Aber was ist umgekehrt?
Ich habe einige Polygone, das sollten Kreise sein. 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 können wir zwei verschiedene Beispiele sehen.
Mein erster Ansatz war es, den maximalen Abstand der Punkte zur Mitte und zum Minimum zu finden. Der Kreis, nach dem wir suchen, liegt vielleicht irgendwo dazwischen.
Gibt es einen Algorithmus für dieses Problem?
5 Antworten
Ich würde scipy verwenden, um einen Kreis auf meine Punkte zu "passen". 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 folgenden Beispiel, 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.
%Vor% 
Vielleicht wäre ein einfacher Algorithmus, zuerst den Schwerpunkt der Punkte zu berechnen (vorausgesetzt, sie sind normalerweise in etwa gleichmäßig beabstandet). 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 ausgeklügeltere Antwort könnte eine einfache Minimierung sein, bei der Sie die Summe der Abstände der Punkte zum Rand des Kreises (oder der Entfernung im Quadrat) minimieren.
Es gibt zwei verschiedene O (n) -Algorithmen zum Bestimmen des kleinsten gezeichneten Kreises, der eine Reihe von Punkten auf der Wikipedia-Seite umfasst. Kleinste-Kreis-Problem . 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 ist vielleicht nicht genau das, was Sie wollen, aber so würde ich anfangen.
Dieses Problem könnte mit dem Problem des kleinsten Kreises identisch sein.
Aber da Sie Messfehler haben, die Ausreißer enthalten könnten, ist RANSAC eine gute Option. Einen Überblick über die Methode (sowie andere grundlegende Techniken) finden Sie Ссылка in Ссылка gibt es weitere Informationen für die Kreisanpassung.
Es ist ziemlich einfach, eine Annäherung zu finden:
%Vor%Erklärt: Lege den Mittelpunkt des Kreises auf das mittlere x und das mittlere y deiner Punkte. Bestimmen Sie dann für jeden Punkt den Abstand zum Mittelpunkt und nehmen Sie den Mittelwert über alle Punkte. Das ist dein Radius.
Dieses vollständige Skript:
%Vor%erzeugt dieses Diagramm:
Dies funktioniert gut, da Sie Polygone mit Messfehlern haben. Wenn Ihre Punkte nicht annähernd gleichmäßig über die Winkel [0,2pi[ verteilt sind, wird es schlecht funktionieren.
Allgemein könnten Sie die Optimierung verwenden.
Tags und Links python computational-geometry