php - 在PHP中的坐标数组之间查找两个最远的对象

Question

我想在我的 $user_devices 数组中找到两个最远的对象(彼此)。

$user_devices 的每个对象都有属性:id、name、imei 和坐标。例如:

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

我要做的是遍历整个数组，将纬度和经度转换为 x 和 y，最后计算位置之间的距离。

问题是该算法应该可以快速处理至少 5000 条记录(位置)，但将其集成到网站中需要大约 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/>';     
}

Answer 1

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