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

In the context of a game program, I have a moving circle and a fixed line segment. The segment can have an arbi开发者_JAVA百科trary 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)

I'm going to answer with pseudo-algorithm - without any code. The way I see it there are two cases in which we might return true, as per the image below:

Here in blue are your circles, the dashed line is the trajectory line and the red line is your given line.

• We build a helper trajectory line, from and to the center of both circles. If this trajectory line intersects the given line - return true. See this question on how to compute that intersection.
• In the second case the first test has failed us, but it might just so happen that the circles nudged the line as they passed on the trajectory anyway. We will need the following constuction:

  

From the trajectory we build normal lines to each point A and B. Then these lines are chopped or extended into helper lines (Ha and Hb), so that their length from A and B is exactly the radius of the circle. Then we check if each of these helper lines intersects with the trajectory line. If they do return true.

• Otherwise return false.

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;
}

Here is some Java that calculates the distance from a point to a line (this is not complete, but will give you the basic picture). The code comes from a class called 'Vector'. The assumption is that the vector object is initialized to the line vector. The method 'distance' accepts the point that the line vector starts at (called 'at' of course), and the point of interest. It calculates and returns the distance from that point to the line.

public class Vector
{
double x_ = 0;
double y_ = 0;
double magnitude_ = 1;

public Vector()
{
}

public Vector(double x,double y)
{
    x_ = x;
    y_ = y;
}

public Vector(Vector other)
{
    x_ = other.x_;
    y_ = other.y_;
}

public void add(Vector other)
{
    x_ += other.x_;
    y_ += other.y_;
}

public void scale(double val)
{
    x_ *= val;
    y_ *= val;
}

public double dot(Vector other)
{
    return x_*other.x_+y_*other.y_;
}

public void cross(Vector other)
{
    x_ = x_*other.y_ - y_*other.x_;
}

public void unit()
{
    magnitude_ = Math.sqrt(x_*x_+y_*y_);
    x_/=magnitude_;
    y_/=magnitude_;
}

public double distance(Vector at,Vector point)
{
    //
    // Create a perpendicular vector
    //
    Vector perp = new Vector();
    perp.perpendicular(this);
    perp.unit();

    Vector offset = new Vector(point.x_ - at.x_,point.y_ - at.y_);
    double d = Math.abs(offset.dot(perp));

    double m = magnitude();
    double t = dot(offset)/(m*m);
    if(t < 0)
    {
        offset.x_ -= at.x_;
        offset.y_ -= at.y_;
        d = offset.magnitude();
    }
    if(t > 1)
    {
        offset.x_ -= at.x_+x_;
        offset.y_ -= at.y_+y_;
        d = offset.magnitude();
    }
    return d;
}

private void perpendicular(Vector other)
{
    x_ = -other.y_;
    y_ = other.x_;
}

public double magnitude()
{
    magnitude_ = Math.sqrt(x_*x_+y_*y_);
    return magnitude_;
}
}