[Festgefressen] Konvexhülle eines polygon berechnen

[jfheins]

@TiGü: Siehe auch hier: http://www.delphipraxis.net/177251-javars-march.html

Zum Winkel: Was schonmal auffällt: Du benötigst DREI Punkte, um einen Winkel aufzuspannen. Bei drei Punkten A, B und C lassen sich zwei Strecken, oder besser noch: Vektoren, AB und BC definieren, zwischen denen dann der Winkel bestimmt wird.

Du berechnest also momentan eben nicht die Innenwinkel. Zur Bestimmung eines Extrempunkts (als Startpunkt für den Graham-Scan) würde sich diese Funktion bedingt eigenen, aber nicht zur Innenwinkelberechnung. Außerdem hast du noch einen Bug drin, üblicherweise schreibt man arctan(y/x). Und am besten nimmt man direkt ArcTan2(y, x) dann bekommt man auch Winkel über den ganzen Kreis.

[Lemmy]

Zitat von jfheins:

Zum Winkel: Was schonmal auffällt: Du benötigst DREI Punkte, um einen Winkel aufzuspannen. Bei drei Punkten A, B und C lassen sich zwei Strecken, oder besser noch: Vektoren, AB und BC definieren, zwischen denen dann der Winkel bestimmt wird.

exakt... mit 2 Punkten, also einem Vektor lässt sich maximal die Richtung bestimmen - was imho für den Algo aber auch funktionieren sollte.

Zitat von jfheins:

Außerdem hast du noch einen Bug drin, üblicherweise schreibt man arctan(y/x). Und am besten nimmt man direkt ArcTan2(y, x) dann bekommt man auch Winkel über den ganzen Kreis.

hm... kommt darauf an... in der Vermessungstechnik sind die Bezeichnungen der Achsen vertauscht (x zeigt nach oben, y nach rechts) und auch der Drehwinkel ist entgegengesetzt dem der Mathematik. Insofern KANN das korrekt sein.

[Mokus]

Zeichnerrisch mit Paint ...
Ich habe den Startpunkt; Puntk 1
und ich habe den end Punkt, punkt 2.

Von deisen Beiden rechne ich doch den innen winkel mit Tangenz aus ?

Oder bin ich da Mathematisch gerade falsch !?



[edit] Aber wie kann ich den nun den Javars March richtig anwenden ?! [/edit]

[jfheins]

Du hast jetzt leider kein Koordinatensystem gemalt, aber ja, das ist der Winkel, den du berechnest. Ich glaube aber nach wie vor, dass das nicht der Winkel ist, den du berechnen solltest. In deinem pdf steht nämlich:

Zitat:

In CW manner, always
making right turns
􀂄 If fail to turn right,
delete previous point
until the turn is correct.

Und um festzustellen, ob man sich gerade nach "rechts" gedreht hat, reicht der Winkel zur Y-Achse eben nicht aus. (Es sei denn, du speicherst den Winkel von allen vorhergehenden Linien, aber danach sieht mir dein Code nicht aus) Die Beurteilung "rechts" geht ja immer von der letzten Bewegungsrichtung aus. Falls du also vom Punkt A kommt und gerade bei Punkt B bist, ist die Frage ob der Winkel ABC kleiner oder größer als 180° ist. (Alternativ: Ist der Winkel zwischen Y-Achse und AB größer oder kleiner als der Winkel der Y-Achse mit BC ?)

[Mokus]

result := cos((sqr(dx) - sqr(dy) - sqr(SeiteC)) / (-2 * dy * SeiteC));
Lautet so der Kosinussatz, wenn ich nach Aplha suche,
oder muss ich noch cos 2 machen ? O.o

[jfheins]

Der Kosinussatz hat mit dem Problem leider nichts zu tun. Da du dich dagegen so sträubst, vermute ich mal dass du in der Schule noch keine Vektorrechnung hattest.

Das ist aber auch gar nicht so schlimm, schließlich habe ich dir in dem anderen Thread ja schon diese Formel verlinkt:
http://upload.wikimedia.org/math/6/c...c3fb51c462.png
Dort kannst du einfach die x und y Koordinaten deiner drei Punkte einsetzen und bekommst eine eindeutige Lösung.