Lines intersect

I was in the middle of a 2d game and I realized that I needed a linesintersect function. I thought it would be simple so I tried to make one and soon realized just how hard it was. I could not find anything in the code archives either. I guess what I am asking is does anyone have a lines intersect function that is efficient and fast? Any help is greatly appreciated :)

http://blitzbasic.com/codearcs/codearcs.php?code=471

This one by sswift in the code archives should be fine.

That one of sswifts doesn't work, as someone has pointed out in the comments. There are several other one's in the archives that do work, though.

[edit]

Actually, here's the functions I have for line intersection:

;
; Determines whether two lines intersect without calculating the actual point of intersection.
;
; Params:
; x1,y1   - Start coords of first line.
; dx1,dy1 - Delta coords of first line.
; x2,y2   - Start coords of second line.
; dx2,dy2 - Delta coords of second line.
;
; Returns:
; True if the lines intersect, false otherwise.
;
Function lines_intersect(x1#, y1#, dx1#, dy1#,  x2#, y2#, dx2#, dy2#)
	
	u_b# = dy2 * dx1 - dx2 * dy1

	If (u_b <> 0) 

		ua_t# = (dx2 * (y1 - y2)) - (dy2 * (x1 - x2))
		ub_t# = (dx1 * (y1 - y2)) - (dy1 * (x1 - x2))
		
		ua# = ua_t / u_b
		ub# = ub_t / u_b

		If (ua >= 0 And ua =< 1 And ub >= 0 And ub =< 1) Then Return True

	EndIf

	Return False
	
End Function

Global intersect_x#, intersect_y#

;
; Determines whether two lines intersect, or not. If the lines do intersect, the
; point of intersection is returned in the global variables intersect_x and intersect_y.
;
; Params:
; x1,y1   - Start coords of first line.
; dx1,dy1 - Delta coords of first line.
; x2,y2   - Start coords of second line.
; dx2,dy2 - Delta coords of second line.
;
; Returns:
; True if the lines intersect, false otherwise.
;
Function lines_intersect_xy(x1#, y1#, dx1#, dy1#,  x2#, y2#, dx2#, dy2#)
	
	u_b# = dy2 * dx1 - dx2 * dy1

	If (u_b <> 0) 

		ua_t# = (dx2 * (y1 - y2)) - (dy2 * (x1 - x2))
		ub_t# = (dx1 * (y1 - y2)) - (dy1 * (x1 - x2))
		
		ua# = ua_t / u_b
		ub# = ub_t / u_b
	
		If (ua >= 0 And ua <= 1 And ub >= 0 And ub <= 1) 

			intersect_x = x1 + (ua * dx1)
			intersect_y = y1 + (ua * dy1)

			Return True

		EndIf 

	EndIf

	Return False
	
End Function

Here is a chunk of code using a modified version of sswifts.

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

Thank you so much pongo for the modified version. I like it the most :)

thanks to everyone else who helped.

P.S. Is there a way to do a search on the code archives? I can't seem to do a search on them. I just have to look through them manually. I guess that is why I have to ask for things like this