Javars March

[Mokus]

HEy ;

so mal ne kleine Frage zu Javars March.

(
http://en.wikipedia.org/wiki/Gift_wrapping_algorithm
)

Wie kann man am besten die virtuelle Gerade zeichnen und kontrollieren ob dort ein Punkt Drauf ist ?
Hab es erst versucht mit einem Steigungsdreieck, dass hab ich aber gelöscht, hatte nicht ganz so hingehauen wie ich wollte.
NUn fang ich wieder von 0 an und wollte mal ein Paar Tipps & Tricks von euch hören...
Hoffe irgendwer hatte das schon einmal gemacht

[jfheins]

Ich würde einfach von allen verbliebenen Punkten den Winkel ausrechnen und dann den kleinsten Winkel hernehmen. (Wenn man die konvexe Hülle im Uhrzeigersinn aufbaut)
Hmmm ... okay das wäre dann wohl http://de.wikipedia.org/wiki/Graham_Scan
Dort ist auch ein schöne Formal angegeben für dein Problem, ob ein gewisse Punkt C auf, links oder rechts der Gerade AB liegt.

Falls du aber ohnehin schon ein Polygon hast, kannst du auch alle Punkte aus dem Polygon entfernen, deren Innenwinkel >= 180° ist. Dann sollte die konvexe Hülle des Polygons übrig bleiben

[Mokus]

http://140.129.20.249/~jmchen/compg/slides/chull.pdf

ab seite 15.

Dort wurde gesagt keine rechts kurve.

Hat wer ne idee , wie man sowas machen könnte ?

[jfheins]

Zitat von Mokus:

ab seite 15.
Dort wurde gesagt keine rechts kurve.

Hä? Dort wird ein Algorithmus gezeigt. Welchen teil davon bringst du jetzt mit "keine rechts kurve" in Verbindung? Der Algorithmus ist ja einmal unterschiedlich für den oberen und den unteren Rand. Beim oberen Rand soll er auch nur Rechtskurven machen - bei einer Linkskurve werden ja Knoten gelöscht, bis sich eine Rechtskurver ergibt. Unten ist es dementsprechend umgekehrt.

Allgemein würde ich aber empfehlen, direkt den Algo von Folie 31/32 zu nehmen - wegen dem besseren Handling von Kollinearen Punkten.

Bei solchen Problem freuen wir uns natürlich auch immer über Code. Das ist aber auch nicht alles: Bei deiner letzten Frage hast du einfach mal zwei Dateien angehängt, das war vielleicht etwas zu viel. Genau richtig muss es sein Und dann ist es bei so einem geometrischen Problem auch immer Hilfreich eine Skizze oder Zeichnung zu haben um dein Problem (und das Problem mit deinem Code) besser zu verstehen. Was ist die Ausgangssituation? Was macht der Code? Was sollte stattdessen passieren?