How can I quickly estimate the distance between two (latitude, longitude) points?

Question

I want to be able to get a estimate of the distance between two (latitude, longitude) points. I want to undershoot, as this will be for A* graph search and I want it to be fast. The points will be at most 800 km apart.

Answer 1

Since the distance is relatively small, you can use the equirectangular distance approximation. This approximation is faster than using the Haversine formula. So, to get the distance from your reference point (lat1/lon1) to the point your are testing (lat2/lon2), use the formula below. Important Note: you need to convert all lat/lon points to radians:

R = 6371  // radius of the earth in km x = (lon2 - lon1) * cos( 0.5*(lat2+lat1) ) y = lat2 - lat1 d = R * sqrt( x*x + y*y ) 

Since 'R' is in km, the distance 'd' will be in km.

Reference: http://www.movable-type.co.uk/scripts/latlong.html

Answer 2

The answers to Haversine Formula in Python (Bearing and Distance between two GPS points) provide Python implementations that answer your question.

Using the implementation below I performed 100,000 iterations in less than 1 second on an older laptop. I think for your purposes this should be sufficient. However, you should profile anything before you optimize for performance.

from math import radians, cos, sin, asin, sqrt def haversine(lon1, lat1, lon2, lat2):     """     Calculate the great circle distance between two points      on the earth (specified in decimal degrees)     """     # convert decimal degrees to radians      lon1, lat1, lon2, lat2 = map(radians, [lon1, lat1, lon2, lat2])     # haversine formula      dlon = lon2 - lon1      dlat = lat2 - lat1      a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2     c = 2 * asin(sqrt(a))      # Radius of earth in kilometers is 6371     km = 6371* c     return km

To underestimate haversine(lat1, long1, lat2, long2) * 0.90 or whatever factor you want. I don't see how introducing error to your underestimation is useful.