At what delta time will two objects collide?

Question

My apologies if this has been posted before. I can't seem to find anything on the topic, via Stackoverflow, nor any of my other google searches.

I have two objects, both containing a position (x and y), as well as a linear velocity (x and y). These objects are moving through a 2d plane. I need to detect when these objects will collide, if they will collide at all. The big problem to my situation is the radius of the objects, as this will effect when they will touch.

I've tried various solutions to this problem over a period of a month, but I'm just not hacking it. What I've managed to do, is calculate the two straight line formulas for the object, and end up with the b and c for both (y=mx + c). I'm trying to compare these two formulas to each other, where x=x and y=y, but end up with a very complex equation, and no idea how to translate this to c#.

This function needs to fire in <50ms as well, to complicate matters. Any advice would go a long way.

Answer 1

You can formulate the problem as a system of two vector equations

p1 = u1 + v1 t
p2 = u2 + v2 t

where p1 is the position of the first object given an initial position u1, velocity v1, and scalar time t. We want to solve for the moment the objects just touch, described by

r1 + r2 = |p1 - p2|

where r1 and r2 are the radii of the objects. Let's define some variables so our derivation is a little cleaner:

x  = u1.x - u2.x
y  = u1.y - u2.y
x' = v1.x - v2.x
y' = v1.y - v2.y

Then we can proceed to solve as follows:

    r1 + r2    = |p1 - p2|
               = sqrt((p1.x - p2.x)^2 + (p1.y - p2.y)^2)                 definition of vector magnitude

=> (r1 + r2)^2 = (p1.x - p2.x)^2 + (p1.y - p2.y)^2                       square both sides
               = (x + x' t)^2 + (y + y' t)^2                             substitute variable definitions
               = x^2 + 2 x x' t + x'^2 t^2 + y^2 + 2 y y' t + y'^2 t^2   expand squares of sums
               = (x'^2 + y'^2) t^2 + 2 (x x' + y y') t + x^2 + y^2       rearrange terms

=> (x'^2 + y'^2) t^2 + 2 (x x' + y y') t + x^2 + y^2 - (r1 + r2)^2 = 0   rearrange terms

This is a quadratic equation, so we can find t using the quadratic formula with

a = x'^2 + y'^2
b = 2 (x x' + y y')
c = x^2 + y^2 - (r1 + r2)^2

If the objects don't collide, the discriminant b^2 - 4 a c will be negative. If the objects collide in the past, the values for t may be negative.

Speaking of which, how do we interpret the fact that we obtain two roots, or two values of t? Consider the following image:

As you can see, we obtain solutions for the first contact, the "entry", as well as when the objects intersect and part, the "exit". This can be useful depending on your needs, but if you just need the contact time, take the smaller t.