Design Question: how to determine distance between multiple lat/long points?

Question

Planning on developing a LAMP web application that allow users to specify their location. I could possibly use Google Map API to convert their location into lat/long coordinates. Assume each user has lat/long coordinates, how do I do the following:

• display the distance between 2 users?
• search for users within a given radius?

UPDATE: SOLUTION USING MySQL: MySQL Great Circle Distance (Haversine formula)

Answer 1

http://en.wikipedia.org/wiki/Haversine_formula

This could be implemented in a stored procedure or in code depending on the amount of data you will have and the specific situation for your application.

I created a stored proc a while back that implemented this calculation as a DistanceBetween() function and it worked well.

Answer 2

In php this is something like

function getDistance($latitude1, $longitude1, $latitude2, $longitude2) {
   $radius = 6371; //For Earth, the mean radius is 6,371.009 km

    $dLat = deg2rad($latitude2 - $latitude1);
    $dLon = deg2rad($longitude2 - $longitude1); 

    $a = sin($dLat/2) * sin($dLat/2) + cos(deg2rad($latitude1)) * cos(deg2rad($latitude2)) * sin($dLon/2) * sin($dLon/2);

    $c = 2 * asin(sqrt($a));

    $d = $radius * $c; 

    return $d;
}

I have seen this implemented in sql aswell

Answer 3

Do you think your users would be willing to type in their zip code? If so, you can eliminate the Google Map API entirely and just query a mySQL table to get their latitude and longitude. I found a few free zip code tables (using google) that had lat, lon values in them. Well, actually they were .csv files, but mySQL can import them just fine.

Using PHP, you can display the users within a given radius like this. Modify this as you wish.

<?
// Define your parameters. Usually, you'd get these from a db or passed in from a form.
$zip = "80233";
$distance = 10; // In miles

// Open up a connection to the poc database
$dbh = mysql_connect ("localhost", "zipcodeDB", "YourDBPassword");
$db = mysql_select_db ("zipcodeDB", $dbh);

// Get the latitude and longitude of the zipcode that was passed
$query = "SELECT * FROM zipcodes WHERE zip=$zip LIMIT 1";
$result = mysql_query($query);
$row = mysql_fetch_object($result);
$knownLat = $row->latitude;
$knownLon = $row->longitude;

// Get a range of latitudes and longitudes to limit the search by 
// so we don't have to search the entire zipcodes table
$latRange = $distance / 69.0499;
$longRange = $distance / (69.0499 * COS(deg2rad($knownLat)));
$latMinRange = $knownLat - $latRange; 
$latMaxRange = $knownLat + $latRange; 
$longMinRange = $knownLon - $longRange; 
$longMaxRange = $knownLon + $longRange; 

// Get all of the users within the passed distance
$query = "SELECT * FROM users 
        JOIN zipcodes ON users.zip=zipcodes.zip 
         AND ((latitude >= $latMinRange AND latitude <= $latMaxRange AND longitude >= $longMinRange AND longitude <= $longMaxRange) AND 
         ((2*3960*ASIN(SQRT(POWER(SIN((RADIANS($knownLat-latitude))/2),2)+COS(RADIANS(latitude))*COS(RADIANS($knownLat))*POWER(SIN((RADIANS($knownLon-longitude))/2),2))))) < $distance)";

$result = mysql_query($query);

// Display the users that are within the set distance
while($row = mysql_fetch_object($result)) {
echo $row->UserName . "<br>";
}

// Close the database
mysql_close($dbh);

exit;

?>

Answer 4

Here is a MySQL stored function I wrote only the other day to calculate Haversine distance:

In this question:

Why does this MySQL stored function give different results than to doing the calculation in the query?

Usage:

SELECT haversine(lat1,lng1,lat2,lng2,units);

Answer 5

You can use the Haversine formula for the first bullet point.

The second issue of finding users within a given radius is a bit more interesting. This is because you probably don't want to apply that formula against every other user in the world to see if they are in your radius or not, as that would be very time-consuming. Instead, I would use an approximation.

One approximation method is to:

1. Find the maximum-minimum possible latitude points in the radius (make sure to account for the poles). Lets say you end up with 20-30 degrees latitude.
2. Split that latitude into n parts. Let's say you choose n=4, which would give the latitude ranges of 20-22.5, 22.5-25, 25-27.5, 27.5-30.
3. For each of these ranges, find the highest and lowest possible longitude values. For example, it might be 45-60 longitude in the 22.5-25 range, and 42-63 longitude in the 25-27.5 latitude range.
4. Check that the users fall into one of the ranges. For example, a user at 26 lat. 42 lon. would fall in our radius, but a user at 23 lat. 43 lon. would fall outside our radius.

Note: you can get as accurate as you want with this method by making a higher value of n, but you must balance that accuracy against the performance hit you are taking.

Answer 6

If you are using MySQL 5.7 you can use built-in function Spacial Distance: ST_Distance_Sphere This way is fastest and most convinient.

https://dev.mysql.com/doc/refman/5.7/en/spatial-convenience-functions.html#function_st-distance-sphere

Example:

SELECT ST_Distance_Sphere( point(lon1, lat1), point(lon2, lat2) )

Please bear in mind that if you are using MariaDB instead of MySQL this function is not available.