Line-to-Square Collision

Does anyone know of how I could conceivably detect whether or not a line intersects a square? Some sort of polygon-polygon collision would also work.

I only need the theory... I can write my own code.

Oh, and 2D only, so no useful picking or triangle stuff. I've tried searching the archives, old posts, and Google too, and I can't seem to get anything useful, so any help would be much appreciated.

You can use the line intersects function Here it is. You would have to call it for every side of the square though and it isn't the most efficient way.

Graphics 1024,768,0,2
SetBuffer BackBuffer()


SeedRnd MilliSecs()
Global x1# = Rnd (0,800)
Global x2# = Rnd (0,800)
Global x3# = Rnd (0,800)
Global x4# = Rnd (0,800)
Global y1# = Rnd (0,600)
Global y2# = Rnd (0,600)
Global y3# = Rnd (0,600)
Global y4# = Rnd (0,600)


; Values returned by the Lines_Intersect() function.
Global Intersection_X#	;x coord of intersection
Global Intersection_Y#	;y coord of intersection
Global Intersection_AB#	;distance along seg AB,... >0 and <1 mean segment is intersected. Segments collide only if both of these are >0 <1
Global Intersection_CD#	;distance along seg CD,... >0 and <1 mean segment is intersected. Segments collide only if both of these are >0 <1


; manually enter some point info
While Not KeyHit(1) 
	Color 255,255,255 ; reset color to white

	Text 50,10,"enter 4 points by pressing 1234,.."

	If KeyDown(2) Then ; key 1
	x1=MouseX()
	y1=MouseY()
	EndIf 

	If KeyDown(3) Then ; key 2
	x2=MouseX()
	y2=MouseY()
	EndIf 

	If KeyDown(4) Then ; key 3
	x3=MouseX()
	y3=MouseY()
	EndIf 

	If KeyDown(5) Then ; key 4
	x4=MouseX()
	y4=MouseY()
	EndIf 

	cross=Lines_Intersect(x1, y1, x2, y2, x3, y3, x4, y4)


	;draw the lines
	Line x1,y1,x2,y2
	Line x3,y3,x4,y4
	Text x1,y1,"1"
	Text x2,y2,"2"
	Text x3,y3,"3"
	Text x4,y4,"4"

	Text 50,50,"crossing="+cross
	Text 50,65,"Intersection_X  : " + Intersection_X#  + "  Intersection_y  : " + Intersection_y#
	Text 50,80,"Intersection_AB : " + Intersection_AB# + "  Intersection_CD : " + Intersection_CD#

	If cross=1 Color 255,0,0 ; if there is an intersection, color the circle red
	Oval Intersection_X-5,Intersection_y-5,10,10  

	Flip
	Cls

Wend 



End



;Lines_Intersect() by sswift 
; -------------------------------------------------------------------------------------------------------------------
; This function determines if two lines in intersect in 2D.
; A & B are the endpoints of the first line segment.  C & D are the endpoints of the second.
;
; If the lines DO NOT instersect, the function returns FALSE.
;
; If the lines DO intersect, the point of intersection is returned in the global variables: 
; Intersection_X#, Intersection_Y#, Intersection_AB#, and Intersection_CD#
;
; Those last two variables indicate the location along each line segment where the point of intersection lies.
;
; For example:
;
; If Intersection_AB# is 0, then the point of intersection is at point A.  If it is 1, then it is at point B.
; If it is 0.5, then it is halfway between the two.  And if it is less than 0 or greater than 1, then the point lies
; on the line but outside of the specified line segment.
;
; Because you can determine if the intersection point lies within both line segments, you can also use this function
; to check to see if the line segments themselves intersect.
;
; Also, if these line segments indicate vectors of motion, then if either of the location values returned is negative
; then you know that the objects paths intersected in the past, and will not intersect in the future.
;
; And finally, please note that segments which are coincident (lie on the same line) are considered to be
; non-intersecting, as there is no single point of intersection.  You can easily detect this condition by changing
; the code below slightly as indicated.


; Code modified by Pongo to return true only if segments intersect
; -------------------------------------------------------------------------------------------------------------------
Function Lines_Intersect(Ax#, Ay#, Bx#, By#, Cx#, Cy#, Dx#, Dy#)
  	Rn# = (Ay#-Cy#)*(Dx#-Cx#) - (Ax#-Cx#)*(Dy#-Cy#)
        Rd# = (Bx#-Ax#)*(Dy#-Cy#) - (By#-Ay#)*(Dx#-Cx#)
		
	If Rd# = 0 
		
		; Lines are parralel.
		; If Rn# is also 0 then lines are coincident.  All points intersect. 
		; Otherwise, there is no intersection point.
		Return False
	Else
		; The lines intersect at some point.  Calculate the intersection point.
        Sn# = (Ay#-Cy#)*(Bx#-Ax#) - (Ax#-Cx#)*(By#-Ay#)
		Intersection_AB# = Rn# / Rd#
		Intersection_CD# = Sn# / Rd#
		Intersection_X# = Ax# + Intersection_AB#*(Bx#-Ax#)
        Intersection_Y# = Ay# + Intersection_AB#*(By#-Ay#)
			
	EndIf
		
	If Intersection_AB#>0 And Intersection_AB#<1 And Intersection_CD#>0 And Intersection_cd#<1
			Return True	
		Else
			Return False
	EndIf


End Function

I think this could be possible using orientation.

Function Orientation% ( x1#,y1#, x2#,y2#, Px#,Py# )
	; Linear determinant of the 3 points.
	; This function returns the orientation of px,py on line x1,y1,x2,y2.
	; Look from x2,y2 to the direction of x1,y1.
	; If px,py is on the right, function returns +1
	; If px,py is on the left, function returns -1
	; If px,py is directly ahead or behind, function returns 0
	Return Sgn((x2 - x1) * (Py - y1) - (Px - x1) * (y2 - y1))
End Function

I think that instead of checking when it does intersect, you need to deductively check when it doesn't intersect. For example put your line in parameters x1,y1,x2,y2 and run it with each of the corners of the square (calling the function 4 times). If the results are the same (-1,-1,-1,-1 or +1,+1,+1,+1), then you definitely have no intersection. If results are different, you need to continue with tests. The second set of tests would be running the function with sides of the square against end points of the line. If both ends of the line are on the "wrong" side of the square side, the line does not intersect. Then do the same for all 4 sides.

I think this would be enough to deduct all the possibilities when it doesn't intersect. I'm not sure though, so you need to test it properly. At maximum, you would be running Orientation function 12 times, but since the math of that function is so simple, it should be quite fast. Also it does less math if there is no intersection.

There should be seperate handling for the case where the length of the line is 0, but that should be easy.