Tim Daneliuk <[EMAIL PROTECTED]> 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. -- http://mail.python.org/mailman/listinfo/python-list
