Punkt im Konvexen Polygon
lima-city → Forum → Sonstiges → Schule, Uni und Ausbildung
ablaufen
aktuell betrachten
algorithmus
anzahl
beliebige richtung
berechnen
bestimmen
http
information
kante
machen
menge
polygon
problem
punkt
schnittpunkt
spezialfall
strahl
tip
url
-
Hallo Leute.
Gibt es eine schnelle Möglichkeit zu bestimmen, ob ein Punkt(x/y) Innerhalb einer Menge von Punkten (konvexes Polygon) liegt?
Wie könnte ich vorgehen, damit ich bei einer grossen Menge von Punkten nicht jedes Mal das Polygon "ablaufen" muss (zum Beispiel um zu bestimmen, ob der Punkt rechts oder Links einer Geraden liegt)?
gruss
x-bLacK
-
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
Der Standartalgorithmus dafür, ist die Anzahl der Schnittpunkte eines Strahls vom Punkt aus in eine beliebige Richtung zu zählen. Wenn sie gerade ist, liegt der Punkt außerhalb des Polygons, wenn sie ungerade ist, dann innerhalb. Bei einem konkaven Polygon kann die Anzahl der Schnittpunkte nur 0 und 2 sein für Außerhalb und 1 für Innerhalb.
Dennoch wirst du auch bei diesem Verfahren alle Seiten durchlaufen müssen (außer du hast weitere Informationen zur Verfügung)
Zum Berechnen der Schnittpunktanzahl: Sende den Strahl einfach immer nach rechts. Dann kannst du prüfen, ob der y Wert des zu prüfenden Punkts zwischen den y-Werten der aktuell betrachten Seite des Polygons liegt. Wenn ja, dann ist es ein Schnittpunkt.
Beitrag zuletzt geändert: 14.11.2010 20:05:38 von nikic -
Vielen Dank für deinen Tipp.
Das hört sich schon gut umsetzbar an.
Aber was mache ich mit dem Spezialfall, falls P ausserhalb des Polygons liegt, aber eine Gerade nach Rechts eine Ecke schneidet.
Die Anzahl wäre dann 1 -> der Algorithmus meint, der Punkt wäre innerhalb des Polygons.
gruss
x-bLacK
-
Hier sind die Algorithmen sehr detailliert erklärt. Oder auch hier.
Die Spezialfälle sind immer ein Problem. Wobei, die Funktion, die entscheidet, ob der Strahl eine Kante des Polynoms schneidet, kann so programmiert werden, dass sie für den Spezialfall Null zurückgibt.
Es kann aber dann leider immer noch zu Problemen kommen, wegen der Rundungsfehler.
Eine robustere Methode ist es über die Anzahl der Umrundungen, die das Polynom um den Punkt macht, zu berechnen.
-
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
