PHP – Computing Total Travel Distance From GPS Tracks

Posted on by Gowtham

Amongst other things, I like to keep a detailed track of where I have been [especially during hiking in the woods, venturing into areas that I have never been before, etc.]. For this purpose, I have configured my Garmin GPSMap 60CSx to record location/date-time data every three seconds and a while ago, I described another API I wrote to store these track points in MySQL. Added advantage of this, as I have mentioned before in previous posts, is that it can be used for geotagging my photographs. For completeness sake, the MySQL table structure that holds track data is given below:

1
2
3
4
5
6
7
8
9
10

CREATE TABLE IF NOT EXISTS `MyDatabase`.`TRK` (
  `id`          int( 11 ) NOT NULL AUTO_INCREMENT PRIMARY KEY ,
  `latitude`    float NULL ,
  `longitude`   float NULL ,
  `altitude`    float NULL ,
  `date`        date NULL ,
  `time`        time NULL
) ENGINE = MYISAM DEFAULT CHARSET latin1 AUTO_INCREMENT=1 ;
 
CREATE UNIQUE INDEX lldt ON `MyDatabase`.`TRK` (`latitude`,`longitude`,`date`,`time`);

Computing Total Travel Distance

Suppose that my GPS recorded my thanksgiving travel – starting from 2009-11-25 at 08:00:00 am EST ($start_datetime = “2009-11-25 03:00:00” ; GPS units save date & time in UTC) till 2009-11-29 at 06:00:00 pm EST ($end_time = “2009-11-29 13:00:00”) – recording track points every three seconds. While recording track points every three seconds in most cases might ensure that straight line approximation is good enough, the code below – for sake of mathematical rigor – uses Haversine formula.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

<!--?php 
 
# Database connection
$host     = 'localhost';
$dbuser   = 'DB_USERNAME';
$dbpasswd = 'DB_PASSWORD';
$database = 'DB_NAME';
 
$connect  = mysql_connect($host, $dbuser, $dbpasswd) or
            die('&lt;b&gt;MySQL Connection Error:&lt;/b&gt; ' .
            mysql_errno() . ': ' .
            mysql_error());
 
mysql_select_db($database, $connect) or
            die('&lt;b&gt;Database Connection Error:&lt;/b&gt; ' .
            mysql_errno() . ': ' .
            mysql_error());
 
# Radius of Earth (in miles)
# Use appropriate conversion factors if
# the distance is desired in other units.
$earth_radius  = 3960.00;
$distance_unit = "miles";
 
# Date / Time in UTC 
$start_datetime = "2009-11-25 03:00:00";
$end_datetime   = "2009-11-29 13:00:00";
 
# Running indices
$i         = 1;
$total_dis = 0.00;
 
# SQL Query #1
# Get all GPS/Date Time points between start_datetime and
# end_datetime
$sql1  = "SELECT latitude, longitude, date, time, ";
$sql1 .= "CONCAT(date, ' ', time) AS datetime ";
$sql1 .= "FROM TRK WHERE CONCAT(date, ' ', time) BETWEEN ";
$sql1 .= "'$start_datetime' AND '$end_datetime' ";
$sql1 .= "ORDER BY UNIX_TIMESTAMP(datetime) ASC ";
$res1  = mysql_query($sql1) or
          die('Invalid Query : ' .
          mysql_errno() . ' : ' .
          mysql_error());
 
while ($myrow1 = mysql_fetch_array($res1)) {
  $lat1 = $myrow1['latitude'];
  $lon1 = $myrow1['longitude'];
  $dat1 = $myrow1['date'];
  $tim1 = $myrow1['time'];
  $dt_1 = "$dat1" . " " . "$tim1";
 
  # SQL Query #2
  # Get the GPS/Date Time point next to the one in question
  $sql2   = "SELECT latitude, longitude, date, time, ";
  $sql2  .= "CONCAT(date, ' ', time) AS trk_dt_0, ";
  $sql2  .= "'$dat1 $tim1' AS trk_dt_1 FROM TRK WHERE ";
  $sql2  .= "UNIX_TIMESTAMP(CONCAT(date, ' ', time)) &gt; ";
  $sql2  .= "UNIX_TIMESTAMP('$dat1 $tim1') ORDER BY ";
  $sql2  .= "UNIX_TIMESTAMP(trk_dt_0) ASC LIMIT 1 ";
  $res2   = mysql_query($sql2) or
             die('Invalid Query : ' .
             mysql_errno() . ' : ' .
             mysql_error());
  $nres2  = mysql_num_rows($res2);
 
  if($nres2 == 1) {
    while ($myrow2 = mysql_fetch_array($res2)) {
      $lat2 = $myrow2['latitude'];
      $lon2 = $myrow2['longitude'];
      $dat2 = $myrow2['date'];
      $tim2 = $myrow2['time'];
      $dt_2 = "$dat2" . " " . "$tim2";
 
      # Compute distance between two points in question using
      # Haversine formula/function.
      # Add the haversine distance to the total/cumulative distance
      $haver_dis = distance_haversine($lat1, $lon1, $lat2, $lon2);
      $total_dis = $total_dis + $haver_dis ;
      $i         = str_pad($i, 6, "0", STR_PAD_LEFT);
 
      # Present results at each step
      # Can be piped out to a flat text file, if need be.
      # Useful to check the speed of movement, etc.
      # echo "    $i :: $dt_1 : $lat1 : $lon1 : $dt_2 : $lat2 : $lon2 : $haver_dis : $total_dis\n";

      # Increment the running index
      $i++;
    }
  }
}
 
# Function to accept latitue and longitude of 
# two locations and compute the distance between them.
function distance_haversine($lat1, $lon1, $lat2, $lon2) {
  global $earth_radius;
  $delta_lat = $lat2 - $lat1 ;
  $delta_lon = $lon2 - $lon1 ;
  $alpha     = $delta_lat/2 ;
  $beta      = $delta_lon/2 ;
 
  $a        = sin(deg2rad($alpha)) * sin(deg2rad($alpha)) + cos(deg2rad($lat1)) * cos(deg2rad($lat2)) * sin(deg2rad($beta)) * sin(deg2rad($beta)) ;
  $c        = asin(min(1, sqrt($a)));
  $distance = 2*$earth_radius * $c;
  $distance = round($distance, 4);
 
  return $distance;
}
 
# Print the summary
echo "\n";
echo "  Start Date Time : $start_datetime\n";
echo "  End Date Time   : $end_datetime\n";
echo "  Total Distance  : $total_dis $distance_unit\n";
echo "\n";
 
# Close the database connection
mysql_close($connect);
?-->


To keep the test case simple and computationally expenses minimal, I used a subset of my Thanksgiving travel – with $start_datetime = “2009-11-25 23:59:30” and $end_datetime = “2009-11-27 00:00:30”. Remembering [clearly] that the odometer read 100 miles for the duration and that we [Nils (@UPBeaches) and yours truly] hiked about a mile [or two], the computed distance [PHP script took 12+ hours on a Intel(R) Xeon(R) CPU L5420 2.50GHz Linux machine with 360MB RAM running x86 version of CentOS 4.7 operating system] from the tracks came out to be 101.9471 miles – a decent agreement I would say. Wouldn’t you agree?

Any suggestions/recommendations to optimize the SQL query and speed up the computation / execution of the PHP script will be greatly appreciated.

Updates (2009.11.30)

With significant suggestions from Srichand, Peter and Jon, I modified the MySQL table structure as well as the PHP script. With the first set of improvements, date and time were merged into one field. That reduced the overall execution time from 650+ minutes to 45 minutes. Second set of improvements included adding an index on date_time field as well as modifying the definition few fields. That reduced the overall execution time to a whopping 3 seconds.

1
2
3
4
5
6
7
8
9
10

CREATE TABLE IF NOT EXISTS `MyDatabase`.`TRK` (
  `id`          int( 11 ) NOT NULL AUTO_INCREMENT PRIMARY KEY ,
  `latitude`    float NOT NULL DEFAULT '0' ,
  `longitude`   float NOT NULL DEFAULT '0' ,
  `altitude`    float NOT NULL DEFAULT '0' ,
  `date_time`   float NOT NULL DEFAULT '0000-00-00 00:00:00' 
) ENGINE = MYISAM DEFAULT CHARSET latin1 AUTO_INCREMENT=1 ;
 
CREATE UNIQUE INDEX dt ON `MyDatabase`.`TRK` (`date_time`);
CREATE UNIQUE INDEX lldt ON `MyDatabase`.`TRK` (`latitude`,`longitude`,`date_time`);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

<!--?php 
# Database connection
$host     = 'localhost';
$dbuser   = 'DB_USERNAME';
$dbpasswd = 'DB_PASSWORD';
$database = 'DB_NAME';
 
$connect  = mysql_connect($host, $dbuser, $dbpasswd) or
            die('&lt;b&gt;MySQL Connection Error:&lt;/b&gt; ' .
            mysql_errno() . ': ' .
            mysql_error());
 
mysql_select_db($database, $connect) or
            die('&lt;b&gt;Database Connection Error:&lt;/b&gt; ' .
            mysql_errno() . ': ' .
            mysql_error());
 
# Radius of Earth (in miles)
# Use appropriate conversion factors if
# the distance is desired in other units.
$earth_radius  = 3960.00;
$distance_unit = "miles";
 
# Date / Time in UTC 
$start_datetime = "2009-11-25 03:00:00";
$end_datetime   = "2009-11-29 13:00:00";
 
# Running indices
$i         = 1;
$total_dis = 0.00;
 
# SQL Query #1
# Get all GPS/Date Time points between start_datetime and
# end_datetime
$sql1  = "SELECT trk_latitude, trk_longitude, trk_datetime ";
$sql1 .= "FROM tracks WHERE trk_datetime BETWEEN ";
$sql1 .= "'$start_datetime' AND '$end_datetime' ";
$sql1 .= "ORDER BY trk_datetime ASC ";
$res1  = mysql_query($sql1) or
          die('Invalid Query : ' .
          mysql_errno() . ' : ' .
          mysql_error());
 
while ($myrow1 = mysql_fetch_array($res1)) {
  $lat1 = $myrow1['trk_latitude'];
  $lon1 = $myrow1['trk_longitude'];
  $dt1  = $myrow1['trk_datetime'];
 
  # SQL Query #2
  # Get the GPS/Date Time point next to the one in question
  $sql2   = "SELECT trk_latitude, trk_longitude, trk_datetime ";
  $sql2  .= "FROM tracks WHERE trk_datetime &gt; '$dt1' ORDER BY ";
  $sql2  .= "trk_datetime ASC LIMIT 1 ";
  $res2   = mysql_query($sql2) or
             die('Invalid Query : ' .
             mysql_errno() . ' : ' .
             mysql_error());
  $nres2  = mysql_num_rows($res2);
 
  if($nres2 == 1) {
    while ($myrow2 = mysql_fetch_array($res2)) {
      $lat2 = $myrow2['trk_latitude'];
      $lon2 = $myrow2['trk_longitude'];
      $dt2  = $myrow2['trk_datetime'];
 
      # Compute distance between two points in question using
      # Haversine formula/function.
      # Add the haversine distance to the total/cumulative distance
      $haver_dis = distance_haversine($lat1, $lon1, $lat2, $lon2);
      $total_dis = $total_dis + $haver_dis ;
      $i         = str_pad($i, 6, "0", STR_PAD_LEFT);
 
      # Present results at each step
      # Can be piped out to a flat text file, if need be.
      # Useful to check the speed of movement, etc.
      # $time_now = date('r');  
      # echo " $i : $time_now : $dt1 : $lat1 : $lon1 : $dt2 : $lat2 : $lon2 : $haver_dis : $total_dis\n";

      # Increment the running index
      $i++;
    }
  }
}
 
# Function to accept latitue and longitude of 
# two locations and compute the distance between them.
function distance_haversine($lat1, $lon1, $lat2, $lon2) {
  global $earth_radius;
  $delta_lat = $lat2 - $lat1 ;
  $delta_lon = $lon2 - $lon1 ;
  $alpha     = $delta_lat/2 ;
  $beta      = $delta_lon/2 ;
 
  $a        = sin(deg2rad($alpha)) * sin(deg2rad($alpha)) + cos(deg2rad($lat1)) * cos(deg2rad($lat2)) * sin(deg2rad($beta)) * sin(deg2rad($beta)) ;
  $c        = asin(min(1, sqrt($a)));
  $distance = 2*$earth_radius * $c;
  $distance = round($distance, 4);
 
  return $distance;
}
 
# Print the summary
echo "\n";
echo "  Start Date Time : $start_datetime\n";
echo "  End Date Time   : $end_datetime\n";
echo "  Total Distance  : $total_dis $distance_unit\n";
echo "\n";
 
# Close the database connection
mysql_close($connect);
?-->

One Reply to “PHP – Computing Total Travel Distance From GPS Tracks”

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.