Нахождение двух самых дальних объектов между массивом координат в PHP - PullRequest
Новая
       105

Нахождение двух самых дальних объектов между массивом координат в PHP

4 голосов
/ 12 марта 2019

Я хочу найти два самых дальних объекта (друг от друга) в моем массиве $ user_devices.

Каждый объект $ user_devices имеет атрибуты: id, name, imei и координаты. Ex.:

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

То, что я пытаюсь сделать, - это пройти весь массив, преобразовать широты и долготы в x и y и, наконец, вычислить расстояние между точками.

Проблема в том, что этот алгоритм должен работать быстро, по крайней мере, с 5 000 записей (местоположений), но его интеграция в веб-сайт занимает около 20 секунд времени загрузки.

Как я могу оптимизировать этот алгоритм? 

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/>';     
}

Ответы [ 2 ]

0 голосов
/ 12 марта 2019

Основная проблема состоит в том, что 5k объектов составляют около 12 миллионов пар, а выполнение чего-либо 10 миллионов раз займет некоторое время. Таким образом, решения будут основываться на отбрасывании пар из рассмотрения.

Если бы объекты были ограничены достаточно небольшим регионом (например, одной страной или континентом), самая отдаленная пара гарантированно находилась бы на выпуклой оболочке . Вероятно, выпуклая оболочка будет иметь около 100 точек, и тогда вы найдете самую дальнюю пару из этих 100. Но это не сработает, если ваши объекты можно будет найти по всему земному шару.

Если вероятностный ответ был приемлемым, вы могли бы использовать алгоритм Монте-Карло и выбирать случайные пары точек и вычислять расстояние между ними. При достаточно большом размере выборки (или, возможно, интеллектуальном алгоритме выборки) вы получите ответ, близкий к истинному значению с высокой вероятностью.

Если вам нужен точный ответ, вы можете поделить глобус на 18x36 блоков по 10x10 градусов (например).

  • Рассматривая только углы каждого блока (и несколько особых случаев для учета блоков и полюсов-антиподов), вы можете вычислить, как далеко могут находиться объекты в двух разных блоках. Например, расстояние между объектами в блоке (0,0) и (0,2) может быть не более 3300 км. Давайте назовем это максимальное расстояние между двумя блоками distmax
  • Для каждой пары непустых блоков B1 и B2 (включая B1 = B2), начиная с пары с наибольшим distmax:
  • Найдите самую отдаленную пару объектов, где один находится в B1, а другой в B2, и назовите расстояние d
  • Откажитесь от пар блоков, имеющих distmax < d, потому что вы знаете, что объекты в них должны быть ближе, чем d друг от друга. Вы избежите вычисления расстояний между большим количеством пар объектов.
0 голосов
/ 12 марта 2019 
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/>';     
}
...