P: n/a

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 straightline
flying distance, or the actual overground 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 Kruskaltype 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, shortestpath, 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 tu****@tundraware.com
PGP Key: http://www.tundraware.com/PGP/  
Share this Question
P: n/a

Tim Daneliuk <tu****@tundraware.com> wrote: 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 straightline flying distance, or the actual overground distance that accounts for the earth's curvature.
Do your planes fly over the earth's surface or through the ground?

Regards,
Casey  
P: n/a

Tim Daneliuk <tu****@tundraware.com> writes: 1) Given the latitude/longitude of two locations, compute the distance between them. "Distance" in this case would be either the straightline flying distance, or the actual overground 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 latlong to 3D rectangular
coordinates and now the angle between the vectors is
arccos(x dotproduct y). The overground 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 Kruskaltype 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, shortestpath, hill climbing, and so forth. It would be even nicer if one could also simulate different routing schemes (Monte Carlo?).
This is certainly NPhard but there are various standard TSP
heuristics (the ones intended for maps with 2d Euclidean distance may
not work on spherical problems though). "Combinatorial Optimization"
by Steiglitz and Papadimitriou is the standard text on this stuff.  
P: n/a

Casey Hawthorne wrote: Tim Daneliuk <tu****@tundraware.com> wrote:
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 straightline flying distance, or the actual overground 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 tu****@tundraware.com
PGP Key: http://www.tundraware.com/PGP/  
P: n/a

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
"straightlinedistance" makes no sense at all  because that would mean
that you'd have to go underground. So it has no realworldapplication 
unless you actually have undergroundplanes ;)
Diez  
P: n/a

> 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 latlong to 3D rectangular coordinates and now the angle between the vectors is arccos(x dotproduct y). The overground 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/algo...cle.php/c5115/
Maybe for python, this is enteresting (haven't used it myself though): http://pyogclib.sourceforge.net/
Diez  
P: n/a

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 "straightlinedistance" makes no sense at all  because that would mean that you'd have to go underground. So it has no realworldapplication  unless you actually have undergroundplanes ;)
Diez
Huh? When traversing along the surface of the earth, it's curvature
is relevant in computing total distance. An airplane flies moreorless
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 overearth path is possible. That's why I specified the
desire to compute both path lengths. Where's the humor?


Tim Daneliuk tu****@tundraware.com
PGP Key: http://www.tundraware.com/PGP/  
P: n/a

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 "straightlinedistance" makes no sense at all  because that would mean that you'd have to go underground. So it has no realworldapplication  unless you actually have undergroundplanes ;)
Diez
Huh? When traversing along the surface of the earth, it's curvature is relevant in computing total distance. An airplane flies moreorless 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 overearth path is possible. That's why I specified the desire to compute both path lengths. Where's the humor?
If you reread 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 straightline flying distance, or the actual overground 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 (~1020 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.  
P: n/a

Tim Daneliuk <tu****@tundraware.com> writes: Huh? When traversing along the surface of the earth, it's curvature is relevant in computing total distance. An airplane flies moreorless 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 overearth 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 3dimensional 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 3space.  
P: n/a

 ....
 1) Given the latitude/longitude of two locations, compute the distance
 between them.

 "Distance" in this case would be either the straightline
 flying distance, or the actual overground distance that accounts
 for the earth's curvature.
# 
NewsGroup .... alt.comp.freeware
Date ......... 20031228
Posted_By .... GRL
Reply_By ..... Sascha Wostmann
the formula is as follows:
D = ACos((Sin(LA1)*Sin(LA2)) + (Cos(LA1)*Cos(LA2)*Cos(LO1LO2))) * 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  UnlimitedUncensoredSecure Usenet News== http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
= East and WestCoast Server Farms  Total Privacy via Encryption =  
P: n/a

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 "straightlinedistance" makes no sense at all  because that would mean that you'd have to go underground. So it has no realworldapplication  unless you actually have undergroundplanes ;)
Diez
Huh? When traversing along the surface of the earth, it's curvature is relevant in computing total distance. An airplane flies moreorless 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 overearth path is possible. That's why I specified the desire to compute both path lengths. Where's the humor?
If you reread 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 > straightline > flying distance, or the actual overground 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 (~1020 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 tu****@tundraware.com
PGP Key: http://www.tundraware.com/PGP/  
P: n/a

Paul Rubin wrote: Tim Daneliuk <tu****@tundraware.com> writes:
Huh? When traversing along the surface of the earth, it's curvature is relevant in computing total distance. An airplane flies moreorless 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 overearth 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 3dimensional 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 3space.
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 overground 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 tu****@tundraware.com
PGP Key: http://www.tundraware.com/PGP/  
P: n/a

On 23 Jun 2005 13:57:17 0700, Paul Rubin <http://ph****@NOSPAM.invalid>
declaimed the following in comp.lang.python: B) By a straight line you could also mean the straight line through the 3dimensional 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).
 ================================================== ============ < wl*****@ix.netcom.com  Wulfraed Dennis Lee Bieber KD6MOG < wu******@dm.net  Bestiaria Support Staff < ================================================== ============ < Home Page: <http://www.dm.net/~wulfraed/> < Overflow Page: <http://wlfraed.home.netcom.com/> <  
P: n/a

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 multimilliondollar heavy airplanes...
Diez  
P: n/a

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/projectio...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 the following tasks:
1) Given the latitude/longitude of two locations, compute the distance between them. "Distance" in this case would be either the straightline flying distance, or the actual overground 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 Kruskaltype 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, shortestpath, 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 tu****@tundraware.com PGP Key: http://www.tundraware.com/PGP/  
P: n/a

On Fri, 24 Jun 2005 13:58:50 +0200, "Diez B. Roggisch" <de***@web.de>
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 multimilliondollar 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 airtoair collision detect systems get more
pervasive, so the pilots can respond to multiple craft intersecting the
same space.
 ================================================== ============ < wl*****@ix.netcom.com  Wulfraed Dennis Lee Bieber KD6MOG < wu******@dm.net  Bestiaria Support Staff < ================================================== ============ < Home Page: <http://www.dm.net/~wulfraed/> < Overflow Page: <http://wlfraed.home.netcom.com/> <  
P: n/a

On Fri, 24 Jun 2005 16:09:24 GMT, Dennis Lee Bieber
<wl*****@ix.netcom.com> declaimed the following in comp.lang.python:
A followup: 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 transoceanic 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
deadreckoning (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 transoceanic 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.
 ================================================== ============ < wl*****@ix.netcom.com  Wulfraed Dennis Lee Bieber KD6MOG < wu******@dm.net  Bestiaria Support Staff < ================================================== ============ < Home Page: <http://www.dm.net/~wulfraed/> < Overflow Page: <http://wlfraed.home.netcom.com/> <  
P: n/a

> The article implied that the automated system would allow for /shorter paths/ (the shortest path is the great circle, so this statement indicates that transoceanic 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   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 3303
 replies: 17
 date asked: Jul 19 '05
