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

Question

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.

1. I want to get all cities within 500km radius from a given city.
2. 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.

Answer 1

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

Answer 2

Google App Engine doesn't support geospatial queries, but you could refer to Geospatial Queries with Google App Engine using GeoModel.

You might also want to consider using other databases like mongoDB that support Geospatial Indexing and maybe having it as an external service which does only that.