to test for the intersection of a circle and a line segment, the easiest approach is through linear algebra, and you can approach it in two ways.
the first approach is to find the closest point on the line segment to the circle and test distances.
the second is to test directly for an intersection between the two objects:
for both ill use the following variables. A is the start of line segment, B the end, C the circle centre, and R the radius with V = B-A
----------------------------------------
-----------------
the first approach would go something like this:
first with a bit of intuition you can think of the closest point of the infinite line defined through A and B to C as being the point on the line at which the vector from this point to C is perpendicular to the line direction (i.e. the circle lies on a line perpendicular to the line segment)
i.e. the closest point is the solution to the equation:
(A + tV - C)%u25CFV = 0
which re-arranging gives:
(A-C)%u25CFV + tV%u25CFV = 0
t = (C-A)%u25CFV / |V|²
in terms of explicit 'x' and 'y' you have:
t = (Vx(Cx-Ax) + Vy(Cy-Ay))/(Vx² + Vy²)
since we only want to test against the line segment AB we have to cap t to the range 0-1 (so that if the closest point is any further than B, it uses B, and if its any further than A it uses A) i.e. if t is less than 0, equate it to 0, if its more than 1, equate it to 1.
the point to test with the circle is then A + tV, and the distance between this point and C is:
|A + tV - C|
for optimization, you needn't calculate the length of this vector, only its square length compared to the square of the circles radius. i.e.
if( |A + tV - C|² < R² ) // colliding
as an example code you might have something like:
function collideLineSegCircle(a:Point, b:Point, c:Point, r:Number):Boolean {
var vx:Number = b.x-a.x;
var vy:Number = b.y-a.y;
var t:Number = (vx*(c.x-a.x) + v.y(c.y-a.y))/(vx*vx+vy*vy);
if(t<0) t = 0;
if(t>1) t = 1;
var px:Number = a.x+vx*t-c.x;
var py:Number = a.y+vy*t-c.y;
return (px*px+py*py < r*r);
}
----------------------------------------
-----------------
the second method would go something like this:
the intersection of the line defined by AB and the circle is the solution to the quadratic equation derived from :
|A + tV - C|² = R²
|(A-C)+tV|² = R²
|A-C|² + t²|V|² + 2t(A-C)%u25CFV - R² = 0 // a quadratic equation in 't'
the real solution set of this equation can be used to calculate whether either intersection (if they exist in the reals) is on the line segment or not.
ultra-pseudo code :
calculate coeffecients of quadratic
calculate descrimininant, if its less than 0 end here.
calculate the 2 values for t, if either one of them is in the range 0-1, the line segment and circle intersect (collide)
as an example code you might have something like:
function collideLineSegCircle(a:Point, b:Point, c:Point, r:Number):Boolean {
var vx:Number = b.x-a.x;
var vy:Number = b.y-a.y;
var dx:Number = a.x-c.x;
var dy:Number = a.y-c.y;
var c0:Number = vx*vx+vy*vy;
var c1:Number = 2*(vx*dx+vy*dy);
var c2:Number = dx*dx+dy*dy-r*r;
var d:Number = c1*c1-4*c0*c2;
if(d<=0) return false;
d = Math.sqrt(d);
c0 = 1/(2*c0);
var t:Number = (d-c1)*c0;
if(t>=0 || t<=1) return true;
t = (-d-c1)*c0;
return (t>=0||t<=1);
}
from examination of the code alone, it can be inferred that although the second method seems more complicated, it should execute faster.
