Seventh Sense Rambling about life's little things, in 7 ≡ 1 (mod 6) fashion

« | »

PHP – Computing Total Travel Distance From GPS Tracks

November 29th, 2009 @ 20:33:47 | GPS, MySQL, PHP

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('<b>MySQL Connection Error:</b> ' .
            mysql_errno() . ': ' .
            mysql_error());
 
mysql_select_db($database, $connect) or
            die('<b>Database Connection Error:</b> ' .
            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)) > ";
  $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('<b>MySQL Connection Error:</b> ' .
            mysql_errno() . ': ' .
            mysql_error());
 
mysql_select_db($database, $connect) or
            die('<b>Database Connection Error:</b> ' .
            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 > '$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);
?>
Share
divider

Responses to PHP – Computing Total Travel Distance From GPS Tracks

  1. NUXI says:
    2009.11.30 at 20:37:54

    I’ve been looking for a topic for a new blog post, so I turned my suggestions into one:

    http://vault24.org/post/485

    Reply
  2. M. Burke says:
    2009.12.13 at 01:22:35

    After looking over the reviews of the various GPS units available, I chose the Garmin 260W for both price and ease of use. We just took our first long distance trip from Northern Michigan to Toledo, Ohio, and I couldn’t be happier with it. Setting it up is a breeze and the graphics are excellent, even on a very sunny day. At night, it switches automatically to an easy-on-the-eyes night mode.
    The best feature is the voice prompt that tells you the street name and distance to your next turn. Toledo streets, like most big cities, are congested and confusing, but the 260W came through, getting us to our destinations every time. I’m sold and will never travel without my Garmin.

    Reply
  3. Sofia Ahr says:
    2009.12.19 at 17:55:45

    Great article, thank you for writing about this. You have a lot of educational articles here, thanks again! I really enjoy this hobby, my daughter and I have been participating in it for awhile now. We are contemplating purchasing a Magellan RoadMate for our vehicle. Do you have any experience with this unit? Click here if you’d like to check out my site. Thanks again for a very informative site!

    Reply
  4. Doug Riess says:
    2009.12.21 at 12:37:20

    Excellent site. How long have been working in Testing? What do you make of Microsoft’s Alan Page and others writing essays about how they improve software? I heard a presentation by Page a couple years ago about large-scale automation, very interesting stuff. Click here if you’d like to check out my site.

    Reply


Leave a Reply


Most of these posts, especially the ones with any hint of technical jargon, are intended to be Note2Self. But if any of them float your boat, then feel free to sail along. If you feel so generous, improve my journey with your comments &/or thoughts!
Looking for MS Thesis or PhD Dissertation Template in LaTeX? Click below!

MTU Create The Future
Twitter

Archives

Planet Kannada

Twitter: @sgowtham Facebook: @sgowtham Linked In: sgowtham

Opinions expressed in these pages are purely personal and do not reflect those of any other institution and/or individual
© 2002-2018 Gowtham • All Rights Reserved