Punkte so ordnen, dass konvexes Polygon entsteht

25.10.2018, 09:13

cawa132

Punkte so ordnen, dass konvexes Polygon entsteht

Meine Frage:
Hallo Leute,

zum Berechnen eines Flächeninhaltes eines Polygons (im 2D) mit 3 bis maximal 6 Eckpunkten, wollte ich die Gauß'sche Trapezformel nutzen. So wie ich das verstanden habe, ist da die Reihenfolge der Punkte entscheident. Leider bekomme ich die Punkte aus dem Programm (Excel, vba) so, dass ich nicht 100%ig zuordnen kann, wie die Reihenfolge ist.
Meine Frage wäre: Nach welcher Methode kann ich die Punkte ordnen, dass immer ein konvexes Polygon entsteht? (Ich behaupte, dass es bei gegebenen Punkte nur exakt eines gibt(?))

Meine Ideen:
Als Definition für den ersten Punkt habe ich mir schon überlegt, dass ich jenen nehmen kann, der vom Koordinatenursprung(x,y) den geringsten Abstand hat. Aber ohne jetzt weitere Annahmen zu treffen fällt mir nicht ein, wie ich die nächsten Punkte zuordnen soll.

Als "bruteforce"-Methode fiel mir noch ein, einfach die Fläche für jede Punktereihenfolge zu berechnen und dann die betragsmäßig größte Fläche zu nutzen. Aber das wäre natürlich nicht sooo elegant smile

Danke für eure Ideen!

25.10.2018, 09:17

cawa132

Auf diesen Beitrag antworten »

Zusatz:
Leider kann ich meinen Beitrag nicht bearbeiten, daher schreibe ich es hier:
Ich habe natürlich direkt nach dem Absenden des Beitrages mal mehr als 4 Punkte aufgezeichnet und schon bemerkt, dass es mehr als ein konvexes Polygon gäbe. Ich suche allerdings immer das mit der betragsmäßig größten Fläche.

25.10.2018, 09:57

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von cawa132
Ich habe natürlich direkt nach dem Absenden des Beitrages mal mehr als 4 Punkte aufgezeichnet und schon bemerkt, dass es mehr als ein konvexes Polygon gäbe.

Wenn die $\begin{eqnarray*} n \end{eqnarray*}$ Punkte (in einer bestimmten Reihenfolge) tatsächlich ein konvexes Polygon bilden, dann gibt es am Ende wirklich auch nur dieses eine Polygon, welches alle gegebenen Punkte enthält. (Wenn du von "mehr als ein" sprichst, redest du anscheinend von was anderem. verwirrt

)

Eine allgemeinere Situation:

Hat man $\begin{eqnarray*} m \end{eqnarray*}$ Punkte in der Ebene, von denen keine drei auf einer Gerade liegen, so gibt es darunter genau eine Auswahl von Punkten ( $\begin{eqnarray*} n \end{eqnarray*}$ an der Zahl, d.h. mit $\begin{eqnarray*} n\leq m \end{eqnarray*}$ ), welche als $\begin{eqnarray*} n \end{eqnarray*}$ -Eck dann die konvexe Hülle aller $\begin{eqnarray*} m \end{eqnarray*}$ Punkte bilden. Du betrachtest, soweit ich das verstanden habe, den Spezialfall $\begin{eqnarray*} n=m \end{eqnarray*}$ dieser allgemeineren Aussage. Die Voraussetzung "keine drei auf einer Gerade" kann man auch fallen lassen, dann kann es u.U. passieren, dass auf den Polygonkanten der konvexen Hülle auch noch weitere Punkte der Menge liegen.

Für diese allgemeinere Situation kenne ich einen Algorithmus, der diese $\begin{eqnarray*} n \end{eqnarray*}$ Punkte in der richtigen Reihenfolge aus den $\begin{eqnarray*} m \end{eqnarray*}$ gegebenen Punkten herausfischt. Mir ist auch so, als hätte ich den im Board hier schon mal gesehen. verwirrt

25.10.2018, 10:22

cawa132

Auf diesen Beitrag antworten »

Du hast recht, mein zweiter Beitrag ist schwachsinn, ich hatte einen kurzen Knoten im Gehirn smile

Ich habe beim Durchsuchen des Boards nichts gefunden, eventuell kenne ich einfach nicht die richtigen Schlagwörter unglücklich

Kennst du noch das Prinzip des Algorithmus? Mit einem Ansatz bekomme ich das sicher auch alleine hin.

25.10.2018, 10:29

cawa132

Auf diesen Beitrag antworten »

Ok, ich habe etwas gefunden:

- "Convex hull algorithms" ist das Schlagwort

... und werde es mal ausprobieren.

Neue Frage »

Antworten »

Punkte so ordnen, dass konvexes Polygon entsteht

Verwandte Themen