Linie mit Polygon schneiden
-
Hallo,
ich habe ein kleines Problem. Ich möchte eine Pfad von S1 nach Z1 (s.u.) berechnen. Für die Pfadberechnung gibt es ja diverse Algorihtmen:- Trapezoide Zellzerlegung
- Konvexe polygonale Zellzerlegung
- Sichtbarkeitsgraph
- usw.
Bei all diesen Algorithmen muss ich eine bzw. mehrer Linie(n) mit dem Polygon (Hindernis) schneiden. Jetzt suche ich nach Informationen/Algorithmen zum Schneiden einer Linie mit einem Polygon. Kann mir da einer Weiterhelfen?
Danke schonmal
/-----------------\ | S1 | | _______ | | / \ | | / / | | | / | | \ | | | \ --- | | \ \ | | | \ | | / / | | / / | | / / | | \--------/ | | Z1 | \----------------/
-
machs so, dass du das Polygon als Geradenzug siehst und dann schneidest du deine linie mit jeder linie des polygons.
-
Daran habe ich auch gedacht, wenn ich aber die Trapezoide Zellzerlegung vornehmen würde, also von allen Kanten des Polynons eine Line nach rechts, links, oben und/oder unten bis zur Kante bzw. einem anderen Hindernis ziehe und bei der Hälfte der Linie einen Punkt machen. Dann hätte ich 26 Punkte. Jetzt würde ich alle Punkte miteinander Punkten verbinden, wenn sie das Polynon nicht kreuzen. Das Verbinden der Punkte ergibt 676 Linien, das Prüfen derer mit dem Polygon wären ca. 9000 Schneideoperationen.
-
Ich kenne das Problem nur von Geoinformatiossystemen. Es gibt eine Bibliothek für solche Problemstellungen. Vielleicht zugroß für eine einfache Fragestellungen aber hier der Link:http://geos.refractions.net/ Gruß Huck