Finding cities close to one another using longitude and latitude

Question

Each user in my db is associated to a city (with it's longitude and latitude)

How would I go about finding out which cities are close to one another?

i.e. in England, Cambridge is fairly close to London.

So If I have a user who lives in Cambridge. Users close to them would be users living in close surrounding cities, such as London, Hertford etc.

Any ideas how I could go about this? And also, how would I define what is close? i.e. in the UK close would be much closer than if it were in the US as the US is far more spread out.

Ideas and suggestions. Also, do you know any services that provide this sort of functionality?

Thanks

Answer 1

Check this thread:

MySQL Great Circle Distance (Haversine formula)

There you have a SQL query to calculate near cities upon latitude and longitude.

Cheers.

Answer 2

If you can call an external web service, you can use the GeoNames API for locating nearby cities within some radius that you define:

http://www.geonames.org/export/web-services.html

Answer 3

Getting coordinates from City names is called reverse geo coding. Google maps has a nice Api fot that.

There is also the Geonames project where you get huge databases of cities, zip codes etc and their cooridnates

However if you already have the coordinates, its a simple calculation to get the distance.

The tricky thing is to get a nice performant version of it. You probably have it stored in a mysql database, so you need to do it there and fast.

It is absolutely possible. I once did a project including that code, I will fetch it and post it here.

However to speed things up I would recommend first doing a rectangular selection around the center coordinates. This is very, very fast using bee tree indexes or even better stuff like multidimensional range search. Then inside that you can then calculate the exact distances on a limited set of data. Outside that recangular selection the directions are so vast that it does not need to be displayed or calculated so accurately. Or just display the country, continent or something like that.

I am still at the office but when i get home i can fetch the codes for you. Int he meantime it would be good if you could inform me how you store your data.

Edit: in the mean time here you have a function which looks right to me (i did it without a function in one query...)

   CREATE FUNCTION `get_distance_between_geo_locations`(`lat1` FLOAT, `long1` FLOAT, `lat2` FLOAT, `long2` FLOAT)
  RETURNS FLOAT
  LANGUAGE SQL
  DETERMINISTIC
  CONTAINS SQL
  SQL SECURITY DEFINER
  COMMENT ''
BEGIN
DECLARE distance FLOAT DEFAULT -1;
DECLARE earthRadius FLOAT DEFAULT 6371.009;
-- 3958.761 --miles
-- 6371.009 --km
DECLARE axis FLOAT;

IF ((lat1 IS NOT NULL) AND (long1 IS NOT NULL) AND (lat2 IS NOT NULL) AND (long2 IS NOT NULL)) THEN -- bit of protection against bad data

  SET axis = (SIN(RADIANS(lat2-lat1)/2) * SIN(RADIANS(lat2-lat1)/2) + COS(RADIANS(lat1)) * COS(RADIANS(lat2)) * SIN(RADIANS(long2-long1)/2) * SIN(RADIANS(long2-long1)/2));
  SET distance = earthRadius * (2 * ATAN2(SQRT(axis), SQRT(1-axis)));

END IF;

RETURN distance;
END;

i quoted this from here: http://sebastian-bauer.ws/en/2010/12/12/geo-koordinaten-mysql-funktion-zur-berechnung-des-abstands.html

and here is another link: http://www.andrewseward.co.uk/2010/04/sql-function-to-calculate-distance.html

Answer 4

The simplest way to do this would be to calculate a bounding box from the latitude and longitude of the city and a distance (by converting the distance to degrees of longitude).

Once you have that box (min latitude, max latitude, min longitude, max longitude), query for other cities whose latitude and longitude are inside the bounding box. This will get you an approximate list, and should be quite fast as it will be able to use any indexes you might have on the latitude and longitude columns.

From there you can narrow the list down if desired using a real "distance between points on a sphere" function.

Answer 5

You need a spatial index or GIS functionality. What database are you using? MySQL and PostgreSQL both have GIS support which would allow you to find the N nearest cities using an SQL query.

Answer 6

Another option you might want to consider would be to put all of the cities into a spatial search tree like a kd-tree. Kd-trees efficiently support nearest-neighbor searches, as well as fast searches for all points in a given bounding box. You could then find nearby cities by searching for a few of the city's nearest neighbors, then using the distance to those neighbors to get an estimate size for a bounding box to search in.