| Line-circle collision |
| VBBR | I'm in the proccess of designing a good and general method for 2D collision detection (maybe I will convert it to full 3D later)
Well, the thing I want to know is very simple really:
- How to know if a circle and a (finite) line are colliding? I don't want anything sophisticated, just a TRUE or FALSE value. |
| Sr. Guapo | I know you can mathematically find the distance between a point (center of circle) and a line, though I don't know the formula/algorithm. You could then compare that value with the radius of the circle to determine if they intersect. It seems like a pretty simple (and fast) method, assming the distance calculation isn't too complicted. |
| VBBR | Yeah I know how to do the distance calculation. Also I saw somewhere here that a circle inersects a line either if one of the two points of the line are inside the circle, or a radius that is perpendicular to the line is colliding with it. |
| Sr. Guapo | OK, I looked up the formula. Givin a 2D line in the form Ax+By+C=0, and a 2D point (r, s), plug it into the equation:
[code]
distance = abs(A * r + B * s + C) / sqrt(A * A + B * B)
[/code]
Looks a little sloooooooooooow, so use sparingly... |
| VBBR | Thanks for the formula. I will try to find a workaround for the square root. |
| VBBR | Oh yeah, and this may sound stupid, but how do I get the A, B and C values? |
| Sr. Guapo | Assuming you have the slope and y-intercept, just solve for 0... Here we go:
y = mx + B (where m is the slope and B is the y-intercept)
mx - y + B = 0
therefore:
A = m
B = -1
C = B |
| game_maker | Hi
same idea :
1) find the point of intersection P
2) find the distance d (center - P)
3) compare if d <= radius
hmmm the problem is how to slove step 1
to find point of intersection (x,y) [2 unknowns] you need [2 equations] satisfy your point (point lies on it)
A) first equation is equation of line [:)] very simple (y=mx+b)
B) second equation is :
assume P2 ,P1 point on the line ; C as the Circle Center ; P is the point of intersection
V1 : vector <C-P>
V2 : vector <P2-P1>
if V2 is perpendicular to V1 then it's the shortest distance
Ie V2 (dot product) V1 = 0
V2.V1 = 0
and
y = mx + b
hence ,,, you got 2 equation ; solve it to find (x,y) point of intersection
regards [:)] |
| game_maker | BTW : if you want BOOLEAN resault then don't calcualte the distance if it is containing sqaure root
i.e. instead of
[code]
resault = r >= (abs(n)/sqr(m))
[/code]
use
[code]
resault = (r*r) >= ((n*n)/m)
[/code]
regards [:)] |
| VBBR | See, the problem is, I don't have a clue about what how the equation of line works. I only know how to represent a line by using the start and end points. |
| Sion | A line is defined by the following equation:
y = ax + b
Where
a is the slope of the line. This is defined by the value that the line moves up on the y-axis when moving 1 to the right on the x-axis. A 45 degree line would when have an a-value of 1 (1y for each 1x) and a 22.5 degree line would have (0.5y for each 1x) and thus moving up a half y-value for each unit moved on the x-axis.
b is the starting position on the y-axis. Changing this value will displace the line along the y-axis. |
| VBBR | Now for the stupiest question... how are the x and y values used... and how do I use this to define a finite line? |
| game_maker | Hi
Ok I wrote this code/method to solve our problem
[code]
Option Explicit
Private Type Vector2D
X As Single
Y As Single
End Type
Const R = 50
Dim BColl As Boolean
Dim S As String
Dim P1 As Vector2D, P2 As Vector2D, P3 As Vector2D
Dim P As Vector2D
Dim M As Single
Private Sub Form_Load()
Me.Width = 10000: Me.Height = 8000: Me.AutoRedraw = True: Me.ScaleMode = 3
P1.X = 250: P1.Y = 250
P2.X = 400: P2.Y = 300
End Sub
Private Sub Form_MouseMove(Button As Integer, Shift As Integer, X As Single, Y As Single)
' init
Cls
BColl = False
S = "P is out the line"
P3.X = X: P3.Y = Y
Me.Circle (P3.X, P3.Y), R
Line (P1.X, P1.Y)-(P2.X, P2.Y)
' find
M = (P2.Y - P1.Y) * IIf(P2.X = P1.X, 0, 1 / (P2.X - P1.X))
P.Y = (M * (M * P3.Y + P3.X - P2.X) + P2.Y) / (1 + M * M)
P.X = P3.X + M * (P3.Y - P.Y)
If (P.X >= P1.X And P.X <= P2.X) Or (P.X < P1.X And P.X > P2.X) Then
S = "P is on the Line"
If R * R >= GetSLength(P3, P) Then BColl = True
ElseIf PointInCircle(P1, P3, R) Then BColl = True
ElseIf PointInCircle(P2, P3, R) Then BColl = True
End If
If BColl Then Me.BackColor = vbRed Else Me.BackColor = vbWhite
Me.Caption = S
' draw
Me.Circle (P.X, P.Y), 5
Me.Line (P3.X, P3.Y)-(P.X, P.Y)
End Sub
Private Function PointInCircle(P As Vector2D, C As Vector2D, R As Single) As Boolean
PointInCircle = R * R >= GetSLength(C, P)
End Function
Private Function GetSLength(V1 As Vector2D, V2 As Vector2D) As Single
GetSLength = (V2.X - V1.X) * (V2.X - V1.X) + (V2.Y - V1.Y) * (V2.Y - V1.Y)
End Function
[/code]
regards [:)] |
| Sion | Nice example game_maker. It is a very good visual presentation of the problem and solution. |
| VBBR | Thanks a lot! Now developing my revolutionary collision code... [:D] |