LineRectIntersection

Übersicht

BlitzBasic

Codearchiv

	Markus Rossé Betreff: LineRectIntersection	Fr, Jan 13, 2006 20:56 Antworten mit Zitat
Ich habe eine ziemlich nützliche Funktion geschrieben, die ein paar von euch vielleicht interessieren könnte. Es geht darum, die Kollision zwischen einer Linie und einem Rechteck zu testen. Ausserdem wird der erste Schnittpunkt auf der Linie zurückgeliefert. Code: [AUSKLAPPEN] [EINKLAPPEN] Global LineRectIntersectionX#,LineRectIntersectionY# ; Important! ;---------------------------------------------------------------------------------------------------- ; This Function determine if a Line and a Rectangle intersect. If there is a intersection, the ; Function returns TRUE, otherwise FALSE. The Coordinates of the first Intersection of the Line ; are returned in the global Variables LineRectIntersectionX# and LineRectIntersectionY#. ;---------------------------------------------------------------------------------------------------- Function LineRectIntersection(LineX1#,LineY1#,LineX2#,LineY2#,RectX#,RectY#,RectWidth#,RectHeight#) Local b#,m#,x#,Intersection If LineY1#=LineY2# If LineX1#<LineX2# For x#=LineX1# To LineX2# If x#>=RectX# And x#<=RectX#+RectWidth# And LineY1#>=RectY# And LineY1#<=RectY#+RectHeight# LineRectIntersectionX#=x# LineRectIntersectionY#=y# Intersection=True End If Next Else For x#=LineX1# To LineX2# Step -1 If x#>=RectX# And x#<=RectX#+RectWidth# And LineY1#>=RectY# And LineY1#<=RectY#+RectHeight# LineRectIntersectionX#=x# LineRectIntersectionY#=y# Intersection=True End If Next End If ElseIf LineX1#=LineX2# If LineY1#<LineY2# For y#=LineY1# To LineY2# If LineX1#>=RectX# And LineX1#<=RectX#+RectWidth# And y#>=RectY# And y#<=RectY#+RectHeight# LineRectIntersectionX#=x# LineRectIntersectionY#=y# Intersection=True End If Next Else For y#=LineY1# To LineY2# Step -1 If LineX1#>=RectX# And LineX1#<=RectX#+RectWidth# And y#>=RectY# And y#<=RectY#+RectHeight# LineRectIntersectionX#=x# LineRectIntersectionY#=y# Intersection=True End If Next End If Else m#=(LineY1#-LineY2#)/(LineX1#-LineX2#) b#=LineY1#-(m#LineX1) If LineX1#<LineX2# For x#=LineX1# To LineX2# y#=(m#x#)+b# If x#>=RectX# And x#<=RectX#+RectWidth# And y#>=RectY# And y#<=RectY#+RectHeight# LineRectIntersectionX#=x# LineRectIntersectionY#=y# Intersection=True End If Next Else For x#=LineX1# To LineX2# Step -1 y#=(m#x#)+b# If x#>=RectX# And x#<=RectX#+RectWidth# And y#>=RectY# And y#<=RectY#+RectHeight# LineRectIntersectionX#=x# LineRectIntersectionY#=y# Intersection=True End If Next End If If Not Intersection If LineY1#<LineY2# For y#=LineY1# To LineY2# x#=(y#-b#)/m# If x#>=RectX# And x#<=RectX#+RectWidth# And y#>=RectY# And y#<=RectY#+RectHeight# LineRectIntersectionX#=x# LineRectIntersectionY#=y# Intersection=True End If Next Else For y#=LineY1# To LineY2# Step -1 x#=(y#-b#)/m# If x#>=RectX# And x#<=RectX#+RectWidth# And y#>=RectY# And y#<=RectY#+RectHeight# LineRectIntersectionX#=x# LineRectIntersectionY#=y# Intersection=True End If Next End If End If End If Return Intersection End Function Und ein Beispiel: Code:* [AUSKLAPPEN] [EINKLAPPEN] SeedRnd(MilliSecs()) HidePointer() Graphics 640,480,0,2 SetBuffer BackBuffer() Global LineRectIntersectionX#,LineRectIntersectionY# ; Important! Type lines Field x1,y1,x2,y2 End Type Local l.lines For n=0 To 20 l=New lines l\x1=Rand(20,620) l\y1=Rand(20,460) l\x2=Rand(20,620) l\y2=Rand(20,460) Next While Not KeyHit(1) Cls t=False For l=Each lines If LineRectIntersection(l\x1,l\y1,l\x2,l\y2,MouseX(),MouseY(),10,10) t=True Line l\x1,l\y1,l\x2,l\y2 Next Rect MouseX(),MouseY(),10,10,t Flip Wend End ;---------------------------------------------------------------------------------------------------- ; This Function determine if a Line and a Rectangle intersect. If there is a intersection, the ; Function returns TRUE, otherwise FALSE. The Coordinates of the first Intersection of the Line ; are returned in the global Variables LineRectIntersectionX# and LineRectIntersectionY#. ;---------------------------------------------------------------------------------------------------- Function LineRectIntersection(LineX1#,LineY1#,LineX2#,LineY2#,RectX#,RectY#,RectWidth#,RectHeight#) Local b#,m#,x#,Intersection If LineY1#=LineY2# If LineX1#<LineX2# For x#=LineX1# To LineX2# If x#>=RectX# And x#<=RectX#+RectWidth# And LineY1#>=RectY# And LineY1#<=RectY#+RectHeight# LineRectIntersectionX#=x# LineRectIntersectionY#=y# Intersection=True End If Next Else For x#=LineX1# To LineX2# Step -1 If x#>=RectX# And x#<=RectX#+RectWidth# And LineY1#>=RectY# And LineY1#<=RectY#+RectHeight# LineRectIntersectionX#=x# LineRectIntersectionY#=y# Intersection=True End If Next End If ElseIf LineX1#=LineX2# If LineY1#<LineY2# For y#=LineY1# To LineY2# If LineX1#>=RectX# And LineX1#<=RectX#+RectWidth# And y#>=RectY# And y#<=RectY#+RectHeight# LineRectIntersectionX#=x# LineRectIntersectionY#=y# Intersection=True End If Next Else For y#=LineY1# To LineY2# Step -1 If LineX1#>=RectX# And LineX1#<=RectX#+RectWidth# And y#>=RectY# And y#<=RectY#+RectHeight# LineRectIntersectionX#=x# LineRectIntersectionY#=y# Intersection=True End If Next End If Else m#=(LineY1#-LineY2#)/(LineX1#-LineX2#) b#=LineY1#-(m#LineX1) If LineX1#<LineX2# For x#=LineX1# To LineX2# y#=(m#x#)+b# If x#>=RectX# And x#<=RectX#+RectWidth# And y#>=RectY# And y#<=RectY#+RectHeight# LineRectIntersectionX#=x# LineRectIntersectionY#=y# Intersection=True End If Next Else For x#=LineX1# To LineX2# Step -1 y#=(m#*x#)+b# If x#>=RectX# And x#<=RectX#+RectWidth# And y#>=RectY# And y#<=RectY#+RectHeight# LineRectIntersectionX#=x# LineRectIntersectionY#=y# Intersection=True End If Next End If If Not Intersection If LineY1#<LineY2# For y#=LineY1# To LineY2# x#=(y#-b#)/m# If x#>=RectX# And x#<=RectX#+RectWidth# And y#>=RectY# And y#<=RectY#+RectHeight# LineRectIntersectionX#=x# LineRectIntersectionY#=y# Intersection=True End If Next Else For y#=LineY1# To LineY2# Step -1 x#=(y#-b#)/m# If x#>=RectX# And x#<=RectX#+RectWidth# And y#>=RectY# And y#<=RectY#+RectHeight# LineRectIntersectionX#=x# LineRectIntersectionY#=y# Intersection=True End If Next End If End If End If Return Intersection End Function Wer Spass daran hat kann es gern noch optimieren. [edit] Ich sollte öfters ins Codearchiv schauen, ein paar Themen weiter unten ist die gleiche Funktion (https://www.blitzforum.de/viewtopic.php?t=1076), allerdings ist diese hier imho Fehlerfrei und berücksichtigt auch Sezialfälle (desshalb ist sie auch so lang) [edit2] Die Funktion ist nicht 100% genau mit der Linienfunktion von Blitzbasic. Dh. wenn ihr 1x1 pixel grosses Rect nehmt, wird die Kollision manchmal von der Linie um einen Pixel abweichen. Das liegt daran, dass Blitzbasic wohl einen anderen Algorithmus für die Linie verwendet als eine Lineare Funktion. cu, Markus Rossé

Markus Rossé

Betreff: LineRectIntersection

Fr, Jan 13, 2006 20:56
Antworten mit Zitat

Ich habe eine ziemlich nützliche Funktion geschrieben, die ein paar von euch vielleicht interessieren könnte. Es geht darum, die Kollision zwischen einer Linie und einem Rechteck zu testen. Ausserdem wird der erste Schnittpunkt auf der Linie zurückgeliefert.

Code: [AUSKLAPPEN]

Global LineRectIntersectionX#,LineRectIntersectionY# ; Important!
;----------------------------------------------------------------------------------------------------
; This Function determine if a Line and a Rectangle intersect. If there is a intersection, the
; Function returns TRUE, otherwise FALSE. The Coordinates of the first Intersection of the Line
; are returned in the global Variables LineRectIntersectionX# and LineRectIntersectionY#.
;----------------------------------------------------------------------------------------------------
Function LineRectIntersection(LineX1#,LineY1#,LineX2#,LineY2#,RectX#,RectY#,RectWidth#,RectHeight#)
Local b#,m#,x#,Intersection
If LineY1#=LineY2#
If LineX1#<LineX2#
   For x#=LineX1# To LineX2#
      If x#>=RectX# And x#<=RectX#+RectWidth# And LineY1#>=RectY# And LineY1#<=RectY#+RectHeight#
         LineRectIntersectionX#=x#
         LineRectIntersectionY#=y#
         Intersection=True
      End If
   Next
Else
   For x#=LineX1# To LineX2# Step -1
      If x#>=RectX# And x#<=RectX#+RectWidth# And LineY1#>=RectY# And LineY1#<=RectY#+RectHeight#
         LineRectIntersectionX#=x#
         LineRectIntersectionY#=y#
         Intersection=True
      End If
   Next
End If
ElseIf LineX1#=LineX2#
If LineY1#<LineY2#
   For y#=LineY1# To LineY2#
      If LineX1#>=RectX# And LineX1#<=RectX#+RectWidth# And y#>=RectY# And y#<=RectY#+RectHeight#
         LineRectIntersectionX#=x#
         LineRectIntersectionY#=y#
         Intersection=True
      End If
   Next
Else
   For y#=LineY1# To LineY2# Step -1
      If LineX1#>=RectX# And LineX1#<=RectX#+RectWidth# And y#>=RectY# And y#<=RectY#+RectHeight#
         LineRectIntersectionX#=x#
         LineRectIntersectionY#=y#
         Intersection=True
      End If
   Next
End If
Else
m#=(LineY1#-LineY2#)/(LineX1#-LineX2#)
b#=LineY1#-(m#*LineX1)
If LineX1#<LineX2#
   For x#=LineX1# To LineX2#
      y#=(m#*x#)+b#
      If x#>=RectX# And x#<=RectX#+RectWidth# And y#>=RectY# And y#<=RectY#+RectHeight#
         LineRectIntersectionX#=x#
         LineRectIntersectionY#=y#
         Intersection=True
      End If
   Next
Else
   For x#=LineX1# To LineX2# Step -1
      y#=(m#*x#)+b#
      If x#>=RectX# And x#<=RectX#+RectWidth# And y#>=RectY# And y#<=RectY#+RectHeight#
         LineRectIntersectionX#=x#
         LineRectIntersectionY#=y#
         Intersection=True
      End If
   Next
End If
If Not Intersection
   If LineY1#<LineY2#
      For y#=LineY1# To LineY2#
         x#=(y#-b#)/m#
         If x#>=RectX# And x#<=RectX#+RectWidth# And y#>=RectY# And y#<=RectY#+RectHeight#
            LineRectIntersectionX#=x#
            LineRectIntersectionY#=y#
            Intersection=True
         End If
      Next
   Else
      For y#=LineY1# To LineY2# Step -1
         x#=(y#-b#)/m#
         If x#>=RectX# And x#<=RectX#+RectWidth# And y#>=RectY# And y#<=RectY#+RectHeight#
            LineRectIntersectionX#=x#
            LineRectIntersectionY#=y#
            Intersection=True
         End If
      Next
   End If
End If
End If
Return Intersection
End Function

Und ein Beispiel:
Code: [AUSKLAPPEN]

SeedRnd(MilliSecs())
HidePointer()
Graphics 640,480,0,2
SetBuffer BackBuffer()

Global LineRectIntersectionX#,LineRectIntersectionY# ; Important!

Type lines
Field x1,y1,x2,y2
End Type
Local l.lines

For n=0 To 20
l=New lines
l\x1=Rand(20,620)
l\y1=Rand(20,460)
l\x2=Rand(20,620)
l\y2=Rand(20,460)
Next

While Not KeyHit(1)
Cls

t=False
For l=Each lines
If LineRectIntersection(l\x1,l\y1,l\x2,l\y2,MouseX(),MouseY(),10,10) t=True
Line l\x1,l\y1,l\x2,l\y2
Next

Rect MouseX(),MouseY(),10,10,t

Flip
Wend
End

;----------------------------------------------------------------------------------------------------
; This Function determine if a Line and a Rectangle intersect. If there is a intersection, the
; Function returns TRUE, otherwise FALSE. The Coordinates of the first Intersection of the Line
; are returned in the global Variables LineRectIntersectionX# and LineRectIntersectionY#.
;----------------------------------------------------------------------------------------------------
Function LineRectIntersection(LineX1#,LineY1#,LineX2#,LineY2#,RectX#,RectY#,RectWidth#,RectHeight#)
Local b#,m#,x#,Intersection
If LineY1#=LineY2#
If LineX1#<LineX2#
   For x#=LineX1# To LineX2#
      If x#>=RectX# And x#<=RectX#+RectWidth# And LineY1#>=RectY# And LineY1#<=RectY#+RectHeight#
         LineRectIntersectionX#=x#
         LineRectIntersectionY#=y#
         Intersection=True
      End If
   Next
Else
   For x#=LineX1# To LineX2# Step -1
      If x#>=RectX# And x#<=RectX#+RectWidth# And LineY1#>=RectY# And LineY1#<=RectY#+RectHeight#
         LineRectIntersectionX#=x#
         LineRectIntersectionY#=y#
         Intersection=True
      End If
   Next
End If
ElseIf LineX1#=LineX2#
If LineY1#<LineY2#
   For y#=LineY1# To LineY2#
      If LineX1#>=RectX# And LineX1#<=RectX#+RectWidth# And y#>=RectY# And y#<=RectY#+RectHeight#
         LineRectIntersectionX#=x#
         LineRectIntersectionY#=y#
         Intersection=True
      End If
   Next
Else
   For y#=LineY1# To LineY2# Step -1
      If LineX1#>=RectX# And LineX1#<=RectX#+RectWidth# And y#>=RectY# And y#<=RectY#+RectHeight#
         LineRectIntersectionX#=x#
         LineRectIntersectionY#=y#
         Intersection=True
      End If
   Next
End If
Else
m#=(LineY1#-LineY2#)/(LineX1#-LineX2#)
b#=LineY1#-(m#*LineX1)
If LineX1#<LineX2#
   For x#=LineX1# To LineX2#
      y#=(m#*x#)+b#
      If x#>=RectX# And x#<=RectX#+RectWidth# And y#>=RectY# And y#<=RectY#+RectHeight#
         LineRectIntersectionX#=x#
         LineRectIntersectionY#=y#
         Intersection=True
      End If
   Next
Else
   For x#=LineX1# To LineX2# Step -1
      y#=(m#*x#)+b#
      If x#>=RectX# And x#<=RectX#+RectWidth# And y#>=RectY# And y#<=RectY#+RectHeight#
         LineRectIntersectionX#=x#
         LineRectIntersectionY#=y#
         Intersection=True
      End If
   Next
End If
If Not Intersection
   If LineY1#<LineY2#
      For y#=LineY1# To LineY2#
         x#=(y#-b#)/m#
         If x#>=RectX# And x#<=RectX#+RectWidth# And y#>=RectY# And y#<=RectY#+RectHeight#
            LineRectIntersectionX#=x#
            LineRectIntersectionY#=y#
            Intersection=True
         End If
      Next
   Else
      For y#=LineY1# To LineY2# Step -1
         x#=(y#-b#)/m#
         If x#>=RectX# And x#<=RectX#+RectWidth# And y#>=RectY# And y#<=RectY#+RectHeight#
            LineRectIntersectionX#=x#
            LineRectIntersectionY#=y#
            Intersection=True
         End If
      Next
   End If
End If
End If
Return Intersection
End Function

Wer Spass daran hat kann es gern noch optimieren.

[edit]
Ich sollte öfters ins Codearchiv schauen, ein paar Themen weiter unten ist die gleiche Funktion (https://www.blitzforum.de/viewtopic.php?t=1076), allerdings ist diese hier imho Fehlerfrei und berücksichtigt auch Sezialfälle (desshalb ist sie auch so lang)

[edit2]
Die Funktion ist nicht 100% genau mit der Linienfunktion von Blitzbasic. Dh. wenn ihr 1x1 pixel grosses Rect nehmt, wird die Kollision manchmal von der Linie um einen Pixel abweichen. Das liegt daran, dass Blitzbasic wohl einen anderen Algorithmus für die Linie verwendet als eine Lineare Funktion.

cu, Markus Rossé