Find The Nearest Location From An Array of Coordinates In PHP

As I discussed in previous tutorials, we have the visitor's latitude and longitude, and an array of locations. Now we can combine the two to figure out which location in that array is closest to our starting coordinates.

What is the fastest way to find the nearest location out of an array of coordinates?

  1. Import the array of coordinates
  2. Based on the array of coordinates, create another array of the respective distances from the initial location
  3. Sort the second array from smallest to largest
  4. Use the key of the first array element from the second array to get the details of the closest location from the first array

Phew that list sounds a bit daunting! Let's see the code first:

$locations = array (
 array (
  "postcode" => "2850",
  "name" => "Aarons Pass",
  "state_code" => "NSW",
  "lat" => "-32.86328",
  "lng" => "149.80375"
 ),
 array (
  "postcode" => "6280",
  "name" => "Abba River",
  "state_code" => "WA",
  "lat" => "-33.68488",
  "lng" => "115.46334"
 ),
 array (
  "postcode" => "6280",
  "name" => "Abbey",
  "state_code" => "WA",
  "lat" => "-33.66077",
  "lng" => "115.25863"
 )
 ...
);

$base_location = array(
  'lat' => "-31.959138",
  'lng' => "115.858072"
);

$distances = array();

foreach ($locations as $key => $location)
{
  $a = $base_location['lat'] - $location['lat'];
  $b = $base_location['lng'] - $location['lng'];
  $distance = sqrt(($a**2) + ($b**2));
  $distances[$key] = $distance;
}

asort($distances);

$closest = $locations[key($distances)];

echo "Closest foreach suburb is: " . $closest['name'];

Not so daunting after all. Let's explore what's happening in the code.

Import the array of coordinates

In my earlier post on importing a CSV file into an array, I covered a quick way to import a lot of data to an array.

I've written the code as above for this tutorial simply for clarity. Because there are so many suburbs in the $locations array, I actually put it in a file called locations.php and called it using:

require('locations.php');

That does the same thing. It just makes it easier to manage.

Based on the array of coordinates, create another array of the respective distances from the initial location

The guts of this code is turning $locations into an array of distances from the base coordinates. I've called that array $distances.

The key of each element in $distances will be the same as the key for that same element in $locations. This is essential for this code to function later.

We start with our initial location:

$base_location = array(
  'lat' => "-31.959138",
  'lng' => "115.858072"
);

You might pull this in dynamically using $_GET.

You might also use it on the fly with an AJAX call from jQuery based on the visitor's location. I wrote about how to get that here.

Next comes the algorithm for calculating the distance from the base location.

I've tested this quite extensively in preparation for this tutorial. Pythagorean Theorem was the fastest and best suited to this project.

See the end of this tutorial for how the tests performed and the code for the other formulae.

The code for looping over each $locations location and calculating how far it is from $base_location is:

$distances = array();

foreach ($locations as $key => $location)
{
  $a = $base_location['lat'] - $location['lat'];
  $b = $base_location['lng'] - $location['lng'];
  $distance = sqrt(($a**2) + ($b**2));
  $distances[$key] = $distance;
}

You could make it smaller by putting $a and $b into the one line, but I broke it apart to make it clear how the algorithm works.

If you want to use a different algorithm, swap out the first three lines inside of the foreach loop.

Normally I'd use more descriptive variables, but years of schooling has me automatically remembering that

a2 + b2 = c2

I'm sure you probably do too.

In case you weren't familiar with the format, $a**2 is PHP for a2. This change came in with PHP 5.6, which if you're reading this, you absolutely should be using that or later.

If you're stuck using an earlier version of PHP, swap $a**2 for

pow($a, 2)

After this foreach loop has finished running, we now have an array of distances from the base location in $distances. It will look something like this:

Array
(
  [0] => 33.957716761229
  [1] => 1.7703103689433
  [2] => 1.8041292012459
  [3] => 31.298059163015
  [4] => 36.246295056854
  [5] => 35.0622192721
)

Note: these aren't actual distances in kilometres or miles. These are relative distances. They also don't take into account the curvature of the Earth. If you need actual distances, you're best to use the Haversine Formula discussed at the bottom

Sort the second array from smallest to largest

Sorting the $distances array from smallest to largest is as simple as:

asort($distances);

Now the array looks like this:

Array
(
  [10712] => 0.0037737207103849
  [10026] => 0.012187097603613
  [4258] => 0.013816152431116
  [14330] => 0.016617217215894
  [12192] => 0.022168618991717
  [6076] => 0.02274286806891
)

If we were to look up $locations[10712], we'd find it was actually the closest location to our initial coordinates. So let's do that.

Use the key of the first array element from the second array to get the details of the closest location from the first array

To pull the key of the first element of $distances, we'd use the code:

$key = key($distances);

So to use that key to find the corresponding location in $locations, we can simply use:

$closest = $locations[key($distances)];

In our example, our base location was -31.959138, 115.858072, which if you check on a map is the Belltower in Perth.

In my $locations array, $locations[10712] is Perth, or more specifically:

array (
  "postcode" => "6000",
  "name" => "Perth",
  "state_code" => "WA",
  "lat" => "-31.9554",
  "lng" => "115.85859"
)

So to display the name, I just use $closest['name'].

I hope you found this tutorial on how to find the nearest location from an array of coordinates useful. Read on for a discussion of the algorithms.

How do the distance calculation algorithms compare?

The main algorithms I considered were:

That list is sorted from fastest and least accurate to slowest and most accurate.

My tests, averaged over 10 runs each, on a list of 16,315 locations, showed the speed of run time were as follows:

  • Pythagorean Theorem: 14 milliseconds
  • Spherical Earth Projected To A Plane: 22 milliseconds
  • Haversine Formula: 24 milliseconds

The 16,000 locations covers all of the suburbs of Australia and New Zealand. There are over 40,000 such locations in USA. The speed will blow out quite a bit on larger data sets.

What is the code for calculating distances?

This code replaces the calculations inside the foreach loop from the initial example. Everything else can stay the same.

Pythagorean Theorem in PHP

The Pythagorean Theorem is a2 + b2 = c2 . It uses right angle calculations to determine the distance, which in our case would be c.

Applied to our location calculations, it looks like this:

$a = $base_location['lat'] - $location['lat'];
$b = $base_location['lng'] - $location['lng'];
$distance = sqrt(($a**2) + ($b**2));

You can read more about it here.

Spherical Earth Projected To A Plane in PHP

The Pythagorean Theorem will give quite inaccurate results once you go more than short distances. The problem is that is calculates based on a straight line, not taking into account the curvature of the Earth.

An attempt to improve upon that is called the Spherical Earth Projected To A Plane Formula.

Essentially it uses some trigonometry to "flatten" the Earth, then calculate distances on that flattened Earth.

Applied to our location calculations, it looks like this:

$delta_lat = $base_location['lat'] - $location['lat'];
$delta_lng = $base_location['lng'] - $location['lng'];
$mean_lat = ($location['lat'] + $base_location['lat']) / 2;
$distance = ($delta_lat**2) + ((cos($mean_lat) * $delta_lng)**2);

If you want the actual distances, you can add these lines:

$earth_radius_km = 6371.009;
$earth_radius_mi = 3958.761;
$actual_distance = $earth_radius_km * sqrt($distance);

Choose between $earth_radius_km and $earth_radius_mi, depending on what units you needed.

Then make sure that you change

$distances[$key] = $distance;

to

$distances[$key] = $actual_distance;

You can read more about the formula here.

Haversine Formula in PHP

The Haversine Formula is widely used in navigation. It's fairly complex, but is the most accurate calculation that ignores elevation (imagine the Earth as one giant ocean surface, with no mountains or valleys).

It's overkill for this example of finding just the closest location, but I've used it in other projects when I needed the closest 100 locations to the starting point.

Used in our calculations, it looks like this:

$lat1 = deg2rad($location['lat']);
$lon1 = deg2rad($location['lng']);
$lat2 = deg2rad($base_location['lat']);
$lon2 = deg2rad($base_location['lng']);

$delta_lat = $lat2 - $lat1;
$delta_lng = $lon2 - $lon1;

$hav_lat = (sin($delta_lat / 2))**2;
$hav_lng = (sin($delta_lng / 2))**2;

$distance = 2 * asin(sqrt($hav_lat + cos($lat1) * cos($lat2) * $hav_lng));

And as with the Spherical Earth example above, if you want the actual distance returned, add the relevant lines:

$earth_radius_km = 6371.009;
$earth_radius_mi = 3958.761;
$actual_distance = $earth_radius_km * $distance;
$distances[$key] = $actual_distance;

If you're interested in the math behind the Haversine Formula, have a look here.

Mike Haydon

Thanks for checking out my WordPress and coding tutorials. If you've found these tutorials useful, why not consider supporting my work?

Buy me a coffee

9 thoughts on “Find The Nearest Location From An Array of Coordinates In PHP”

  1. Thank you! This solved a problem I had for the last few days!
    Used it in TS:
    const distance = Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2))

    This really was a big help.

    Reply
  2. Wow Mike, that is fantastic script! But I need to ask you a on thing:

    How can I use your script for calculating every points within 5, 1000, 2000 meters? If I wanna pass to your script meters limit for finding nearest but not over (for example) 1000 meters?
    Thanks for any answer!

    Reply
  3. Hi,
    and my another question is: how can I find the circle around from latitude and longitude of my position within 1000 meters (alias 1 km)?
    Thanks

    Reply
  4. This is great! Thanks for sharing. It does just want I need it to do.

    I did get an error using the last bit of code here:
    $actual_distance = $earth_radius_km * distance;

    Needs a $ in front of distance.

    Reply
  5. This is a life saver of a post. I used the Haversine Formula and it seems to work nicely. I had a massive number of locations and needed my search to look at the distance between points, then exclude posts based on whether they were inside a distance range. It finishes off the filter I am working on nicely and neatly. Good work and thank you!

    Reply

Leave a Comment