Mathe - Punkte im Polygon sortieren
-
Hallo zusammen!
Ich verzweifle noch.
Gegeben seien mehrere Punkte im (2d) Raum durch Ihre Koordinaten x,y.
Ich möchte nun um die Punkte eine Linie (Polygon) zeichnen.
Das Polyxgon soll bestimmt sein durch die außenliegenden Punkte.Ich habe es immerhin schon mal geschafft, aus einer Fülle von Punkten die außenliegenden Punkte zu ermitteln.
Aber wenn ich jetzt ein Polygon zeichne, geht das Polygon wild durcheinander da die Punkte ja nicht sortiert sind.
Eine erste Überlegung war, einfach von einem Punkt zu seinem nächsten eine Linie zu ziehen. Problem sind dabei Punkte die zwar weiter weg von einem Punkt, aber trotzdem jetzt "eingegliedert" werden müssen.Bsp:
A..............B
.....................................C
D..............E (Die Punkte(.) sind nur zur Darstellung - also nicht als Linien gedacht)Wie würden die Linien nun verlaufen???
Es müsste die Linie über A-B-C-E-D-A verlaufen.
Also eine Linie von B nach C (aber nicht B nach E obwohl der Punkt E schliesslich näher an B liegt!!!)Hoffe, ihr könnt mein Problem verstehen.
Gruß
Riese
-
Wäre das hier vielleicht auch eine Lösung für Dein Problem?
-
Eigentlich eine gute Idee.
Aber woher weiß ich den "Ursprung" zwischen denen die Punkte gerechnet werden können.
Ich habe zwar einen Algorithmus mit dem ich den Schwerpunkt der Figur berechnen kann, der nützt aber nix, da dazu die Punkte in der richtigen Reihenfolge sein müssen.
Ich werde mal weiter darüber nachdenken ...
Die Idee die Sache in Polarkoo. umzurechnen ist gut!
-
Mach doch den Schwerpunkt zum Nullpunkt...
-
RieseXXL schrieb:
Eigentlich eine gute Idee.
Ich habe zwar einen Algorithmus mit dem ich den Schwerpunkt der Figur berechnen kann, der nützt aber nix, da dazu die Punkte in der richtigen Reihenfolge sein müssen.Die Punkte liegen nicht in der richtigen Reihenfolge - das ist ja mein Problem!
-
Rechne sie nach Polar um und sortiere die Punkte nach aufsteigendem Winkel. Benutze den Schwerpunkt als Mittelpunkt für die Polardarstellung.
-
Convexe huelle?
http://www.google.com/search?hl=en&ie=UTF-8&oe=UTF-8&q=Graham+convex+hull&btnG=Google+Search
-
Wow!!!
Also die Geschichte mit der Graham Convexen Hülle ist sehr interessant.
Allerdings verstehe ich die Sache nicht so ganz.
Also ich suche mir einen Punkt der auf jeden Fall auf der Hülle liegt (zB. Punkt mit max. Y).
Dann bilde ich Dreiecke zu den anderen Punkten und vermesse die Winkel (zu der Horizontalen oder wie wird der Winkel gemessen???)
Dann werden die Punkte sortiert nach aufsteigendem Winkel.
Dann kommt der eigentliche Algorithmus in dem irgendwie nach rechts/links sortiert werden muss. Wie das funzt habe ich kein Plan.
Kann mir jemand helfen (b7f7 vielleicht?)?
Hat jemand vielleicht sogar einen Algorithmus in C, Pascal o.ä.?Gruß
Riese
-
ich habe damals einen Punkt der "neben" Ymax liegt genommen(wenn zwei punkte gleichen Ymax wert haben ist der winkel halt Null).
Mein algo kann ich leider nicht posten, denn der war fuer meinen Arbeitgeber
Fuer die winkel kann ich dir nur raten eine Sortierung zu verwenden welche schnell ist.
immer bedenken in welchem Wertebereich die winkel sein koennen.
Histogramm der moeglichen winkel und das dann als lookup table zum sortieren.
und dann feinsortieren mit sort() aus der STL die Sortierung muss genau sein weill sonst der algo gegen den Baum geht.dann kommt die sache mit dem Stack und dem "2D-Kreuzprodukt" wo entschieden wird auf welcher seite einer graden ein punkt liegt (rechts/links abbiegen).
-
Das mit dem "Arbeitgeberproblem" ist klar!
b7f7 schrieb:
dann kommt die sache mit dem Stack und dem "2D-Kreuzprodukt" wo entschieden wird auf welcher seite einer graden ein punkt liegt (rechts/links abbiegen).
Kannst Du da noch ein paar Worte verlieren?
Was muss getan werden wenn welcher Punkt auf welcher Seite?!
Häh!? Verstehe das irgendwie net so.Gruß
Riese
-
in nem anderen beitrag war da grad was
http://www.c-plusplus.net/forum/viewtopic.php?t=47645
es lohnt sich dazu auch mal die Java anims anzusehn die google findet.