[Festgefressen] Konvexhülle eines polygon berechnen

[Mokus]

Hey Community,

ich habe ein Problem.
arbeite seit nun ein paar Tagen ein einem Problem .
Ich habe mir ein Programm ausgearbeitet, jedenfalls versucht, das die Konvexe hülle eines Polygons berechnene soll.
Soweit sogut, ich habe mir die einzelnen Winkel berechnet etc.
MIt Testparameter ausprobiert, das Polygon X Mal gezeichent, aber es haut nicht hin.
Ab den Punkt 546 | 801 ist ein Winkel kleiner, als der auf der Hülle.
Und daher versaut es mir die ganze berechnung.
Nun wollten ich irgendwie irgendwas versuchen mit dem Letzen Winkel als parameter mitgeben und von dort aus die WInkel berechnen....
Weiß nur noch nicht so ganz wie.

Ich lade euch mal das Projekt hoch, und wäre euch echt dankbar wenn ihr mir da irgendwie helfen könntet.

( wäre auch supaa, wenn ihr mir meinen Fehler zeigt ggf auch erläutert)

Dank im Vorraus

[Mokus]

Nun gut,
mir wurde zu Ohren getragen, dass dieser Topic nicht sehr genau ist, und ich daher nicht mit Hilfe rechnen kann.
Also werde ich etwas konkreter;

Ich habe ein Polygon, mit verschiedenen Punkten. DIe Punkte werden per Mausklick gespeichert.
Um die Konvexehülle zu erzeugen, wollte ich zu jeden Punkt ein Dreieck bilden und deren Winkel bestimmen.
Diese Winkel kontrollier ich dann, und such dann nach dem größten, ggf den kleinsten.
( Hängt halt davon ab, wierum gelaufen werden soll. )
Nun ist aber das Problem, ich bestimm die Innenwinkel und gleiche diese Miteinnander.
Diese Ergebnisse könnten gefälscht werden.

folgende Function sollte es mir aber errechnen.

Delphi-Quellcode:

function TPoly.berechneWinkel(Punkt1, Punkt2: TPunkt): Real;
var
  dx, dy: Real;
begin

  dx := Punkt2.IXKoordinate - Punkt1.IXKoordinate;
  dy := Punkt2.IYKoordinate - Punkt1.IYKoordinate;
  
    if (dx = 0) and (dy = 0) then
    begin
      result := 360;

   end
    else
      result := RadToDeg(ArcTan(dx / dy));
  end;
end

Nun ist die Frage, das ist eher eine mathematisches Problem, wie kann ich per Delphi die AUSSENwinkel errechnen ?

[TiGü]

Welchen Algorithmus verwendest du denn?
Graham-Scan, Jarvis-March...?

[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.