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] |