-5

私はこのようなPHPで座標の配列を持っています:

Array ( 
    [0] => Array ( 
        [0] => 39.1057579 
        [1] => 26.5451331 
    ) 
    [1] => Array ( 
        [0] => 39.1057579 
        [1] => 26.5451331 
        [2] => 39.1055889 
        [3] => 26.5452403 
    ) 
    [2] => Array ( 
        [0] => 39.1057579 
        [1] => 26.5451331 
        [2] => 39.1055889
    )
)

start latlng と end latlng を入力として関数を検索し、最短経路として座標の配列を返します。

4

1 に答える 1

1

Mark Ba​​ker が指摘したように、ダイクストラのアルゴリズムのようなものを使用して加重グラフをトラバースする必要があります (これは、距離を含めるときに得られるものです)。

ここで見つけた簡単な距離関数を次に示します。

<?php

/*::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*/
/*::                                                                         :*/
/*::  This routine calculates the distance between two points (given the     :*/
/*::  latitude/longitude of those points). It is being used to calculate     :*/
/*::  the distance between two locations using GeoDataSource(TM) Products    :*/
/*::                                                                         :*/
/*::  Definitions:                                                           :*/
/*::    South latitudes are negative, east longitudes are positive           :*/
/*::                                                                         :*/
/*::  Passed to function:                                                    :*/
/*::    lat1, lon1 = Latitude and Longitude of point 1 (in decimal degrees)  :*/
/*::    lat2, lon2 = Latitude and Longitude of point 2 (in decimal degrees)  :*/
/*::    unit = the unit you desire for results                               :*/
/*::           where: 'M' is statute miles                                   :*/
/*::                  'K' is kilometers (default)                            :*/
/*::                  'N' is nautical miles                                  :*/
/*::  Worldwide cities and other features databases with latitude longitude  :*/
/*::  are available at http://www.geodatasource.com                          :*/
/*::                                                                         :*/
/*::  For enquiries, please contact sales@geodatasource.com                  :*/
/*::                                                                         :*/
/*::  Official Web site: http://www.geodatasource.com                        :*/
/*::                                                                         :*/
/*::         GeoDataSource.com (C) All Rights Reserved 2013                  :*/
/*::                                                                         :*/
/*::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*/
function distance($lat1, $lon1, $lat2, $lon2, $unit) {

  $theta = $lon1 - $lon2;
  $dist = sin(deg2rad($lat1)) * sin(deg2rad($lat2)) +  cos(deg2rad($lat1)) * cos(deg2rad($lat2)) * cos(deg2rad($theta));
  $dist = acos($dist);
  $dist = rad2deg($dist);
  $miles = $dist * 60 * 1.1515;
  $unit = strtoupper($unit);

  if ($unit == "K") {
    return ($miles * 1.609344);
  } else if ($unit == "N") {
      return ($miles * 0.8684);
    } else {
        return $miles;
      }
}

echo distance(32.9697, -96.80322, 29.46786, -98.53506, "M") . " Miles<br>";
echo distance(32.9697, -96.80322, 29.46786, -98.53506, "K") . " Kilometers<br>";
echo distance(32.9697, -96.80322, 29.46786, -98.53506, "N") . " Nautical Miles<br>";

?>

ノード間のすべての距離を見つけるには、すべてのノードを単純にループする必要があります。次のような配列が得られます。

$distance[0][1] = 10;
$distance[0][2] = 12;
$distance[0][3] = 7;
...
$distance[4][3] = 14;

配列の次元はノード番号を表し、割り当てられた値は距離です。この配列を Dijkstra で実行して、最短の加重パスを見つけます。

これがお役に立てば幸いです。さらに支援が必要な場合は、質問を絞り込んでより絞り込むことをお勧めします。グラフ トラバーサルは、非常に幅広い研究分野です。幸運を。

于 2013-10-01T23:46:03.787 に答える