Best method for working out locations within a radius of starting point

Question

I'm aiming to create a feature in my latest project preferably using PHP. When each user signs up they are going to input their postcode. Then hopefully I will be converting this to lat/long using Open Street Map.

Anyway, I want to be able to find out other users located near the current user. I have seen a lot of people using the Haversine formula, however this would mean that the user queried every other user's details to work out the distance. I could cache this but its soon going to become outdated as new users sign up.

What sort of effect would running the following query have on my system?

sql = "SELECT zipcode, ( 3959 * acos( cos( radians( {$coords['latitude']} ) ) * cos( radians( latitude ) ) * cos( radians( longitude ) - radians( {$coords['longitude']} ) ) + sin( radians( {$coords['latitude']} ) ) * sin( radians( latitude ) ) ) ) AS distance FROM zipcodes HAVING distance <= {$radius} ORDER BY distance";

Thats pulled from somone's blog.

I dont have any figures for the signup rate or the amount of users as it's still in development.

I would apriciate any feedback or other methods that I could use to find matching users within a specific radius.

Thanks
Jamie

Answer 1

There are GIS and Spatial Extensions to mySql in version 4.1, see here. From the description you will find, that it is used for problems like you have here:

A GIS (geographic information system) stores and looks up objects which have one or more spatial attributes, such as size and position, and is used to process such objects. A simple example would be a system that stores addresses in a town using geographic coordinates. If this rather static data was then combined with other information, such as the location of a taxi-cab, then this data could be used to find the closest cab to a certain location.

It adds several things to MySql like:

• Spacial keys and the POINT type:

  CREATE TABLE address ( address CHAR(80) NOT NULL, address_loc POINT NOT NULL, PRIMARY KEY(address), SPATIAL KEY(address_loc) );

• Conversion routines

  INSERT INTO address VALUES('Foobar street 12', GeomFromText('POINT(2671 2500)'));

• GIS calculation functions

  SELECT c.cabdriver, ROUND(GLength(LineStringFromWKB(LineString(AsBinary(c.cab_loc), AsBinary(a.address_loc))))) AS distance FROM cab c, address a ORDER BY distance ASC LIMIT 1;

(Examples taken from link above)

Answer 2

Admittedly this is Javascript not PHP, but it would be trivial to convert I'd imagine.

It calculates the distance between two points, accounting for the curvature of the Earth. Is used it in a logistics app a while back before replacing it with code that does it using a proper road route.

It might be of use to you....

<script type="text/javascript">
function getDistance(lat1,lng1,lat2,lng2)
 {
  p1 = new VELatLong(lat1,lng1);
  p2 = new VELatLong(lat2,lng2);
  miles = true;
  p1.Latitude= latLonToRadians(p1.Latitude);
  p1.Longitude= latLonToRadians(p1.Longitude);
  p2.Latitude= latLonToRadians(p2.Latitude);
  p2.Longitude= latLonToRadians(p2.Longitude);
  var R = 6371; // earth's mean radius in km
  var dLat  = p2.Latitude- p1.Latitude;
  var dLong = p2.Longitude- p1.Longitude;
  var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
  Math.cos(p1.Latitude) * Math.cos(p2.Latitude) * Math.sin(dLong/2) * 
Math.sin(dLong/2);
  var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
  var disKm = R * c;
  var disMiles = disKm * 0.6214;
  alert (miles ? disMiles : disKm);
 }
 //  convert lat/long in degrees to radians
 function latLonToRadians( point )
 {
  return point * Math.PI / 180;
 }
</script>

Oh, and VELatLong objects come from the Virtual Earth API (http://msdn.microsoft.com/en-us/library/bb412519.aspx), but are basically a glorified struct, so you should be able to find a suitable replacement

Answer 3

The problem can be greatly simplified if you are willing to loosen the definition of "within a certain radius" to not specifically be a circle. If you simplify to a "square", you can find all location within the "radius" with 2 simple "between" clauses (one for lat one for long). eg:

SELECT * FROM location WHERE
  lat BETWEEN (my_lat - radius) AND (my_lat + radius)
  AND long BETWEEN (my_long - radius) AND (my_long + radius);

Of course, this could be used to select a subset of your locations before using a more accurate method to calculate the actual distance to them.