Modify Circle-Infinite Line Collision To Work With Line Segments

Question

Alright, so all I need is if a line is crossing a circle, it returns true. If the line is going through the circle, it also returns true. All else is false. Basically a line segment

Here is some code that I've tried:

Examples:

        Vector2 pointA, pointB;
        pointA = locationA;
        pointB = locationB;

        pointA.Normalize();
        pointB.Normalize();

        float dx = pointB.X - pointA.X;
        float dy = pointB.Y - pointA.Y;

        float dr = (float)Math.Sqrt((dx * dx) + (dy * dy));

        float D = (pointA.X * pointB.Y) - (pointB.X * pointA.Y);

        float delta = (circle.radius * circle.radius) * (dr * dr) - (D * D);

        if (delta > 0) return true;
        else return false;

Or

        float dx = locationB.X - locationA.X;
        float dy = locationB.Y - locationA.Y;

        float a = (dx * dx) + (dy * dy);

        float b = 2 * (dx * (locationA.X - circle.position.X) +
                       dy * (locationA.Y - circle.position.Y));

        float c = (circle.position.X * circle.position.X) +
                  (circle.position.Y * circle.position.Y);

        c += (locationA.X * locationA.X) +
             (locationA.Y * locationA.Y);

        c -= 2 * (circle.position.X * locationA.X + circle.position.Y * locationA.Y);
        c -= circle.radius * circle.radius;

        float delta = b * b - 4 * a * c;

        if (delta < 0)
            return false;
        else
            return true;

I tried that code thinking it was for line segments, but after testing it, I realized it was for infinite line detection.

Does anyone know of a website that has math/pseudo/code for this? All my google searching is turning up nothing useful. Also on Wolfram, I'm only finding infinite line to circle collision.

Much appreciated! Shyy,

EDIT:

Updated attempt:

        Vector2 d = locationB - locationA;
        Vector2 p = locationA - circle.position;

        Vector2 x = locationA + d;
        Vector2 radius = x - circle.position;

        Vector2 rSq = (d * d) + (p * d) + (d * p) + (p * p);

        Vector2 t = (d * d) + 2 * (p * d) + (p * p) - (radius * radius);

        Vector2 u = d * d;
        Vector2 v = 2 * (p * d);
        Vector2 w = (p * p) - (radius * radius); // circle.radius did not work does not work here, as radius was float. Converted to Vector2 above.

        Vector2 r = (u * (t * t)) + v * t + w;

Answer 1

In complement to the previous answer (japreiss'), you can see if the segment is included in the circle with no more maths and a little extra logic.

You get, with the same reasoning and notations, to ut² + vt + w <= 0, which you want to verify for all t in [0,1].

You solved for its roots r1 and r2 if they exist. You know that on both ends, your polynomial diverges to infinity (because u > 0) so it is negative between the roots. That also means the polynomial is always non-negative with less than two roots. So if r1 <= 0 && r2 >= 1 you have it totally included.

So the initial expressing u, v and w stays the same, and solving the second order polynomial's roots as well. Then, the final logic would be :

• if no real roots, return false
• if a single root r, return true iff r >= 0 || r <= 1
• if two roots r1 and r2 (with r1 < r2 by construction) return false iff r1 > 1 || r2 < 0.

Indeed, with those two tests false either (at least) a root is in [0,1], thus the segment intersects the circle, or if none are then [r1, r2] necessarily overlaps [0,1], meaning the segment is included in the circle.

Answer 2

suppose your line segment goes between points a and b. treat it as a parametric equation. first,

    let d = b - a

so your line segment is described by:

    a + td for all real numbers between 0 and 1

and the infinite line that contains it is described by:

    a + td for all real numbers

because if t is negative or > 1, you are continuing on the same line, but no longer inside the segment.

meanwhile, for any point on the circle edge, the following is true:

    length(point - center) = radius

---

now we have equations defining the infinite line and the circle edge. if there's an intersection point x between them, then x must satisfy both equations:

    x = a + td for some real number t

    length(x - center) = radius

putting the two together, we are looking for a value of t that satisfies the following equation:

    length(a + td - center) = radius

the nice thing about this problem formulation is that if we find an intersection, we will know its t value, so it is only a tiny bit more work to test if it is inside the segment.

---

if we define p = a - center, then our equation becomes simpler:

    length(td + p) = radius

expand the definition of vector length and square both sides:

    sqrt((td + p) · (td + p)) = radius

    (td + p) · (td + p) = radius²

by the distributivity of dot products:

    (td + p) · td + (td + p) · p = radius²

    (td · td) + (p · td) + (td · p) + (p · p) = radius²

do some algebra to bring out t:

    t² (d · d) + 2t (p · d) + (p · p) - radius² = 0

let's simplify it by defining variables for all our non-t terms, which are all scalars, not vectors:

    let u = d · d
        v = 2 (p · d)
        w = (p · p) - radius²

so now our equation is:

    ut² + vt + w = 0

this is a quadratic equation. we can solve it with the quadratic formula.

---

since our quadratic equation is in terms of t, its roots will be values of t that we can plug back into our parametric line equation.

if the quadratic equation has no real roots, the infinite line doesn't intersect the circle edge at all, so the segment certainly doesn't either.

if it has one or two real roots, the line intersects the circle edge, but the segment might not. for each root r, we need to check if

    0 <= r <= 1

if so, then by our parametric definition, the segment intersects the circle at

    a + rd

naturally, if the equation has 2 roots and this is true for both, then the circle and line segment intersect at 2 places.

---

to implement this math in code, work backwards from the end to figure out what values you need to compute. Your goal is to solve the quadratic equation ut² + vt + w = 0. This will give you 0, 1, or 2 roots. Then you will return true if at least one root is in the range 0 <= t <= 1.

so work backwards from the definitions of u, v, and w until you get everything in terms of a, b, center, and radius - the inputs to your function.

---

Since OP had trouble converting the math above into code, here is some code.

Vector2 d = locationB - locationA;
Vector2 p = locationA - circle.position;
double u = d*d;
double v = 2*p*d;
double w = p*p - circle.radius*circle.radius;

// apply quadratic formula
// NOTE: THIS CODE IS PROBABLY NOT NUMERICALLY STABLE.
// LOOK IN A NUMERICAL ANALYSIS BOOK
// IF YOU NEED TO SOLVE THIS PROBLEM FOR REAL.
double discriminant = v*v - 4*u*w;
if (discriminant < 0) {
    // no real roots, infinite line does not intersect circle
}
else if (discriminant == 0) {
    // 1 real root, infinite line is tangent to circle.
    // if tangent lines don't count, then return false here. otherwise...
    double t = -v / (2*u);
    return (t >= 0 && t <= 1);
}
else {
    // 2 real roots, infinite line intersects circle
    double t0 = (-v + Math.Sqrt(discriminant)) / (2*u);
    double t1 = (-v - Math.Sqrt(discriminant)) / (2*u);
    return (t0 >= 0 && t0 <= 1) || (t1 >= 0 && t1 <= 1);
}

---

as @Cimbali pointed out, this method won't detect when the segment lies completely inside the circle. If you need to recognize that case, you can simply check if:

    length(a - center) <= radius and length(b - center) <= radius

but there might be way to do it with less computational effort too.