[bmx] GetIntersectionLineCircle() by SebHoll [ 1+ years ago ]

[BlitzBot]

Title : GetIntersectionLineCircle()
Author : SebHoll
Posted : 1+ years ago

Description : 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.

Code :

Code: BlitzMax

1. SuperStrict
2.  
3. Local tmpIntersectLineCircle#[][]
4. Local mx:Float, my: Float, mode:Int = 2
5.  
6. Graphics 640, 480, 0
7.  
8. While Not (KeyHit(key_escape) Or AppTerminate())
9.        
10.         Cls
11.                
12.                 SetColor(50, 200, 100);DrawCircle(320, 240, 40)
13.                 mx = MouseX();my = MouseY()
14.                
15.                 SetColor(50, 70, 222);DrawLine(0,0, mx, my)
16.                
17.                 SetColor(255,50,30)
18.                 DrawText "No. of Collisions: " + tmpIntersectLineCircle.length, (GraphicsWidth()-TextWidth("No. of Collisions:  "))/2, 20
19.                
20.                 If (mode=1) Then
21.                         DrawText("Using GetIntersectionLineCircle()",(GraphicsWidth()-TextWidth("Using GetIntersectionLineCircle()"))/2,5)
22.                         tmpIntersectLineCircle = GetIntersectionLineCircle( [0.0,0.0], [mx, my], [320.0, 240.0], 40.0 )
23.                 ElseIf (mode=2) Then
24.                         DrawText("Using GetIntersectionLineCircle2()",(GraphicsWidth()-TextWidth("Using GetIntersectionLineCircle2()"))/2,5)
25.                         tmpIntersectLineCircle = GetIntersectionLineCircle2( [0.0,0.0], [mx, my], [320.0, 240.0], 40.0 )
26.                 EndIf
27.                
28.                 SetColor(255, 0,0)
29.                
30.                 For Local tmpIntersectionPoint#[] = EachIn tmpIntersectLineCircle      
31.                         DrawCircle(tmpIntersectionPoint[0], tmpIntersectionPoint[1], 4)
32.                 Next
33.                
34.                 SetColor(255,255,255)
35.                 DrawText("[F1] Use GetIntersectionLineCircle()", GraphicsWidth()-TextWidth("[F1] Use GetIntersectionLineCircle()"),GraphicsHeight()-(TextHeight("A")*2))
36.                 DrawText("[F2] Use GetIntersectionLineCircle2()", GraphicsWidth()-TextWidth("[F2] Use GetIntersectionLineCircle2()"),GraphicsHeight()-TextHeight("A"))
37.                
38.                 If KeyHit(KEY_F1) Then mode = 1
39.                 If KeyHit(KEY_F2) Then mode = 2
40.                
41.         Flip 1
42.        
43. Wend
44.  
45. Function GetIntersectionLineCircle#[][]( pLinePoint1#[], pLinePoint2#[], pCircleCenter#[], pCircleRadius# )
46.  
47.         Local tmpIntersections#[][]
48.        
49.         Local p# = pCircleCenter[0], q# = pCircleCenter[1]
50.         Local m# = (pLinePoint2[1]-pLinePoint1[1])/(pLinePoint2[0]-pLinePoint1[0])
51.         Local r# = pCircleRadius
52.         Local t# = pLinePoint2[1]- (m*pLinePoint2[0])
53.         Local s# = t-q
54.        
55.         Local a# = m*m + 1, b# = (2*m*s) - (2*p), c# = (s*s) + (p*p) - (r*r)
56.        
57.         Local bsqminfourac# = b*b-4*a*c
58.        
59.         If bsqminfourac > 0 Then
60.                
61.                 bsqminfourac = Sqr(bsqminfourac)
62.                
63.                 Local x1# = ((-b)+bsqminfourac)/(2*a)
64.                 Local x2# = ((-b)-bsqminfourac)/(2*a)
65.                
66.                 tmpIntersections = [[x1,(m*x1)+t],[x2,(m*x2)+t]]
67.                
68.         ElseIf bsqminfourac = 0 Then
69.                
70.                 tmpIntersections = [[(-b)/(2*a),(-b*m)/(2*a)+t]]
71.                
72.         EndIf
73.        
74.         Return tmpIntersections
75.  
76. EndFunction
77.  
78. Function GetIntersectionLineCircle2#[][]( pLineStart#[], pLineEnd#[], pCircleCenter#[], pCircleRadius# )
79.        
80.         Local tmpResult#[][]
81.         Local tmpIntersectLineCircle#[][] = GetIntersectionLineCircle( pLineStart, pLineEnd, pCircleCenter, pCircleRadius )
82.        
83.         Local minX# = Min(pLineStart[0],pLineEnd[0]), maxX# = Max(pLineStart[0],pLineEnd[0])
84.         Local minY# = Min(pLineStart[1],pLineEnd[1]), maxY# = Max(pLineStart[1],pLineEnd[1])
85.        
86.         For Local tmpIntersectionPoint#[] = EachIn tmpIntersectLineCircle
87.                
88.                 If tmpIntersectionPoint[0] < maxX And tmpIntersectionPoint[0] > minX And ..
89.                         tmpIntersectionPoint[1] < maxY And tmpIntersectionPoint[1] > minY Then
90.                        
91.                         tmpResult = tmpResult + [tmpIntersectionPoint]
92.                        
93.                 EndIf
94.        
95.         Next
96.        
97.         Return tmpResult
98.        
99. EndFunction
100.  
101. Function DrawCircle(xCentre:Float, yCentre:Float, Radius:Float)
102.         DrawOval(xCentre - (Radius), yCentre - (Radius), Radius * 2, Radius * 2)
103. EndFunction

Comments :


big10p(Posted 1+ years ago)

 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.


SebHoll(Posted 1+ years ago)

 <div class="quote"> Does this only report intersections with the circle circumference? I mean, if the line is entirely contained inside the circle, is an intersection reported? </div>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.<div class="quote"> 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.  </div>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!


big10p(Posted 1+ years ago)

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


SebHoll(Posted 1+ years ago)

 <div class="quote"> Ah, OK. Not quite what I'm looking for. Nevermind. </div>You could still use this function, but you would need to process the results accordingly:

Code: [Select]

SuperStrict

For Local tmpIntersection#[] = EachIn big10psFunction( [0.0,0.0], [1.0,1.0], [0.0,0.0],25 )

Print "Intersection at (" + tmpIntersection[0] + ", " + tmpIntersection[1] + ")"

Next

Function big10psFunction#[][]( 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 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
Notice, how no intersection are now reported as the points are contained within the circle.


big10p(Posted 1+ years ago)

 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.


GregBUG(Posted 1+ years ago)

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

Code: [Select]

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





SebHoll(Posted 1+ years ago)

 <div class="quote"> @SebHollI have tried the code, but I think there is something that doesn't work with the recognition of the collision...try this code... </div>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.

Code: [Select]

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 = big10psFunction( [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 big10psFunction#[][]( 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 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

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.


GregBUG(Posted 1+ years ago)

 ops... thanks SebHollBig10ps solved my problems...thanks again SebHoll


SebHoll(Posted 1+ years ago)

 <div class="quote"> thanks SebHollBig10ps solved my problems...thanks again SebHoll </div>No probs! Would you mind if I changed the original code above to your demo as it demonstrates the function a lot better?


GregBUG(Posted 1+ years ago)

 no probs! thanks SebHoll!


SebHoll(Posted 1+ years ago)

 <div class="quote"> no probs! thanks SebHoll!  </div>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 Great(Posted 1+ years ago)

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


spacerat(Posted 1+ years ago)

 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 Great(Posted 1+ years ago)

 <div class="quote"> 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.  </div>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.


SpectreNectar(Posted 1+ years ago)

 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:

Code: [Select]

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

EndFunctionHaven't fully tested it [/i]