Circle line-segment collision detection algorithm?
algorithm, collision-detection, geometry, line, math
Solution
Taking
- E is the starting point of the ray,
- L is the end point of the ray,
- C is the center of sphere you're testing against
- r is the radius of that sphere
Compute: d = L - E ( Direction vector of ray, from start to end ) f = E - C ( Vector from center sphere to ray start )
Then the intersection is found by.. Plugging: P = E + t * d This is a parametric equation: Px = Ex + tdx Py = Ey + tdy into (x - h)2 + (y - k)2 = r2 (h,k) = center of circle.
Note: We've simplified the problem to 2D here, the solution we get applies also in 3D
to get:
- Expand x2 - 2xh + h2 + y2 - 2yk + k2 - r2 = 0
- Plug x = ex + tdx y = ey + tdy ( ex + tdx )2 - 2( ex + tdx )h + h2 + ( ey + tdy )2 - 2( ey + tdy )k + k2 - r2 = 0
- Explode ex2 + 2extdx + t2dx2 - 2exh - 2tdxh + h2 + ey2 + 2eytdy + t2dy2 - 2eyk - 2tdyk + k2 - r2 = 0
- Group t2( dx2 + dy2 ) + 2t( exdx + eydy - dxh - dyk ) + ex2 + ey2 - 2exh - 2eyk + h2 + k2 - r2 = 0
- Finally, t2( d · d ) + 2t( e · d - d · c ) + e · e - 2( e · c ) + c · c - r2 = 0 Where d is the vector d and · is the dot product.
- And then, t2( d · d ) + 2t( d · ( e - c ) ) + ( e - c ) · ( e - c ) - r2 = 0
- Letting f = e - c t2( d · d ) + 2t( d · f ) + f · f - r2 = 0
So we get: t2 * (d · d) + 2t*( f · d ) + ( f · f - r2 ) = 0
So solving the quadratic equation:
float a = d.Dot( d ) ;
float b = 2*f.Dot( d ) ;
float c = f.Dot( f ) - r*r ;
float discriminant = b*b-4*a*c;
if( discriminant < 0 )
{
// no intersection
}
else
{
// ray didn't totally miss sphere,
// so there is a solution to
// the equation.
discriminant = sqrt( discriminant );
// either solution may be on or off the ray so need to test both
// t1 is always the smaller value, because BOTH discriminant and
// a are nonnegative.
float t1 = (-b - discriminant)/(2*a);
float t2 = (-b + discriminant)/(2*a);
// 3x HIT cases:
// -o-> --|--> | | --|->
// Impale(t1 hit,t2 hit), Poke(t1 hit,t2>1), ExitWound(t1<0, t2 hit),
// 3x MISS cases:
// -> o o -> | -> |
// FallShort (t1>1,t2>1), Past (t1<0,t2<0), CompletelyInside(t1<0, t2>1)
if( t1 >= 0 && t1 <= 1 )
{
// t1 is the intersection, and it's closer than t2
// (since t1 uses -b - discriminant)
// Impale, Poke
return true ;
}
// here t1 didn't intersect so we are either started
// inside the sphere or completely past it
if( t2 >= 0 && t2 <= 1 )
{
// ExitWound
return true ;
}
// no intn: FallShort, Past, CompletelyInside
return false ;
}
Problem
I have a line from A to B and a circle positioned at C with the radius R. What is a good algorithm to use to check whether the line intersects the circle? And at what coordinate along the circles edge it occurred?