Bester Algorithmus die Kanten (Polygon) der Scheitelpunkte finden

Question

Ich habe eine große Reihe von Eckpunkten, sind einige von ihnen Kanten, einige redundant sind (in der Form), und ich möchte diejenigen entfernen.

Der einfachste Algorithmus, den ich denken konnte, eins nach dem anderen überprüft, ob sie die Form von den anderen gebildet getroffen. Aber es soll ein sehr langsamer Algorithmus sein.

Ich dachte an einem von der Kante (der einer am weitesten vom Ursprung pro Beispiel) Kommissionierung und berechnet den längsten Weg von diesem Anfang ... sollte den Randweg, nicht wahr?

Jeder Vorschlag?

Answer 1

Der Trick mit polyedrischen Algorithmen ist die Wahl ein, die mit Ihrem Eingang und die gewünschten Ausgabe paßt, da es mehr als ein Weg, um einen Polyeder und die Umwandlung zwischen den Darstellungen darstellen kann teuer werden. In diesem Fall beginnen Sie mit Punkten und wollen mit den Eckpunkten beenden, so dass der Graham scannen Algorithmus zu berechnen, sollten die Eckpunkte des konvexe Hülle den Trick tun, obwohl es einige Mühe könnte zu verlängern es vorbei an dem 2-D-Fall. Es ist O ( n log n ) in der Anzahl von Eingangsscheitelpunkten.

Answer 2

Ich weiß nicht, was der beste Algorithmus, dass Polygon zu finden ist, aber das Polygon das Sie suchen, ist „Convex Hull“ genannt.

Mit dem für die Suche, sollten Sie einen Matching-Algorithmus finden.

Answer 3

die konvexe Hülle einer der recherchierten Probleme der Computational Geometry ist. Der Graham Scan ist eine der einfacheren konvexe Hülle Algorithmen , aber sicherlich nicht der einzige. The Gift-Wrapping-Algorithmus , auch Jarvis' March genannt, ist die einfachste ich kenne. The Stony Brook Algorithmus Repository hat mehrere Implementierungen von konvexen Hülse Algorithmen in C und C ++. Geometrie in Aktion hauptsächlich Anwendungen von konvexen Hüllen zeigt. Hier ist eine Sammlung von niedrig-dimensionalen und beliebige dreidimensionale konvexe Hülle Berechnung Programme