# Looking For Geodetic Python Software

Discussion in 'Python' started by Tim Daneliuk, Jun 22, 2005.

1. ### Tim DaneliukGuest

Is anyone aware of freely available Python modules that can do any of

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,
--
----------------------------------------------------------------------------
Tim Daneliuk
PGP Key: http://www.tundraware.com/PGP/

Tim Daneliuk, Jun 22, 2005

2. ### Casey HawthorneGuest

Tim Daneliuk <> wrote:

>Is anyone aware of freely available Python modules that can do any of
>
>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?

--
Regards,
Casey

Casey Hawthorne, Jun 23, 2005

3. ### Paul RubinGuest

Tim Daneliuk <> writes:
> 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.

Paul Rubin, Jun 23, 2005
4. ### Tim DaneliukGuest

Casey Hawthorne wrote:
> Tim Daneliuk <> wrote:
>
>
>>Is anyone aware of freely available Python modules that can do any of
>>
>>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?
>
>
> --
> Regards,
> Casey

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

--
----------------------------------------------------------------------------
Tim Daneliuk
PGP Key: http://www.tundraware.com/PGP/

Tim Daneliuk, Jun 23, 2005
5. ### Diez B. RoggischGuest

Tim Daneliuk wrote:
> Casey Hawthorne wrote:
>>
>> Do your planes fly over the earth's surface or through the ground?

>
>
> 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, Jun 23, 2005
6. ### Diez B. RoggischGuest

> 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

Diez B. Roggisch, Jun 23, 2005
7. ### Tim DaneliukGuest

OT: Re: Looking For Geodetic Python Software

Diez B. Roggisch wrote:
> Tim Daneliuk wrote:
>
>> Casey Hawthorne wrote:
>>
>>>
>>> Do your planes fly over the earth's surface or through the ground?

>>
>>
>>
>> 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

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?

--
----------------------------------------------------------------------------
Tim Daneliuk
PGP Key: http://www.tundraware.com/PGP/

Tim Daneliuk, Jun 23, 2005
8. ### Rocco MorettiGuest

Re: OT: Re: Looking For Geodetic Python Software

Tim Daneliuk wrote:
> Diez B. Roggisch wrote:
>
>> Tim Daneliuk wrote:
>>
>>> Casey Hawthorne wrote:
>>>
>>>>
>>>> Do your planes fly over the earth's surface or through the ground?
>>>
>>>
>>>
>>>
>>> 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

>
>
> 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.

Rocco Moretti, Jun 23, 2005
9. ### Paul RubinGuest

Re: OT: Re: Looking For Geodetic Python Software

Tim Daneliuk <> writes:
> 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.

Paul Rubin, Jun 23, 2005
10. ### Cousin StanleyGuest

| ....
| 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

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 ....

--
Stanley C. Kitching
Human Being
Phoenix, Arizona

----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

Cousin Stanley, Jun 23, 2005
11. ### Tim DaneliukGuest

Re: OT: Re: Looking For Geodetic Python Software

Rocco Moretti wrote:

> Tim Daneliuk wrote:
>
>> Diez B. Roggisch wrote:
>>
>>> Tim Daneliuk wrote:
>>>
>>>> Casey Hawthorne wrote:
>>>>
>>>>>
>>>>> Do your planes fly over the earth's surface or through the ground?
>>>>
>>>>
>>>>
>>>>
>>>>
>>>> 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

>>
>>
>>
>> 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)

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
PGP Key: http://www.tundraware.com/PGP/

Tim Daneliuk, Jun 23, 2005
12. ### Tim DaneliukGuest

Re: OT: Re: Looking For Geodetic Python Software

Paul Rubin wrote:

> Tim Daneliuk <> writes:
>
>>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.

Yeah, after rereading my original question, I realize that it could

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...
----------------------------------------------------------------------------
Tim Daneliuk
PGP Key: http://www.tundraware.com/PGP/

Tim Daneliuk, Jun 23, 2005
13. ### Dennis Lee BieberGuest

Re: OT: Re: Looking For Geodetic Python Software

On 23 Jun 2005 13:57:17 -0700, Paul Rubin <http://>
declaimed the following in comp.lang.python:

>
> 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).

--
> ============================================================== <
> | Wulfraed Dennis Lee Bieber KD6MOG <
> | Bestiaria Support Staff <
> ============================================================== <
> Overflow Page: <http://wlfraed.home.netcom.com/> <

Dennis Lee Bieber, Jun 24, 2005
14. ### Diez B. RoggischGuest

Re: OT: Re: Looking For Geodetic Python Software

Dennis Lee Bieber wrote:
> 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

Diez B. Roggisch, Jun 24, 2005
15. ### paronGuest

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

Tim Daneliuk wrote:
> Is anyone aware of freely available Python modules that can do any of
>
> 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,
> --
> ----------------------------------------------------------------------------
> Tim Daneliuk
> PGP Key: http://www.tundraware.com/PGP/

paron, Jun 24, 2005
16. ### Dennis Lee BieberGuest

Re: OT: Re: Looking For Geodetic Python Software

On Fri, 24 Jun 2005 13:58:50 +0200, "Diez B. Roggisch" <>
declaimed the following in comp.lang.python:

> 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.

--
> ============================================================== <
> | Wulfraed Dennis Lee Bieber KD6MOG <
> | Bestiaria Support Staff <
> ============================================================== <
> Overflow Page: <http://wlfraed.home.netcom.com/> <

Dennis Lee Bieber, Jun 24, 2005
17. ### Dennis Lee BieberGuest

Re: OT: Re: Looking For Geodetic Python Software

On Fri, 24 Jun 2005 16:09:24 GMT, Dennis Lee Bieber
<> declaimed the following in comp.lang.python:

A follow-up:

> 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
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.

--
> ============================================================== <
> | Wulfraed Dennis Lee Bieber KD6MOG <
> | Bestiaria Support Staff <
> ============================================================== <
> Overflow Page: <http://wlfraed.home.netcom.com/> <

Dennis Lee Bieber, Jun 25, 2005
18. ### Diez B. RoggischGuest

Re: OT: Re: Looking For Geodetic Python Software

> 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

Diez B. Roggisch, Jun 25, 2005