Line Intersect Circle

BlitzMax Forums/BlitzMax Beginners Area/Line Intersect Circle

GregBUG

(Posted 2007) [#1]

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!

TaskMaster

(Posted 2007) [#2]

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.

Grey Alien

(Posted 2007) [#3]

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

SebHoll

(Posted 2007) [#4]

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?

GregBUG

(Posted 2007) [#5]

thanks guys!

@SebHoll wow!

SebHoll

(Posted 2007) [#6]

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

GregBUG

(Posted 2007) [#7]

@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

Poit	(Posted 2012) [#8]

has anyone gotten this detection working with vertical or near vertical lines? this returns more inaccurate the closer the line is to vertical and nothing at all for a vertical line.

col	(Posted 2012) [#9]

Hiya,

I tried the code and it does suffer from bad vertical intersections. I didn't bother to try fix it as I had this on my h/drive which gives much more information...

If you can't understand how to use it then let me know and I'll help you out.

Move the line with W,S,A,D and the mouse.

Strict

Type TVector2
	Field X#,Y#
EndType

Global Origin:TVector2 = New TVector2
Global Dir:TVector2 = New TVector2
Global CircleCenter:TVector2 = New TVector2
Global CircleRadius#
Global PPoint#[2]		'Parametric point of intersction of the line
Global IPoint:TVector2[] = New TVector2[2] 'Intersection points
Global NPoint:TVector2[] = New TVector2[2] 'Normal at intersection points

IPoint[0] = New TVector2 ; IPoint[1] = New TVector2
NPoint[0] = New TVector2 ; NPoint[1] = New TVector2

CircleCenter.X = 400 ; CircleCenter.Y = 300
CircleRadius = 100

Origin.X = 400 ; Origin.Y = 40

Graphics 800,600
While Not KeyDown(KEY_ESCAPE) And Not AppTerminate()
	Cls
	
	Dir.X = MouseX() - Origin.X
	Dir.Y = MouseY() - Origin.Y
	
	If KeyDown(KEY_W) And Origin.Y > 0 Origin.Y :- 2
	If KeyDown(KEY_S) And Origin.Y < 600 Origin.Y :+ 2
	If KeyDown(KEY_A) And Origin.X > 0 Origin.X :- 2
	If KeyDown(KEY_D) And Origin.X < 800 Origin.X :+ 2
	
	SetColor 0,255,0
	DrawOval CircleCenter.X - CircleRadius,CircleCenter.Y - CircleRadius,CircleRadius*2,CircleRadius*2
	
	If IntersectLineCircle(Origin,Dir,CircleCenter,CircleRadius,PPoint,IPoint,NPoint)
		If PPoint[0] > 0.0 And PPoint[0] < 1.0
			SetColor 255,0,0
			DrawOval IPoint[0].X-4,IPoint[0].Y-4,8,8
			
			SetColor 255,255,0
			DrawLine IPoint[0].X,IPoint[0].Y,IPoint[0].X+(NPoint[0].X *40),IPoint[0].Y+(NPoint[0].Y *40)
		EndIf
		If PPoint[1] > 0.0 And PPoint[1] < 1.0
			SetColor 255,0,0
			DrawOval IPoint[1].X-4,IPoint[1].Y-4,8,8

			SetColor 255,255,0
			DrawLine IPoint[1].X,IPoint[1].Y,IPoint[1].X+(NPoint[1].X *40),IPoint[1].Y+(NPoint[1].Y *40)
		EndIf
	EndIf
	
	SetColor 255,255,255
	DrawOval Origin.X-5,Origin.Y-5,10,10
	DrawOval MouseX()-5,MouseY()-5,10,10
	DrawLine Origin.X,Origin.Y,MouseX(),MouseY()

	Flip
Wend
End

Function IntersectLineCircle(O:TVector2,D:TVector2,C:TVector2,Radius#,T#[],Intersect:TVector2[] Var,Normal:TVector2[] Var)
	Local Diff:TVector2 = New TVector2
	Diff.X = O.X - C.X
	Diff.Y = O.Y - C.Y
	
	Local A# = (Dir.X * Dir.X) + (Dir.Y * Dir.Y)
	Local B# = (Diff.X * Dir.X) + (Diff.Y * Dir.Y)
	Local Coeff# = (Diff.X * Diff.X) + (Diff.Y * Diff.Y) - (Radius*Radius)
	
	Local Intersecting# = B * B - A * Coeff
	If Intersecting < 0.0 Return False
	
	Local sqrIntersecting = Sqr(Intersecting)
	Local InvA# = 1.0 / A
	T[0] = (-B - sqrIntersecting ) * InvA
	T[1] = (-B + sqrIntersecting ) * InvA
	
	Local invRadius# = 1.0 / Radius
	
	Intersect[0].X = O.X + T[0] * D.X
	Intersect[0].Y = O.Y + T[0] * D.Y
	Intersect[1].X = O.X + T[1] * D.X
	Intersect[1].Y = O.Y + T[1] * D.Y
	
	Normal[0].X = (Intersect[0].X - C.X) * invRadius
	Normal[0].Y = (Intersect[0].Y - C.Y) * invRadius
	Normal[1].X = (Intersect[1].X - C.X) * invRadius
	Normal[1].Y = (Intersect[1].Y - C.Y) * invRadius
	Return True
EndFunction

Last edited 2012

Poit	(Posted 2012) [#10]

Hey!

Thanks so much for this, seems to work awesomely!

the command Var makes those input values update globaly? never knew that... o.0

should be simple enough to incorporate. :D

col	(Posted 2012) [#11]

the command Var makes those input values update globaly? never knew that... o.0

Using Var will pass the variable by pointer, or by reference - whatever people choose to call it these days. So altering the value of the variable in the 'called function' will also alter the same variable in the 'calling function'. This can help reduce the use of real Global variables. I dont think you actually need it in this example, as you are passing objects in such as a type or an array as these are passed to a function by reference anyway, but it's there for completeness and understanding when you read the code 6 months later :P

A good use is when you want to return more than one value from the function : bit of a pain as a function can only return one value. Say you have 2 or 3 Local variables in one function that you want altered by another function. Instead of making them Globals, put those variable into the parameters of the function using Var on the end, alter them in the 'called function' and they are also altered in the 'calling code' too.

Poit	(Posted 2012) [#12]

yeah, stuff I should have known for years lol.

thanks again.