Finding the Closest X to Y

Finding the distance between different locations is a programming task that I've done a number of times. The idea seems simple - the user wants to know the closest branch, store, or distributor relative to them. Ignoring some possible use cases (commuting routes, varying convenient starting locations, on-the-way errand stops) you end up with the relatively simple problem of comparing distances between a list of points to a single point.

Follow the Roads with Google Maps Distance Matrix

For the most accurate results I often default to a distance matrix call provided by an online service. The goto for this is Google Maps API. Of course, this is assuming that people will be measuring distance by driving (and not going as-the-crow-flies), which seems reasonable. All you need to do is pass in two sets of parameters: the list of possible destinations and the primary location. The API will return some solid information back, including the interpreted geolocation, level of accuracy, and distance.

// let's say that a google employee wanted to go off-site for lunch
$origin = '1600 Amphitheatre Parkway, Mountain View, CA 94043';

$burger_joints = array(
	'In-N-Out Burger, 1159 N Rengstorff Ave, Mountain View, CA',
	'McDonalds, 1060 N Rengstorff Ave, Mountain View, CA',
	'The Counter, 369 S California Ave, Mountain View, CA',
	'Shoreline Grill, 1020 N Rengstorff Ave, Mountain View, CA');

// all the values need to be safely encoded
$origin = urlencode($origin);
$burger_joints = implode('|', $burger_joints);
$burger_joints = urlencode($burger_joints);

// construct the request to api
$request = '';
$request .= 'http://maps.googleapis.com/maps/api/distancematrix/json';
$request .= "?origins={$origin}";
$request .= "&destinations={$burger_joints}";
$request .= '&sensor=false';

// make the request, pull the response
$response = file_get_contents($request);
$response = json_decode($response);

// just in case something is not accepted
if($response->status != 'OK')
	exit("Huh, there was an error. Response: {$response->status}");

// loop through response
// verify that address was accepted and store in sortable array
$distance_container = array();
foreach($response->rows[0]->elements as $index => $element)
{
	if($element->status != 'OK')
		continue;
	
	$distance = $element->distance->value;
	$address = $response->destination_addresses[$index];
	
	$distance_container[$distance] = $address;
}

// sort by distance!
ksort($distance_container);

Where this approach fails is when you have more than 100 possible locations. The free services are limited to around 100 locations per request (or, like Google's API, 100 locations per 10 seconds or 2500 locations per 24 hours (if you try to get tricky)). If your application could exceed any of these limits you'll either need to pay for the API or try a different solution.

Geocoding, because Address are Meh

Online services (like Google Maps) are nice because they will convert our everyday nomenclature (street addresses) into specific points (latitude and longitude). Once we start moving into custom distance formulas we'll need to use specific points. If you're dealing with street addresses you'll need to convert them into latitude/longitude with a geocoding services. And yes, you can use Google Maps API, although they will only convert so many per unit of time. You should store the coordinates to avoid geocoding on each application load.

// let's find the position of the Googleplex
$address = '1600 Amphitheatre Parkway, Mountain View, CA 94043';
$address = urlencode($address);

// construct the request to api
$request = '';
$request .= 'http://maps.googleapis.com/maps/api/geocode/json';
$request .= "?address={$address}";
$request .= '&sensor=false';

// make the request, pull the response
$response = file_get_contents($request);
$response = json_decode($response);

// just in case something is not accepted
if($response->status != 'OK')
	exit("Huh, there was an error. Response: {$response->status}");

// get the latitude and longitude, which will be in degree format
$latitude = $response->results[0]->geometry->location->lat;
$longitude = $response->results[0]->geometry->location->lng;

Gross Approximation: Welcome to Flatland

Earth is a big place. For short distances you can pretend that the earth is flat (Pythagoras is totally overrated) and do some simple maths (but we'll still use his formula). This gets increasingly inaccurate as the points move away from each other and/or they move towards the poles. If you're worried about such things (or are dealing with distances more than 20 km away) you may want to use a spherical earth projected to a plane.

// if you want the approximate distance, not just relative
$earth_radius = 6371; // km

// Googleplex!
$latitude1 = 37.422163;
$longitude1 = -122.083059;

// that Shoreline Grill sounded nommy
$latitude2 = 37.419192;
$longitude2 = -122.093386;

// deg2rad is not really necessary if you are just comparing
$latitude_difference = deg2rad($latitude1) - deg2rad($latitude2);
$longitude_difference = deg2rad($longitude1) - deg2rad($longitude2);

// flat earth, pythagorean style
$distance = pow($latitude_difference, 2) + pow($longitude_difference, 2);
$distance = sqrt($distance) * $earth_radius; // unnecessary for comparison


// sphere projected on a plane
// note: php cos requires the arg to be in radians
$mean_latitude = ($latitude1 + $latitude2) / 2;
$distance = pow($latitude_difference, 2);
$distance += pow($longitude_difference * cos($mean_latitude), 2);

$distance = sqrt($distance) * $earth_radius; // unnecessary for comparison

Where the flat projection approach really shines is the computation speed. You can simplify these formulas if you aren't truly interested in the distance, just in the relative closeness. After all, the distances may be inaccurate with this method but their relative closeness will be less off.

Spherical Approximation on Perfect Earth

If you are dealing with a lot of varying distances, especially in the latitudinal dimension, the next step for accuracy would use spherical trigonometry. This will get accuracy to about .5%, since Earth is not a perfect sphere (the bulge around the equator). There are two main methods here - tunnels (like, through Earth and stuff) and circles (more like planes flying around). Either one will get you a good idea of relative closeness, while the circle one will get you a better idea of as-the-crow-flies distances.

// if you want the approximate distance, not just relative
$earth_radius = 6371; // km

// Googleplex!
$latitude1 = 37.422163;
$longitude1 = -122.083059;

// still trying to find Shoreline...
$latitude2 = 37.419192;
$longitude2 = -122.093386;

// for tunnels we'll need 'colatitude'
$colatitude1 = 90 - $latitude1;
$colatitude2 = 90 - $latitude2;

// since we're using sine and cosine, everything needs to be converted
$latitude1 = deg2rad($latitude1);
$colatitude1 = deg2rad($colatitude1);
$longitude1 = deg2rad($longitude1);
$latitude2 = deg2rad($latitude2);
$colatitude2 = deg2rad($colatitude2);
$longitude2 = deg2rad($longitude2);

// okay, tunnels first!
$distance = 0;
$distance += pow(cos($colatitude2) * cos($longitude2)
	- cos($colatitude1) * cos($longitude1), 2);
$distance += pow(cos($colatitude2) * sin($longitude2)
	- cos($colatitude1) * sin($longitude1), 2);
$distance += pow(sin($colatitude2) - sin($colatitude1), 2);

// again, this is not necessary if you're just comparing
$distance = sqrt($distance) * $earth_radius;


// if tunnels aren't your thing, try as-the-crow-flies
$distance = 0;
$distance += sin($latitude1) * sin($latitude2);
$distance += cos($latitude1) * cos($latitude2)
	* cos($longitude2 - $longitude1);
$distance = acos($distance);

// unneccessary for vanilla comparisons
$chord *= $earth_radius;

Too Close to Perfection - Ellipsoids

The formulas necessary for trigonometry with ellipsoids are tough and computationally ridiculous. If you are worried about this level of accuracy you'd be better off worrying about how far off your distances are going to be with roads, topology, and lakes. Seriously. I'm not going to talk about ellipsoids.

Conclusion

These different methods can be summed up very nicely based off of the relative number of points you're dealing with and the speed that your application needs to return data by.

• Less than 100 points - use online mapping service
• More than 100 points - use spherical tunnels
• Way more than 100 points - use spherical projected on a plane
• Way, way more than 100 points that are really close - use Pythagorean