Lines intersect

Blitz3D Forums/Blitz3D Beginners Area/Lines intersect

Nate the Great

(Posted 2008) [#1]

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 :)

Matty

(Posted 2008) [#2]

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

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

big10p

(Posted 2008) [#3]

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

Pongo

(Posted 2008) [#4]

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

Nate the Great

(Posted 2008) [#5]

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