2D collision between a moving circle and a fixed line segment

Question

In the context of a game program, I have a moving circle and a fixed line segment. The segment can have an arbitrary size and orientation.

• I know the radius of the circle: r
• I know the coordinates of the circle before the move: (xC1, yC1)
• I know the coordinates of the circle after the move: (xC2, yC2)
• I know the coordinates of the extremities of the line segment: (xL1, yL1) - (xL2, yL2)

I am having difficulties trying to compute:

• A boolean: If any part of the circle hits the line segment while moving from (xC1, yC1) to (xC2, yC2)
• If the boolean is true, the coordinates (x, y) of the center of the circle when it hits the line segment (I mean when circle is tangent to segment for the first time)

Answer 1

Look here:

Line segment / Circle intersection

If the value you get under the square root of either the computation of x or y is negative, then the segment does not intersect. Aside from that, you can stop your computation after you have x and y (note: you may get two answers)

Update I've revised my answer to very specifically address your problem. I give credit to Doswa for this solution, as I pretty much followed along and wrote it for C#. The basic strategy is that we are going to locate the closest point of your line segment to the center of the circle. Based on that, we'll look at the distance of that closest point, and if it is within the radius, locate the point along the direction to the closest point that lies right at the radius of the circle.

// I'll bet you already have one of these.
public class Vec : Tuple<double, double>
{
  public Vec(double item1, double item2) : base(item1, item2) { }
  public double Dot(Vec other) 
    { return Item1*other.Item1 + Item2*other.Item2; }
  public static Vec operator-(Vec first, Vec second) 
    { return new Vec(first.Item1 - second.Item1, first.Item2 - second.Item2);}
  public static Vec operator+(Vec first, Vec second) 
    { return new Vec(first.Item1 + second.Item1, first.Item2 + second.Item2);}
  public static Vec operator*(double first, Vec second) 
    { return new Vec(first * second.Item1, first * second.Item2);}
  public double Length() { return Math.Sqrt(Dot(this)); }
  public Vec Normalize() { return (1 / Length()) * this; }
}

public bool IntersectCircle(Vec origin, Vec lineStart, 
      Vec lineEnd, Vec circle, double radius, out Vec circleWhenHit)
{
    circleWhenHit = null;

    // find the closest point on the line segment to the center of the circle
    var line = lineEnd - lineStart;
    var lineLength = line.Length();
    var lineNorm = (1/lineLength)*line;
    var segmentToCircle = circle - lineStart;
    var closestPointOnSegment = segmentToCircle.Dot(line) / lineLength;

    // Special cases where the closest point happens to be the end points
    Vec closest;
    if (closestPointOnSegment < 0) closest = lineStart;
    else if (closestPointOnSegment > lineLength) closest = lineEnd;
    else closest = lineStart + closestPointOnSegment*lineNorm;

    // Find that distance.  If it is less than the radius, then we 
    // are within the circle
    var distanceFromClosest = circle - closest;
    var distanceFromClosestLength = distanceFromClosest.Length();
    if (distanceFromClosestLength > radius) return false;

    // So find the distance that places the intersection point right at 
    // the radius.  This is the center of the circle at the time of collision
    // and is different than the result from Doswa
    var offset = (radius - distanceFromClosestLength) *
                 ((1/distanceFromClosestLength)*distanceFromClosest);
    circleWhenHit = circle - offset;

    return true;
}