Winkelberechnung im Gegenuhrzeigersinn bei Graphen |
24.03.2011, 18:40 | markusin | Auf diesen Beitrag antworten » | ||
Winkelberechnung im Gegenuhrzeigersinn bei Graphen 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 |
||||
24.03.2011, 19:53 | riwe | Auf diesen Beitrag antworten » | ||
RE: Winkelberechnung im Gegenuhrzeigersinn bei Graphen was sind denn u und v |
||||
25.03.2011, 11:14 | markusin | Auf diesen Beitrag antworten » | ||
RE: Winkelberechnung im Gegenuhrzeigersinn bei Graphen u,v sind Knoten (P1,P2,P3,P4) |
||||
25.03.2011, 12:00 | riwe | Auf diesen Beitrag antworten » | ||
RE: Winkelberechnung im Gegenuhrzeigersinn bei Graphen
kannst du mir den 1. satz/ absatz 2 übersetzen |
||||
25.03.2011, 13:12 | 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 |
||||
25.03.2011, 13:29 | 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 wenn du nichts passendes findest, kriegst du ein paar links von mir - nächste woche. (ich bin rentner und in meiner datscha |
||||
Anzeige | ||||
|
||||
28.03.2011, 20:10 | 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 |
||||
30.03.2011, 09:29 | 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 |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|