Posted By

garretjames on 09/26/13


Tagged

GPS geolocation


Versions (?)

Geo


 / Published in: PHP
 

The comments are in the script, but it takes a tab delimited file with city name and lat long coordinates, and plot's the shortest travel distance amongst the geodesic globe.

  1. <?php
  2.  
  3. /**
  4. *@author Garret James Hornby
  5. *@date 9/14/2011
  6. *@require >=PHP 4
  7. **/
  8.  
  9. /**
  10. *Script that takes a list of cities in the file cities.txt and gives the shortest path to travel between all of them.
  11. **/
  12.  
  13. $cityArr = array(); //An array to collect the input from cities.txt
  14. $travelRoute = array(); //An array to collect the city names in an ordered list by shortest distance
  15.  
  16. /**
  17. *Function called to intialize the script
  18. */
  19. function initSolve()
  20. {
  21. global $cityArr, $travelRoute;
  22.  
  23. $cities = "cities.txt";
  24. $citiesIn = fopen($cities, "r");
  25. $cityList = fread($citiesIn, filesize($cities));
  26. fclose($citiesIn);
  27. $splitLines = explode("\n", $cityList);
  28.  
  29. foreach($splitLines as $item)
  30. {
  31. $splitTabs = explode("\t", $item);
  32. $cityArr[] = array("name" => $splitTabs[0], "lat" => $splitTabs[1], "long" => $splitTabs[2]);
  33. }
  34.  
  35. setPushPop(0);
  36. getDistances();
  37. }
  38.  
  39. /**
  40. *Pushes the next destination, found to have the shortest distance, into travelRoute and pops it from cityArr
  41. *
  42. *@param (int)$index
  43. */
  44. function setPushPop($index)
  45. {
  46. global $cityArr, $travelRoute;
  47.  
  48. array_push($travelRoute, $cityArr[$index]);
  49. unset($cityArr[$index]);
  50. }
  51.  
  52. /**
  53. *Calculates the distance between two sets of latitude / longitude points. The calculation is using the World Geodetic System 84 (WGS84). Instead of treating earth as a perfect sphere, these calculations use an accurate ellipsoidal model of Earth. This function is a port of Vincenty Inverse Solution of Geodesics on the Ellipsoid.
  54. *
  55. *@param (float)$lat1
  56. *@param (float)$long1
  57. *@param (float)$lat2
  58. *@param (float)$long2
  59. *@return (float)
  60. */
  61. function getDistanceCalc($lat1, $long1, $lat2, $long2)
  62. {
  63. //Using the numbers provided from WGS84 with major radius 'a', semi-minor radius 'b', and inverse flattening 'f'. All numbers are calculated in meters.
  64. $gsArr = array("a" => 6378137, "b" => 6356752.314245, "f" => 1/298.257223563);
  65.  
  66. $longDiff = ($long2 - $long1);
  67. $longRad = deg2rad($longDiff);
  68.  
  69. $upper1 = atan((1 - $gsArr["f"]) * tan(deg2rad($lat1)));
  70. $upper2 = atan((1 - $gsArr["f"]) * tan(deg2rad($lat2)));
  71.  
  72. $upper1Sin = sin($upper1);
  73. $upper1Cos = cos($upper1);
  74. $upper2Sin = sin($upper2);
  75. $upper2Cos = cos($upper2);
  76.  
  77. $lambda = $longRad;
  78. $lambdaProc = 0;
  79. $i = 100;
  80.  
  81. while((abs($lambda - $lambdaProc) > (1* pow(10,-12))) && (--$i > 0))
  82. {
  83.  
  84. $lambdaSin = sin($lambda);
  85. $lambdaCos = cos($lambda);
  86. $sigmaSin = sqrt(($upper2Cos*$lambdaSin) * ($upper2Cos*$lambdaSin) + ($upper1Cos * $upper2Sin - $upper1Sin * $upper2Cos * $lambdaCos) * ($upper1Cos * $upper2Sin - $upper1Sin * $upper2Cos * $lambdaCos));
  87. if($sigmaSin == 0) return 0;
  88. $sigmaCos = $upper1Sin * $upper2Sin + $upper1Cos * $upper2Cos * $lambdaCos;
  89. $sigma = atan2($sigmaSin, $sigmaCos);
  90. $alphaSin = $upper1Cos * $upper2Cos * $lambdaSin / $sigmaSin;
  91. $alphaCos = 1 - $alphaSin * $alphaSin;
  92. $sigma2Cos = $sigmaCos - 2*$upper1Sin*$upper2Sin/$alphaCos;
  93. if (is_numeric($sigma2Cos) == false) $sigma2Cos = 0;
  94. $circ = $gsArr["f"] / 16 * $alphaCos * (4 + $gsArr["f"] * (4 - 3 * $alphaCos));
  95. $lambdaProc = $lambda;
  96. $lambda = $longRad + (1 - $circ) * $gsArr["f"] * $alphaSin *
  97. ($sigma + $circ * $sigmaSin * ($sigma2Cos + $circ * $sigmaCos * (-1 + 2 * $sigma2Cos * $sigma2Cos)));
  98. }
  99.  
  100. if ($i==0) return 0;
  101.  
  102. $upperSq = $alphaCos * ($gsArr["a"] * $gsArr["a"] - $gsArr["b"] * $gsArr["b"]) / ($gsArr["b"] * $gsArr["b"]);
  103. $A = 1 + $upperSq / 16384 * (4096 + $upperSq * (-768 + $upperSq * (320 - 175 * $upperSq)));
  104. $B = $upperSq / 1024 * (256 + $upperSq * (-128 + $upperSq * (74 - 47 * $upperSq)));
  105. $deltaSigma = $B * $sigmaSin * ($sigma2Cos + $B / 4 * ($sigmaCos * (-1 + 2 * $sigma2Cos * $sigma2Cos)- $B / 6 * $sigma2Cos * (-3 + 4 * $sigmaSin * $sigmaSin) * (-3 + 4 * $sigma2Cos * $sigma2Cos)));
  106. $distance = $gsArr["b"] * $A * ($sigma - $deltaSigma);
  107.  
  108. //This should fix the curvuture problem.
  109. //$delta = sig(($yprime/$xprime)) * tan(xattr_get(filename, name));
  110.  
  111.  
  112.  
  113. return round($distance, 3); //return to the nearest millimeter
  114. }
  115.  
  116. /**
  117. *A funtion that calculates the distance between the last element in travelRoute (most recently visited location) and the locations left in cityArr (all the locations left to visit.)
  118. */
  119. function getDistances()
  120. {
  121. global $cityArr, $travelRoute;
  122.  
  123. $distIndex = array();
  124. $minDist = array();
  125.  
  126. foreach($cityArr as $key => $searchCity)
  127. {
  128. $distance = getDistanceCalc($travelRoute[count($travelRoute)-1]['lat'],$travelRoute[count($travelRoute)-1]['long'],$searchCity['lat'],$searchCity['long']);
  129. $distIndex[]= array("key" => $key, "distance" => $distance);
  130. array_push($minDist, $distance);
  131. }
  132. foreach($distIndex as $nextCity)
  133. {
  134. if($nextCity['distance'] == min($minDist))
  135. {
  136. $nextKey = $nextCity['key'];
  137. setPushPop($nextKey);
  138. }
  139. }
  140.  
  141. if(empty($cityArr))
  142. {
  143. //This could be seperated into an output function if output was to be further dynamic and expounded upon.
  144. foreach($travelRoute as $whereTo)
  145. {
  146. $travelName = $whereTo["name"];
  147. print("$travelName\n");
  148. }
  149. }
  150. else{getDistances();}
  151. }
  152.  
  153. initSolve(); //Intialize the script
  154. ?>

Report this snippet  

You need to login to post a comment.