Finding two farthest objects between array of coordinates in PHP

Question

I want to find two farthest objects (from each other) in my $user_devices array.

Every object of $user_devices has attributes: id, name, imei and coordinates. Ex.:

$user_devices = array(
    'id' => '1',
    'name' => 'First object',
    'imei' => '123456789',
    'coordinates' => '51.313032,11.798092'
);

What I'm trying to do is go through the whole array, convert latitudes and longitudes to x and y and finally calculate the distance between locations.

The problem is that this algorithm should work fast with at least 5 000 records (locations), but integrating it into a website takes about 20 seconds of load time.

How can I optimize this algorithm?

public static function get_farthest_devices($user_devices)
{

    $r = 6378; // Earth radius in km
    $max_distance = 0;
    $count = count($user_devices);

    for ($i = 0; $i < $count - 1; $i++) {
        $coordinates = $user_devices[$i]->coordinates;
        $coordinates_explode = explode(',', $coordinates);

        $lat = $coordinates_explode[0];
        $lng = $coordinates_explode[1];

        $x1 = $r * cos(deg2rad($lat)) * cos(deg2rad($lng));
        $y1 = $r * cos(deg2rad($lat)) * sin(deg2rad($lng));

        for ($j = $i + 1; $j < $count; $j++) {
            $coordinates = $user_devices[$j]->coordinates;
            $coordinates_explode = explode(',', $coordinates);

            $lat = $coordinates_explode[0];
            $lng = $coordinates_explode[1];

            $x2 = $r * cos(deg2rad($lat)) * cos(deg2rad($lng));
            $y2 = $r * cos(deg2rad($lat)) * sin(deg2rad($lng));

            $distance_between_points = sqrt( pow($x2-$x1, 2) + pow($y2-$y1, 2) );

            if($distance_between_points > $max_distance)
            {
                $max_distance = $distance_between_points;
                $obj_i = $user_devices[$i];
                $obj_j = $user_devices[$j];
            }
        }
    }

    echo 'MAX distance is between: ' . $obj_i->name . ' (' . $obj_i->imei . ') and ' . $obj_j->name . ' (' . $obj_j->imei . ') ' .  $max_distance . ' km<br/>';     
}

Can the objects be anywhere on the globe or are they in a limited area (for example, in a certain country or city)? — Joni, Mar 12 '19 at 14:02
Why not use a database for that? Insert each record in a table and perform a query — Nico Haase, Mar 12 '19 at 14:07
The whole user_devices array is fetched from database. Every device location can change every x seconds. On every page load user should see which two devices are farthest from each other. — senti, Mar 12 '19 at 14:18
Create a triangle from the first three points, then for each given next point either extend it (if point is outside the resulting figure) or leave at as is, depending on whether this point is inside the resulting figure. For each point in the figure, store the coords so you don't have to explode/deg2rad/sin/cos again and again. — raina77ow, Mar 12 '19 at 14:43
BTW, isn't the formula you use different from [Haversine](https://stackoverflow.com/questions/27928/calculate-distance-between-two-latitude-longitude-points-haversine-formula)? — raina77ow, Mar 12 '19 at 14:43
Do you need the answer to be exact or is a probabilistic "within +/-5% of the answer 95% of the time" solution ok? — Joni, Mar 12 '19 at 14:46
@Joni I'm not sure if I got it right, but it would be nice to have a loading (calculating) time somewhere around 5 seconds for 5 000 records. — senti, Mar 12 '19 at 15:02
Remember that when the distance is higher than one half of Earth's circumference, then it's shorter distance the other way around. — helvete, Mar 13 '19 at 10:18

score 0 · Answer 1 · answered Mar 12 '19 at 14:51

public static function get_farthest_devices($user_devices)
{

$xyImei[] = array();
$r = 6378; // Earth radius in km
$max_distance = 0;

foreach($user_devices as $dev) {   // x,y calculate only one for one device
  $coordinates_explode = explode(',', $dev->coordinates);
  $lat = $coordinates_explode[0];
  $lng = $coordinates_explode[1];
  $xyImei[$dev->imei]['x'] = $r * cos(deg2rad($lat)) * cos(deg2rad($lng));
  $xyImei[$dev->imei]['y'] = $r * cos(deg2rad($lat)) * sin(deg2rad($lng));
}

foreach($user_devices as $dev1) {  // calculate distance 
  $x1 = $xyImei[$dev1->imei]['x'];
  $y1 = $xyImei[$dev1->imei]['y'];

  foreach($user_devices as $dev2) {
  $x2 = $xyImei[$dev2->imei]['x'];
  $y2 = $xyImei[$dev2->imei]['y'];

  if ($dev1->imei != $dev2->imei)  // special case
  if ($x2-$x1 == 0) 
    $distance_between_points = abs($y2-$y1);
  else
    if ($y2-$y1 == 0) 
      $distance_between_points = abs($x2-$x1);
    else
      $distance_between_points = sqrt( pow($x2-$x1, 2) + pow($y2-$y1, 2) );

    if($distance_between_points > $max_distance)
    {
    $max_distance = $distance_between_points;
    $obj_i = $dev1;
    $obj_j = $dev2;
    }

  }

}

echo 'MAX distance is between: ' . $obj_i->name . ' (' . $obj_i->imei . ') and ' . $obj_j->name . ' (' . $obj_j->imei . ') ' .  $max_distance . ' km<br/>';     
}

Joni · Answer 2 · 2019-03-12T18:49:39.590

The main problem is that 5k objects make about 12 million pairs, and doing anything 10 million times is going to take some time. So the solutions will revolve around discarding pairs from consideration.

If the objects were limited to a sufficiently small region (for example, a single country or continent) the most distant pair would be guaranteed to lie on the convex hull. The convex hull would probably have around 100 points, and then you'd find the most distant pair among those 100. But this won't work if your objects can be found all over the globe.

If a probabilistic answer was acceptable, you could use a Monte Carlo algorithm and select random pairs of points and compute the distance between them. With a sufficiently large sample size (or maybe a smart sampling algorithm) you'll get an answer that's close to the true value with a high probability.

If you need the exact answer, what you can do is subdivide the globe into 18x36 blocks of 10x10 degrees (for example).

Looking at just the corners of each block (and a few special cases to consider antipodal blocks and poles), you can compute how far the objects in two different blocks can be. For example, distance between an objects in block (0,0) and (0,2) can be at most 3300km. Let's call this max distance between two blocks distmax
For each pair of non-empty blocks B1 and B2 (including B1=B2), starting with the pair with largest distmax:
Find the most distant pair of objects where one is in B1 and the other in B2, and call the distance d
Discard the pairs of blocks that have distmax < d because you know the objects in them must be closer than d from each other. You'll avoid computing the distances between a large number of pairs of objects.

Finding two farthest objects between array of coordinates in PHP

2 Answers2