Looking For Geodetic Python Software

[Tim Daneliuk]

Is anyone aware of freely available Python modules that can do any of
the following tasks:

1) Given the latitude/longitude of two locations, compute the distance
between them. "Distance" in this case would be either the straight-line
flying distance, or the actual over-ground distance that accounts for
the earth's curvature.

2) Given n latitude/longitude coordinates, compute the
"geocenter". That is, return the lat/long of the location that
is most "central" to all n initial coordinates.

3) Given n lat/long coordinates, compute a Kruskal-type spanning
tree.

4) Given n lat/long coordinates, compute an optimal (shortest or longest)
visitation path that reaches each node exactly once. Better still would
be something that had "pluggable" heuristic engines so we could try
different approaches like greedy, shortest-path, hill climbing, and
so forth. It would be even nicer if one could also simulate different
routing schemes (Monte Carlo?).

In effect, I'm looking for something that mates traditional graph traversal
heuristics with operations research tools working on a geodetic
coordinate system. This is *waaaaay* outside my field of expertise so
I'm hoping someone has taken the pain of it for dummies like me

TIA,

 

[Casey Hawthorne]

Is anyone aware of freely available Python modules that can do any of
the following tasks:

1) Given the latitude/longitude of two locations, compute the distance
between them. "Distance" in this case would be either the straight-line
flying distance, or the actual over-ground distance that accounts for
the earth's curvature.

Do your planes fly over the earth's surface or through the ground?

 

[Paul Rubin]

1) Given the latitude/longitude of two locations, compute the distance
between them. "Distance" in this case would be either the straight-line
flying distance, or the actual over-ground distance that accounts for
the earth's curvature.

For spherical earth, this is easy, just treat the 2 locations as
vectors whose origin is at the center of the earth and whose length is
the radius of the earth. Convert the lat-long to 3-D rectangular
coordinates and now the angle between the vectors is
arccos(x dotproduct y). The over-ground distance is then just R*theta
where theta is the angle.

2) Given n latitude/longitude coordinates, compute the
"geocenter". That is, return the lat/long of the location that
is most "central" to all n initial coordinates.

Not sure what this is.

3) Given n lat/long coordinates, compute a Kruskal-type spanning
tree.

Not sure what this is.

4) Given n lat/long coordinates, compute an optimal (shortest or longest)
visitation path that reaches each node exactly once. Better still would
be something that had "pluggable" heuristic engines so we could try
different approaches like greedy, shortest-path, hill climbing, and
so forth. It would be even nicer if one could also simulate different
routing schemes (Monte Carlo?).

This is certainly NP-hard but there are various standard TSP
heuristics (the ones intended for maps with 2-d Euclidean distance may
not work on spherical problems though). "Combinatorial Optimization"
by Steiglitz and Papadimitriou is the standard text on this stuff.

 

[Tim Daneliuk]

Do your planes fly over the earth's surface or through the ground?

Why do you presume this has anything to do with airplanes?

 

[Diez B. Roggisch]

Why do you presume this has anything to do with airplanes?

That was supposed to be a funny remark regarding that your
"straight-line-distance" makes no sense at all - because that would mean
that you'd have to go underground. So it has no real-world-application -
unless you actually have underground-planes

Diez

 

[Diez B. Roggisch]

For spherical earth, this is easy, just treat the 2 locations as

vectors whose origin is at the center of the earth and whose length is
the radius of the earth. Convert the lat-long to 3-D rectangular
coordinates and now the angle between the vectors is
arccos(x dotproduct y). The over-ground distance is then just R*theta
where theta is the angle.

It's a bit more complicated in the real world - usually one takes a
spheroid as defined by the wgs84 standard:

http://www.codeguru.com/Cpp/Cpp/algorithms/article.php/c5115/

Maybe for python, this is enteresting (haven't used it myself though):

http://pyogclib.sourceforge.net/


Diez

 

[Tim Daneliuk]

That was supposed to be a funny remark regarding that your
"straight-line-distance" makes no sense at all - because that would mean
that you'd have to go underground. So it has no real-world-application -
unless you actually have underground-planes

Diez

Huh? When traversing along the surface of the earth, it's curvature
is relevant in computing total distance. An airplane flies more-or-less
in a straight line above that curvature. For sufficiently long airplane
routes (where the ascent/descent distance is trivial compared to the
overall horizontal distance traversed), a straight line path shorter
than the over-earth path is possible. That's why I specified the
desire to compute both path lengths. Where's the humor?

 

[Rocco Moretti]

Huh? When traversing along the surface of the earth, it's curvature
is relevant in computing total distance. An airplane flies more-or-less
in a straight line above that curvature. For sufficiently long airplane
routes (where the ascent/descent distance is trivial compared to the
overall horizontal distance traversed), a straight line path shorter
than the over-earth path is possible. That's why I specified the
desire to compute both path lengths. Where's the humor?

If you re-read what you wrote you'll see the phrase "straight line
flying distance.":

> 1) Given the latitude/longitude of two locations, compute the distance
> between them. "Distance" in this case would be either the
> straight-line
> flying distance, or the actual over-ground distance that accounts
> for the earth's curvature.

Casey was pointing out that, due to the convex curvature of the Earth, a
"straight line" between, say, Hong Kong and New York would happen to
pass several miles below the surface of California. For an extreme
example, a Euclidean straight line from the North pole to the south pole
would pass through the center of the earth. Note that you've attached
"Flying distance" to the phrase "Straight line" - Hollywood not
withstanding, there isn't a machine able to "fly" through the center of
the earth. The fact that it might be an unintentional error only adds to
the humor. (c.f Freudian Slips)

Given the relative thinness of the atmosphere (~10-20 km) in comparison
with the radius of the earth (~6,400 km), any plane flight of a
considerable distance will be curved in the Euclidean sense, no matter
how they changed their altitude inbetween.

 

[Paul Rubin]

Huh? When traversing along the surface of the earth, it's curvature
is relevant in computing total distance. An airplane flies more-or-less
in a straight line above that curvature. For sufficiently long airplane
routes (where the ascent/descent distance is trivial compared to the
overall horizontal distance traversed), a straight line path shorter
than the over-earth path is possible. That's why I specified the
desire to compute both path lengths. Where's the humor?

It's just not clear what you meant:

A) The shortest path between two points on a curved surface is
called a geodesic and is the most meaningful definition of
"straight line" on a curved surface. The geodesic on a sphere is
sometimes called a "great circle".

B) By a straight line you could also mean the straight line through
the 3-dimensional Earth connecting the two points on the surface.
So the straight line from the US to China would go through the
center of the earth.

C) Some people seem to think "straight line" means the path you'd
follow if you took a paper map, drew a straight line on it with a
ruler, and followed that path. But that path itself would depend
on the map projection and is generally not a geodesic, and neither
is it straight when you follow it in 3-space.

 

[Cousin Stanley]

| ....
| 1) Given the latitude/longitude of two locations, compute the distance
| between them.
|
| "Distance" in this case would be either the straight-line
| flying distance, or the actual over-ground distance that accounts
| for the earth's curvature.

# ---------------------------------------------------------------

NewsGroup .... alt.comp.freeware
Date ......... 2003-12-28
Posted_By .... GRL
Reply_By ..... Sascha Wostmann

the formula is as follows:

D = ACos((Sin(LA1)*Sin(LA2)) + (Cos(LA1)*Cos(LA2)*Cos(LO1-LO2))) * r

with:

LA1 / LA2 = latitude position 1 / 2
LO1 / LO2 = longitude 1 / 2
r = radius of earth (~ 6371 km = ~3958,75 miles)
D = distance between locations (in km or miles depending on r)

Source: somewhere below http://geoclassphp.sourceforge.net

# ----------------------------------------------------------------

About 18 months ago I put together a couple of small Python programs
to compute great circle distances from the above formula ....

http://fastq.com/~sckitching/Python/gcircle.py
[ 2.6 kb ]

http://fastq.com/~sckitching/Python/gcircle_dms.py
[ 3.4 kb ]

The first prompts the user for Lat/Long in fixed point degrees.

The second prompts the user of Lat/Long in degrees minutes seconds.

I only checked a few distances known distances at the time,
but they seemed to be OK ....

 

[Tim Daneliuk]

If you re-read what you wrote you'll see the phrase "straight line
flying distance.":


Casey was pointing out that, due to the convex curvature of the Earth, a
"straight line" between, say, Hong Kong and New York would happen to
pass several miles below the surface of California. For an extreme
example, a Euclidean straight line from the North pole to the south pole
would pass through the center of the earth. Note that you've attached
"Flying distance" to the phrase "Straight line" - Hollywood not
withstanding, there isn't a machine able to "fly" through the center of
the earth. The fact that it might be an unintentional error only adds to
the humor. (c.f Freudian Slips)

Yikes! And I thought I was being clear. Sigh ... back to English 101
for moi.

Given the relative thinness of the atmosphere (~10-20 km) in comparison
with the radius of the earth (~6,400 km), any plane flight of a
considerable distance will be curved in the Euclidean sense, no matter
how they changed their altitude inbetween.

OK, now *I* get the joke too Sorry for being obtuse ...

 

[Tim Daneliuk]

It's just not clear what you meant:

A) The shortest path between two points on a curved surface is
called a geodesic and is the most meaningful definition of
"straight line" on a curved surface. The geodesic on a sphere is
sometimes called a "great circle".

B) By a straight line you could also mean the straight line through
the 3-dimensional Earth connecting the two points on the surface.
So the straight line from the US to China would go through the
center of the earth.

C) Some people seem to think "straight line" means the path you'd
follow if you took a paper map, drew a straight line on it with a
ruler, and followed that path. But that path itself would depend
on the map projection and is generally not a geodesic, and neither
is it straight when you follow it in 3-space.

Yeah, after rereading my original question, I realize that it could
be read that way. My Bad. What I had in mind was this:


A ------------------------------


E ---------------------------
/ \
/ \


Where A was an airplane's line of flight between endponts and E was the
great circle (geodesic) distance over ground. It seemed to me that if
the ascent/descent distance for A is very small compared to the length of A,
the flight distance would be shorter than the over-ground distance. But,
as Rocco points out in another response, this is not so.

I stand (well, sit, actually) corrected!

Many thanks to all of you who took the time to unscramble my English and
lack of geometric understanding...

 

[Dennis Lee Bieber]

B) By a straight line you could also mean the straight line through
the 3-dimensional Earth connecting the two points on the surface.
So the straight line from the US to China would go through the
center of the earth.

No, it wouldn't... The US and China are both in the northern
hemisphere, so a straight line through the earth would pass noticeably
north of the center (and probably to one side, depending on start/end
longitude). In order to pass through the center, one would need a sign
change in latitude (along with a 180deg rotation in longitude).

Of course, the great circle arc, except for paths with start/end
latitude of 0 (equator) or with (lon1 - lon2) = 0, require a constant
variation in compass heading -- and I don't think IFR currently make use
of great circle arcs (and GPS to maintain them).

--

 

[Diez B. Roggisch]

Of course, the great circle arc, except for paths with start/end
latitude of 0 (equator) or with (lon1 - lon2) = 0, require a constant
variation in compass heading -- and I don't think IFR currently make use
of great circle arcs (and GPS to maintain them).

I'm not totally sure what you mean by IFR - but I know for certain that
intercontinental flights do flight on great circles - as this saves
considerable amounts of distance and thus time, fuel and money. And GPS
isn't exactly news on multi-million-dollar heavy airplanes...


Diez

 

[paron]

Howard Butler http://hobu.biz/ has some nice Python wrappers for gdal
and Frank Warmerdam's other tools. I have to say, though, that geodesy
is inherently complicated. Python makes it easy to program, but not
easy to understand. http://maps.hobu.net:7080/RPC2 is an XMLRPC service
that he exposes that will transform various coordinate systems: take a
look at http://hobu.biz/index_html/projection_service/blogentry_view to
see what I mean.

Ron Phillips

 

[Dennis Lee Bieber]

I'm not totally sure what you mean by IFR - but I know for certain that
intercontinental flights do flight on great circles - as this saves
considerable amounts of distance and thus time, fuel and money. And GPS
isn't exactly news on multi-million-dollar heavy airplanes...

Instrument Flight Rules

So far as I recall, the FAA (for US at least) has not approved
GPS paths. Long flights tend to run plumb line segments mapping straight
(by compass) lines onto a great circle -- sort of "fly one hour on
heading X1, turn to X1 for second hour, X3 for third hour..." Partly
this is also the air traffic control system wanting "corridors" that
they can maintain spacing in -- proposals to permit "free flight" seem
to be held up until air-to-air collision detect systems get more
pervasive, so the pilots can respond to multiple craft intersecting the
same space.

--

 

[Dennis Lee Bieber]

So far as I recall, the FAA (for US at least) has not approved
GPS paths. Long flights tend to run plumb line segments mapping straight

USAToday had a short blurb on something the FAA/Air Traffic
Control is implementing for trans-oceanic flights, which is expected to
be in place over the next few years. Automated position reports.

Currently, the air traffic control system relies upon the pilots
reporting, at 50 minute intervals, their position, so ATC can update the
pointers on the route maps. Between those updates, ATC is likely using
dead-reckoning (compass heading and airspeed) to estimate potential
close approaches.

The article implied that the automated system would allow for
/shorter paths/ (the shortest path is the great circle, so this
statement indicates that trans-oceanic flights are not using great
circle/GPS routing). Most likely, the flights are using 50 minute "plumb
lines", with a heading change at the 50 minute mark, so current position
and new heading can be reported to ATC. GPS may be supplying the pilots
with position info, but they may not be free to make the constant
heading changes... The automated system may send this information
digitally at much higher rate than 50 minutes, allowing ATC to plot near
realtime positions.

--

 

[Diez B. Roggisch]

The article implied that the automated system would allow for

/shorter paths/ (the shortest path is the great circle, so this
statement indicates that trans-oceanic flights are not using great
circle/GPS routing). Most likely, the flights are using 50 minute "plumb
lines", with a heading change at the 50 minute mark, so current position
and new heading can be reported to ATC. GPS may be supplying the pilots
with position info, but they may not be free to make the constant
heading changes... The automated system may send this information
digitally at much higher rate than 50 minutes, allowing ATC to plot near
realtime positions.

Looks as if I stand corrected - I remember clearly when we were
introduced to great circles in school, that the example given were
intercontinental flights. So it appears that they use a discretization
scheme that our teacher embezzled. Terry Pratchett calls that "Lies for
kids".

On further thinking, it makes sense that it's not allowed to constantly
change heading - it makes the course estimation for e.g. approaching
aircrafts complicated.

Thanks for pointing that out!


Diez