Herausfinden ob ein beliebiger Punkt im Polygon ist

[Prophet05]

Hi,

mich würde mal interessieren wie man herausfindet ob sich ein punkt in oder ausserhalb eines polygons befindet. Ich habe auch schon danach gesucht und den Satz von Pick (http://de.wikipedia.org/wiki/Satz_von_Pick) gefunden aber damit kann man nur die anzahl der Punkte errechnen. Und auch im artikel üder Polygone (http://de.wikipedia.org/wiki/Polygon) wird immer nur der Umfang oder der Flächeninhalt berechnet aber nie wird bestimmt ob ein punkt im Polygon liegt oder nicht.
Ich habe mir bereits überlegt das ich einfach alle linien überprüfen und schaue auf welcher seite der Linie der Punkt liegt aber dabei habe ich das problem das ich nicht weiß wie ich innen und außen beim polygon definieren kann...

Gruß, Prophet

[butterkeks]

Innen uns Außen kannst du z.B. über das Skalarprodukt definieren... für eine Strecke von P1 bis P2 und einen zu testenden Punkt P3 nimmst dafür den Normalvektor von (P2-P1) und den Vektor (P3-P1).

Ist der Wert für alle Strecken des Polygons größer 0 (bzw. für alle kleiner 0, je nachdem), dann liegt der Punkt innerhalb/außerhalb des Polygons.

[Prophet05]

Das verstehe ich nicht ganz eine strecke hat kein "innen". Ich würde mit den skalarprodukt doch nur die fläche errechnen welche alle drei punkte aufspannen.
Wenn ich nun P3 prüfen will aber P1 und P2 zusammen nur eine strecke sind dann kann P3 nie innerhalb von P12 liegen...
Oder habe ich die missverstanden? Ich brauche doch mindesten drei punkte um eine ebene zu definieren und einen vierten um dessen position zu prüfen. Wir soll das dann mit nur drei punkten möglichsein?

[butterkeks]

ja, vielleicht hätte ich es besser "links" und "rechts" nennen sollen... mit dem Skalarprodukt kannst du herausfinden, auf welcher Seite der Strecke sich ein Punkt befindet (bzw. ob er sich genau auf ihr (bzw. der Geraden, die durch die Strecke bestimmt wird) befindet).

Was nun "links" und "rechts" genau ist, hängt davon ab, ob du den Normalvektor von (P1-P2) oder (P2-P1) nimmst und ob du den "positiven" oder "negativen" Normalvektor wählst (es gibt ja immer zwei). Dies bestimmt das Vorzeichen des Skalarprodukts (und dieses wiederum wie gesagt, ob sich der Punkt "links" oder "rechts" von der Seite befindet).

Wenn du dein Polygon als "Streckenzug" ansiehst, erübrigt sich schon mal das mit der Subtraktionsreihenfolge, d.h. erst die Strecke von P0 bis P1, dann die strecke von P2 bis P3, usw. betrachtest, weil du den Vektor immer gleich bildest.

Beim Normalvektor hast du einfach die Wahl (es ist nur wichtig, dass du ihn immer auf dieselbe Weise bildest).

Ich spreche bisher übrigens nur von 2D... in 3D kannst du entsprechend den Normalvaktor deiner Polygone ("Ebenen") bilden, genauso das Skalarprodukt ausrechnen und ebenso vergleichen.

[Xpyder]

Ich habe dazu zwei Ansätze anzubieten.
Zu beachten: Beide Ansätze funktionieren erst einmal nur für KONVEXE Polygone (welche, in denen kein Punkt "nach innen zeigt"). Ich erkläre später noch, wie für konkave Polygone zu verfahren ist.
(Ach so. Man sollte vielleicht eindeutig definieren, ob ein Punkt, der sich genau auf einer Begrenzungslinie befindet, als außerhalb oder innerhalb definiert wird.)

1)
Einmal den schon genannten, nämlich zu schauen, auf welcher Seite der Linien der Punkt liegt. Dazu muß man lediglich in der Reihenfolge der Punkte immer eine konstante "Richtung" einhalten, d.h. entweder man benennt die Punkte immer im Uhrzeigersinn oder immer gegen den Uhrzeigersinn. Das dient dazu, um den Strecken, die das Polygon begrenzen, eine RICHTUNG geben zu können, d.h. es sind dann eigentlich Vektoren. Haben sie eine Richtung, kann man auch definieren, ob sich ein Punkt links oder rechts davon befindet. Habe mal in meinem Text über binäre Bäume (http://igames.inside1.net/html/dosd2.htm) beschrieben, wie man so etwas macht.
Im Klartext: Alle Punkte eines Polygons rechtsherum "benennnen" (also numerieren). Nehmen wir ein, es wäre ein Pentagon (Fünfeck), dann hätte man z.B. die Punkte 0,1,2,3,4 und würde die Strecken 0->1, 1->2, 2->3, 3->4 und 4->0 testen müssen. Man verlängert die Strecke zu einer Geraden (mit normaler linearer Geradengleichung der Form y=mx+n, ja, den Fall senkrechter Geraden habe ich auch in besagtem Text behandelt). Diese Gerade schneidet den Raum in zwei Teile, der Punkt kann auf der Geraden oder in einer der beiden Hälften liegen.
Bei einem rechtsherum benannten Polygon muß ein Punkt RECHTS von ALLEN Geraden liegen -> dann liegt er innerhalb des Polygons, sonst außerhalb. (Und daran denken, daß die "Gerade" nun eine "Richtung" hat, d.h. sie wird ausgehend von ihrem Anfangspunkt in Richtung ihres Endpunkts betrachtet. Geht sie von oben nach unten, ist "links" im Koordinatensystem natürlich optisch rechts.)

2)
Der andere Ansatz erfordert zwar nicht zwingend in eine bestimmte Richtung durchnumerierte Punkte, aber es macht es leichter und kann daher nicht schaden. Es ist etwas "komplizierter", aber das kommt wohl dann ganz auf die Umsetzung an. Man geht hier davon aus, daß jeder Eckpunkt ja von zwei Strecken eingeschlossen wird und somit einen Winkel bildet, d.h. sozusagen ein (unendlich langes) Tortenstück einer Ebene aufspannt. Alle diese "Winkelstücken" übereinander ergeben dann das Polygon, wenn man nur die Punkte benutzt, die in allen Stücken vorkommen, d.h. diese Ebenenteile beschneiden sich gegenseitig. Das nur zur Erklärung.
Wenn man mehrere Punkte testen will, sollte man erst einmal die "Vorarbeit" leisten, damit man das nicht jedes Mal machen muß:
Für jeden Punkt berechnet man den Winkel, in dem der VORIGE und der NÄCHSTE Punkt (im Polygon) zu diesem Punkt stehen. (Daher ist es vielleicht doch eine gute Idee, die Punkte durchzunumerieren.) (Winkel ausrechnen mit Arcustangens - wenn man es auf einem Computer machen will, gibt es hier die Möglichkeit, mit Tabellen und einer kleinen lustigen Subroutine zu arbeiten, hab das auch schonmal vorgestellt, unter anderem in diesem Programm, das diese "Farbentheorie" erklärte.) Das heißt, man hat für jeden Punkt einen Start- und einen End-Winkel.
Wie der Test geht, ist nun leicht zu ersehen: Es ist einfach für jeden Eckpunkt des Polygons zu testen, ob sich der zu testende Punkt innerhalb des Intervalls [Startwinkel...Endwinkel] befindet - dabei natürlich beachten, daß Winkel bei 360° auf 0 "wraparounden"... (aber wem erzähl ich das?)
Liegt der zu testende Punkt für alle Eckpunkte innerhalb der aufgespannten Winkel, dann liegt er innerhalb, ansonsten außerhalb des Polygons.
Achso: Wenn man ein Fünfeck hat, müßte man dann also den Winkel zum vorigen Punkt und zum nächsten Punkt für jeden Punkt berechnen, also zehn Winkel? - Falsch. Denn der Winkel zum vorigen Punkt kann ja aus dem Winkel des vorigen Punktes zum nächsten (das ist der aktuelle!) ermittelt werden - es ändert sich ja nur die Richtung, da beide Punkte vertauscht sind.

Die Erklärung für konkave Polygone:
Da relativ viele Dinge, die mit konvexen Polygonen funktionieren, dies bei konkaven Polygonen nicht mehr tun, empfiehlt sich in solchen Fällen einfach die folgende Vorgehensweise: Man zerlegt ein konkaves Polygon so lange (durch das Einbringen von Diagonalen), bis nur noch konvexe Polygone übrig sind und testet das Ganze dann für die konvexen Polygone. Hierbei ist lediglich zu beachten: Soll der Fall, daß sich ein Punkt genau AUF der Außenkante des Polygons befindet, gesondert betrachtet werden, so sind natürlich die Diagonalen (die ja dann zu Außenkanten der Teilpolygone werden!) gesondert zu "markieren" - Speziell, wenn man Methode 1 benutzt.). Sollte dann ein Punkt sich AUF einer solchen Diagonale befinden, so
ist das dann kein "Sonderfall" mehr, sondern er liegt dann innerhalb des Polygons, da die Diagonalen ja nur eingebrachte Hilfslinien sind.)

Die Diagonale für ein konkaves Viereck ist (wenn man den konkaven Punkt kennt) relativ leicht zu finden: Man verbindet den konkaven Punkt mit den übernächsten Punkt. (Ein Viereck hat nur zwei Diagonalen - und die andere Diagonale läge bei einem konkaven Viereck außerhalb des Vierecks.) Dadurch zerfällt das Viereck in zwei Dreiecke (die bekanntlich immer konvex sind).

Wie stellt man rechnerisch fest, ob ein Polygon konkav ist und an welchem Punkt?
Dazu eignen sich die in Methode 2 vorgestellten "Winkel zum vorherigen Punkt": Solange der Abstand zum vorherigen Winkel immer kleiner (oder gleich) 180° bleibt (dran denken: mathematisch positive Winkel = gegen den Uhrzeigersinn...), hat man ein Polygon mit durchgehend linksherum gehenden Punkten. Umgekehrt kann man auch ein "rechtsherum" beschriftetes Polygon haben, da müssen dann die Abstände zum jeweils vorigen Winkel immer >=180° bleiben. Sobald ein Winkel davon abweicht, weiß man, daß das Polygon konkav ist und welcher der konkave Punkt ist.
Einfacher ist wohl folgendes:
Man definiert einfach: Für jeden Punkt muß der Abstand des Winkels zum vorherigen Winkel immer <=180° sein, jeder andere Punkt ist konkav. Sollte man zum Schluß mehr konkave als konvexe Punkte haben (was natürlich Blödsinn wäre!), wird die Definition einfach umgekehrt und das Polygon als "umgedreht" betrachtet - also als ein rechtsherum beschriftetes Polygon, und die vorher konkaven Punkte sind jetzt konvex und die vorher konvexen jetzt konkav.

Beim Einbringen der Diagonalen (für das Zerschneiden in konvexe Polygone) ist zu beachten:
a) Der erste Punkt ist immer ein konkaver Punkt
b) Der zweite Punkt ist ein konkaver oder konvexer Punkt, vorzugsweise aber ein konkaver, wenn vorhanden.
c) Wichtig ist dabei aber, daß die Diagonale keine der Außenlinien des Polygons schneiden darf.

Diese vielen Dinge erklären auch, wieso es - wenn man beispielsweise so etwas wie 3D-Vektorgrafik oder 3D-Spiele bauen wollen würde - besser ist, vieles vorher (im Editor) zu definieren (z.B. Reihenfolge der Punktbeschriftung, oder daß Polygone grundsätzlich konvex sein müssen). Im 3D wird es nämlich meist auch wichtig, welche Seite des Polygons man gerade betrachtet...

Ich hoffe, diese kleinen Anmerkungen konnten erst einmal weiterhelfen.

[Prophet05]

Ok, das habe ich nun soweit verstanden. Aber wie finde ich den nun heraus ob link = innen oder rechts = innen?
987
Hier siehst du mein problem. Bei strecke P16 ist oben = außen und unten = innen. Aber bei P45 ist oben = innen und unten = außen. Wie löse ich diese problem? Das ganze wird ja sogar noch komplizierter wenn ich ein strenförmiges polygon habe. Dort wechselt diese beziehung ja sogar bei jeder strecke! (Ups habe eine Punkt vergessen)

[Prophet05]

Ja, danke das hat mir einiges klar gemacht (hätte ich da nicht auch selbst drauf kommen können? :D ). Die grundsätzlichen überlegungen sind einleuchtend.

Vielen dank!

[Mr.Homm]

Wenn du einen Punkt, welcher mit Sicherheit außerhalb des Polygons mit dem gefragten Punkt verbindest und zählst, wie häufig diese Gerade Polygonkanten überschreitet, liegt der Punkt bei einer ungeraden Anzahl innerhalb, bei einer geraden Anzahl außerhalb des Polygons. Siehe: http://www.teco.edu/~biebl/10_geometrie.pdf (http://www.teco.edu/%7Ebiebl/10_geometrie.pdf)

[Prophet05]

Danke, auch ein interessanter ansatz!

[Scavi]

@Mr. Homm: http://www.coding-board.de/board/showpost.php?p=72546&postcount=2 ;)

und für den Rest auch: http://www.coding-board.de/board/showthread.php?t=12594

[Firefall]

Eigentlich könnte man doch einfach das Polygon als Bitmap rendern, dann in die Y-Zeile des zu testenden Punktes springen, und alle Pixel von oben nach unten durchgehen, bis man auf den Punkt trifft. Immer, wenn ein Punkt des Polygons angetroffen wird, wird eine Boolean Variable umgekehrt (Not-Operation). Am Anfang ist diese false. Ist sie beim erreichen des Punktes true, so liegt der Punkt innerhalb. Ansonsten liegt er ausserhalb. Spezialfälle KÖNNEN die Eckpunkte sein.

[DarkTom]

Letztlich ist das ja der Ansatz, den MrHomm in Post #8 (http://www.coding-board.de/board/showpost.php?p=141038&postcount=8) angesprochen hat. Nur mit zwei bis drei Verschlechterungen:

1. Da muss man viel mehr Pixel betrachten als man Kanten auf Schnitt testen muss.

2. Wenn wir nicht ausschliesslich mit ganzen Koordinaten arbeiten verfälscht das aufgezwungene Raster das Ergebnis.

3. Die Spezialfälle brauchen dann auch noch eine Sonderbehandlung. Das müssen auch nicht nur Eckpunkte sondern können auch Schnittpunkte sein (bei einem nicht-einfachen Polygon).

Alles in allem also viel mehr Arbeit als wenn wir einfach nur Schnitte berechnen müssen.