## Posted By

garretjames on 09/26/13

## Who likes this?

1 person have marked this snippet as a favorite

# 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.

`<?php /***@author Garret James Hornby*@date 9/14/2011*@require >=PHP 4**/ /***Script that takes a list of cities in the file cities.txt and gives the shortest path to travel between all of them.**/ \$cityArr = array(); //An array to collect the input from cities.txt\$travelRoute = array(); //An array to collect the city names in an ordered list by shortest distance /***Function called to intialize the script*/function initSolve(){	global \$cityArr, \$travelRoute; 	\$cities = "cities.txt";	\$citiesIn = fopen(\$cities, "r");	\$cityList = fread(\$citiesIn, filesize(\$cities));	fclose(\$citiesIn);	\$splitLines = explode("\n", \$cityList); 	foreach(\$splitLines as \$item)	{		\$splitTabs = explode("\t", \$item);		\$cityArr[] = array("name" => \$splitTabs[0], "lat" => \$splitTabs[1], "long" => \$splitTabs[2]);	} 	setPushPop(0);	getDistances();} /***Pushes the next destination, found to have the shortest distance, into travelRoute and pops it from cityArr**@param (int)\$index*/function setPushPop(\$index){	global \$cityArr, \$travelRoute; 	array_push(\$travelRoute, \$cityArr[\$index]);	unset(\$cityArr[\$index]);} /***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.**@param (float)\$lat1*@param (float)\$long1*@param (float)\$lat2*@param (float)\$long2*@return (float)*/function getDistanceCalc(\$lat1, \$long1, \$lat2, \$long2){	//Using the numbers provided from WGS84 with major radius 'a', semi-minor radius 'b', and inverse flattening 'f'. All numbers are calculated in meters.	\$gsArr = array("a" => 6378137, "b" => 6356752.314245, "f" => 1/298.257223563); 	\$longDiff = (\$long2 - \$long1);	\$longRad = deg2rad(\$longDiff); 	\$upper1 = atan((1 - \$gsArr["f"]) * tan(deg2rad(\$lat1)));	\$upper2 = atan((1 - \$gsArr["f"]) * tan(deg2rad(\$lat2))); 	\$upper1Sin = sin(\$upper1);	\$upper1Cos = cos(\$upper1);	\$upper2Sin = sin(\$upper2);	\$upper2Cos = cos(\$upper2); 	\$lambda = \$longRad;	\$lambdaProc = 0;	\$i = 100; 	while((abs(\$lambda - \$lambdaProc) > (1* pow(10,-12))) && (--\$i > 0))	{ 		\$lambdaSin = sin(\$lambda);		\$lambdaCos = cos(\$lambda);		\$sigmaSin = sqrt((\$upper2Cos*\$lambdaSin) * (\$upper2Cos*\$lambdaSin) + (\$upper1Cos * \$upper2Sin - \$upper1Sin * \$upper2Cos * \$lambdaCos) * (\$upper1Cos * \$upper2Sin - \$upper1Sin * \$upper2Cos * \$lambdaCos));		if(\$sigmaSin == 0) return 0;		\$sigmaCos = \$upper1Sin * \$upper2Sin + \$upper1Cos * \$upper2Cos * \$lambdaCos;		\$sigma = atan2(\$sigmaSin, \$sigmaCos);		\$alphaSin = \$upper1Cos * \$upper2Cos * \$lambdaSin / \$sigmaSin;		\$alphaCos = 1 - \$alphaSin * \$alphaSin;		\$sigma2Cos = \$sigmaCos - 2*\$upper1Sin*\$upper2Sin/\$alphaCos;		if (is_numeric(\$sigma2Cos) == false) \$sigma2Cos = 0;		\$circ = \$gsArr["f"] / 16 * \$alphaCos * (4 + \$gsArr["f"] * (4 - 3 * \$alphaCos));		\$lambdaProc = \$lambda;		\$lambda = \$longRad + (1 - \$circ) * \$gsArr["f"] * \$alphaSin *		(\$sigma + \$circ * \$sigmaSin * (\$sigma2Cos + \$circ * \$sigmaCos * (-1 + 2 * \$sigma2Cos * \$sigma2Cos)));	} 	if (\$i==0) return 0; 	\$upperSq = \$alphaCos * (\$gsArr["a"] * \$gsArr["a"] - \$gsArr["b"] * \$gsArr["b"]) / (\$gsArr["b"] * \$gsArr["b"]);	\$A = 1 + \$upperSq / 16384 * (4096 + \$upperSq * (-768 + \$upperSq * (320 - 175 * \$upperSq)));	\$B = \$upperSq / 1024 * (256 + \$upperSq * (-128 + \$upperSq * (74 - 47 * \$upperSq)));	\$deltaSigma = \$B * \$sigmaSin * (\$sigma2Cos + \$B / 4 * (\$sigmaCos * (-1 + 2 * \$sigma2Cos * \$sigma2Cos)- \$B / 6 * \$sigma2Cos * (-3 + 4 * \$sigmaSin * \$sigmaSin) * (-3 + 4 * \$sigma2Cos * \$sigma2Cos)));	\$distance = \$gsArr["b"] * \$A * (\$sigma - \$deltaSigma); 	//This should fix the curvuture problem.	//\$delta = sig((\$yprime/\$xprime)) * tan(xattr_get(filename, name));   	return round(\$distance, 3); //return to the nearest millimeter} /***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.)*/ function getDistances(){	global \$cityArr, \$travelRoute; 	\$distIndex = array();	\$minDist = array(); 	foreach(\$cityArr as \$key => \$searchCity)	{		\$distance = getDistanceCalc(\$travelRoute[count(\$travelRoute)-1]['lat'],\$travelRoute[count(\$travelRoute)-1]['long'],\$searchCity['lat'],\$searchCity['long']);		\$distIndex[]= array("key" => \$key, "distance" => \$distance);		array_push(\$minDist, \$distance);	}	foreach(\$distIndex as \$nextCity)	{		if(\$nextCity['distance'] == min(\$minDist))		{			\$nextKey =  \$nextCity['key'];			setPushPop(\$nextKey);		}	} 	if(empty(\$cityArr))	{		//This could be seperated into an output function if output was to be further dynamic and expounded upon.		foreach(\$travelRoute as \$whereTo)		{			\$travelName = \$whereTo["name"];			print("\$travelName\n");		}	}	else{getDistances();}} initSolve(); //Intialize the script?>`