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

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.

• can the airplanes change directions/speeds or do they move in fixed directions? – Aron Ahmadia Jul 18 '12 at 18:58
• @AronAhmadia: Eventually, I want them to change directions, but I'm first considering the simpler case they remain in fixed directions. – Paul Jul 18 '12 at 19:01
• rather than checking the polygons at each time step, have you considered checking which paths come within intersection range, then only checking times when one of the planes is within intersection of the other path? or are there too many path intersections for this to be efficient? – Godric Seer Jul 18 '12 at 19:49

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.

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.

• Oops... i didn't realize i wrote "miles" where I meant to write "kilometers". I'll adjust the question. – Paul Jul 18 '12 at 21:05

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$.

• Oh, I see this is essentially equivalent to Mike Dunlavey's suggestion. – Joseph O'Rourke Jul 18 '12 at 22:21