Hi!
Ich beschäftige mich zur Zeit mit geometrischen Algorithmen und bin gerade bei dem Problem der Berechnung des Schnitts zwischen 2 konvexen Polygonen. Ich habe mir hierzu mal einen Algorithmus angeschaut, der eine lineare Laufzeit besitzt (O(n)). Der Algorithmus ist z.B. in dem Buch „Computational Geometry in C“ von Joseph O’Rourke beschrieben. Die Grundidee ist folgende: Voraussetzung ist, dass beide Polygonen gleich ausgerichtet sind (z.B. gegen den Uhrzeigersinn). Man wählt von jedem Polygon jeweils eine aktive (gerichtete) Kante aus und setzt entweder die eine oder die andere nach bestimmten Regeln eine Kante weiter. Seien die Polygone A und B, die jeweils aktiven Kanten a (bei A) und b (bei B). Wenn jetzt z.B. a nach b zielt, dann setze ich a eine Kante weiter. Auf diese Weise will man die Kanten a und b immer treffen lassen, wenn es einen Schnittpunkt gibt. Ich hoffe jemand kennt den Algorithmus.
Jedenfalls gibt es 4 Regeln nach O’Rourke:
a) Keine Kante zeigt auf die jeweils andere => setze eine beliebige weiter
b) Beide Kanten zeigen jeweils aufeinander => Setze die Kante entsprechend dem Umlaufsinn (z.b. Gegenuhrzeigersinn) eins weiter
c bzw. d) Kante a zeigt auf b => setze a eine Kante weiter (analoges für Kante b, was Fall d ist)
Meine Fragen:
- Funktioniert dieses Verfahren auch für einfache Polygone, also Polygone, die nicht konvex sind?
- Ich habe einmal versucht selbst ein Beispiel durchzuführen, aber es hat bei mir nicht funktioniert. Könnte mir jemand anhand des folgendne Beispiels den Durchlauf der Kanten erläutern? Ich habe hier mal ein Beispiel hochgeladen:
http://www.bilder-space.de/show_img.php?img=840353-1…
Eventuell habe ich auch die Regeln falsch verstanden.
Danke schon mal im Voraus!