Winkelberechnung im Gegenuhrzeigersinn bei Graphen

Neue Frage »

markusin Auf diesen Beitrag antworten »
Winkelberechnung im Gegenuhrzeigersinn bei Graphen
Hallo Allerseits;

in meinen Algorithmus moechte ich in einem gerichteten Graphen, startend von einer (auesseren) Kante
alle Kanten besuchen, die mit dem kleinsten Winkel versehen sind.

Zu jeder Kante e(u,v) hab ich die Koordinaten von u und v. Dann berechne ich den Winkel zu den anliegenden Kanten, indem ich den Cosinussatz verwende. Jedochist die loesung nicht korrekt.
Ich schildere es kurz anhand dieses Bildes
, bei folgendem Bild hab ich ein Problem:
[attach]18777[/attach]


Nehmen wir an ich moechte den kleinsten Winkel (Gegen den Uhrzeigersinn)
zwischen (p1,p2) - (p2,p3) und (p1,p2) - (p2,p4)

Wenn ich den Cosinussatz verwende, erzeuge ich mir noch zusaetzlich die Linien (p1,p3) und (p1,p4), damit ich die Winkel P1P2P3 und P1P2P4 berechnen kann.
Mit dem Kosinussatz berechnet er mir folgendes:
P1P2P3 = 170 grad
P1P2P4 = 165 grad

Ich wuerde mir aber erwarten, dass P1P2P4 = 195 grad ergibt, weil der Winkel von (p1,p2) aus gemessen werden sollte.

Kennt jemand eine Loesung fuer mein Problem

Danke und Gruesse

Markus


edit: Bitte keine Links zu externen Hosts. Habe die Grafik als Dateianhang hochgeladen.
LG sulo
riwe Auf diesen Beitrag antworten »
RE: Winkelberechnung im Gegenuhrzeigersinn bei Graphen
was sind denn u und v verwirrt
markusin Auf diesen Beitrag antworten »
RE: Winkelberechnung im Gegenuhrzeigersinn bei Graphen
u,v sind Knoten (P1,P2,P3,P4)
riwe Auf diesen Beitrag antworten »
RE: Winkelberechnung im Gegenuhrzeigersinn bei Graphen
Zitat:
Original von markusin
u,v sind Knoten (P1,P2,P3,P4)


kannst du mir den 1. satz/ absatz 2 übersetzen verwirrt
markusin Auf diesen Beitrag antworten »
RE: Winkelberechnung im Gegenuhrzeigersinn bei Graphen
Logisch, sorry wg. meiner miserablen Formulierung:

Mein Algorithmus berechnet eine Art konvexe Huelle ueber einen gerichteten Graphen.
Ausgangspunkt ist jene Kante, die sich am weitesten oben links befindet.
Waehrend jeder Iteration wird immer diejenige Kante als naechstes bearbeiten, die den kleinsten Winkel im Gegen-Uhrzeigersinn hat.

In der obigen Abbildung ist die aktuelle Kante, die bearbeitet wird Kante(P1,P2):
man sucht sich alle angrenzenden Kanten {(P2,P3),(P2,P4)} und ermittelt die Winkel im GegenUhrzeigersinn: sprich
Winkel-P1P2P3 und Winkel-P1P2P4.

Wie kann ich dieses Problem mathematisch Loesen?

Hab ich mich jetzt deutlicher ausgedrueckt?

Gruesse Markus
riwe Auf diesen Beitrag antworten »
RE: Winkelberechnung im Gegenuhrzeigersinn bei Graphen
net wirklich oder doch.
formulieren wir es so:
P2 hat bei dir die (relativen) koordinaten (0/0) und P1 dann u1/v1 ? usw.

suche doch einmal unter "konvexe hülle", da gibt es jede menge zu finden Augenzwinkern

wenn du nichts passendes findest, kriegst du ein paar links von mir
- nächste woche.
(ich bin rentner und in meiner datscha Augenzwinkern
 
 
markusin Auf diesen Beitrag antworten »
RE: Winkelberechnung im Gegenuhrzeigersinn bei Graphen
Servus Werner,

ich hab mir jetz mal den Quickhull Algorithmus angeschaut. Hierbei wird der winkel zwischen dem aktuellen knoten und allen anderen gemessen.

Ich verstehe hier aber nicht das Konzept, sprich die mathematische Formel, die verwendet wird, um den Winkel zwischen P1,P3 und P1,P4 zu berechnen. Aus einigen Implementierungen sehe ich, dass die atan funktion verwendet wird. Koenntest du mir dies naeher erlaeutern?

Die Links kannst du mir dennoch schicken.

Danke

Gruesse Markus
markusin Auf diesen Beitrag antworten »
RE: Winkelberechnung im Gegenuhrzeigersinn bei Graphen
Hi,

ich hab jetzt das Problem loesen koennen;

ich hab die relative Position der x und y Koordinaten verwendet und diese der Funktion atan2() uebergeben.
Das waere in dem obigen Bild:
atan2(P3.y-P1.y , P3.x-P1.x) und
atan2(P4.y-P1.y , P4.x-P1.x)

und dann das minimum der beiden verwendet.

Gruesse Markus
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »