[bb] BMax - Accurate 2D Line Circle Intersection by col [ 1+ years ago ]

[BlitzBot]

Title : BMax - Accurate 2D Line Circle Intersection
Author : col
Posted : 1+ years ago

Description : This code gives an accurate result of a 2D Line intersecting a 2D circle.

The code uses a simple type 'TVector2' for holding a 2D coord repesented as X and Y.

Parameters are:-
1. The origin of the line as a TVector2 type.
2. The direction of the line as a TVector2 type. Easily calculated as the endpoint coords of the line minus the origin coords.
3. The center of the 2D circle that you want to test for the line to intersect with.
4. The radius of the circle that you want to test for the line to intersect with.
5. A 2 component float array that can be used to retrieve the parametric intersections of the line. Remember that the line can intersect as it enters and leaves the circle giving 2 points of intersection. Parametric lines are represented with the start point being 0 and the endpoint being 1. Halfway along the line would be a value of 0.5
6. An array of 2 TVectors that will hold the coords of the 2 intersection points.
7. An array of 2 TVectors that will hold the 'Normal' vector at the intersection points. The 'Normal' vector is the vector that is at right angles to the point on the sphere of intersection.

There is a little example usage demo to show how to use it.
Use W,S,A,D and the mouse to move line around on onscrren.

This is public domain so use and abuse.

Code :

Code: BlitzBasic

1. Strict
2.  
3. Type TVector2
4.         Field X#,Y#
5. EndType
6.  
7. Global Origin:TVector2 = New TVector2
8. Global Dir:TVector2 = New TVector2
9. Global CircleCenter:TVector2 = New TVector2
10. Global CircleRadius#
11. Global PPoint#[2]               'Parametric point of intersction of the line
12. Global IPoint:TVector2[] = New TVector2[2] 'Intersection points
13. Global NPoint:TVector2[] = New TVector2[2] 'Normal at intersection points
14.  
15. IPoint[0] = New TVector2 ; IPoint[1] = New TVector2
16. NPoint[0] = New TVector2 ; NPoint[1] = New TVector2
17.  
18. CircleCenter.X = 400 ; CircleCenter.Y = 300
19. CircleRadius = 100
20.  
21. Origin.X = 400 ; Origin.Y = 40
22.  
23. Graphics 800,600
24. While Not KeyDown(KEY_ESCAPE) And Not AppTerminate()
25.         Cls
26.        
27.         Dir.X = MouseX() - Origin.X
28.         Dir.Y = MouseY() - Origin.Y
29.        
30.         If KeyDown(KEY_W) And Origin.Y > 0 Origin.Y :- 2
31.         If KeyDown(KEY_S) And Origin.Y < 800 Origin.Y :+ 2
32.         If KeyDown(KEY_A) And Origin.X > 0 Origin.X :- 2
33.         If KeyDown(KEY_D) And Origin.X < 600 Origin.X :+ 2
34.        
35.         SetColor 0,255,0
36.         DrawOval CircleCenter.X - CircleRadius,CircleCenter.Y - CircleRadius,CircleRadius*2,CircleRadius*2
37.        
38.         If IntersectLineCircle(Origin,Dir,CircleCenter,CircleRadius,PPoint,IPoint,NPoint)
39.                 If PPoint[0] > 0.0 And PPoint[0] < 1.0
40.                         SetColor 255,0,0
41.                         DrawOval IPoint[0].X-4,IPoint[0].Y-4,8,8
42.                        
43.                         SetColor 255,255,0
44.                         DrawLine IPoint[0].X,IPoint[0].Y,IPoint[0].X+(NPoint[0].X *40),IPoint[0].Y+(NPoint[0].Y *40)
45.                 EndIf
46.                 If PPoint[1] > 0.0 And PPoint[1] < 1.0
47.                         SetColor 255,0,0
48.                         DrawOval IPoint[1].X-4,IPoint[1].Y-4,8,8
49.  
50.                         SetColor 255,255,0
51.                         DrawLine IPoint[1].X,IPoint[1].Y,IPoint[1].X+(NPoint[1].X *40),IPoint[1].Y+(NPoint[1].Y *40)
52.                 EndIf
53.         EndIf
54.        
55.         SetColor 255,255,255
56.         DrawOval Origin.X-5,Origin.Y-5,10,10
57.         DrawOval MouseX()-5,MouseY()-5,10,10
58.         DrawLine Origin.X,Origin.Y,MouseX(),MouseY()
59.  
60.         Flip
61. Wend
62. End
63.  
64. Function IntersectLineCircle(O:TVector2,D:TVector2,C:TVector2,Radius#,T#[] Var,Intersect:TVector2[] Var,Normal:TVector2[] Var)
65.         Local Diff:TVector2 = New TVector2
66.         Diff.X = O.X - C.X
67.         Diff.Y = O.Y - C.Y
68.        
69.         Local A# = (Dir.X * Dir.X) + (Dir.Y * Dir.Y)
70.         Local B# = (Diff.X * Dir.X) + (Diff.Y * Dir.Y)
71.         Local Coeff# = (Diff.X * Diff.X) + (Diff.Y * Diff.Y) - (Radius*Radius)
72.        
73.         Local Intersecting# = B * B - A * Coeff
74.         If Intersecting < 0.0 Return False
75.        
76.         Local sqrIntersecting = Sqr(Intersecting)
77.         Local InvA# = 1.0 / A
78.         T[0] = (-B - sqrIntersecting ) * InvA
79.         T[1] = (-B + sqrIntersecting ) * InvA
80.        
81.         Local invRadius# = 1.0 / Radius
82.        
83.         Intersect[0].X = O.X + T[0] * D.X
84.         Intersect[0].Y = O.Y + T[0] * D.Y
85.         Intersect[1].X = O.X + T[1] * D.X
86.         Intersect[1].Y = O.Y + T[1] * D.Y
87.        
88.         Normal[0].X = (Intersect[0].X - C.X) * invRadius
89.         Normal[0].Y = (Intersect[0].Y - C.Y) * invRadius
90.         Normal[1].X = (Intersect[1].X - C.X) * invRadius
91.         Normal[1].Y = (Intersect[1].Y - C.Y) * invRadius
92.         Return True
93. EndFunction

Comments : none...