Punkt in Polygon

[Anonym]

Hallo, liebe Gemeinde

Ich habe die Eckpunkte eines geschlossenen Polygons P und die Koordinaten eines Punktes X, alles in 2 Dimensionen. Wie kann ich testen, ob X in P liegt oder nicht?

Der Standard-Algorithmus geht so: Ziehe von X aus eine Linie nach rechts. Zähle, wie oft diese horizontale Linie eine Kante des Polygons schneidet. Wenn diese Anzahl ungerade ist, liegt X innerhalb von P.

Der Algorithmus liefert jedoch nicht immer das richtige Ergebnis. Sobald die horizontale Linie durch einen Eckpunkt des Polygons geht, können Fehler auftreten. Stellt euch als Polygon eine Raute (ein Salino) vor und als Punkt X nehmen wir den Mittelpunkt des Salinos. Die horizontale Linie von X nach rechts trifft genau den Eckpunkt der Raute, geht also durch 2 Kanten.

Kennt einer von euch einen Workaround für dieses Problem oder einen immer richtigen Algorithmus?

Vielen Dank schon mal im Voraus

cu Stefan.

[Lutz_Lehmann]

Da Du eine Reihenfolge der Eckpunkte des Polygons hast, lass doch einfach den zweiten Punkt aus der Kante raus, dann z"ahlt dieser nur einmal bei der folgenden Kante.

MfG Lutz

[Anonym]

Hi Lutz

Das habe ich mir schon überlegt. Das würde dann bedeuten, dass Eckpunkte nur einfach zählen würden.

Dies kann aber zu Problemen führen, wenn die Polyogne nicht konvex sind.

Nimm z.B. wieder eine Raute. Wenn du die untere Ecke leicht umknickst, bekommst du ein 6-eckiges Polygon. Jetzt nimm einen Punkt etwas links vom umgeknickten Eckpunkt. Dieser Punkt schneidet dann genau den Eckpunkt und die äußere rechte Kante der Raute. Wenn Eckpunkte jetzt nur einfach zählen, bekomme ich 2 Hits, und der Punkt würde fälschlicherweise als außerhalb des Polygons gewertet. Ich versuch das mal zu malen:

 /\
 / \
 / \
 / \
/ \
\ \_\_\_\_\_\_/\_\_\_ Diese Linie hätte 2 Hits!
 \* /\ /
 \/ \/

Hast du vielleicht noch eine Idee?

cu Stefan.

[Ted_Striker]

Hi Stefan,

da die Polygonzüge nicht notwendig konvex sind, ist das Problem tatsächlich nicht so ganz trivial. Ich habe eben mal etwas darüber nachgedacht und bin auf zwei Ideen gekommen:

1. Die Polygonzüge sind nicht nur einfach zusammenhängend, sondern bogenzusammenhängend. Wenn Du also einen beliebigen inneren Punkt des Polygonzugs kennst, so existiert ein Polygonzug zu dem zu prüfenden Punkt, welcher ganz in dem geschlossenen Polygonzug liegt, ergo keine Kante schneidet, was leicht zu überprüfen ist. Das eigentliche Problem liegt im Auffinden dieses Polygonzugs, wobei jedoch die Tatsache hilft, dass es auch immer einen achsenparallelen Polygonzug zwischen den Punkten gibt. Dieses könnte man über Backtracking ermitteln, jedoch sind diese Algorithmen von stark wachsender Zeitkomplexität. Auch könnte es Probleme mit der diskreten Darstellung im Rechner geben, da eine kleine Entfernung zum Rand schnell man zu einem Schnitt werden kann.

2. Aus der Endlichkeit der Punktmenge im Rechner ist mir dann eine neue Idee gekommen, deren Realisierbarkeit von der Größe der Polygone abhängt. Zunächst speicherst Du alle Randpunkte in einem Array ab, wobei es nicht verkehrt ist, wenn Du hashst oder wenigstens logarithmisches suchen realisiert. Und nun zahlt sich aus, dass ich mal auf einem DOS-Rechner Minesweeper nachprogrammiert habe. Es ist sehr einfach, eine rekursive Funktion zu schreiben, welche, ausgehend von einem Punkt (z.B Knoten) alle inneren Punkte des Polygonzug ermittelt und abspeichert. Dieses Array durchsuchst Du dann nach Deinem Punkt. Das kann bei großen Flächen aber auch schnell zeitkritisch werden.

Wenn es auch sicher nicht das Optimum ist, vielleicht konnte ich Dich wenigstens auf ein Paar Ideen bringen.

Gruß
Ted

PS.: Die Aufgabe kommt mir so vor, als würde sie an jeder Ecke gebraucht. Hast Du in Büchern über Computergrafik nichts passendes gefunden?

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

[Anonym]

ein kleiner beitrag von mir(nur schnell ausgedacht, ich weiss nicht ob der gut ist)

ansatz:

du bildest eine menge von y koordinaten, die auf der x koordinate deines punktes liegen und pruefst ob punkt.y ein element dieser menge ist.

dazu must du eigentlich nur fuer alle vektor(die eckpunkte kennst du hast du gesagt?) pruefen, ob sie deine horizontale schneiden und welche von diesen sich gegenueber liegen.

[Claudio_Eckert]

Hi,

eine Idee von einem Nicht-Mathematiker

Wie wäre es damit:
Einfach auch mitzählen, ob ein SchnittPUNKT doppelt gezählt wurde:

Wenn es eine gerade Anzahl von Treffern gab und und ein Punkt wurde doppelt gezählt, dann gilt er als ungerade (drin)

Wenn es eine gerade Anzahl von Treffern gab, und kein Punkt kam doppelt, dann bleibt es dabei (draussen).

Wenn es einen ungerade Anzahl von Treffern gab, bleibt es dabei (drin).

Oder hab ich was übersehen?
Claudio

[Anonym]

Hi Claudio

Ich versuch mal wieder ein Gegenbeispiel zu malen:

 /\
 / \
\*-/ \--- Ungerade Trefferzahl =\> drin ?!
 / / (ich meine natürlich die Ecke)
/ /
|----/

Man müsste deine Idee des Mitzählens auch noch auf ungerade Trefferzahl erweitern.

Denke für den Input, ich muss mal drüber nachdenken …

cu Stefan.

[Anonym]

Hi Ted

Ich habe eben mal etwas
darüber nachgedacht und bin auf zwei
Ideen gekommen:

Ja, dann lass mich mal nicht doof sterben

1. Die Polygonzüge sind nicht nur einfach
   zusammenhängend, sondern
   bogenzusammenhängend. Wenn Du also einen
   beliebigen inneren Punkt des Polygonzugs
   kennst, so existiert ein Polygonzug zu
   dem zu prüfenden Punkt, welcher ganz in
   dem geschlossenen Polygonzug liegt, ergo
   keine Kante schneidet, was leicht zu
   überprüfen ist.

Einleuchtend trivial klar!

Das eigentliche Problem
liegt im Auffinden dieses Polygonzugs,
wobei jedoch die Tatsache hilft, dass es
auch immer einen achsenparallelen
Polygonzug zwischen den Punkten gibt.

Im Moment fällt mir nicht ein, warum dies nicht so sein sollte. Also glaube ich dir das erstmal.

Dieses könnte man über Backtracking
ermitteln, jedoch sind diese Algorithmen
von stark wachsender Zeitkomplexität.

Zeit habe ich in Massen. Es geht eigentlich darum, in einem Polygon-Haufen dasjenige Polygon heruas zu finden, in das mit der Maus geklickt wurde. Allerdings ist Backtracking natürlich sehr langsam und bei fast 10000 zu überprüfenden Polygonen, könnte selbst der Mirco$oft-erprobte Anwender etwas unruhig werden …

2. Aus der Endlichkeit der Punktmenge im
   Rechner ist mir dann eine neue Idee
   gekommen, deren Realisierbarkeit von der
   Größe der Polygone abhängt. Zunächst
   speicherst Du alle Randpunkte in einem
   Array ab, wobei es nicht verkehrt ist,
   wenn Du hashst oder wenigstens
   logarithmisches suchen realisiert.

Ja gut, das wäre kein Problem …

Und nun zahlt sich aus, dass ich mal auf
einem DOS-Rechner Minesweeper
nachprogrammiert habe. Es ist sehr
einfach, eine rekursive Funktion zu
schreiben, welche, ausgehend von einem
Punkt (z.B Knoten) alle inneren Punkte
des Polygonzug ermittelt und abspeichert.
Dieses Array durchsuchst Du dann nach
Deinem Punkt. Das kann bei großen Flächen
aber auch schnell zeitkritisch werden.

Sehe ich auch so. Dürfte in der Praxis nur schwer umsetzbar sein. Vielleicht in 20 Jahren, wenn wir den Terra-Hertz-Prozessor haben …

Wenn es auch sicher nicht das Optimum
ist, vielleicht konnte ich Dich
wenigstens auf ein Paar Ideen bringen.

Ja, hat es. Ich werde am Wochenende mal darüber nachdenken …

PS.: Die Aufgabe kommt mir so vor, als
würde sie an jeder Ecke gebraucht. Hast
Du in Büchern über Computergrafik nichts
passendes gefunden?

An jeder Ecke wird ja auch der von mir beschriebene Standard-Algorithmus verwendet. Die kleinen Fehler werden dabei anscheinend in Kauf genommen …

cu Stefan.

[Anonym]

Hi Dog

du bildest eine menge von y koordinaten,
die auf der x koordinate deines punktes
liegen und pruefst ob punkt.y ein element
dieser menge ist.

Das ist so ähnlich wie der Standard-Algorithmus, halt nur in y-Richtung anstatt in x-Richtung.

dazu must du eigentlich nur fuer
alle vektor(die eckpunkte kennst du hast
du gesagt?) pruefen, ob sie deine
horizontale schneiden und welche von
diesen sich gegenueber liegen.

Wie gesagt, es ist dem Standard-Algorithmus sehr ähnlich. Aber du hast mich gerade auf eine Super-Idee gebracht. Ich muss mal drüber nachdenken …

Vielen Dank …

cu Stefan.

[Anonym]

Ich habe die Eckpunkte eines
geschlossenen Polygons P und die
Koordinaten eines Punktes X, alles in 2
Dimensionen. Wie kann ich testen, ob X in
P liegt oder nicht?

Zieh von jedem Eckpunkt des Polygons einen Vektor zum Testpunkt P und berechne den Winkel zwischen dem Vektor und einer anliegenden Kante (z. B. immer die im Uhrzeigersinn liegende Kante, Richtung nicht zwischendrin wechseln).

Dann addierst Du die Winkel. Wenn Du eine Summe von 360° bekommst, ist der Punkt drinnen.

Du mußt natürlich mit Fließkommazahlen vorsichtig sein, es kann sein, daß durch Ungenauigkeiten nicht 360° rauskommt, sondern 359,999999° oder so.

Mathias Ricken

[Anonym]

Hi Mathias

Dieses Verfahren scheitert meines Erachtens nach bereits bei dem simpelsten nicht-trivialen Polygon, bei einem Dreieck. Oder habe ich dich falsch verstanden?

cu Stefan.

[Anonym]

bei einem dreieck funktioniert es m.e., weil du ja die drei winkel addierst, die jeweils zwischen den vektoren:

ax und bx;
bx cx;
cx ax addierst,

bei komplexeren figuren (z.b. eine spiralfoermige)duerfte es an der analyse der figur scheitern

[Anonym]

ich glaube ich weiss woran du denkst…

meinst du vielleicht die analyse, ob der punkt zwischen zwei (mehr od. weniger) parallelen kanten liegt?

dann denk an dein bsp der raute mit der umgeknickten ecke, wenn der punkt in der linken unteren ecke liegt, liegt er zwischen zwei kanten, aber auch wenn er zwischen den bd. unt. ecken liegt… und dann wird es interessant

[Anonym]

wahrscheinlich musst du mehrere ausschlussverfahren anwenden,

der erste schritt waere wahrscheinlich alle polygone auszuschliessen, fuer die gilt:

(alle polygon.x punkt.x) ||
(alle polygon.y punkt.y)

vielleicht finden sich ja noch mehr solcher regeln

[Anonym]

hey!!! coole idee!!!

was hab ich in der schule gelernt?
es gibt 'ne mathematische und 'ne graphische loesung.

die graphische ist geillll:

du zeichnest die polygone mit gruen in eine schwarze bitmap und testet ob der punkt gruen ist!!!

[Anonym]

bei komplexeren figuren (z.b. eine
spiralfoermige)duerfte es an der analyse
der figur scheitern

Entschuldigt bitte, ich hab mich falsch erinnert. Man muß die Winkel am Testpunkt nehmen.

Dies geht bei allen geschlossenen Polygonzügen, siehe Game Developer Magazine, Ausgabe Januar 1999, Seite 21 ff.

Zitat: „[…] Unfortunately, the aforementioned dot product test won’t work on these concave polygons. […] One method for determining if the test point is inside the concave polygon comes from the idea that a circle is 360 degrees. Calculate the angle between each vertex and the test point (at the test point itself) and then add up all the angles. If the total is equal to 360, then you are inside. […]“

Evtl. gibts bei www.gdmag.com auch Source Code dazu.

–Mathias

[Chris_b6f451]

du zeichnest die polygone mit gruen in
eine schwarze bitmap und testet ob der
punkt gruen ist!!!

hi!
wirklich originell, muß man zugeben.
aber woher weiss man, in welchem polygon der kommissar X liegt?
zumindest sollte man zu jedem polygon die „bounding box“, das umhüllende viereck, speichern und zuerst alle 10000 polygone auf einen potentiellen treffer überprüfen.
dann zählt man die anzahl der ***VERSCHIEDENEN*** Schnittpunkte mit dem Kommissar und einem Punkt innerhalb eines polygons. Ein Vorredner hat das glaub ich schon erwähnt.
was mich wundert ist, das das beschriebene Problem gar nicht auftaucht, wenn Du die Berechnung des Schnittes änderst. Jede Kante zwischen zwei Kontrollpunkten läßt sich als Vektor A + t (B-A) auffassen. Ein Schnittpunkt mit einer Geraden bedeutet 0

[Anonym]

aber woher weiss man, in welchem polygon
der kommissar X liegt?

naja, dazu koennte man den farbwert hochzaehlen. oder halt den polygonindex als farbwert nutzen.

[Anonym]

Hi MAthias

Entschuldigt bitte, ich hab mich falsch
erinnert. Man muß die Winkel am Testpunkt
nehmen.

Kein Problem. Deswegen DISKUTIEREN wir hier ja ))

Evtl. gibts bei www.gdmag.com auch Source
Code dazu.

Danke für den Tipp. Das verfahren müsste eigentlich funktionieren. Jetzt muss ich nur zusehen, dass es von der Laufzeit her nicht zu teuer wird.

Danke erstmal …

cu Stefan.

[Anonym]

Hi Dog

die graphische ist geillll:

du zeichnest die polygone mit gruen in
eine schwarze bitmap und testet ob der
punkt gruen ist!!!

Hmmm. Wirklich nicht schlecht. Ich denke, daraus kann man was machen ))

Ich nehme einfach einen Algorithmus zum Füllen von Polygonen und prüfe, ob einer der Füllpunkte gleich meinem Punkt X ist. Das Füllen von Polygonen klappt ja anscheinend ganz gut …

Danke dir ))

cu Stefan.