4

This issue I can't really solve till now although I read through several articles already - hope somebody can help here.

Facts (know variables):

  • Two moving objects on earth surface, both with current know latitude/longitude coordinates.
  • The speed of both objects is know as well (in m/s).
  • The direction (angle) of one object is know.

Now I want to calculate the direction (angle) of the second moving object needed to intersect with (hit) the other moving object.

As the distance between the objects is small (in the range of only 5-20 km) and no very high accuracy is needed, it is OK to consider the earth surface as plane.

Therefore I already tried working with this great library: http://www.codeproject.com/Articles/990452/Interception-of-Two-Moving-Objects-in-D-Space

But I don't really get that to work as I don't know how to convert speed in m/s back and forth to latitude/longitude velocity vectors.

To better understand the problem here an example with values:

  • Moving object 1 (runner):
    • Current location: latitude: 38.565, longitude: -98.513
    • Speed: 100 m/s
    • Direction: 270°
  • Moving object 2 (chaser):
    • Current location: latitude: 38.724, longitude: -98.449
    • Speed: 150 m/s
    • Direction: To be calculated

Any help on that would be highly appreciated, thanks in advance!

ab-tools
  • 528
  • 5
  • 18
  • 2
    Don't convert velocity to lat/long vector, that would be very inconvenient. Assume one object starts at the origin, and convert the other object coordinates to metres relative to the origin. – n. m. could be an AI May 16 '16 at 09:06
  • First thanks a lot for your quick comment, but I'm really a bit lost with that: The library linked above would need velocity vectors plus the absolute positions of both objects (not a relative position of the second object to the first one). Seems that I would not be able to use this library then. Do you have a suggestion how to start with the calculation then? Or any other library I can use? Thanks you! – ab-tools May 16 '16 at 09:27
  • 1
    There is no such thing as absolute coordinates in this Universe. All coordinates are relative to something. You are free to choose this something. "The start position of the first object" is as good a starting point as any other. – n. m. could be an AI May 16 '16 at 09:42
  • OK, then runner would be at 0,0 and chaser at 0.159,0.064, right? But that does not solve the "speed problem": How to convert the runner speed to a velocity vector which is needed for the library linked above? Of course, I don't need to use exactly this library, but I just did not find any other algorithm to use yet... Thanks agian for your support! – ab-tools May 16 '16 at 09:52
  • "How to convert the runner speed to a velocity vector". You have an absolute value and an angle. How to convert these to a vector? With trigonometry. – n. m. could be an AI May 16 '16 at 09:59
  • Yes, I tried it like this already: `RunnerVelocity = new SVector2d(speed * Math.Cos(angleRadian), speed * Math.Sin(angleRadian))` and then the result of the calculation back to an angle like this: `ChaserAngleRadian = Math.Atan2(ChaserVelocity.X, ChaserVelocity.Y)`. But the resulting angle was just wrong. Did I make a mistake in these conversions? – ab-tools May 16 '16 at 10:13
  • Atan2 normally requires (y, x). – n. m. could be an AI May 16 '16 at 10:31
  • You're absolutely right, thanks! Unfortunately the chaser object still does not hit the runner... I guess the speed unit doesn't matter here, right? – ab-tools May 16 '16 at 10:56
  • I think you need to ask another question with all relevant data. Of course speed units should correspond to the distance units. – n. m. could be an AI May 16 '16 at 10:59
  • But what other data would be needed beside the data I've provided above? All know values even with a concrete example is written above. Regarding the speed units: I have no distance units in the calculation (see data above), just locations and speeds. Therefore the speed unit should not matter as long it's always the same, right? – ab-tools May 16 '16 at 11:03
  • All data deeded to reproduce the problem. Beside your source data that is already in the post, show intermediate data (coordinates of both objects, velocity vectors) that you feed to the library; the answer you get from the library; and your conversion of the answer to your final format. Distance units are the same as location units, but yes, it shouldn't really matter. – n. m. could be an AI May 16 '16 at 14:35

1 Answers1

10

If the distances are small and you convert the latitude/longitude coordinates to x,y coordinates on a flat plane as you suggest, using e.g. the answers to this question, then the math needed to solve this problem is quite straightforward.

The image below shows the location of chaser and target at time 0 (red and blue dot), their velocity (the circles show their range after time 1, 2, 3...) and the trajectory of the target (blue ray).

The green curve contains all locations where target and chaser could be at the same moment if they keep moving at their current velocity. The intersection of this curve with the target's trajectory is the interception point (pink dot).

moving target interception

If the interception happens after time t, then the distance travelled by chaser and target is t.vc and t.vt. We also know the distance d between the chaser and target at time 0, and the angle α between the line segment connecting chaser and target and the target's trajectory. If we enter these into the cosine rule we get:

(t . vc)2 = (t . vt)2 + d2 - 2 . d . t . vt . cos(α)

Which transforms to this quadratic equation when we solve for time t:

(vc2 - vt2) . t2 + (2 . d . vt . cos(α)) . t - d2 = 0

If we solve this using the quadratic formula:

t = (- b ± √(b2 - 4 . a . c)) / (2 . a)
where:
a = vc2 - vt2
b = 2 . d . vt . cos(α)
c = - d2

a non-negative discriminant means interception is possible, and the root obtained by using addition in the quadratic formula is the first or only time of interception.

interception of faster target

As you can see in the image above, if the chaser is slower than the target, there are potentially two interception points if the target moves towards the chaser (blue ray intersects with green curve), but none if the target moves away from the chaser. Using addition in the quadratic formula gives the first interception point (using subtraction would give the second).

We can then calculate the position of the target after time t, which is the interception point, and the direction from the chaser to this point.


The JavaScript code snippet below demonstrates this method, with the values from both images. It uses angles in radians and the orientation: 0 = right, π/2 = up, π = left, -π/2 = down. The case where the chaser and target have equal velocity (and the curve is a straight line) is solved using the isosceles triangle theorem, because otherwise it would lead to a division by zero in the quadratic equation.

function intercept(chaser, target) {
    var dist = distance(chaser, target);
    var dir = direction(chaser, target);
    var alpha = Math.PI + dir - target.dir;
    // EQUAL VELOCITY CASE: SOLVE BY ISOSCELES TRIANGLE THEOREM
    if (chaser.vel == target.vel) {
        if (Math.cos(alpha) < 0) return NaN;    // INTERCEPTION IMPOSSIBLE
        return (dir + alpha) % (Math.PI * 2);
    }
    // GENERAL CASE: SOLVE BY COSINE RULE AND QUADRATIC EQUATION
    var a = Math.pow(chaser.vel, 2) - Math.pow(target.vel, 2);
    var b = 2 * dist * target.vel * Math.cos(alpha);
    var c = -Math.pow(dist, 2);
    var disc = Math.pow(b, 2) - 4 * a * c;
    if (disc < 0) return NaN;                   // INTERCEPTION IMPOSSIBLE
    var time = (Math.sqrt(disc) - b) / (2 * a);
    var x = target.x + target.vel * time * Math.cos(target.dir);
    var y = target.y + target.vel * time * Math.sin(target.dir);
    return direction(chaser, {x: x, y: y});

    function distance(p, q) {
        return Math.sqrt(Math.pow(p.x - q.x, 2) + Math.pow(p.y - q.y, 2));
    }
    function direction(p, q) {
        return Math.atan2(q.y - p.y, q.x - p.x);
    }
}
var chaser = {x: 196, y: -45, vel: 100};
var target = {x: 139, y: -312, vel: 75, dir: 0.1815142422};
document.write(intercept(chaser, target) + "<br>"); // -1.015 rad = -58.17°
var chaser = {x: 369, y: -235, vel: 37.5};
var target = {x: 139, y: -376, vel: 75, dir: 0.1815142422};
document.write(intercept(chaser, target) + "<br>"); // -1.787 rad = -102.4°

other interception points

The green curve effectively divides the 2D plane into a zone where the target will arrive first, and a zone where the chaser will arrive first. If you want the chaser and the target to move at constant speed and collide (imagine e.g. a torpedo being fired at a moving ship) then you'd aim for a point on the curve, where the two will arrive at the same time, as explained above.

However, if the chaser can go to a point and wait there for the target to arrive (imagine e.g. a person trying to catch a bus), then every point on the target's trajectory that is within the "chaser's zone" could be the interception point.

In the first image (slower target) the curve is a circle around the target, and once the target moves out of this circle (to the right of the interception point indicated in pink), the chaser could always get there first and wait for the target. This could be useful if you want a safety margin in case the chaser's or target's speed isn't constant.

In the second image (faster target) the curve is a circle around the chaser, and every point on the target's trajectory inside this circle could be the interception point. The chaser could e.g. move perpendicular to the target's trajectory, in order to minimise the distance travelled, or aim at a point halfway between the first and last interception point to maximise the waiting time.

  • I know I'm not supposed to say thinks in comments, but this was exactly what I needed, so, thanks! One thing though `target.dir` is as radians right? I dont understand your comment `// -1.015 radians = -58.17 degrees` .. is it just to give an example? seems oddly specific – sch Oct 18 '17 at 09:42
  • @klskl Indeed, the comments in the code give the results of the two examples, and the values are angles in radians. (I added the conversion to degrees in the comments because non-mathematicians will be more used to seeing degrees than radians.) – m69's been on strike for years Oct 18 '17 at 12:39
  • Someone asked [a question](https://stackoverflow.com/questions/57745068/intersection-of-two-moving-objects) about your code – Jonas Wilms Sep 01 '19 at 11:06