Punkt-in-Polygon-Test nach JORDAN

Ma_Scht — Thu, 08 Jun 2023 08:03:07 GMT

Howdy, wer's mal braucht.
Routine prüft, ob sich ein Pkt. in einem beliebigen Polygon befindet.
Für Testzwecke hat der folgende Polygon 6 Eckpunkte.
Einfach die dyn HoSpos (befinden sich zu Beginn im Objektursprung) aufziehen!
Gruß

!!!anzulegende PARAMETER:
"PktTestX" vom Typ LÄNGE
"PktTestY" vom Typ LÄNGE
"PktAnz" vom Typ GANZZAHL, Startwert = 6
"PktX" 1-dimensionales ARRAY, [7], vom Typ LÄNGE
"PktY" 1-dimensionales ARRAY, [7], vom Typ LÄNGE

!!! 2-D-SCRIPT:
!!!!!! https://de.wikipedia.org/wiki/Punkt-in- ... ach_Jordan !!!!!!

EPS = 0.0001
unID = 1
HOTSPOT2 0 , 0 , unID : unID=unID+1 !Fangpunkt am Objekteinsetzpunkt
CIRCLE2 0 , 0 , 0.025

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!! Position des Testpunktes !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!! Vertikale Richtung
HOTSPOT2 pktTestX,0,unID,pktTestY,1+128 : unID=unID+1 !Basisfangpunkt
HOTSPOT2 pktTestX,pktTestY,unID,pktTestY,2 : unID=unID+1 !beweglicher Fangpunkt
HOTSPOT2 pktTestX,-1,unID,pktTestY,3 : unID=unID+1 !Referenzrichtung
!!! Horizontale Richtung
HOTSPOT2 0,pktTestY,unID,pktTestX,1+128 : unID=unID+1 !Basisfangpunkt
HOTSPOT2 pktTestX,pktTestY,unID,pktTestX ,2: unID=unID+1 !beweglicher Fangpunkt
HOTSPOT2 -1,pktTestY,unID,pktTestX,3 : unID=unID+1 !Referenzrichtung

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!! Eckpunkte des Polygons !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
FOR i = 1 TO PktAnz
!!! Vertikale Richtung
HOTSPOT2 PktX ,0 ,unID,PktY ,1+128 : unID=unID+1 !Basisfangpunkt
HOTSPOT2 PktX,PktY,unID,PktY,2, PktY,"Y Pkt.Nr: " + STR(i,1,0): unID=unID+1 !beweglicher Fangpunkt
HOTSPOT2 PktX,-1,unID,PktY,3 : unID=unID+1 !Referenzrichtung
!!! Horizontale Richtung
HOTSPOT2 0,PktY,unID,PktX,1+128 : unID=unID+1 !Basisfangpunkt
HOTSPOT2 PktX,PktY,unID,PktX,2, PktX,"X Pkt.Nr: " + STR(i,1,0) : unID=unID+1 !beweglicher Fangpunkt
HOTSPOT2 -1,PktY,unID,PktX,3 : unID=unID+1 !Referenzrichtung

!TEXT2 pktX, pktY, STR(i,1,0) + " (" + STR(pktX,3,2) + "|" + STR(pktY,3,2) + ")"
TEXT2 pktX, pktY, STR(i,1,0)
NEXT i

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!! Außenkonturen des Polygons !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
PktX[PktAnz+1] = PktX[1]
PktY[PktAnz+1] = PktY[1]

FOR i = 1 TO PktAnz
LINE2 PktX,PktY, PktX[i+1],PktY[i+1]
HOTLINE2 PktX,PktY, PktX[i+1],PktY[i+1]
NEXT i

CIRCLE2 pktTestX, pktTestY, 0.1 !!!! Das ist der Punkt der getestet werden soll, ob er im Dreieck liegt
HOTARC2 pktTestX, pktTestY, 0.1 ,0,360, unID : unID=unID+1

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!! Punkt-in-Polygon-Test nach JORDAN !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!! https://de.wikipedia.org/wiki/Punkt-in- ... ach_Jordan !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

ergKPT = 0 !!! INITIALISIERUNG - Ergebnis des KreuzProdukt-Testes

!!!Funktion: PunktInPolygon
!!!Parameter: Ecken P[1], ...,P[n] eines ebenen Polygons P, Testpunkt Q
!!!Rückgabe: +1, wenn Q innerhalb P liegt;
!!! −1, wenn Q außerhalb P liegt;
!!! 0, wenn Q auf P liegt

!!! Zur Sicherheit nochmal, falls o.g. AußenKontur nicht existiert !!!
PktX[PktAnz+1] = PktX[1]
PktY[PktAnz+1] = PktY[1]
toggleBinDrinJN = -1

FOR i = 1 TO PktAnz - 0
checker = 0

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!! KreuzProduktTest - BEGINN !!!!!
!!!Funktion: KreuzProdTest
!!!Parameter: Punkte
!!! A = (pktTestX,pktTestY),
!!! B = (PktX,PktY),
!!! C = (PktX[i+1],PktY[i+1])
!!!Rückgabe: −1, wenn der Strahl von A nach rechts die Kante [BC] schneidet
!!!(außer im unteren Endpunkt);
!!! 0, wenn A auf [BC] liegt;
!!! +1, ansonsten

IF ABS(pktTestY - PktY) < EPS AND ABS(PktY < PktY[i+1]) < EPS THEN
IF ( PktX <= pktTestX AND pktTestX <= PktX[i+1] ) OR ( PktX[i+1] <= pktTestX AND pktTestX <= PktX) THEN
ergKPT = 0
ELSE
ergKPT = 1
ENDIF
ENDIF

IF ABS(pktTestY - PktY) < EPS AND ABS(pktTestX - PktX) < EPS THEN
ergKPT = 0
ENDIF

IF PktY > PktY[i+1] THEN
checker = 1
tempX = PktX
tempY = PktY
PktX = PktX[i+1]
PktY = PktY[i+1]
PktX[i+1] = tempX
PktY[i+1] = tempY
ENDIF

IF (pktTestY <= PktY) OR (pktTestY > PktY[i+1]) THEN
ergKPT = 1
ENDIF

delta2 = (PktX - pktTestX) * (PktY[i+1] - pktTestY) - (PktY - pktTestY) * (PktX[i+1] - pktTestX)

IF delta2 > EPS THEN
!!! zus. folg. Prüfung v. SCHT ergänzt, dann funzt es !!!
IF pktTestY > PktY AND pktTestY < PktY[i+1] THEN
ergKPT = -1
ENDIF
ELSE
IF delta2 < 0 THEN
ergKPT = 1
ELSE
ergKPT = 0
ENDIF
ENDIF

!!!!! Zurück holen der ursprünglichen Werte f. d. nächsten Schleifendurchlauf !!!!!
IF checker = 1 THEN
tempX = PktX
tempY = PktY
PktX = PktX[i+1]
PktY = PktY[i+1]
PktX[i+1] = tempX
PktY[i+1] = tempY
ENDIF

!TEXT2 -1 + 0.75 * i , 2.00 , STR(ergKPT,1,0)
!!!!! KreuzProduktTest - ENDE !!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

toggleBinDrinJN = toggleBinDrinJN * ergKPT

!TEXT2 -1 + 0.75 * i , 2.50 , "t:" + STR(toggleBinDrinJN , 1 , 0)

NEXT i

xxx= 1
yyy= 2
IF toggleBinDrinJN < 0 THEN TEXT2 xxx , yyy , "Bin doch kein Hund! Will nicht draußen bleiben! 😞"
IF toggleBinDrinJN = 0 THEN TEXT2 xxx , yyy , "Bin gut drauf 🙂"
IF toggleBinDrinJN > 0 THEN TEXT2 xxx , yyy , "Ich bin drin! 🙂)"

END:::::::::::::::::::::::::::::::

Re: Punkt-in-Polygon-Test nach JORDAN

Hmooslechner — Thu, 08 Jun 2023 10:33:40 GMT

hätte ich schon öfter brauchen können - ist die Frage, wie "performat" es ist, wenn man viele Punkte nachprüft.

ähnliche Funktionen habe ich selber "zusammengeschustert", als ich mit einem Fliesen-GDL vor ca.10 Jahren mal "an seine Grenzen" gescriptet hatte.

War damals so gedacht:

https://www.youtube.com/watch?v=n1MPKb2YTMs

Muss mich mal wieder reintiegern, ob Dein Script hier was bringen würde.

Ich den denke an Fliesen zählen im Polygon..

Thema "Re: Punkt-in-Polygon-Test nach JORDAN" in Programmierung

Punkt-in-Polygon-Test nach JORDAN

Re: Punkt-in-Polygon-Test nach JORDAN