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 DOT d) + 2t*( f DOT d ) + ( f DOT 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 ;
}

Answer 2

Here is good solution in JavaScript (with all required mathematics and live illustration) https://bl.ocks.org/milkbread/11000965

Though is_on function in that solution needs modifications:

function is_on(a, b, c) {
    return Math.abs(distance(a,c) + distance(c,b) - distance(a,b))<0.000001;
}

Answer 3

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:

Answer 4

In this post circle line collision will be checked by checking distance between circle center and point on line segment (Ipoint) that represent intersection point between normal N (Image 2) from circle center to line segment.

(https://i.stack.imgur.com/3o6do.png)

On image 1 one circle and one line are shown, vector A point to line start point, vector B point to line end point, vector C point to circle center. Now we must find vector E (from line start point to circle center) and vector D (from line start point to line end point) this calculation is shown on image 1.

(https://i.stack.imgur.com/7098a.png)

At image 2 we can see that vector E is projected on Vector D by "dot product" of vector E and unit vector D, result of dot product is scalar Xp that represent the distance between line start point and point of intersection (Ipoint) of vector N and vector D. Next vector X is found by multiplying unit vector D and scalar Xp.

Now we need to find vector Z (vector to Ipoint), its easy its simple vector addition of vector A (start point on line) and vector X. Next we need to deal with special cases we must check is Ipoint on line segment, if its not we must find out is it left of it or right of it, we will use vector closest to determine which point is closest to circle.

(https://i.stack.imgur.com/p9WIr.png)

When projection Xp is negative Ipoint is left of line segment, vector closest is equal to vector of line start point, when projection Xp is greater then magnitude of vector D then Ipoint is right of line segment then closest vector is equal to vector of line end point in any other case closest vector is equal to vector Z.

Now when we have closest vector , we need to find vector from circle center to Ipoint (dist vector), its simple we just need to subtract closest vector from center vector. Next just check if vector dist magnitude is less then circle radius if it is then they collide, if its not there is no collision.

(https://i.stack.imgur.com/QJ63q.png)

For end, we can return some values for resolving collision , easiest way is to return overlap of collision (subtract radius from vector dist magnitude) and return axis of collision, its vector D. Also intersection point is vector Z if needed.

Answer 5

I wrote a small script to test intersection by projecting circle's center point on to line.

vector distVector = centerPoint - projectedPoint;
if(distVector.length() < circle.radius)
{
    double distance = circle.radius - distVector.length();
    vector moveVector = distVector.normalize() * distance;
    circle.move(moveVector);
}

http://jsfiddle.net/ercang/ornh3594/1/

If you need to check the collision with the segment, you also need to consider circle center's distance to start and end points.

vector distVector = centerPoint - startPoint;
if(distVector.length() < circle.radius)
{
    double distance = circle.radius - distVector.length();
    vector moveVector = distVector.normalize() * distance;
    circle.move(moveVector);
}

https://jsfiddle.net/ercang/menp0991/

Answer 6

This solution I found seemed a little easier to follow then some of the other ones.

Taking:

p1 and p2 as the points for the line, and
c as the center point for the circle and r for the radius

I would solve for the equation of the line in slope-intercept form. However, I didn't want to have to deal with difficult equations with c as a point, so I just shifted the coordinate system over so that the circle is at 0,0

p3 = p1 - c
p4 = p2 - c

By the way, whenever I subtract points from each other I am subtracting the x's and then subtracting the y's, and putting them into a new point, just in case someone didn't know.

Anyway, I now solve for the equation of the line with p3 and p4:

m = (p4_y - p3_y) / (p4_x - p3) (the underscore is an attempt at subscript)
y = mx + b
y - mx = b (just put in a point for x and y, and insert the m we found)

Ok. Now I need to set these equations equal. First I need to solve the circle's equation for x

x^2 + y^2 = r^2
y^2 = r^2 - x^2
y = sqrt(r^2 - x^2)

Then I set them equal:

mx + b = sqrt(r^2 - x^2)

And solve for the quadratic equation (0 = ax^2 + bx + c):

(mx + b)^2 = r^2 - x^2
(mx)^2 + 2mbx + b^2 = r^2 - x^2
0 = m^2 * x^2 + x^2 + 2mbx + b^2 - r^2
0 = (m^2 + 1) * x^2 + 2mbx + b^2 - r^2

Now I have my a, b, and c.

a = m^2 + 1
b = 2mb
c = b^2 - r^2

So I put this into the quadratic formula:

(-b ± sqrt(b^2 - 4ac)) / 2a

And substitute in by values then simplify as much as possible:

(-2mb ± sqrt(b^2 - 4ac)) / 2a
(-2mb ± sqrt((-2mb)^2 - 4(m^2 + 1)(b^2 - r^2))) / 2(m^2 + 1)
(-2mb ± sqrt(4m^2 * b^2 - 4(m^2 * b^2 - m^2 * r^2 + b^2 - r^2))) / 2m^2 + 2
(-2mb ± sqrt(4 * (m^2 * b^2 - (m^2 * b^2 - m^2 * r^2 + b^2 - r^2))))/ 2m^2 + 2
(-2mb ± sqrt(4 * (m^2 * b^2 - m^2 * b^2 + m^2 * r^2 - b^2 + r^2)))/ 2m^2 + 2
(-2mb ± sqrt(4 * (m^2 * r^2 - b^2 + r^2)))/ 2m^2 + 2
(-2mb ± sqrt(4) * sqrt(m^2 * r^2 - b^2 + r^2))/ 2m^2 + 2
(-2mb ± 2 * sqrt(m^2 * r^2 - b^2 + r^2))/ 2m^2 + 2
(-2mb ± 2 * sqrt(m^2 * r^2 + r^2 - b^2))/ 2m^2 + 2
(-2mb ± 2 * sqrt(r^2 * (m^2 + 1) - b^2))/ 2m^2 + 2

This is almost as far as it will simplify. Finally, separate out to equations with the ±:

(-2mb + 2 * sqrt(r^2 * (m^2 + 1) - b^2))/ 2m^2 + 2 or     
(-2mb - 2 * sqrt(r^2 * (m^2 + 1) - b^2))/ 2m^2 + 2 

Then simply plug the result of both of those equations into the x in mx + b. For clarity, I wrote some JavaScript code to show how to use this:

function interceptOnCircle(p1,p2,c,r){
    //p1 is the first line point
    //p2 is the second line point
    //c is the circle's center
    //r is the circle's radius

    var p3 = {x:p1.x - c.x, y:p1.y - c.y} //shifted line points
    var p4 = {x:p2.x - c.x, y:p2.y - c.y}

    var m = (p4.y - p3.y) / (p4.x - p3.x); //slope of the line
    var b = p3.y - m * p3.x; //y-intercept of line

    var underRadical = Math.pow((Math.pow(r,2)*(Math.pow(m,2)+1)),2)-Math.pow(b,2)); //the value under the square root sign 

    if (underRadical < 0){
    //line completely missed
        return false;
    } else {
        var t1 = (-2*m*b+2*Math.sqrt(underRadical))/(2 * Math.pow(m,2) + 2); //one of the intercept x's
        var t2 = (-2*m*b-2*Math.sqrt(underRadical))/(2 * Math.pow(m,2) + 2); //other intercept's x
        var i1 = {x:t1,y:m*t1+b} //intercept point 1
        var i2 = {x:t2,y:m*t2+b} //intercept point 2
        return [i1,i2];
    }
}

I hope this helps!

P.S. If anyone finds any errors or has any suggestions, please comment. I am very new and welcome all help/suggestions.