NewsForumsCodeLogsGallerySpecsSearch

Code archives/Algorithms/GetIntersectionLineCircle()

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

Download source code

GetIntersectionLineCircle() by SebHoll2007
These function will return the points of intersection (if there are any) for any line and any circle. Please note that all values passed to and from the function are floating point.

GetIntersectionLineCircle(): Returns points of intersection for any line which passes through the points specified.

GetIntersectionLineCircle2(): Returns points of interesection for a line that starts and ends at the points given. Note: This function requires GetIntersectionLineCircle() in order to run.

The parameters are as follows:

pLineStart#[] - Any point on the line that's being tested, e.g. [3.0,5.0].
pLineEnd#[] - Any other point on the line that's being tested, e.g. [1.0, 3.0]
pCircleCenter#[] - The center of the circle that's being tested, e.g. [1.5, 3.5]
pCircleRadius# - The radius of the circle that's being tested, e.g. 5.2 .

It's worth noting that the two points passed must be different, otherwise there could be an infinite number of lines running through them.

Credit goes to GregBUG for the sample code that shows these functions working. 
SuperStrict

Local tmpIntersectLineCircle#[][]
Local mx:Float, my: Float, mode:Int = 2

Graphics 640, 480, 0

While Not (KeyHit(key_escape) Or AppTerminate())
	
	Cls
		
		SetColor(50, 200, 100);DrawCircle(320, 240, 40)
		mx = MouseX();my = MouseY()
		
		SetColor(50, 70, 222);DrawLine(0,0, mx, my)
		
		SetColor(255,50,30)
		DrawText "No. of Collisions: " + tmpIntersectLineCircle.length, (GraphicsWidth()-TextWidth("No. of Collisions:  "))/2, 20
		
		If (mode=1) Then
			DrawText("Using GetIntersectionLineCircle()",(GraphicsWidth()-TextWidth("Using GetIntersectionLineCircle()"))/2,5)
			tmpIntersectLineCircle = GetIntersectionLineCircle( [0.0,0.0], [mx, my], [320.0, 240.0], 40.0 )
		ElseIf (mode=2) Then
			DrawText("Using GetIntersectionLineCircle2()",(GraphicsWidth()-TextWidth("Using GetIntersectionLineCircle2()"))/2,5)
			tmpIntersectLineCircle = GetIntersectionLineCircle2( [0.0,0.0], [mx, my], [320.0, 240.0], 40.0 )
		EndIf
		
		SetColor(255, 0,0)
		
		For Local tmpIntersectionPoint#[] = EachIn tmpIntersectLineCircle	
			DrawCircle(tmpIntersectionPoint[0], tmpIntersectionPoint[1], 4)
		Next
		
		SetColor(255,255,255)
		DrawText("[F1] Use GetIntersectionLineCircle()", GraphicsWidth()-TextWidth("[F1] Use GetIntersectionLineCircle()"),GraphicsHeight()-(TextHeight("A")*2))
		DrawText("[F2] Use GetIntersectionLineCircle2()", GraphicsWidth()-TextWidth("[F2] Use GetIntersectionLineCircle2()"),GraphicsHeight()-TextHeight("A"))
		
		If KeyHit(KEY_F1) Then mode = 1
		If KeyHit(KEY_F2) Then mode = 2
		
	Flip 1
	
Wend

Function GetIntersectionLineCircle#[][]( pLinePoint1#[], pLinePoint2#[], pCircleCenter#[], pCircleRadius# )

	Local tmpIntersections#[][]
	
	Local p# = pCircleCenter[0], q# = pCircleCenter[1]
	Local m# = (pLinePoint2[1]-pLinePoint1[1])/(pLinePoint2[0]-pLinePoint1[0])
	Local r# = pCircleRadius
	Local t# = pLinePoint2[1]- (m*pLinePoint2[0])
	Local s# = t-q
	
	Local a# = m*m + 1, b# = (2*m*s) - (2*p), c# = (s*s) + (p*p) - (r*r)
	
	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

Function GetIntersectionLineCircle2#[][]( pLineStart#[], pLineEnd#[], pCircleCenter#[], pCircleRadius# )
	
	Local tmpResult#[][]
	Local tmpIntersectLineCircle#[][] = GetIntersectionLineCircle( pLineStart, pLineEnd, pCircleCenter, pCircleRadius )
	
	Local minX# = Min(pLineStart[0],pLineEnd[0]), maxX# = Max(pLineStart[0],pLineEnd[0])
	Local minY# = Min(pLineStart[1],pLineEnd[1]), maxY# = Max(pLineStart[1],pLineEnd[1])
	
	For Local tmpIntersectionPoint#[] = EachIn tmpIntersectLineCircle
		
		If tmpIntersectionPoint[0] < maxX And tmpIntersectionPoint[0] > minX And ..
			tmpIntersectionPoint[1] < maxY And tmpIntersectionPoint[1] > minY Then
			
			tmpResult = tmpResult + [tmpIntersectionPoint]
			
		EndIf
	
	Next
	
	Return tmpResult
	
EndFunction

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

Comments

big10p2007
Does this only report intersections with the circle circumference? I mean, if the line is entirely contained inside the circle, is an intersection reported?

I can't test as I don't have bmax but might try converting it to blitz3D if it does exactly what I need.

BTW, you can speed the code up a bit by doing m*m etc. instead of m^2. Also, you're calling Sqr twice on the same value.


SebHoll2007
Does this only report intersections with the circle circumference? I mean, if the line is entirely contained inside the circle, is an intersection reported?

Well, what happens is that the two co-ordinates you provide are converted into a straight line that spans all possible values. If the circle and the line intersect at any point (even if the two points you give are inside the circle), then it will find the points of intersection as if that line carried on forever.

BTW, you can speed the code up a bit by doing m*m etc. instead of m^2. Also, you're calling Sqr twice on the same value.

The function is quite fast (it takes about 0.002ms to complete on my computer), but that's no excuse for sloppy programming. I'll change it!


big10p2007
Ah, OK. Not quite what I'm looking for. Nevermind. :)


SebHoll2007
Ah, OK. Not quite what I'm looking for. Nevermind. :)

You could still use this function, but you would need to process the results accordingly:



Notice, how no intersection are now reported as the points are contained within the circle.


big10p2007
Thanks. During the site down time, I managed to find a function on the net that I modified to do what I want. Actually looks like it works in basically the same way as yours.


GregBUG2007
@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



SebHoll2007
@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...

Nice example by the way - however, it works fine for me! Two circles show on the outside of the circle where the line will pass through as if both sides went off to infinity (i.e. it will almost always show two points of intersections, unless you can get the exact tangent).

Are you looking for something like Big10p, where if the line terminates inside the circle, then only one point of intersection is returned, i.e.



If this doesn't answer you question, can you please describe exactly what problem you are having and I'll try my best to help.


GregBUG2007
ops...

thanks SebHoll

Big10ps solved my problems...

thanks again SebHoll


SebHoll2007
thanks SebHoll

Big10ps solved my problems...

thanks again SebHoll

No probs! Would you mind if I changed the original code above to your demo as it demonstrates the function a lot better?


GregBUG2007
no probs! thanks SebHoll!


SebHoll2007
no probs! thanks SebHoll!

Thanks, I've tweaked the code so that it can show the two different functions (which I've now named GetIntersectionLineCircle() and GetIntersectionLineCircle2() as the function I wrote for Big10p looks like it will be useful to other people).


Nate the Great2009
thank you everyone who helped with this. This has been the best code I can find for my physics engine!


spacerat2009
Sorry to say, but this code doesn't entirely work: nothing is returned if the line going through the circle is completely horizontal or vertical. For the vertical case, I've pinned it down to the gradient (m) being infinate, and blitz not being able to do calculations with infinity. I'm not sure how to fix it though.


Nate the Great2009
Sorry to say, but this code doesn't entirely work: nothing is returned if the line going through the circle is completely horizontal or vertical. For the vertical case, I've pinned it down to the gradient (m) being infinate, and blitz not being able to do calculations with infinity. I'm not sure how to fix it though.



hmm odd. It works perfectly for my physics engine. (see link in my sig or check out the blitz showcase) Maybe I modified it to work. I remember having a few problems like this but nothing hard to fix.

edit: ok so the code only fails if the line is verticle. It works great for horizontal lines.


SpectreNectar2010
To fix that you'd do a test and swap the x1/x2 and y1/y2 values for the line if it was vertical, like in this old inefficient thing of mine that I converted from the GML language:

Function circle_on_plane%(xx#,yy#,rr#, x1#, y1#, x2#, y2#)
	
	Local intersectx#, intersecty#
	
	Local xdif#, ydif#
	xdif = x2-x1
	ydif = y2-y1
	
	If xdif=0 And ydif=0 Then
		Return False
	EndIf
	
	If xdif<>0 Then
		
		Local a1#,b1#,a2#,b2#
		a1 = ydif/xdif
		b1 = y1-a1*x1
		If a1=0 Then
			intersectx = xx
			intersecty = y1
		Else
			a2 = -1/a1
			b2 = yy-a2*xx
			intersectx = (b2-b1)/(a1-a2)
			intersecty = a1*intersectx+b1
		EndIf
		
		If rr<point_distance(xx,yy,intersectx,intersecty) Then
			Return False
		EndIf
		
	ElseIf ydif<>0 Then
		
		Local a1#,b1#,a2#,b2#
		a1 = xdif/ydif
		b1 = x1-a1*y1
		If a1=0 Then
			intersectx = x1
			intersecty = yy
		Else
			a2 = -1/a1
			b2 = xx-a2*yy
			intersecty = (b2-b1)/(a1-a2)
			intersectx = a1*intersecty+b1
		EndIf
		
		If rr<point_distance(xx,yy,intersectx,intersecty) Then
			Return False
		EndIf
		
	EndIf
	
	If Not (point_distance(xx,yy,x1,y1)>rr And point_distance(xx,yy,x2,y2)>rr) Then
		Return True
	EndIf
	If x1<x2 Then
		If y1<y2 Then
			If (x1>intersectx Or y1>intersecty Or x2<intersectx Or y2<intersecty) Then
				Return False
			EndIf
		Else
			If (x1>intersectx Or y1<intersecty Or x2<intersectx Or y2>intersecty) Then
				Return False
			EndIf
		EndIf
	Else
		If y1<y2 Then
			If (x1<intersectx Or y1>intersecty Or x2>intersectx Or y2<intersecty) Then
				Return False
			EndIf
		Else
			If (x1<intersectx Or y1<intersecty Or x2>intersectx Or y2>intersecty) Then
				Return False
			EndIf
		EndIf
	EndIf
	
	Return True
	
EndFunction


Haven't fully tested it


Code Archives Forum