2d line intersects other 2d line + intersection 2d point

Started by RemiD, November 25, 2022, 10:20:47

Previous topic - Next topic

RemiD


;2d line intersects other 2d line example by RemiD (20221124)
;also calculates the intersection 2d point
;line intersects line math formula by NoseKills (20141023)

Graphics(640,480,32,2)

SeedRnd(MilliSecs())

;intersection point
Global intersect_x# : Global intersect_y#

Repeat

;line01 points p0 and p1
p0x# = Rand(0,640-1) : p0y# = Rand(0,480-1)
p1x# = Rand(0,640-1) : p1y# = Rand(0,480-1)

;line23 points p2 and p3
p2x# = Rand(0,640-1) : p2y# = Rand(0,480-1)
p3x# = Rand(0,640-1) : p3y# = Rand(0,480-1)

;check if the 2 lines intersect or not
R% = LineIntersectsLine( p0x, p0y, p1x, p1y, p2x, p2y, p3x, p3y )

SetBuffer(BackBuffer())
Color(0,0,0) : Cls()

;draw line01
Color(250,250,250) : Line( p0x, p0y, p1x, p1y )

;draw line23
Color(250,250,250) : Line( p2x, p2y, p3x, p3y )

If( R = True )
  Color(250,250,250) : Text( 0,0,"lines intersect at "+Str(Int(intersect_x))+","+Str(Int(intersect_y)) )
  ;draw intersection point
  Color(250,0,250) : Rect( intersect_x-1, intersect_y-1, 3, 3, True )
EndIf

Flip()

WaitKey()

Until( KeyHit(1) = True )

End()

;line intersects line math formula by NoseKills (20141023)
Function LineIntersectsLine( p0_x#, p0_y#, p1_x#, p1_y#, p2_x#, p2_y#, p3_x#, p3_y# )

s1_x# = p1_x - p0_x     
s1_y# = p1_y - p0_y
s2_x# = p3_x - p2_x   
s2_y# = p3_y - p2_y

s# = ( -s1_y * ( p0_x - p2_x ) + s1_x * ( p0_y - p2_y ) ) / ( -s2_x * s1_y + s1_x * s2_y )
t# = ( s2_x * ( p0_y - p2_y ) - s2_y * ( p0_x - p2_x ) ) / ( -s2_x * s1_y + s1_x * s2_y )

If( s >= 0 And s <= 1 And t >= 0 And t <= 1 )
  ;intersection detected
  intersect_x = p0_x + (  t * s1_x ) : intersect_y = p0_y + ( t * s1_y )
  Return True
Else
  ;no intersection
  intersect_x = 0 : intersect_y = 0
  Return False
EndIf

End Function

RemiD

#1

;2d line intersects other 2d line example by RemiD (20221125)
;also calculates the intersection 2d point
;line intersects line math formula by Minassian (20101122)

Graphics(640,480,32,2)

SeedRnd(MilliSecs())

;intersection point
Global intersect_x# : Global intersect_y#

Repeat

;line01 points p0 and p1
p0x# = Rand(0,640-1) : p0y# = Rand(0,480-1)
p1x# = Rand(0,640-1) : p1y# = Rand(0,480-1)

;line23 points p2 and p3
p2x# = Rand(0,640-1) : p2y# = Rand(0,480-1)
p3x# = Rand(0,640-1) : p3y# = Rand(0,480-1)

;check if the 2 lines intersect or not
R% = LineIntersectsLine( p0x, p0y, p1x, p1y, p2x, p2y, p3x, p3y )

SetBuffer(BackBuffer())
Color(0,0,0) : Cls()

;draw line01
Color(250,250,250) : Line( p0x, p0y, p1x, p1y )

;draw line23
Color(250,250,250) : Line( p2x, p2y, p3x, p3y )

If( R = True )
  Color(250,250,250) : Text( 0,0,"lines intersect at "+Str(Int(intersect_x))+","+Str(Int(intersect_y)) )
  ;draw intersection point
  Color(250,0,250) : Rect( intersect_x-1, intersect_y-1, 3, 3, True )
EndIf

Flip()

WaitKey()

Until( KeyHit(1) = True )

End()

;line intersects line math formula by Minassian (20101122)
Function LineIntersectsLine( p1_x#, p1_y#, p2_x#, p2_y#, p3_x#, p3_y#, p4_x#, p4_y# )

Ax# = p2_x-p1_x
Bx# = p3_x-p4_x

;// X bound box test //
if( Ax < 0 )
  x1lo# = p2_x : x1hi# = p1_x
else
  x1hi# = p2_x : x1lo# = p1_x
endif

if( Bx > 0 )
  if( x1hi < p4_x OR p3_x < x1lo ) : return false : endif
else
   if( x1hi < p3_x OR p4_x < x1lo ) : return false : endif
endif

Ay# = p2_y - p1_y
By# = p3_y - p4_y

;// Y bound box test //
If( Ay < 0 )                 
  y1lo# = p2_y : y1hi# = p1_y
Else
  y1hi# = p2_y : y1lo# = p1_y
EndIf

If( By > 0 )
  If( y1hi < p4_y Or p3_y < y1lo ) : Return False : EndIf
Else
  If( y1hi < p3_y Or p4_y < y1lo ) : Return False : EndIf
EndIf

Cx# = p1_x - p3_x
Cy# = p1_y - p3_y

;// alpha numerator //
d# =  ( By * Cx ) - ( Bx * Cy )

;// both denominator //
f# = ( Ay * Bx ) - ( Ax * By )

;// alpha tests //
If( f > 0 )
  If( d < 0 Or d > f ) : Return False : EndIf
Else
  If( d > 0 Or d < f ) : Return False : EndIf
EndIf

;// beta numerator//
e# = ( Ax * Cy ) - ( Ay * Cx ) 

;// beta tests //
If( f > 0 )                         
  If( e < 0 Or e > f ) : Return False : EndIf
Else
  If( e > 0 Or e < f ) : Return False : EndIf
EndIf

;// check if they are parallel //
If( f = 0) : Return False : EndIf
       
;// compute intersection coordinates //
;// numerator //
num# = d * Ax;

intersect_x = p1_x + num / f

num# = d * Ay

intersect_y = p1_y + num / f

Return True

End Function