5

I have a graph in which each node is a geographical point on the surface of the earth, defined by it's latitude / longitude coordinates.

Correct ways to calculate the distance between two such points could be the Haversine Formula for spherical earth models, or Vincenty's inverse problem for spheroidal earth models.

But these are very costly in terms of computational resources, and in A* basically you don't need the absolute values of those results, you only need them for comparison purposes.

In my A* algorithm the heuristic function is the shortest distance between 2 points (defined as the length of the smaller great circle arc between the 2 points in a spherical model), and the actual path between two nodes is a linestring, whose length is calculated basically in the same way, just that you sum distances between consecutive vertices.

So, if d(A, B) is the actual geographical distance between A and B (as latitude / longitude points), the problem basically is to find the most computationally efficient distance estimator d*(A, B) that satisfies conditions needed for A* to work properly, such as:

  • if d(A, B) < d(C, D) then d*(A, B) < d*(C, D).
  • if d(A, B) + d(E, F) < d(C, D) then d*(A, B) + d*(E, F) < d*(C, D)

I even saw in some places that people recommend Euclidean distance for such a case, even though latitude / longitude are angles. It may be the case, but I'm interested if it's "mathematically correct" to assume that it satisfies conditions such as above.

  • I was taught that an acceptible estimator just needed to have d*(A,B) < d(A,B), There are some nicer properties for monotonic heuristics d*(A,F) < d(A,B)+d*(B,F) but non monotonic work just fine. – ratchet freak Jan 22 '15 at 14:48
5

If the area where the nodes can be is small (relatively, the size of half the US is small enough) and away from the poles then you can reasonably approach the problem using just the longitude and latitude as X/Y coordinates. Near the poles you can treat them as polar coordinates with the 90°-latitude as the distance from center and the longitude as the angle from the x-axis.

If you are working across the globe you can transform the lat/lon into a point on a 3D unit sphere, then take the euclidean distance between them. The length of the chord between the 2 points. (2 sin and cos for each coordinate (precomputed), plus a square root). This is however poorly conditioned when the points are close together. Another option instead of the euclid distance is to get the dot product between them and find the acos of it. This will result in the angle between the points.

  • Hmm, it seems to me that the second part is actually better when the points are close to each other. Then the Euclidian distance path will be close to the shortest path on the sphere surface. But when they are on the opposite sides of the Earth - the Euclidian distance will give Pi times less distance than is real. – Ordous Jan 22 '15 at 14:20
  • @Ordous except on earth scale a second (1/3600 of a degree or 5*10^-6 radians) is ~30m , it all depends on the scale – ratchet freak Jan 22 '15 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.