Lines Intersect

This code has been declared by its author to be Public Domain code.

Lines Intersect by GfK

(Posted 1+ years ago)

There's a few examples of this already, but I wanted to write my own so that I understand it.

Note that it uses double precision throughout for accuracy, as otherwise the results on near-horizontal/vertical lines can be a touch erratic.

Speed tests: 5,000 iterations takes 1ms or less

Strict

'THE MATHS BIT


	Function intersect(x1:Double, y1:Double, x2:Double, y2:Double, u1:Double, v1:Double, u2:Double, v2:Double, xResult:Double var, yResult:Double var)
		Local m1:Double, m2:Double, b1:Double, b2:Double
		
		'CALCULATE SLOPE OF EACH LINE AND CHECK FOR POTENTIAL DIVISION-BY-ZERO 
		If (x2 - x1) <> 0
			m1 = (y2 - y1) / (x2 - x1)
		Else
			m1 = (y2 - y1)
		EndIf
		If (u2 - u1) <> 0
			m2 = (v2 - v1) / (u2 - u1)
		Else
			m2 = (v2 - v1)
		EndIf
		
		b1 = y1 - (m1 * x1)
		b2 = v1 - (m2 * u2)

		xresult = (v1 - y1 - (u1 * m2) + (x1 * m1)) / (m1 - m2)
		yResult = m1 * xResult + b1

		'NOTES
		'If m1 = m2 then both lines are parallel and will never intersect.
		'If m1 = m2 AND b1 = b2, then both lines are colinear (i.e. the same).
	End Function


'END OF MATHS BIT


'DEMO CODE

Graphics 800, 600

'define two lines as four pairs of x/y coordinates:
'line 1
Local x1:Double = 60, y1:Double = 450
Local x2:Double = 300, y2:Double = 50 'don't really need this as we'll use the mouse coords.
'line 2
Local u1:Double = 50, v1:Double = 100
Local u2:Double = 700, v2:Double = 525

'These vars will contain the intersection point.
Local xC:Double, yC:Double

While Not KeyDown(KEY_ESCAPE)
	intersect(x1, y1, Double(MouseX()), Double(MouseY()), u1, v1, u2, v2, xC, yC) 'calculate the point of intersection (xC and yC)
	Cls
	Draw(x1, y1, MouseX(), MouseY(), u1, v1, u2, v2) 'Draw the lines
	SetColor 0, 0, 255
	DrawOval xC - 5, yC - 5, 10, 10 'Draw oval at intersection point
	Flip
Wend

Function Draw(x1:Double, y1:Double, x2:Double, y2:Double, u1:Double, v1:Double, u2:Double, v2:Double)
	SetColor 255, 255, 0
	DrawLine x1, y1, x2, y2
	SetColor 255, 0, 0
	DrawLine u1, v1, u2, v2
End Function
'END OF DEMO CODE

Comments

AndrewT

(Posted 1+ years ago)

Nice job. I just made a line intersection function for the same reason you did, and it turned out near-identical; great minds think alike. ;)

Also, you can check for intersection between line segments as opposed to lines as well by checking if the intersection point is between the endpoints of both lines by adding this to the end of your function

	If Between(X, X1, X2) And Between(Y, Y1, Y2) And Between(X, X3, X4) And Between(Y, Y3, Y4)
                'Line segments intersect, return 1
		Return 1
	EndIf

        Return 0

Here's the Between function:

Function Between:Int(X:Float, B:Float, T:Float)
	If T > B
		If X > B And X < T
			Return 1
		EndIf
	Else
		If X > T And X < B
			Return 1
		EndIf
	EndIf
	Return 0
EndFunction

Might slow it down a bit, which is why I made a separate function to check for segment intersection.

GfK	(Posted 1+ years ago)

Thanks for that. I was going to add that later but you just saved me the trouble. ;)

Difference

(Posted 1+ years ago)

Thanks both.

Small error in the code above (that goes unnoticed if you don't need to check for colinear lines )

b2 = v1 - (m2 * u2)

should be

b2 = v1 - (m2 * u1)

Code Archives Forum