I was recently searching for the mathematical formula to find closest point of approach (CPA) between one ship and another ship. I need to apply the formula in my radar ship program and I can’t find the correct way to calculates it.
Does anybody know what the correct formula (or pseudo-code) is instead of plotting it manually?
6
Excuse any math errors that might appear below but the basic approach is valid.
You can represent your ships coordinates using parametric equations.
Pxy(t) = (x(t),y(t))
Meaning that the ship’s x-location is represented as a function of time and independently it’s y-location is represented as a function of time.
For example,
Xa(t) = t; Ya(t) = 2t + 5 would represent a straight line with coordinates (0, 5) at t = 0.
Xb(t) = t - 4; Yb(t) = t + 10 would represent a straight line with coordinates (-4, 10) at t = 0.
You then plug in both ships parametric equations into the distance formula to calculate the distance from each other at time = t.
D = sqrt((Xa(t) - Xb(t))2 + ((Ya(t) - Yb(t))2)
Using the above examples
D = sqrt((t - (t -4))2 + ((2t + 5) - (t + 10))2)
D = sqrt(16 + t2 -10t + 25) = sqrt(t2 - 10t + 41)
Then solve the equation for its minimum (t = 5)
Plug in the value for t in the distance formula and you’ve got the minimum distance and the time between the 2 ships.
The cool thing about this method is that your ships don’t have to travel in straight lines (like the example above), as long as their positions can be represented by a function. Of course, the more complex the path the more difficult it is to solve the minimum.
Also, this approach translates to any number of dimensions you want to work in, not just 2-D.
Additionally, it shows one of many uses for that calculus class that everybody thinks was useless for computer science.
If you limit the ships movements to straight lines then this should be relatively straight forward to implement and will run quite quickly. I don’t think there’s a quicker and more accurate way to do this.
Another good thing using this method is that it is deterministic in how long it will take to execute. The other suggestions of increment the time and see what you get could take a very large number of increments to result in an answer. You won’t know how long it takes until you execute it for each situation.
1
If both vessels are moving I would probably just calculate both their positions (based on current heading and speed) for every minute in the next N minutes – and then the Euclidean distance between the two points at each time interval
If one ship is stationary you could do a line-to-point closest distance
9