Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
2  
A quick search on google for "Closest Point of Approach" gives back geomalgorithms.com/a07-_distance.html as one of the top results. It has the algorithim and some C++ source with it. –  MichaelT Apr 8 '13 at 2:39
    
@MichaelT You might want to put that as an answer instead of a comment. –  Martin Wickman Apr 8 '13 at 13:35
    
@MartinWickman I would feel bad about giving a link only answer, and my math background isn't up to giving a non-link answer. –  MichaelT Apr 8 '13 at 13:38
    
@MichaelT: However just the link is a better answer than the only one so far (by Martin) –  mattnz Apr 8 '13 at 20:29
    
Whats the requirement - is it truly CPA, or collision avoidance? Col. Avoid. can stop much sooner than CPA processing (Often its easy to confirm CPA > minima and stop processing) –  mattnz Apr 8 '13 at 20:32
show 1 more comment

2 Answers

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 + t^2 -10t + 25) = Sqrt(t^2 - 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.

share|improve this answer
    
maybe it will works! Thanks. I try to understand that formula you gave. –  Syamilsynz Apr 12 '13 at 17:04
add comment

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

share|improve this answer
    
Just a remark. If one ship is stationary, you would have to be aiming for it in order to hit it. Well, okay, not quite, there is also current and wind to consider. However OP seems to be after a collision warning system and stationary ships usually do not figure into that as they are easily avoided, it is other moving ships that need to be assessed continually especially in low visibility conditions where the easy visual assessment (does the bearing change) is out. –  Marjan Venema Apr 8 '13 at 6:58
    
You still have a closest approach to a stationary object. There may be rules that say you can't approach within x km and so this would be a useful feature for a maritime radar system –  Martin Beckett Apr 8 '13 at 12:39
1  
There is no need for the "if one ship is stationary". Just use the line-to-point closest distance calculation using the relative velocity (i.e. do the calculation in the ship frame of reference rather than the earth frame). –  kevin cline Apr 8 '13 at 16:19
    
@kevincline - yes, I meant that If one ship was stationary an exact calculation would be worthwhile. But othewrwise just run a time series ie. simulation. In practice a stationary ship is just the same calcualtion with one having zero speed. –  Martin Beckett Apr 8 '13 at 16:24
1  
@jk - if the ships are far enough apart that you need to consider geodesics then you probably don't need to worry about their point of closest approach! –  Martin Beckett Apr 9 '13 at 15:40
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.