Cfrgtkky

I am trying to find the time at which 2 airplanes could potentially collide with each other. When I say collide, I mean the circular region around an airplane overlaps with the circular region around another airplane. The circular regions all have the same radius. Assuming that all airplanes follow a straight path, I wanted to find the time at which the airplanes start colliding.

I have been thinking of different ways of approaching the problem:

• Assuming the positions of an arbitrary plane A and plane B after time t were:

$$begin{pmatrix} a \ b end{pmatrix} + begin{pmatrix} c \ d end{pmatrix} t$$
$$begin{pmatrix} x \ y end{pmatrix} + begin{pmatrix} u \ v end{pmatrix} t$$
respectively, then the euclidean distance must be:
$$sqrt {(a + ct - x - ut)^2 + (b + dt - y - vt)^2} ge 2r$$
where r is the radius of the region around the 2 airplanes. After that, when both sides are squared and rearranged, I would end up with a quadratic equation which will give me 2 values of t(using the quadratic formula).

• The second method was to take the Euclidean distance and differentiate it with respect to t and equate that equation to zero to find the minimum distance between the 2 airplanes.

These are the only two method I have been able to think of. For the first method, will there be only 1 solution to the equation, since the airplanes are travelling in a straight line? If there are 2 and both are positive, which one should I use?

Moreover, for the second method, I am afraid that it will yield a time that is too late since it will compute the time at which they are closest and not the time at which they start colliding. Is there a way to work around this? I would prefer that because the equation that I get is will only produce 1 solution so I will not have to go through using 2 values of t(I am writing a program so I would like it to run as fast as possible).

Finally, I just wanted to know whether there were any simpler and faster ways of doing this. A hint would be appreciated very much!

Thank you so much:)

Here's a vector-based approach based on the geometric figure below.

Here, $A$ and $B$ are the initial positions of the two aircraft,
with $A = begin{pmatrix} a\ bend{pmatrix}$
and $B = begin{pmatrix} x\ yend{pmatrix}.$
Let's assume the distance between $A$ and $B$ is at least $2r,$ since otherwise
we can just say the aircraft have already "collided."

For the purpose of finding time to "collision," we compute all speeds and distances in a frame of reference in which the aircraft at $A$ does not move.
The vector from $A$ to $B,$ which is the initial position of the aircraft at $B$ relative to $A,$ is
$p = begin{pmatrix} x - a\ y - bend{pmatrix}.$
The velocity of the aircraft at $B$ relative to $A$ is
$w = begin{pmatrix} u - c\ v - dend{pmatrix}.$

Find the unit vector $hat w$ in the same direction as $w.$
That is, set $hat w = frac{1}{lVert wrVert} w.$

Find a unit vector $hat n$ perpendicular to $hat w.$
A simple way to do this is a transformation on the coordinates of $hat w.$
That is, if $hat w = begin{pmatrix} hat w_x\ hat w_yend{pmatrix}$
then $hat n = begin{pmatrix} -hat w_y\ hat w_xend{pmatrix}.$

It does not matter which side of the vector $w$ the vector $hat n$ points to;
it just needs to be perpendicular.

Let $s = - p cdot hat w$ and $d = p cdot hat n.$
In effect, this gives $A$ coordinates in a coordinate system centered at $B$
with axes in the directions of $hat w$ and $hat n.$
The number $s$ is also the distance from $B$ to the point of closest approach of the aircraft, labeled $D$ in the figure.

If $s$ is negative, the point of closest approach is behind the aircraft at $B.$
In that case, since we've already assumed the aircraft start at a distance at least $2r,$ we can say the aircraft are flying away from each other and will not "collide" at any future time.

Since $2r$ is the maximum distance at which the aircraft's circular regions could overlap, if $d > 2r$ then the line projected from the vector $w$ never gets close enough to $A$ to cause a "collision."
But if $d leq 2r$ we have at least one intersection of the line with the circle.

Setting $q = sqrt{(2r)^2 - d^2},$
the distance from $B$ to the closest point of intersection with the circle,
namely $C,$ is $s - q.$

To get the time at which the aircraft first "collide," we divide the distance to the start of the "collision" by the relative speed with which the aircraft starting at $B$ approaches that point. That is,
$$ t = frac{s - q}{lVert w rVert}. $$

Let's make this a little easier. Suppose that one plane is parked on the tarmac, on one of two parallel runways.

The other plane approaches, on the other parallel runway. At some moment, $t_1$ it gets to be distance $2r$ from the parked plane. A few moments later, at $t_2$, it gets as close as possible to the parked plane. Then it begins to get farther away, and at time $t_3$ it's again at distance $2r$ from the parked plane. After that, things are safe again.

$t_1$ and $t_3$ are the times generated by method 1, the quadratic approach. Time $t_2$ is the time generated by method 2, the "closest approach" method. YOu can see that these times are different, but that in general, we have that $t_2$ is between $t_1$ and $t_3$.

"But what about the general case?" I hear you cry. Well...believe it or not, this is the general case. IF you express everything in a coordinate system that's centered at the (moving) location of plane 1, then plane 1's position, in this moving coord system, is constantly the origin. And plane 2's position, in this moving coordinate system, is $P(t) = (P_2 - P_1) + t(v_2 - v_1)$, where $P_1$ is the (fixed, global) location of plane 1 at time $t = 1$, and $v_1$ is the velocity vector of plane 1 in that global coordinate system, and similarly for $P_2$ and $v_2$.

"OK, fine. But which is the right method to use, and can this be done more efficiently?", you ask.

I think that method 1 is the right method, because it answers the question you asked, namely, "at what time are the planes at the critical distance?" On the other hand, if time is really critical, you may not want to go solving a quadratic, which takes a bit of algebra. So one thing to do is this:

Use method 2 to find the moment $t_2$ when the planes are closest. Compute the squared distance $u$ between them at this moment, and compare to the (precomputed) constant $4r^2$. If $u > 4r^2$, then the planes never get close enough to worry about, and having solved one linear equation, you can quit.

If $u le 4r^2$, the you can look at your quadratic,
$$
h(t) = at^2 + bt + c
$$
and know that the roots are at
$$
t_{1,3} = frac{-b pm sqrt{b^2 - 4ac}}{2a} = frac{-b}{2a} pm frac{sqrt{b^2 - 4ac}}{2a}.
$$
The amazing thing is that the number $frac{-b}{2a}$ is exactly the number $t_2$, so your solution is
$$
t_{1,3} = t_2 pm frac{sqrt{b^2 - 4ac}}{2a}.
$$
which saves you a tiny bit of computation in applying method 1 in those cases where the planes DO have a potential collision.