Velocity Reviews > Looking For Geodetic Python Software

# Looking For Geodetic Python Software

Tim Daneliuk
Guest
Posts: n/a

 06-22-2005
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 http://www.velocityreviews.com/forums/(E-Mail Removed)
PGP Key: http://www.tundraware.com/PGP/

Casey Hawthorne
Guest
Posts: n/a

 06-23-2005
Tim Daneliuk <(E-Mail Removed)> 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

Paul Rubin
Guest
Posts: n/a

 06-23-2005
Tim Daneliuk <(E-Mail Removed)> 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.

Tim Daneliuk
Guest
Posts: n/a

 06-23-2005
Casey Hawthorne wrote:
> Tim Daneliuk <(E-Mail Removed)> 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 (E-Mail Removed)
PGP Key: http://www.tundraware.com/PGP/

Diez B. Roggisch
Guest
Posts: n/a

 06-23-2005
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
Guest
Posts: n/a

 06-23-2005
> 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/algo...cle.php/c5115/

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

http://pyogclib.sourceforge.net/

Diez

Tim Daneliuk
Guest
Posts: n/a

 06-23-2005
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 (E-Mail Removed)
PGP Key: http://www.tundraware.com/PGP/

Rocco Moretti
Guest
Posts: n/a

 06-23-2005
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.

Paul Rubin
Guest
Posts: n/a

 06-23-2005
Tim Daneliuk <(E-Mail Removed)> 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.

Cousin Stanley
Guest
Posts: n/a

 06-23-2005
| ....
| 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 =----

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Fred Javascript 0 10-09-2009 08:09 AM Fred Java 0 10-09-2009 08:08 AM Fred C Programming 0 10-09-2009 08:06 AM info@killetsoft.de Java 0 12-26-2007 01:35 PM info@killetsoft.de C++ 0 12-26-2007 01:35 PM