I'm trying to implement a method to check if a circle, given a certain displacement vector, will collide with a line segment. Though I don't follow some of the math, I've managed already to get a working method to determine if a circle will collide with an infinite line, defined by a line segment:

        public static CollisionData CircleVSLine(Vector2 position, float radius, VectorX displacement, LineSegment line)
        {
            CollisionData data = new CollisionData();

            Vector2 line_to_circle;

            VectorX line_vector = new VectorX(line.Size);
            Vector2 n = line_vector.Normal;

            //Shortest distance from circle's center to line - before vector is applied 
            line_to_circle = line.Position1 - position;
            float d1 = Math.Abs(VectorX.DotProduct(line_to_circle,n));

            //After vector is applied
            line_to_circle = line.Position1 - position - displacement.Components;
            float d2 = Math.Abs(VectorX.DotProduct(line_to_circle, n));

            float t = (radius - d1) / (d2 - d1);

            if (Math.Abs(d2) < radius)
            {
                data.Collides = true;
                data.CollisionPoint = position + (displacement * t);
            }

            return data;
        }

And below is my attempt to check for collisions on line segments:

        public static CollisionData CircleVSLineSegment(Vector2 position, float radius, VectorX displacement, LineSegment line)
        {
            VectorX line_vector = new VectorX(line.Size);
            //First check if collision happened on entire length of line
            CollisionData data = CircleVSLine(position,radius,displacement,line);

            //Early out
            if (!data.Collides) { return data; }

            /* Next, get the vector form Position1 to data.CollisionPoint. If they are going in the same general direction,
             * they will have a positive Dot Product, if they aren't, then the collision point must be BEHIND line_vector 
             * (I.E., not ON the vector, and not truly colliding.)
             * http://hub.tutsplus.com/tutorials/quick-tip-collision-detection-between-a-circle-and-a-line-segment--active-10632 */

            VectorX start_to_circle = new VectorX(position - line.Position1);
            float dot_start = VectorX.DotProduct(line_vector.Components, start_to_circle.Components);

            //Early out
            if (dot_start < 0) { data.Collides = false; return data; }

            if (line.Position1.X == 48 + 16)
            {
                //Debugger.Break();
                GameStatus.Pause();
            }
            if (position.Y < line.Position1.Y && line.Position1.X == 48+16) Debugger.Break();

            /* Next, we make sure the collision point doesn't happen after line_vector has ended. If it does, the projection
             * of start_to_circle onto line_vector will exceed the length of line_vector. */

            float projection = start_to_circle.ScalarProjection(line_vector);
            if (projection > line_vector.Length) { data.Collides = false; }

            return data;
        }

As you can see, I link to a tutorial which attempts to explain how the test is done. The algorithm treats the line segment as a vector (which I know is strange), and first tests to see if the circle is actually colliding with the line defined by our line segment BEFORE the start of said line segment. It then tests in an entirely different way to see if the circle collides with the line at a point AFTER the vector ends. If it doesn't collide before the line segment, and it doesn't collide after the line segment, it collides on the line segment.

The logic of the first half of the test is that if two vectors (the vector defined by our line segment, and the vector from the start of that line segment to the starting position of our circle) have generally opposite directions, then the circle MUST be behind the start of our line segment vector, which makes sense to me. The test to check if the two vectors ARE going in the same direction though, gives lots of false positives. This is my big issue. I haven't even got to the second half of the algorithm, which doesn't seem to be working either.

Can anyone help me wrap my mind around this? I'd like to repeat that I do have a working test for circles vs infinite lines, which I don't want to discard and which I feel will provide a lot of the data needed to make the more precise circle vs line segment test. Any input would be really appreciated.

Treat it like a circle against an infinite line first. Validate the t value of the intersection between the circle and the infinite line is valid first [0 - 1]. Then, take the scalar projection of this intersection pt onto p0p1 and validate that the scalar projection is also valid [0 - 1]. Give this a try:

bool TestSweptCircleLine(const Vector2& c, const float r, const Vector2& d, const Vector2& p0, const Vector2& p1, float &outT) {
    Vector2 p0p1 = p1 - p0;
    // we have this annoying case first, where the circle is *already* intersecting the line segment so check for that first.  In this case, t would be 0.0f.  As for intersection points technically you have 2, but your "solver" might just want to use c
    Vector2 closestPointOnLineSegment = p0 + p0p1 * Saturate(Dot(c - p0, p0p1) / Dot(p0p1, p0p1));
    if (DistSquared(closestPointOnLineSegment, c) <= r * r)
    {
       outT = 0.0f;
       return true;
    }
    Vector2 p0p1Perp = RightPerp(p0p1);
    // can avoid normalisation here, but lets keep this simpler for now
    Vector2 pn = Normalise(p0p1Perp);
    float   pd = -Dot(pn, p0);
    // system of equations is:
    // dot(pn, X) = -pd +- r (X is any point that is +r or -r distance away from the infinite line)
    // c + d * t = X (t is in the 0 to 1 range inclusive, X in this case is again the center of the circle when it intersects the infinite line (not necessarily the segment))
    // using substitution and solving for T
    float distanceLineToCenterOfCircle = Dot(pn, c) + pd; // just line signed plane distance
    float signSideOfLine = Sign(distanceLineToCenterOfCircle );
    // if our sign is positive, then our system of equations is + R
    // if not our system of equations is - R
    float modR = signSideOfLine * r;
    outT = (((-pd + modR) - Dot(pn, c)) / (Dot(pn, d)));
    // now validate t and s
    if (outT >= 0.0f && outT <= 1.0f)
    {
        // alright, our swept circle is intersecting the infinite line
        // now validate that this intersection is in the line segment
        // range too
        Vector2 ptCenterOfCircleWhenIntersecting = c + d * outT;
        Vector2 ptOnLineWhenIntersecting = ptCenterOfCircleWhenIntersecting + pn * -modR;
        // find the scalar projection of ptOnLineWhenIntersecting.  If it is between 0 and 1 inclusive we have an intersection
        float s = Dot(ptOnLineWhenIntersecting - p0, p0p1) / Dot(p0p1, p0p1);
        if (s >= 0.0f && s <= 1.0f)
        {
            return true;
        }
    }
    return false;
}

Thanks for the great replies! I0k0, your function is the only one doing a sweep test, which was my goal. I have a couple questions on some of your values.

d - Is this the diameter of the circle?

outT - I have no idea what this is, can you explain?

Saturate() - I've read that saturation arithmetic constrains the result of any mathematical operation to a range of values. Is this what you're doing? If so, what are you constraining the values to? 0-1?

Thanks for the great replies! I0k0, your function is the only one doing a sweep test, which was my goal. I have a couple questions on some of your values.

d - Is this the diameter of the circle?

outT - I have no idea what this is, can you explain?

Saturate() - I've read that saturation arithmetic constrains the result of any mathematical operation to a range of values. Is this what you're doing? If so, what are you constraining the values to? 0-1?

Hi

d: d is the sweep vector. So if your swept circle has a velocity of {2, 0} for the given frame, you'd pass that vector for d.

outT: The multiplier of d that gives you the point at the center of the circle when the circle first intersects the line: X = c + d * t. It's useful for getting a percentage of your sweep that contact was made. It's very useful for things like raycasts. Perhaps for your needs at a higher level just a boolean test is needed, but the way I'm doing the test you have to calculate this t value anyways.

Saturate: saturate is equivalent to Clamp(someVal, 0.0, 1.0)

Hope that helps.

        public static CollisionData CircleVSLine(Vector2 position, float radius, VectorX displacement, LineSegment line)
        {
            CollisionData data = new CollisionData();
 
            Vector2 line_to_circle;
 
            VectorX line_vector = new VectorX(line.Size);
            Vector2 n = line_vector.Normal;
 
            //Shortest distance from circle's center to line - before vector is applied 
            line_to_circle = line.Position1 - position;
            float d1 = Math.Abs(VectorX.DotProduct(line_to_circle, n));
 
            //After vector is applied
            line_to_circle = line.Position1 - position - displacement.Components;
            float d2 = Math.Abs(VectorX.DotProduct(line_to_circle, n));
 
            data.Ratio = (radius - d1) / (d2 - d1);
 
            if (Math.Abs(d2) < radius)
            {
                data.Collides = true;
                data.CollisionPoint = position + (displacement * data.Ratio);
            }
 
            return data;
        }