Der beste Algorithmus, um die Kanten (Polygone) von Scheitelpunkten zu finden

Question

Ich habe eine große Anzahl von Scheitelpunkten, einige davon sind Kanten, einige sind redundant (innerhalb der Form) und ich möchte diese entfernen.

Der einfachste Algorithmus, den ich mir vorstellen kann, besteht darin, einen nach dem anderen zu überprüfen, wenn sie die von den anderen gebildete Form treffen. Aber es sollte ein sehr langsamer Algorithmus sein.

Ich dachte daran, eine von der Kante (die am weitesten vom Ursprung entfernt pro Beispiel) zu wählen und den längsten Weg von diesem Anfang zu berechnen ... sollte den Kantenweg bekommen, richtig?

Irgendwelche Vorschläge?

Answer 1

Der Trick mit polyedrischen Algorithmen ist die Wahl eines, das zu Ihrer Eingabe und Ihrer gewünschten Ausgabe passt, da es mehrere Möglichkeiten zur Darstellung eines Polyeders gibt und die Konvertierung zwischen den Darstellungen teuer sein kann. In diesem Fall beginnen Sie mit Punkten und möchten mit Scheitelpunkten enden. Daher sollte der Graham scan Algorithmus zur Berechnung der Scheitelpunkte der convex hull den Zweck erfüllen, obwohl es einige Anstrengungen erfordern könnte, ihn über den 2-D-Fall hinaus zu erweitern. Es ist O (n log n) in der Anzahl der Eingabeecken.

Answer 2

Ich weiß nicht, was der beste Algorithmus ist, um das Polygon zu finden, aber das Polygon, nach dem Sie suchen, heißt "Convex Hull".

Wenn Sie danach suchen, sollten Sie einen passenden Algorithmus finden.

Answer 3

The Convex Hull ist eines der am meisten erforschten Probleme der Computational Geometry. Der Graham Scan ist einer der einfacheren convex hull algorithms, aber sicher nicht der einzige. The Gift-wrapping Algorithm, auch Jarvis 'March genannt, ist die einfachste, die ich kenne. The Stony Brook algorithm repository hat mehrere Implementierungen von konvexen Hüllenalgorithmen in C und C++. Geometry in Action zeigt hauptsächlich Anwendungen von konvexen Rümpfen. Hier ist eine Sammlung von low-dimensional und arbitrary-dimensional konvexen Hüllen Berechnungsprogrammen.