Calculate distance between cities & find surrounding cities based on GeoPT, in Python on Google App Engine

distance, geolocation, google-app-engine, python

Solution

This works perfect but is a lil slow :

Function to Calculate Distance. The Arguments passed to this function are tuples of latitude and longitude of a location or a Geopt():

def HaversineDistance(location1, location2):
  """Method to calculate Distance between two sets of Lat/Lon."""
  lat1, lon1 = location1
  lat2, lon2 = location2
  earth = 6371 #Earth's Radius in Kms.

 #Calculate Distance based in Haversine Formula
 dlat = math.radians(lat2-lat1)
 dlon = math.radians(lon2-lon1)
 a = math.sin(dlat/2) * math.sin(dlat/2) + math.cos(math.radians(lat1)) * math.cos(math.radians(lat2)) * math.sin(dlon/2) * math.sin(dlon/2)
 c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a))
 d = earth * c
 return d

Function to calculate Surrounding cities within a radius. This is a method under the City model which store all cities:

def get_closest_cities(self, kms):
  cities = []
  #Find surrounding Cities of a given city within a given radius
  allcities = self.country.city_set
  for city in allcities:
    distance = HaversineDistance((self.location.lat, self.location.lon),(city.location.lat, city.location.lon))
    if not distance >= kms:
      cities.append((city.name, int(distance)))
  cities.remove(cities[0])
  return cities

Problem

I have a cities model defined which saves the `geoname_id` and `location` (as GeoPt) of a city. There are two things that I want to achieve. - I want to get all cities within `500km` radius from a given city. - I want to calculate distance in `km` between two given cities. What would be the best way to achieve this, keeping in mind that I have a very large database of cities and I do not want to sacrifice a lot on the performance factor. Any help or advice is appreciated.

Original source