How can I detect which among N bodies with different velocities will collide?

Question

Suppose I have N different airplanes traveling on a two dimensional rectangular plane of size 400km x 400km (i.e. it is as if all planes travel at the same altitude). Assume each airplane has a randomly generated starting and ending points. Also, assume that the airplanes can have different speeds. We assume that two airplanes will "collide" if they come within 10 km of each other. Based upon this information, how can I efficiently determine which pairs of airplanes will inevitably collide?

Update: As far as I can tell, it would require something similar to a line segment intersection algorithm, but instead of a line having zero width, it has a thickness of 20km. I'm just not sure how to incorporate the time dynamics into the detection algorithm. I suppose I could use a polygon-intersection at each (small) time step to determine if they collide, but I wanted to see if there is a more efficient way to detect it without going through pair-wise polygon intersection at each time step.

Answer 1

At a point in time, each airplane has a position and a velocity vector. For each airplane A, subtract its position and velocity vector from every other airplane B. That puts each other B airplane into an A-relative coordinate system.

Then for each B airplane, do a little trigonometry to see if its velocity vector brings it within a distance of 10 from the origin.

Answer 2

Consider the trajectory of a plane as a line in three-dimensional $(x,y,t)$ space given by the segment $x_{start},y_{start},t_{start}$ to $x_{end},y_{end},t_{end}$. To make things like computing distances meaningful it is probably useful to measure time with the same units as distances, i.e., for example, in kilometers using the constant speed $v$ of planes. For example a time of $t=940$ km is then equivalent to $t=1$ hour assuming a speed of $v=940$ km/h.

For each pair of planes it is then a simple exercise to compute the minimal Euclidean distance in this three-dimensional space. This already gives an indication whether planes come close to each other but it isn't quite what you want because the distance is not spatial but spatio-temporal. You'll have to work a bit to see if one can be converted into the other. (Essentially it is a question of which norm you compute the distance in, but that's not useful since it may not be convenient to compute the distance between two lines in anything but the Euclidean norm.)

Another idea that can work in this regard is to consider the "safety zone" of each plane as a cylinder or tube with spatial radius 20 kilometers around the space-time lines of each plane. Detecting collision then simply becomes an exercise to see if two such cylinders have an intersection.

Answer 3

Here is one way to perform the computation for any two planes $p_1$ and $p_2$, moving at velocities $v_1$ and $v_2$. You could repeat this computation for every pair.

Subtract $v_1$ from both velocities, so that now $p'_1$ is fixed and $p'_2$ is moving with velocity $v_2-v_1$. Imagine drawing the line $L$ that $p'_2$ follows. You want the closest approach of $L$ to the fixed point $p'_1$. This is a straightforward calculation, which could be organized as follows.

Assign a parameter $t$ to points $p'_2(t)$ on $L$. Then compute $|| p'_1 - p'_2(t) ||$. Minimize this w.r.t. $t$. You will obtain the radius of the sphere centered on $p'_1$ that is tangent to $L$.