Funktion Punkt im Polygon

Übersicht

BlitzMax, BlitzMax NG

Codearchiv & Module

	BlitzMoritz Betreff: Funktion Punkt im Polygon	So, März 29, 2009 11:00 Antworten mit Zitat
Bitte nicht aufregen - ich weiß, dieses Thema hatten wir schon ein paar Mal, aaaber: https://www.blitzforum.de/foru...t++polygon Dieser Thread stammt aus dem BB-Codearchiv und kann nicht 1:1 auf BM übertragen werden. https://www.blitzforum.de/foru...t++polygon Und aus diesem Thread ist keine fertige Function für das BM-Codearchiv entstanden. Anstatt aber einen uralten Thread auszugraben (und dafür Haue zu kriegen ), wollte ich die Sache für BlitzMax jetzt einfach mal abschließen und folgende winzige Funktion zur Verfügung stellen, die für jedes Polygon-Array (ob konvex oder konkav ist egal!) sehr schnell bestimmt, ob ein Punkt drinnen liegt oder nicht. Die geniale Idee dazu stammt nicht von mir, sondern von Steffen aus dem oben genannten zweiten Thread: Code: [AUSKLAPPEN] [EINKLAPPEN] Function PointInPolygon:Byte(Px:Float, Py:Float, Poly:Float[]) 'gibt True zurück, falls sich der Punkt [Px,Py] im Polygon-Array Poly befindet Local CountIntersections:Int 'zählt die Schnittpunkte For Local i:Int = 0 To Len(Poly)-1 Step 2 Local j:Int = (i + 2) Mod Len(Poly) Local ExternX:Float = Max(Poly[i], Poly[j]) + 1 If (Poly[i+1] > Py And Poly[j+1] < Py) Or (Poly[i+1] < Py And Poly[j+1] > Py) Then Local IntersectionX:Float = (Poly[j]-Poly[i]) / (Poly[j+1]-Poly[i+1]) * (Py - Poly[i+1]) + Poly[i] If IntersectionX >= Px And IntersectionX <= ExternX Then CountIntersections = CountIntersections + 1 End If Next If CountIntersections / 2 * 2 = CountIntersections Then Return False 'gradzahlig Return True 'ungeradzahlig: Punkt befindet sich IM Polygon! End Function Und wer's sich in einer kleinen Demo ansehen will: Code: [AUSKLAPPEN] [EINKLAPPEN] '##### Demo-Programm (PointInPolygon): ########## Graphics 960,720 SetLineWidth(2) Local Polygon:Float[] = CreateRandomPolygon(100) Repeat Cls DrawText "Neues Zufalls-Polygon (100 Punkte) mit Leertaste", 10, 10 If PointInPolygon(MouseX(), MouseY(), Polygon) = True Then SetColor 255,0,0 DrawText "Maus befindet sich im Polygon!", 360, 690 Else SetColor 0,0,255 End If DrawPolygonLines(Polygon) SetColor 0,255,0 DrawPolygonPoints(Polygon) Flip If KeyHit(KEY_SPACE) Then Polygon = CreateRandomPolygon(100) Until KeyDown(KEY_ESCAPE) Or AppTerminate() '------------------------------------------------------------------- Function CreateRandomPolygon:Float[](Count:Int, CentralDistance:Int = 320) Local NewPoly:Float[2Count] Local ZX:Int = Rand(CentralDistance, GraphicsWidth()-CentralDistance) Local ZY:Int = Rand(CentralDistance, GraphicsHeight()-CentralDistance) Local Distance:Int, Angle:Float = Rand(0,360) For Local c:Int = 0 To Count - 1 Distance = CentralDistance Rand(40, 100)/100.0 Angle = Angle + 360.0 / Count + (360.0 / Count )/3 * Rand(-100,+100) / 100.0 NewPoly[2c] = ZX + DistanceCos(Angle) NewPoly[2c+1] = ZY + DistanceSin(Angle) Next Return NewPoly End Function '------------------------------------------------------------------- Function DrawPolygonLines(Poly:Float[]) Local Count:Int = Len(Poly) For Local i:Int = 0 To Count-1 Step 2 Local j:Int = (i + 2) Mod Count DrawLine(Poly[i], Poly[i+1], Poly[j], Poly[j+1]) Next End Function '------------------------------------------------------------------- Function DrawPolygonPoints(Poly:Float[]) Local Count:Int = Len(Poly) For Local i:Int = 0 To Count-1 Step 2 DrawOval(Poly[i]-2, Poly[i+1]-2, 4, 4) Next End Function '------------------------------------------------------------------- Ich habe übrigens bei der Demo auf die BlitzMax-eigene Function DrawPoly mit gutem Grund verzichtet, da diese bei konkaven Formen mitunter ziemlichen Schrott darstellt, keine Ahnung, warum...

BlitzMoritz

Betreff: Funktion Punkt im Polygon

So, März 29, 2009 11:00
Antworten mit Zitat

Bitte nicht aufregen - ich weiß, dieses Thema hatten wir schon ein paar Mal, aaaber:
https://www.blitzforum.de/foru...t++polygon Dieser Thread stammt aus dem BB-Codearchiv und kann nicht 1:1 auf BM übertragen werden.
https://www.blitzforum.de/foru...t++polygon Und aus diesem Thread ist keine fertige Function für das BM-Codearchiv entstanden.
Anstatt aber einen uralten Thread auszugraben (und dafür Haue zu kriegen Wink

), wollte ich die Sache für BlitzMax jetzt einfach mal abschließen und folgende winzige Funktion zur Verfügung stellen, die für jedes Polygon-Array (ob konvex oder konkav ist egal!) sehr schnell bestimmt, ob ein Punkt drinnen liegt oder nicht. Die geniale Idee dazu stammt nicht von mir, sondern von Steffen aus dem oben genannten zweiten Thread:
Code: [AUSKLAPPEN]

Function PointInPolygon:Byte(Px:Float, Py:Float, Poly:Float[])
'gibt True zurück, falls sich der Punkt [Px,Py] im Polygon-Array Poly befindet
Local CountIntersections:Int 'zählt die Schnittpunkte
For Local i:Int = 0 To Len(Poly)-1 Step 2
   Local j:Int = (i + 2) Mod Len(Poly)
   Local ExternX:Float = Max(Poly[i], Poly[j]) + 1
   If (Poly[i+1] > Py And Poly[j+1] < Py) Or (Poly[i+1] < Py And Poly[j+1] > Py) Then
      Local IntersectionX:Float = (Poly[j]-Poly[i]) / (Poly[j+1]-Poly[i+1]) * (Py - Poly[i+1]) + Poly[i]
      If IntersectionX >= Px And IntersectionX <= ExternX Then CountIntersections = CountIntersections + 1
   End If
Next
If CountIntersections / 2 * 2 = CountIntersections Then Return False 'gradzahlig
Return True 'ungeradzahlig: Punkt befindet sich IM Polygon!
End Function

Und wer's sich in einer kleinen Demo ansehen will:

Code: [AUSKLAPPEN]

'##### Demo-Programm (PointInPolygon): ##########
Graphics 960,720
SetLineWidth(2)
Local Polygon:Float[] = CreateRandomPolygon(100)
Repeat
Cls
DrawText "Neues Zufalls-Polygon (100 Punkte) mit Leertaste", 10, 10
If PointInPolygon(MouseX(), MouseY(), Polygon) = True Then
   SetColor 255,0,0
   DrawText "Maus befindet sich im Polygon!", 360, 690
Else
   SetColor 0,0,255
End If
DrawPolygonLines(Polygon)
SetColor 0,255,0
DrawPolygonPoints(Polygon)
Flip
If KeyHit(KEY_SPACE) Then Polygon = CreateRandomPolygon(100)
Until KeyDown(KEY_ESCAPE) Or AppTerminate()
'-------------------------------------------------------------------
Function CreateRandomPolygon:Float[](Count:Int, CentralDistance:Int = 320)
Local NewPoly:Float[2*Count]
Local ZX:Int = Rand(CentralDistance, GraphicsWidth()-CentralDistance)
Local ZY:Int = Rand(CentralDistance, GraphicsHeight()-CentralDistance)
Local Distance:Int, Angle:Float = Rand(0,360)
For Local c:Int = 0 To Count - 1
   Distance = CentralDistance * Rand(40, 100)/100.0
   Angle = Angle + 360.0 / Count + (360.0 / Count )/3 * Rand(-100,+100) / 100.0
   NewPoly[2*c] = ZX + Distance*Cos(Angle)
   NewPoly[2*c+1] = ZY + Distance*Sin(Angle)
Next
Return NewPoly
End Function
'-------------------------------------------------------------------
Function DrawPolygonLines(Poly:Float[])
Local Count:Int = Len(Poly)
For Local i:Int = 0 To Count-1 Step 2
   Local j:Int = (i + 2) Mod Count
   DrawLine(Poly[i], Poly[i+1], Poly[j], Poly[j+1])
Next
End Function
'-------------------------------------------------------------------
Function DrawPolygonPoints(Poly:Float[])
Local Count:Int = Len(Poly)
For Local i:Int = 0 To Count-1 Step 2
   DrawOval(Poly[i]-2, Poly[i+1]-2, 4, 4)
Next
End Function
'-------------------------------------------------------------------

Ich habe übrigens bei der Demo auf die BlitzMax-eigene Function DrawPoly mit gutem Grund verzichtet, da diese bei konkaven Formen mitunter ziemlichen Schrott darstellt, keine Ahnung, warum...