Calculating Collision Times Between Two Circles - Physics

Question

I keep stumbling into game/simulation solutions for finding distance while time is running, and it's not what I'm looking for.

I'm looking for an O(1) formula to calculate the (0 or 1 or 2) clock time(s) in which two circles are exactly r1+r2 distance from each other. Negative time is possible. It's possible two circles don't collide, and they may not have an intersection (as in 2 cars "clipping" each other while driving too close to the middle of the road in opposite directions), which is messing up all my mx+b solutions.

Technically, a single point collision should be possible.

I'm about 100 lines of code deep, and I feel sure there must be a better way, and I'm not even sure whether my test cases are correct or not. My initial setup was:

dist( x1+dx1*t, y1+dy1*t, x2+dx2*t, y2+dy2*t ) == r1+r2

By assuming the distance at any time t could be calculated with Pythagoras, I would like to know the two points in time in which the distance from the centers is precisely the sum of the radii. I solved for a, b, and c and applied the quadratic formula, and I believe that if I'm assuming they were phantom objects, this would give me the first moment of collision and the final moment of collision, and I could assume at every moment between, they are overlapping.

I'm working under the precondition that it's impossible for 2 objects to be overlapping at t0, which means infinite collision of "stuck inside each other" is not possible. I'm also filtering out and using special handling for when the slope is 0 or infinite, which is working.

I tried calculating the distance when, at the moment object 1 is at the intersection point, it's distance from object 2, and likewise when o2 is at the intersection point, but this did not work as it's possible to have collision when they are not at their intersection.

I'm having problems for when the slopes are equal, but different magnitude.

Is there a simple physics/math formula for this already?

Programming language doesn't matter, pseudcode would be great, or any math formula that doesn't have complex symbols (I'm not a math/physics person)... but nothing higher order (I assume python probably has a collide(p1, p2) method already)

Answer 1

There is a simple(-ish) solution. You already mentioned using the quadratic formula which is a good start.

First define your problem where the quadratic formula can be useful, in this case, distance between to centers, over time.

• Let's define our time as t
• Because we are using two dimensions we can call our dimensions x & y
• First let's define the two center points at t = 0 of our circles as a & b
• Let's also define our velocity at t = 0 of a & b as u & v respectively.
• Finally, assuming a constant acceleration of a & b as o & p respectively.
• The equation for a position along any one dimension (which we'll call i) with respect to time t is as follows: i(t) = 1 / 2 * a * t^2 + v * t + i0; with a being constant acceleration, v being initial velocity, and i0 being initial position along dimension i.
• We know the distance between two 2D points at any time t is the square root of ((a.x(t) - b.x(t))^2 + (a.y(t) - b.y(t))^2)
• Using the formula of position along a dimensions we can substitute everything in the distance equation in terms of just t and the constants we defined earlier. For shorthand we will call the function d(t);
• Finally using that equation, we will know that the t values where d(t) = a.radius + b.radius are where collision starts or ends.
• To put this in terms of quadratic formula we move the radius to the left so we get d(t) - (a.radius + b.radius) = 0
• We can then expand and simplify the resulting equation so everything is in terms of t and the constant values that we were given. Using that solve for both positive & negative values with the quadratic formula.
• This will handle errors as well because if you get two objects that will never collide, you will get an undefined or imaginary number.

You should be able to translate the rest into code fairly easily. I'm running out of time atm and will write out a simple solution when I can.

Answer 2

Following up on @TinFoilPancakes answer and heavily using using WolframAlpha to simplify the formulae, I've come up with the following pseudocode, well C# code actually that I've commented somewhat:

The Ball class has the following properties:

public double X;
public double Y;
public double Xvel;
public double Yvel;
public double Radius;

The algorithm:

public double TimeToCollision(Ball other)
{
    double distance = (Radius + other.Radius) * (Radius + other.Radius);
    double a = (Xvel - other.Xvel) * (Xvel - other.Xvel) + (Yvel - other.Yvel) * (Yvel - other.Yvel);
    double b = 2 * ((X - other.X) * (Xvel - other.Xvel) + (Y - other.Y) * (Yvel - other.Yvel));
    double c = (X - other.X) * (X - other.X) + (Y - other.Y) * (Y - other.Y) - distance;
    double d = b * b - 4 * a * c;
    // Ignore glancing collisions that may not cause a response due to limited precision and lead to an infinite loop
    if (b > -1e-6 || d <= 0)
        return double.NaN;
    double e = Math.Sqrt(d);
    double t1 = (-b - e) / (2 * a);    // Collison time, +ve or -ve
    double t2 = (-b + e) / (2 * a);    // Exit time, +ve or -ve
    // b < 0 => Getting closer
    // If we are overlapping and moving closer, collide now
    if (t1 < 0 && t2 > 0 && b <= -1e-6)
        return 0;
    return t1;
}

The method will return the time that the Balls collide, which can be +ve, -ve or NaN, NaN means they won't or didn't collide.

Further points to note are, we can check the discriminant against <zero to bail out early which will be most of the time, and avoid the Sqrt. Also since I'm using this in a continuous collision detection system, I'm ignoring collisions (glancing) that will have little or no impact since it's possible the response to the collision won't change the velocities and lead to the same situation being checked infinitely, freezing the simulation.

The 'b' variable can used for this check since luckily it's similar to the dot product. If b is >-1e-6 ie. they're not moving closer fast enough we return NaN, ie. they don't collide. You can tweak this value to avoid freezes, smaller will allow closer glancing collisions but increase the chance of a freeze when they happen like when a bunch of circles are packed tightly together. Likewise to avoid Balls moving through each other we signal an immediate collison if they're already overlapping and moving closer.