Line Intersect Circle

hi!
someone can help me to find a function to
detect if a line collide with a circle ? (and determine intersection points?)

please helpme !!!

I have tried various methods but they are slow...

help!

To find if the line intersects the circle, just take the point at the center of the circle, use the point distance to line formula and then check if that distance is less than the radius of the circle.

Pretty sure I posted some code for this in the main BMax forum. Check back a page or two.

Thought I'd have a go at the challenge, so after thinking through the algebra on a piece of paper, how about something like this:

Basically you pass any two points on the line, the center of the circle, and the radius to GetIntersectionLineCircle() and the function will return the points of intersection (if there are any).

SuperStrict

Local tmpIntersectLineCircle#[][]

'tmpIntersectLineCircle = GetIntersectionLineCircle( [0.0,6.25], [1.0,7.0], [0.0, 0.0], 1.0 )
'tmpIntersectLineCircle = GetIntersectionLineCircle( [0.0,6.25], [1.0,7.0], [0.0, 0.0], 5.0 )

Local i%, tmpMax% = 1000		'Change this to find an average time for multiple calls
Local tmpTime% = MilliSecs()

For i% = 0 Until tmpMax
	tmpIntersectLineCircle = GetIntersectionLineCircle( [0.0,6.25], [1.0,7.0], [3.0, 4.0], 25.0 )
Next

Print "Time Taken to Make " + i + " Calls: " + (MilliSecs()-tmpTime) + " ms"
Print "Average Time Taken per Call: " + ((MilliSecs()-tmpTime)/1.0/i) + " ms"

Select tmpIntersectLineCircle.length

	Case 0;	Print "Line does not intersect with circle!"
	Case 1;	Print "Line is a tangent to the circle, and touches at (" + tmpIntersectLineCircle[0][0] + ", " + tmpIntersectLineCircle[0][1] + ")"
	Case 2;	Print "Line goes through the circle at (" + tmpIntersectLineCircle[0][0] + ", " + tmpIntersectLineCircle[0][1] + ") and (" + ..
			tmpIntersectLineCircle[1][0] + ", " + tmpIntersectLineCircle[1][1] + ")"

EndSelect

Function GetIntersectionLineCircle#[][]( pLineStart#[], pLineEnd#[], pCircleCenter#[], pCircleRadius# )

	Local tmpIntersections#[][]
	
	Local p# = pCircleCenter[0], q# = pCircleCenter[1]
	Local m# = (pLineEnd[1]-pLineStart[1])/(pLineEnd[0]-pLineStart[0])
	Local r# = pCircleRadius
	Local t# = pLineEnd[1]- (m*pLineEnd[0])
	Local s# = t-q
	
	Local a# = m^2 + 1, b# = (2*m*s) - (2*p), c# = s^2 + p^2 - (r^2)
	
	Local bsqminfourac# = b^2-4*a*c
	
	If bsqminfourac > 0 Then
		
		Local x1# = ((-b)+Sqr(bsqminfourac))/(2*a)
		Local x2# = ((-b)-Sqr(bsqminfourac))/(2*a)
		
		tmpIntersections = [[x1,(m*x1)+t],[x2,(m*x2)+t]]
		
	ElseIf bsqminfourac = 0 Then
		
		tmpIntersections = [[(-b)/(2*a),(-b*m)/(2*a)+t]]
		
	EndIf
	
	Return tmpIntersections

EndFunction

I've added a timer, so you can see how fast it is... On my Intel Core 2 Duo 2.00Ghz, it takes approx 0.002ms to find the two points of intersection!

Who say's high school maths doesn't come in handy?

thanks guys!

@SebHoll wow!

I've added this to the code archives in case anybody else needs to use it.

@SebHoll

I have tried the code, but I think there is something that doesn't work with the recognition of the collision...
try this code...

thanks

SuperStrict

Local tmpIntersectLineCircle#[][]

Graphics 640, 480, 0

Local mx:Float, my: Float
While Not KeyHit(key_escape)
	Cls
		SetColor(50, 200, 100)
		DrawCircle(320, 240, 40)
		mx = MouseX()
		my = MouseY()
		SetColor(50, 70, 222)
		DrawLine(0,0, mx, my)
		tmpIntersectLineCircle = GetIntersectionLineCircle( [0.0,0.0], [mx, my], [320.0, 240.0], 40.0 )
		If tmpIntersectLineCircle.length = 1			
			SetColor(255, 0,0)
			DrawCircle(tmpIntersectLineCircle[0][0], tmpIntersectLineCircle[0][1], 4)
		EndIf
		If tmpIntersectLineCircle.length = 2			
			SetColor(255,50,30)
			DrawText "COLLISION", 290, 20
			SetColor(255, 0,0)
			DrawCircle(tmpIntersectLineCircle[1][0], tmpIntersectLineCircle[1][1], 4)
			DrawCircle(tmpIntersectLineCircle[0][0], tmpIntersectLineCircle[0][1], 4)
		EndIf
	
	Flip 0
Wend

Function DrawCircle(xCentre:Float, yCentre:Float, Radius:Float) 
	DrawOval(xCentre - (Radius), yCentre - (Radius), Radius * 2, Radius * 2) 
End Function

Function GetIntersectionLineCircle#[][]( pLineStart#[], pLineEnd#[], pCircleCenter#[], pCircleRadius# )

	Local tmpIntersections#[][]
	
	Local p# = pCircleCenter[0], q# = pCircleCenter[1]
	Local m# = (pLineEnd[1]-pLineStart[1])/(pLineEnd[0]-pLineStart[0])
	Local r# = pCircleRadius
	Local t# = pLineEnd[1]- (m*pLineEnd[0])
	Local s# = t-q
	
	Local a# = m*m + 1, b# = (2*m*s) - (2*p), c# = s^2 + p^2 - (r^2)
	
	Local bsqminfourac# = b*b-4*a*c
	
	If bsqminfourac > 0 Then
		
		bsqminfourac = Sqr(bsqminfourac)
		
		Local x1# = ((-b)+bsqminfourac)/(2*a)
		Local x2# = ((-b)-bsqminfourac)/(2*a)
		
		tmpIntersections = [[x1,(m*x1)+t],[x2,(m*x2)+t]]
		
	ElseIf bsqminfourac = 0 Then
		
		tmpIntersections = [[(-b)/(2*a),(-b*m)/(2*a)+t]]
		
	EndIf
	
	Return tmpIntersections

EndFunction