Circle line-segment collision detection algorithm?

Solution 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 ;
}

Solution 2:

No one seems to consider projection, am I completely off track here?

Project the vector AC onto AB. The projected vector, AD, gives the new point D.
If the distance between D and C is smaller than (or equal to) R we have an intersection.

Like this:

Solution 3:

I would use the algorithm to compute the distance between a point (circle center) and a line (line AB). This can then be used to determine the intersection points of the line with the circle.

Let say we have the points A, B, C. Ax and Ay are the x and y components of the A points. Same for B and C. The scalar R is the circle radius.

This algorithm requires that A, B and C are distinct points and that R is not 0.

Here is the algorithm

// compute the euclidean distance between A and B
LAB = sqrt( (Bx-Ax)²+(By-Ay)² )

// compute the direction vector D from A to B
Dx = (Bx-Ax)/LAB
Dy = (By-Ay)/LAB

// the equation of the line AB is x = Dx*t + Ax, y = Dy*t + Ay with 0 <= t <= LAB.

// compute the distance between the points A and E, where
// E is the point of AB closest the circle center (Cx, Cy)
t = Dx*(Cx-Ax) + Dy*(Cy-Ay)    

// compute the coordinates of the point E
Ex = t*Dx+Ax
Ey = t*Dy+Ay

// compute the euclidean distance between E and C
LEC = sqrt((Ex-Cx)²+(Ey-Cy)²)

// test if the line intersects the circle
if( LEC < R )
{
    // compute distance from t to circle intersection point
    dt = sqrt( R² - LEC²)

    // compute first intersection point
    Fx = (t-dt)*Dx + Ax
    Fy = (t-dt)*Dy + Ay

    // compute second intersection point
    Gx = (t+dt)*Dx + Ax
    Gy = (t+dt)*Dy + Ay
}

// else test if the line is tangent to circle
else if( LEC == R )
    // tangent point to circle is E

else
    // line doesn't touch circle

Solution 4:

Okay, I won't give you code, but since you have tagged this algorithm, I don't think that will matter to you. First, you have to get a vector perpendicular to the line.

You will have an unknown variable in y = ax + c ( c will be unknown )
To solve for that, Calculate it's value when the line passes through the center of the circle.

That is,
Plug in the location of the circle center to the line equation and solve for c.
Then calculate the intersection point of the original line and its normal.

This will give you the closest point on the line to the circle.
Calculate the distance between this point and the circle center (using the magnitude of the vector).
If this is less than the radius of the circle - voila, we have an intersection!

Solution 5:

Another method uses the triangle ABC area formula. The intersection test is simpler and more efficient than the projection method, but finding the coordinates of the intersection point requires more work. At least it will be delayed to the point it is required.

The formula to compute the triangle area is : area = bh/2

where b is the base length and h is the height. We chose the segment AB to be the base so that h is the shortest distance from C, the circle center, to the line.

Since the triangle area can also be computed by a vector dot product we can determine h.

// compute the triangle area times 2 (area = area2/2)
area2 = abs( (Bx-Ax)*(Cy-Ay) - (Cx-Ax)(By-Ay) )

// compute the AB segment length
LAB = sqrt( (Bx-Ax)² + (By-Ay)² )

// compute the triangle height
h = area2/LAB

// if the line intersects the circle
if( h < R )
{
    ...
}        

UPDATE 1 :

You could optimize the code by using the fast inverse square root computation described here to get a good approximation of 1/LAB.

Computing the intersection point is not that difficult. Here it goes

// compute the line AB direction vector components
Dx = (Bx-Ax)/LAB
Dy = (By-Ay)/LAB

// compute the distance from A toward B of closest point to C
t = Dx*(Cx-Ax) + Dy*(Cy-Ay)

// t should be equal to sqrt( (Cx-Ax)² + (Cy-Ay)² - h² )

// compute the intersection point distance from t
dt = sqrt( R² - h² )

// compute first intersection point coordinate
Ex = Ax + (t-dt)*Dx
Ey = Ay + (t-dt)*Dy

// compute second intersection point coordinate
Fx = Ax + (t+dt)*Dx
Fy = Ay + (t+dt)*Dy

If h = R then the line AB is tangent to the circle and the value dt = 0 and E = F. The point coordinates are those of E and F.

You should check that A is different of B and the segment length is not null if this may happen in your application.