views:

545

answers:

5

I need help writing the following method:

def get_new_location(current_location, target_location, distance_travelled):
    ...
    ...
    return new_location

where all locations are (lat,long)

I realize that there are different models for the earth (WGS-84, GRS-80, ...) which take into account the fact that the earth is an ellipsoid. For my purposes, this level of precision is not necessary, assuming a perfect sphere is good enough.

UPDATE

I'm fine tuning my question taking into account some of the responses.

benjismith argues that my question cannot be answered because there is more than one shortest path between points on the globe. He has a lot of backing in the form of votes, so I guess there's something I don't understand, because I disagree.

The midpoint between any two locations on a sphere is a circular arc.

I concede that this is true when two points are at complete opposites. By this I mean that both points, while remaining on the surface of the sphere, could not be any further away from each other. In this case there are infinite number of equidistant paths joining both points. This, however, is an edge case, not the rule. In all other cases, the vast majority of cases, there is a single shortest path.

To illustrate: if you were to hold a string which passed through two points, and pulled it tight, would there not be only one possible path on which the string would settle (except the edge case already discussed)?

Now, prior to asking the question, obtaining the distance between two points and the heading was not a problem.

I guess what I should have asked is if the following is valid:

def get_new_location(current_location, target_location, percent_traveled):
    new_location.lon = (1-percent_traveled)*current_location.lon+percent_traveled*target_location.lon
    new_location.lat = (1-percent_traveled)*current_location.lat+percent_traveled*target_location.lat
    return new_location

If I were to follow this path, would I be following the great-circle, the rhumb line, ... or would I be completely off? (I know these terms now because of Drew Hall's answer.)

+3  A: 

As BenjiSmith said, there are potentially several paths that connect any A & B on the globe, but the two most popular (by far!) are the "great circle" and "rhumb line" paths.

A great circle gives the shortest distance (by constructing a plane from the two points & the center of the earth & following a circular arc in that plane).

A rhumb line maintains a constant heading, trading some distance (can be extreme at high latitudes) for ease of use. That is, in a boat or plane, you simply point at the desired heading and go until you arrive at your destination (whereas with a great circle the heading changes continuously). In mid latitudes the distance penalty isn't too severe.

Be warned, both path types have discontinuities involving the poles and ambiguities when dealing with antipodal points (pts opposite each other on the sphere).


To build a great circle, you'll want to convert the points to 3D cartesian coordinates (I'll leave this step out but it's trivial for a spherical earth & found iteratively for an oblate earth model a la WGS-84).

Let a be the unit vector pointing at the start point from the center of the earth.

Let b be the unit vector pointing at the end point from the center of the earth.

Let r be the radius of the earth.

Let d be the (given) distance traveled.

Construct the unit vector normal to the G.C. plane by taking the cross product of the unit vectors a and b. That is, let n = a x b.

The (given) distance traveled is the length of the arc formed by sweeping the vector ra around n by some angle theta. Recalling that the circumference of the full great circle is 2 * pi * r, we find theta = d/r.

The cartesian point corresponding to the new location is thus found by rotating ra around n by theta radians. Convert that cartesian point to lat/long & you're done.

I won't derive the rhumb line math here, but will say that the Mercator map projection has the property that rhumb lines are straight. You can easily construct a rhumb line with the mercator projection formula, but you'll have to define some error tolerance so you can break the path up into short, straight segments.

Good luck!

Drew Hall
i updated my question taking into account your answer.
carrier
A: 

Here's an online calculator to find the great circle distance from longitude and latitude. All the calculations are in client-side JavaScript, so you can view the page source to see the code. Also, here's a page deriving the equations used in the calculator.

John D. Cook
+1  A: 

Regarding your updated question:

What you seem to be doing is a linear interpolation of lat/lon coordinates. This is a valid path, but it's neither the great circle or the rhumb line. In fact, because meridians converge as latitude increases (in the northern hemisphere, at least), a smooth interpolation in the lat/lon sense would result in an oddly accelerating path on the ground.

If you were describing interpolation in cartesian coordinates, you'd at least be moving in the right plane but the path would cut through the surface of the earth (i.e. it'd be a chord on the great circle, rather than an arc).

Drew Hall
A: 

Your updated sample code would not always follow the correct path.

For a quick example, consider the following two points on the equator in the middle of the pacific ocean:

  • current_location: lat = 0, lon = -179
  • target_location: lat = 0, lon = 179

These two points are very close together (only two degrees of longitude apart), but when percent_traveled is at 0.5, new_location would be: lat = 0, lon = 0, which is a point on the opposite side of the globe.

edit: it gets worse

Consider the follwing two points in the northern hemisphere:

  • current_location: lat = 80, lon = 0
  • target_location: lat = 80, lon = 180

The great circle path between these two points goes directly over the north pole, but new_location would move around the globe, remaining parallel to the equator.

e.James
thanks for you input. you make a valid point. i already had a strategy for dealing with this though, i just didn't want to clutter the example code so that the focus would remain the issue i needed help with.
carrier
Fair enough. I have posted a new answer with some sample code in an effort to answer the original question. Hope it helps!
e.James
+1  A: 
e.James