CONCAVE-Polygonscheitelpunkte im (Zähler) im Uhrzeigersinn bestellen?

Question

Ich habe eine Reihe von ungeordneten Scheitelpunkten, die ein konkaves Polygon bilden können. Jetzt möchte ich sie entweder im oder gegen den Uhrzeigersinn bestellen.

An answer here schlägt vor, die folgenden Schritte:

• Finden Sie das Polygon-Zentrum
• Compute Winkel
• Bestell Punkte Winkel

Dies ist natürlich nur für konvexen Polygon und wird fehlschlagen, wenn die Punkte bilden eine konkave.

Wie kann ich dies zu einem konkaven machen?

Ich benutze Python, aber alle generischen Antworten willkommen.

Answer 1

Im Allgemeinen scheint Ihr Problem unklar definiert. Um zum Beispiel den folgenden Satz von Eckpunkten gegeben:

 

, welche dieser nicht-konvexe Polygone würden Sie als die „richtige“ Weg, um sie zu verbinden?

     

Nun, natürlich gibt es verschiedene Kriterien, die Sie wählen zwischen verschiedenen möglichen Aufträge nutzen könnten. Sie können beispielsweise die Reihenfolge auswählen, die die Gesamtlänge der Kanten minimiert, was zu ziemlich "vernünftigen" Ergebnissen führen sollte, wenn die Punkte tatsächlich nahe beieinander an der Grenze eines einfachen Polygons liegen :

 

Leider für einen allgemeinen Satz von Punkten, die Ordnung zu finden, die die Gesamtkantenlänge erweist sich als a well known NP-complete problem minimiert. Das heißt, es gibt viele heuristic algorithms, die in der Regel finden eine fast optimale Lösung schnell, auch wenn sie nicht immer garantieren können, dass die Lösung, die sie finden, das wahre Minimum ist.