Zergling-new

Hallo,

ich möchte per Funktion berechnen ob sich ein Punkt P innerhalb eines Polygons befindet.
Ein Polygon definiere ich als eine Liste von Punkten (ich nenne es mal "Polygon-Punktliste"), welche nacheinander mit Linien verbunden sind. Ich verzichte extra auf das Wort Kante.

Ich habe eine Lösung (nicht ohne Hilfe) gefunden von der ich glaube, dass sie richtig ist und würde gern wissen, ob der Gedanke alle Fälle abdeckt.
Vielleicht macht sich der ein oder andere der Lust hat das ganze auf Papier anschaulich, ist dann wesentlich einfacher zu verstehen.

Ich ziehe von dem Punkt P eine Linie zu einem Punkt, der garantiert außerhalb des Polygons liegt (schonmal ein Schwachpunkt *1). Zum Beispiel Q(MAX_INT, P.y). Es ensteht also eine waagerechte Linie von P nach Q.
Nun zähle und vergleiche ich alle Schnittpunkte zwischen der Linie PQ und den Polygon Linien. Bei den Schnittpunkten, die _nicht_ Teil der Polygon-Punktliste sind (also keine Polygon-Ecken sind) zähle ich den Zähler um 1 hoch, sonst nicht, denn dann habe ich eine Ecke erwischt und befinde mich noch in dem Raum (innen/außen) wo ich mich vor der "Kollision" befand.
Ist der Zähler am Ende gerade, befindet sich Punkt P außerhalb des Polygons, bei ungerader Anzahl befindet er sich innerhalb.

Wandere ich vom Punkt Q der garantiert außerhalb liegt zum Punkt P und kreuze nur eine Polygon-Linie, befinde ich mich danach innerhalb des Polygons, durchstoße ich die nächste bin ich wieder außerhalb usw.

Die Frage ist, habe ich alle Möglichkeiten abgedeckt, bzw. was wären Spezialfälle?
- Die PQ-Linie stimmt mit einer Polygon-Linie überein. Ist nicht relevant mit meinem Lösungsgedanken oder?
- Punkt P ist eine Ecke des Polygons (sehe gerade, dieser Fall wäre schonmal nicht abgedeckt und müsste wohl extra behandelt werden)
- Was ist mit Polygonen die sich selbst schneiden ("8"er-Form)

*1) Vielleicht könnte ich MAX_INT durch MAX(alle x-Werte der Polygon-Punkte) + 1 definieren.

Mister Ad

Flor1an

Naja wenn du jetzt theoretisch nen Polygon hast und dann innen noch nen weiteren Punkt der selbst zum Polygon gehört zieht er ja auch Linien bzw. Flächen im Polygon. Daher könnte doch deine "waagerechte" theoretisch durch 2 Flächen gehen und trozdem im Polygon sein!

Eigentlich ist doch ein Polygon im Sinne von Modellen etc. beim PC gebilde die weder konkav seien können noch das sich Flächen schneiden ("8"er-Form).

Inwiefern brauchst du denn so eine Überprüfung? Vlt lässt sich das ganze ja ganz anders lösen.

*edit*

Übrigens hast du ja gemeint dein Polygon besteht aus lauter Linien ... eigentlich besteht es doch aus lauter Flächen oder? Und du müsstest doch die Schnittpunkte zwischen den einzelnen Flächen und der Linie PQ berechnen?!?

Und die Berechnung zwischen Fläche und Strecke (um PQ mal mathematisch auszudrücken) dürfte sich nicht sehr einfach gestallten. Mathematisch gesehen is es ja nich das Problem nur woher weißte denn zwischen welchen Punkten es eine Fläche gibt und zwischen welchen nicht. Stell dir Quader vor! Da haste 6 Flächen außen und dann nochmal diese "Diagonal" Flächen wie auch immer die durch die Mitte gehen.

agrajag

Ich hätte ganz spontan gesagt:

Leg eine waagrechte und eine senkrechte Linie durch den Punk und zähle dann die Schnittpunkte mit den Linien zwischen den einzelnen Punkten. Ist die Anzahl beidemale gerade ist alles ok. Ist sie ungerade prüfe ob der Punkt auf einer der Linien liegt.

Eigentlich genau wie deine Lösung nur doppelt soviele Berechnungen

__________________
Today you...Tomorrow me.

Zergling-new

Hallo, erstmal danke dass du dir Zeit genommen hast.
Die Überprüfung ist Teil eines Unit-Tests.
Diese Funktionen berechnen Schnittpunkte und -Linien zwischen Punkten, Ellipsen, Linien oder Polygonen.
Ich soll nun deren Korrektheit überprüfen.

Mit Polygon meine ich keine Ansammlung dreieckiger Flächen, sondern eine Fläche, begrenzt durch die Linien zwischen "nebeneinander" liegenden Punkten. Ich bin jetzt zu hause, kann also mal mit Photoshop was basteln


Schwarz = Punkte des Polygons
Rot = "Linien des Polygons"
P = Jackpot, innerhalb oder außerhalb
Q = garantiert außerhalb befindlicher Punkt

Wenns natürlich ne andere Art gibt es herauszufinden oder wenn du es anders lösen würdest nur her damit


Edit: @Werbegeschenk: Kann ich überhaupt berechnen ob sich eine unendliche Gerade mit einer endlichen Strecke kreuzt?

Flor1an

Solang du den Richtungsvektor oder zwei Punkte kennst ist das kein Problem!

Danke für die Zeichnung, ich dachte du meinst Gebilde in 3D aber bei 2D ist es bissl einfacher.

Du hast gemeint du zählst die Ecken nicht mit .... angenommen der Punkt der nahe an Q liegt würde auf der blauen Linie sein! Dann hättest du als Counter 2 ... aber der Punkt ist innen im Polygon!

Ich glaub des wird wirklich schwierig. Du könntest theoretisch den Punkt Q so wählen das kein Polygonpunkt auf PQ liegt damit ist auch ausgeschlossen das PQ mit einer Strecke des Polygons zusammenfällt. Dann würde dein Lösungsvorschlag funktionieren würd ich jetzt sagen. Aber müsstest halt ausschließen dass eine Ecke auf PQ liegt.

imported_Ben

http://www.acm.org/pubs/tog/editors/erich/ptinpoly/
Vielleicht hilft es.

Den Link habsch ma von 'nem Kommilitonen erhalten. Ist schon was länger her .. aber hat mir diesbzgl. weitergeholfen.

__________________
Webentwickler-Blog - Buchbesprechung PHP Design Patterns - SQL-Antipatterns