addElement('header', null, 'Travelling Salesman Problem Solver'); $form->addElement('file', 'kmfile', 'KML file:'); $form->addElement('submit', null, 'Upload'); // try to validate a form if ($form->validate()) { // determine the filename of the uploaded file $uploadInfo = $form->getSubmitValue('kmfile'); $kmlfile = $uploadInfo['tmp_name']; // read the uploaded file into an associative array $doc = implode('', file($kmlfile)); $unserializer = &new XML_Unserializer(); // Check whether serialization worked if (PEAR::isError($unserializer->unserialize($doc))) { die($status->getMessage()); } $kmldata = $unserializer->getUnserializedData(); $placemarks = array(); $placemark_count = 0; $oelocations = array(); // extract the placemarks searchplacemarks($kmldata); foreach ($placemarks as $placemark) { // get lat and lon from the array in radians $coordinates = $placemark['Point']['coordinates']; // coordinates are separated by commas list($longitude, $latitude, $altitude) = explode(',', $coordinates); // convert to radians $lat = deg2rad($latitude); $lon = deg2rad($longitude); // stick into an associative array $oelocations[$placemark_count]['lat'] = $lat; $oelocations[$placemark_count]['lon'] = $lon; $placemark_count++; } // keep the size manageable -- take the first x placemarks if ($placemark_count > 9) {$placemark_count = 9;} // build an array of distances between each placemark $oedistances = array(); for ($i = 0; $i < $placemark_count; $i++) : for ($j = $i + 1; $j < $placemark_count; $j++) : //You can use direct distance rather than great circle distances $oedistances[$i][$j] = distance($oelocations[$i]['lat'],$oelocations[$i]['lon'],$oelocations[$j]['lat'],$oelocations[$j]['lon']); // Don't believe me? Here's how you'd do it with great circle distances: // $oedistances[$i][$j] = haversine($oelocations[$i]['lat'],$oelocations[$i]['lon'],$oelocations[$j]['lat'],$oelocations[$j]['lon']); // The following is inefficient, I know $oedistances[$j][$i] = $oedistances[$i][$j]; endfor; endfor; $size = $placemark_count - 1; $perm = range(0, $size); //create an array to hold permutations of all routes $pnum = factorial($size); $minimum = 1000000000; // keep track of the shortest route until now // fill the array with the needed route permutations. for ($m = 0; $m < $pnum; $m++): foreach ($perm as $i) { $perms[$m][] = $i; } $perm = pc_next_permutation($perm, $size); endfor; // for every route permutation, add up the total distance for ($i = 0; $i < $m; $i++): for ($k = 0; $k < $size; $k++): $temp_sum[$i] += $oedistances[$perms[$i][$k]][$perms[$i][$k+1]]; endfor; $temp_sum[$i] += $oedistances[$perms[$i][$size]][$perms[$i][0]]; // is it the shortest thus far? if ($temp_sum[$i] < $minimum) { $minimum = $temp_sum [$i] ; $index = $i; // if so, remember which permutation it was } endfor; // build the KML file $response = ''; $response .= ''; $response .= " \n"; $response .= " Traveling Salesman Problem: Shortest route"; $response .= " 1\n"; $response .= " 0\n"; $response .= " \n"; $response .= " 1\n"; $response .= " \n"; // add the LineString coordinates of the shortesr route for ($k = 0; $k <= $size; $k++): $response .= rad2deg($oelocations[$perms[$index][$k]]['lon']) . ", " . rad2deg($oelocations[$perms[$index][$k]]['lat']) . ",0\n"; endfor; $response .= rad2deg($oelocations[$perms[$index][0]]['lon']) . ", " . rad2deg($oelocations[$perms[$index][0]]['lat']) . ",0\n"; $response .= " \n"; $response .= " \n"; $response .= " \n"; $response .= '' . "\n"; // send the response file header('Content-Type: application/vnd.google-earth.kml+xml'); header('Content-Disposition: attachment; filename="tsp.kml"'); echo $response; exit(); } // Show the form echo ''; echo ''; $form->display(); echo '

Upload a KML file (NOT KMZ) containing placemarks. Only the first nine placemarks encountered will be used in the calculation of the shortest route connecting all of them. More info here.

'; echo '

Click here for the source code.

'; echo ''; exit(); // declaration of functions // permutation generator // adapted from O'Reilly's Perl Cookbook, I think: // http://tinyurl.com/krw8k // Not the most efficient routine, as mirror images are also returned. Since it doesn't matter to us in which direction we travel a route, I need to find a permutation generator that does not return mirror images. function pc_next_permutation($p, $size) { for ($i = $size - 1; $p[$i] >= $p[$i+1]; --$i) { } for ($j = $size; $p[$j] <= $p[$i]; --$j) { } $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp; for (++$i, $j = $size; $i < $j; ++$i, --$j) { $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp; } return $p; } // look for array elements that are placemarks function searchplacemarks($data) { global $placemarks; foreach($data as $key => $value) { if ($key === "Point") { $placemarks[] = $data; } else { if (count($value) > 1) { searchplacemarks($value); } } } } //Find the direct Euclidian distance between 2 points in 3D space function distance($lat1,$long1,$lat2,$long2) { // convert spherical coordinate into cartesian $x1 = cos($lat1) * sin($long1); $y1 = cos($lat1) * cos($long1); $z1 = sin($lat1); $x2 = cos($lat2) * sin($long2); $y2 = cos($lat2) * cos($long2); $z2 = sin($lat2); // Find the distances $distx = abs($x1-$x2); $disty = abs($y1-$y2); $distz = abs($z1-$z2); $d = sqrt(pow($distx,2) + pow($disty,2) + pow($distz,2)); return $d; } // find the great circle distance between two points // adapted from Wanting Seed blog: // http://wantingseed.com/sprout/2003/06/10/distance-between-two-points-on-earth/ function haversine($lat1,$long1,$lat2,$long2) { $dlat = abs($lat2 - $lat1); $dlong = abs($long2 - $long1); $l = ($lat1 + $lat2) / 2; $a = 6378; $b = 6357; $e = sqrt(1 - ($b * $b)/($a * $a)); $r1 = ($a * (1 - ($e * $e))) / pow((1 - ($e * $e) * (sin($l) * sin($l))), 3/2); $r2 = $a / sqrt(1 - ($e * $e) * (sin($l) * sin($l))); $ravg = ($r1 * ($dlat / ($dlat + $dlong))) + ($r2 * ($dlong / ($dlat + $dlong))); $sinlat = sin($dlat / 2); $sinlon = sin($dlong / 2); $a = pow($sinlat, 2) + cos($lat1) * cos($lat2) * pow($sinlon, 2); $c = 2 * asin(min(1, sqrt($a))); $d = $ravg * $c; return $d; } // return the factorial of a number function factorial($number) { if ($number == 0) return 1; return $number * factorial($number - 1); } ?>