Gegeben ein Vektor von Punkten (möglicherweise nicht in der richtigen Reihenfolge), finde Polygon (nicht konvexe Hülle)

1. Heuristik zur Bestimmung der Form

Es gibt keine eindeutige Lösung, daher gibt es keinen einfachen Algorithmus. Sie könnten versuchen, Ihre Intuition irgendwie nachzuahmen.

• Beginnen Sie mit einem zufälligen Punkt und verbinden Sie jeden Punkt mit seinem nächsten Nachbarn. Verbinden Sie dann den letzten Punkt mit dem ersten.
• Beginnen Sie mit der Auswahl eines Punktes und seines nächsten Nachbarn und verbinden Sie sie mit einer Linie. Fügen Sie nun iterativ einen weiteren Punkt hinzu. Wählen Sie immer den Punkt, der den Winkel zwischen dem letzten Liniensegment und dem neu hinzugefügten Liniensegment minimiert.

Beide Methoden funktionieren im Allgemeinen nicht wirklich, sie garantieren nicht einmal Kreuzungen zu vermeiden. Sie können versuchen, dies durch Rückverfolgung zu beheben, wenn Sie einen offensichtlichen Fehler (z. B. eine Kreuzung) feststellen und dann zum letzten Entscheidungspunkt zurückgehen und stattdessen den "zweitbesten" Ansatz wählen, ....

Aber da die Lösung nicht einzigartig ist, erwarte nicht zu viel von diesen Heuristiken.

2. Durchschnitt der Ecken

Der Durchschnittspunkt für die Scheitelpunkte ist einfach zu berechnen. Fügen Sie einfach alle Punkte zusammen und teilen Sie durch die Anzahl der Punkte, die Sie gerade hinzugefügt haben, dies ist der Durchschnitt. Was dich wahrscheinlich mehr interessiert, ist der Mittelpunkt im Sinne von "Schwerpunkt", siehe unten.

3. Mittelpunkt

Um den Massenschwerpunkt zu bestimmen, müssen Sie zuerst die Form definieren. Das bedeutet, dass Sie etwas wie Schritt 1 tun müssen.

Eine einfach zu implementierende Methode zur Berechnung des Mittelpunkts für das Polygon ist.

• Setzen Sie einen Begrenzungsrahmen um das Polygon.
• Erzeugt zufällig Punkte innerhalb der Begrenzungsbox.
• Bestimmen Sie für jeden dieser Punkte, ob er innerhalb des Begrenzungsrahmens ist, falls nicht, dann werfen Sie ihn weg. Um festzustellen, ob sich ein Punkt in einem beliebigen Polygon befindet, verwenden Sie einen Strahlentest .
• Für alle Punkte, die Sie behalten haben, wenden Sie Ansatz 2 an. Der Durchschnittspunkt dieser Punkte ist eine gute Annäherung an den Mittelpunkt.

Es gibt keine eindeutige Lösung für ein konkaves Polygon:

Das konvexe Polygon kann eindeutig als die konvexe Hülle der Punkte gefunden werden (wenn Sie wissen, dass die Punkte ein konvexes Polygon bilden).

Eine gegebene Menge von Punkten kann im Allgemeinen auf viele Arten verbunden werden, um ein sich nicht selbst schneidendes Polygon zu bilden. Sie können Pech haben, es sei denn, Sie haben mehr Informationen über die Arten von Polygonen, die die Punkte darstellen könnten.