Circle line-segment collision detection algorithm?

Question

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?

Answer 1

Taking

1. E is the starting point of the ray,
2. L is the end point of the ray,
3. C is the center of sphere you're testing against
4. 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:
P_x = E_x + td_x
P_y = E_y + td_y
into
(x - h)² + (y - k)² = r²
(h,k) = center of circle.

Note: We've simplified the problem to 2D here, the solution we get applies also in 3D

to get:

1. Expand x² - 2xh + h² + y² - 2yk + k² - r² = 0
2. Plug x = e_x + td_x
   y = e_y + td_y
   ( e_x + td_x )² - 2( e_x + td_x )h + h² + ( e_y + td_y )² - 2( e_y + td_y )k + k² - r² = 0
3. Explode e_x² + 2e_xtd_x + t²d_x² - 2e_xh - 2td_xh + h² + e_y² + 2e_ytd_y + t²d_y² - 2e_yk - 2td_yk + k² - r² = 0
4. Group t²( d_x² + d_y² ) + 2t( e_xd_x + e_yd_y - d_xh - d_yk ) + e_x² + e_y² - 2e_xh - 2e_yk + h² + k² - r² = 0
5. Finally, t²( d · d ) + 2t( e · d - d · c ) + e · e - 2( e · c ) + c · c - r² = 0
   Where d is the vector d and · is the dot product.
6. And then, t²( d · d ) + 2t( d · ( e - c ) ) + ( e - c ) · ( e - c ) - r² = 0
7. Letting f = e - c t²( d · d ) + 2t( d · f ) + f · f - r² = 0

So we get:
t² * (d · d) + 2t*( f · d ) + ( f · f - r² ) = 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 ;
}