Algorithmus für: "Liegt ein Punkt innerhalb eines Polygons?"
-
Hallo,
Ich habe eine Liste von Punkten, die einen Polygonzug beschreiben, wobei die letzte Kante den letzten Punkt mit dem ersten wieder verbindet.
Weiterhin weiß ich, dass sich die Linien niemals schneiden, das Polygon also nicht irgndwie "komisch" aussieht.
Gibt es dafür einen Alogrithmus, in den ich einen Punkt reinwerfen kann und der dann true/false zurückgibt, ob der Punkt innerhalb dieses Polygons liegt?
THX i.V.
-
Gibt es dafür einen Alogrithmus, in den ich einen Punkt reinwerfen kann und der dann true/false zurückgibt, ob der Punkt innerhalb dieses Polygons liegt?
Ja. Ist es ein spezielles Polygon, z.B. konvex oder sternfoermig, oder eher allgemein? Fuer allgemeine kann man z.B. ueber die "Kreuzungszahl" gehen: http://www-lehre.informatik.uni-osnabrueck.de/~cg/2002/skript/node43.html . Hat das Polygon besondere Eigenschaften, dann gibt es bessere Algorithmen.
-
Schieß einen Strahl vom Punkt aus in irgendeine Richtung zähle die Anzahl der Schnitte mit den Seiten. Ist diese ungerade dann liegt der Punkt im Polygon.
-
Ben04 schrieb:
Schieß einen Strahl vom Punkt aus in irgendeine Richtung zähle die Anzahl der Schnitte mit den Seiten. Ist diese ungerade dann liegt der Punkt im Polygon.
Das ist ein üblicher und einfacher Algorithmus. Beim Implementieren muss man nur auf wenige Spezialfälle achten, wie zum Beispiel, dass der Strahl genau durch eine Ecke geht oder genau auf einer Kante liegt (also Strahl und Kante übereinander).
Wenn n die Zahl der Kanten des Polygons ist, dann hat dieser Algorithmus eine Laufzeit von O(n). Bei großen Polynomen kann es sich daher schon lohnen, etwas besseres zu suchen. "Trapezoidal Map" ist (soweit ich weiß) eine übliche Alternative, die allerdings nicht mehr so einfach zu implementieren ist: Man hat einen relativ teuren Preprocessing-Schritt, der das Polynom verarbeitet. Danach kann man die Anfragen "liegt ein Punkt im Polygon" allerdings viel schneller beantworten.
Es gibt auch einfachere Verfahren als trapezoidal map, die teilweise andere Laufzeit-Garantien und andere Speicher-Anforderungen haben, dafür aber einfacher zu implementieren sind. Der Artikel Point location auf Wikipedia zeigt ein paar.
-
Schieß einen Strahl vom Punkt aus ... Das ist ein üblicher und einfacher Algorithmus.
Warum wiederholt ihr mich. In dem Link steht alles wichtige drin.
Bei großen Polynomen kann es sich daher schon lohnen, etwas besseres zu suchen. "Trapezoidal Map"
Nein, Trapezoidal Maps sind fuer Karten, nicht fuer einzelne Polygone.
-
knivil schrieb:
Schieß einen Strahl vom Punkt aus ... Das ist ein üblicher und einfacher Algorithmus.
Warum wiederholt ihr mich. In dem Link steht alles wichtige drin.
Bei großen Polynomen kann es sich daher schon lohnen, etwas besseres zu suchen. "Trapezoidal Map"
Nein, Trapezoidal Maps sind fuer Karten, nicht fuer einzelne Polygone.
Einzelne Polygone sind ja auch Karten.
