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

You'll need some math here:

Suppose A = (Xa, Ya), B = (Xb, Yb) and C = (Xc, Yc). Any point on the line from A to B has coordinates (alpha*Xa + (1-alpha)Xb, alphaYa + (1-alpha)*Yb) = P

If the point P has distance R to C, it must be on the circle. What you want is to solve

distance(P, C) = R

that is

(alpha*Xa + (1-alpha)*Xb)^2 + (alpha*Ya + (1-alpha)*Yb)^2 = R^2
alpha^2*Xa^2 + alpha^2*Xb^2 - 2*alpha*Xb^2 + Xb^2 + alpha^2*Ya^2 + alpha^2*Yb^2 - 2*alpha*Yb^2 + Yb^2=R^2
(Xa^2 + Xb^2 + Ya^2 + Yb^2)*alpha^2 - 2*(Xb^2 + Yb^2)*alpha + (Xb^2 + Yb^2 - R^2) = 0

if you apply the ABC-formula to this equation to solve it for alpha, and compute the coordinates of P using the solution(s) for alpha, you get the intersection points, if any exist.

Answer 2

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!

Answer 3

Weirdly I can answer but not comment... I liked Multitaskpro's approach of shifting everything to make the centre of the circle fall on the origin. Unfortunately there are two problems in his code. First in the under-the-square-root part you need to remove the double power. So not:

var underRadical = Math.pow((Math.pow(r,2)*(Math.pow(m,2)+1)),2)-Math.pow(b,2));

but:

var underRadical = Math.pow(r,2)*(Math.pow(m,2)+1)) - Math.pow(b,2);

In the final coordinates he forgets to shift the solution back. So not:

var i1 = {x:t1,y:m*t1+b}

but:

var i1 = {x:t1+c.x, y:m*t1+b+c.y};

The whole function then becomes:

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(r,2)*Math.pow(m,2) + Math.pow(r,2) - Math.pow(b,2); //the value under the square root sign 

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

Answer 4

Just an addition to this thread... Below is a version of the code posted by pahlevan, but for C#/XNA and tidied up a little:

    /// <summary>
    /// Intersects a line and a circle.
    /// </summary>
    /// <param name="location">the location of the circle</param>
    /// <param name="radius">the radius of the circle</param>
    /// <param name="lineFrom">the starting point of the line</param>
    /// <param name="lineTo">the ending point of the line</param>
    /// <returns>true if the line and circle intersect each other</returns>
    public static bool IntersectLineCircle(Vector2 location, float radius, Vector2 lineFrom, Vector2 lineTo)
    {
        float ab2, acab, h2;
        Vector2 ac = location - lineFrom;
        Vector2 ab = lineTo - lineFrom;
        Vector2.Dot(ref ab, ref ab, out ab2);
        Vector2.Dot(ref ac, ref ab, out acab);
        float t = acab / ab2;

        if (t < 0)
            t = 0;
        else if (t > 1)
            t = 1;

        Vector2 h = ((ab * t) + lineFrom) - location;
        Vector2.Dot(ref h, ref h, out h2);

        return (h2 <= (radius * radius));
    }

Answer 5

If you find the distance between the center of the sphere (since it's 3D I assume you mean sphere and not circle) and the line, then check if that distance is less than the radius that will do the trick.

The collision point is obviously the closest point between the line and the sphere (which will be calculated when you're calculating the distance between the sphere and the line)

Distance between a point and a line:
http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html

Answer 6

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.