Gausi - Fr 18.09.09 16:19
Titel: Nächsten Punkt im Uhrzeigersinn finden

---

Ich hab da ein kleines Problem mit nem dicken Brett vorm Kopf, soll heißen: Mein Code geht nicht. :oops:

Folgendes Problem. Ich habe einen Punkt, um den herum weitere Punkte angeordnet sind. Von einem dieser äußeren Punkte bin ich gerade gekommen, und möchte nun den nächsten Punkt im Uhrzeigersinn (oder halt immer genau andersrum) herausfinden. Wie mach ich das?

Hintergrund: Ich habe einen (nicht planaren) Graphen in der Ebene eingebettet und möchte die äußere Kontur bestimmen. Einen Punkt zu finden ist einfach (halt einen mit minimaler X-Koordinate). Und dann möchte ich halt auf dem "Rand" weiterlaufen. Gewissermaßen an jedem Kreisverkehr (Knoten) direkt die erste Ausfahrt wieder raus.

Das sieht also so aus:


Dummerweise verläuft sich mein Code regelmäßig und verfranst sich dann total - daher poste ich ihn gar nicht und hoffe auf klärende, frische Denkansätze. :D

delfiphan - Fr 18.09.09 16:35

---

Du willst die konvexe Hülle [http://de.wikipedia.org/wiki/Konvexe_H%C3%BClle] finden? Da gibt es einige Algorithmen, meistens O(n log n)
Im Prinzip sortiert man die Punkte nach Winkel und baut sich ein immer grösser werdendes Polygon auf.

Gausi - Fr 18.09.09 16:45

---

Nein, einfach nur die Hülle. Konvex muss das nicht sein. Bei der konvexen Hülle kann ich ja beliebig Punkte verbinden, hier darf ich nur solche verbinden, die durch eine Kante verbunden sind. Und irgendwie läuft mein Verfahren zur Bestimmung des kleinsten nächsten Winkels öfter mal in die falsche Richtung. :autsch:

delfiphan - Fr 18.09.09 16:49

---

Wie berechnest du denn die Winkel? ArcTan2?

Gausi - Fr 18.09.09 17:37

---

Indirekt, ich nehm ArcCos, und das verwendet ja ArcTan2. Klar, da kommt ein Wert zwischen 0 und Pi raus. Da addiere ich aber auch schonmal Pi drauf, um den "richtigen Winkel" zu bekommen. Vermutlich hab ich da den Fehler, aber wie gesagt: Brett vorm Kopf. Deswegen mein Ansatz hier: Mal von vorne anfangen. ;-)

delfiphan - Fr 18.09.09 17:41

---

Gausi hat folgendes geschrieben :

Indirekt, ich nehm ArcCos, und das verwendet ja ArcTan2 (...) Vermutlich hab ich da den Fehler

Aber wieso nicht gleich ArcTan2? Die Funktion ist dafür konzipiert und du gehst Spezialfälle wie Division durch 0 aus dem Weg. Einfach ∆x und ∆y als Eingabe und schon kriegst du den Winkel.

Gausi - Mo 21.09.09 15:19

---

Ok, das Brett war noch dicker als gedacht. Kann sein, dass das mit den Winkeln doch alles richtig war, aber das Verfahren ist generell Banane, soll heißen: Das, was ich da finden möchte, muss gar nicht existieren, da nicht jeder Kreuzungspunkt zwischen zwei Knoten auch wieder ein Knoten sein muss. Wenn man so ein Konstrukt wie im Bild hat, dann fängt der Unsinn halt an...

Danke trotzdem für die Hilfe, ich werde das wohl komplett anders lösen müsssen (mit der konvexen Hülle als Basis, und dann Hüllen-Kanten, die nicht existieren, durch kürzesete Wege ersetzen)