src/viktrack.c

   1 /*
   2  * viking -- GPS Data and Topo Analyzer, Explorer, and Manager
   3  *
   4  * Copyright (C) 2003-2005, Evan Battaglia <gtoevan@gmx.net>
   5  * Copyright (c) 2012, Rob Norris <rw_norris@hotmail.com>
   6  *
   7  * This program is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation; either version 2 of the License, or
  10  * (at your option) any later version.
  11  *
  12  * This program is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with this program; if not, write to the Free Software
  19  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  20  *
  21  */
  22 #ifdef HAVE_CONFIG_H
  23 #include "config.h"
  24 #endif
  25
  26 #include <glib.h>
  27 #include <time.h>
  28 #include <stdlib.h>
  29 #ifdef HAVE_STRING_H
  30 #include <string.h>
  31 #endif
  32 #ifdef HAVE_MATH_H
  33 #include <math.h>
  34 #endif
  35
  36 #include "coords.h"
  37 #include "vikcoord.h"
  38 #include "viktrack.h"
  39 #include "globals.h"
  40 #include "dems.h"
  41
  42 VikTrack *vik_track_new()
  43 {
  44   VikTrack *tr = g_malloc0 ( sizeof ( VikTrack ) );
  45   tr->ref_count = 1;
  46   return tr;
  47 }
  48
  49 void vik_track_set_comment_no_copy(VikTrack *tr, gchar *comment)
  50 {
  51   if ( tr->comment )
  52     g_free ( tr->comment );
  53   tr->comment = comment;
  54 }
  55
  56
  57 void vik_track_set_name(VikTrack *tr, const gchar *name)
  58 {
  59   if ( tr->name )
  60     g_free ( tr->name );
  61
  62   tr->name = g_strdup(name);
  63 }
  64
  65 void vik_track_set_comment(VikTrack *tr, const gchar *comment)
  66 {
  67   if ( tr->comment )
  68     g_free ( tr->comment );
  69
  70   if ( comment && comment[0] != '\0' )
  71     tr->comment = g_strdup(comment);
  72   else
  73     tr->comment = NULL;
  74 }
  75
  76 void vik_track_set_description(VikTrack *tr, const gchar *description)
  77 {
  78   if ( tr->description )
  79     g_free ( tr->description );
  80
  81   if ( description && description[0] != '\0' )
  82     tr->description = g_strdup(description);
  83   else
  84     tr->description = NULL;
  85 }
  86
  87 void vik_track_ref(VikTrack *tr)
  88 {
  89   tr->ref_count++;
  90 }
  91
  92 void vik_track_set_property_dialog(VikTrack *tr, GtkWidget *dialog)
  93 {
  94   /* Warning: does not check for existing dialog */
  95   tr->property_dialog = dialog;
  96 }
  97
  98 void vik_track_clear_property_dialog(VikTrack *tr)
  99 {
 100   tr->property_dialog = NULL;
 101 }
 102
 103 void vik_track_free(VikTrack *tr)
 104 {
 105   if ( tr->ref_count-- > 1 )
 106     return;
 107
 108   if ( tr->name )
 109     g_free ( tr->name );
 110   if ( tr->comment )
 111     g_free ( tr->comment );
 112   if ( tr->description )
 113     g_free ( tr->description );
 114   g_list_foreach ( tr->trackpoints, (GFunc) g_free, NULL );
 115   g_list_free( tr->trackpoints );
 116   if (tr->property_dialog)
 117     if ( GTK_IS_WIDGET(tr->property_dialog) )
 118       gtk_widget_destroy ( GTK_WIDGET(tr->property_dialog) );
 119   g_free ( tr );
 120 }
 121
 122 /**
 123  * vik_track_copy:
 124  * @tr: The Track to copy
 125  * @copy_points: Whether to copy the track points or not
 126  *
 127  * Normally for copying the track it's best to copy all the trackpoints
 128  * However for some operations such as splitting tracks the trackpoints will be managed separately, so no need to copy them.
 129  *
 130  * Returns: the copied VikTrack
 131  */
 132 VikTrack *vik_track_copy ( const VikTrack *tr, gboolean copy_points )
 133 {
 134   VikTrack *new_tr = vik_track_new();
 135   VikTrackpoint *new_tp;
 136   GList *tp_iter = tr->trackpoints;
 137   new_tr->visible = tr->visible;
 138   new_tr->is_route = tr->is_route;
 139   new_tr->has_color = tr->has_color;
 140   new_tr->color = tr->color;
 141   new_tr->bbox = tr->bbox;
 142   new_tr->trackpoints = NULL;
 143   if ( copy_points )
 144   {
 145     while ( tp_iter )
 146     {
 147       new_tp = g_malloc ( sizeof ( VikTrackpoint ) );
 148       *new_tp = *((VikTrackpoint *)(tp_iter->data));
 149       new_tr->trackpoints = g_list_append ( new_tr->trackpoints, new_tp );
 150       tp_iter = tp_iter->next;
 151     }
 152   }
 153   vik_track_set_name(new_tr,tr->name);
 154   vik_track_set_comment(new_tr,tr->comment);
 155   vik_track_set_description(new_tr,tr->description);
 156   return new_tr;
 157 }
 158
 159 VikTrackpoint *vik_trackpoint_new()
 160 {
 161   VikTrackpoint *tp = g_malloc0(sizeof(VikTrackpoint));
 162   tp->speed = NAN;
 163   tp->course = NAN;
 164   tp->altitude = VIK_DEFAULT_ALTITUDE;
 165   tp->hdop = VIK_DEFAULT_DOP;
 166   tp->vdop = VIK_DEFAULT_DOP;
 167   tp->pdop = VIK_DEFAULT_DOP;
 168   return tp;
 169 }
 170
 171 void vik_trackpoint_free(VikTrackpoint *tp)
 172 {
 173   g_free(tp);
 174 }
 175
 176 VikTrackpoint *vik_trackpoint_copy(VikTrackpoint *tp)
 177 {
 178   VikTrackpoint *rv = vik_trackpoint_new();
 179   *rv = *tp;
 180   return rv;
 181 }
 182
 183 /**
 184  * track_recalculate_bounds_last_tp:
 185  * @trk:   The track to consider the recalculation on
 186  *
 187  * A faster bounds check, since it only considers the last track point
 188  */
 189 static void track_recalculate_bounds_last_tp ( VikTrack *trk )
 190 {
 191   GList *tpl = g_list_last ( trk->trackpoints );
 192
 193   if ( tpl ) {
 194     struct LatLon ll;
 195     // See if this trackpoint increases the track bounds and update if so
 196     vik_coord_to_latlon ( &(VIK_TRACKPOINT(tpl->data)->coord), &ll );
 197     if ( ll.lat > trk->bbox.north )
 198       trk->bbox.north = ll.lat;
 199     if ( ll.lon < trk->bbox.west )
 200       trk->bbox.west = ll.lon;
 201     if ( ll.lat < trk->bbox.south )
 202       trk->bbox.south = ll.lat;
 203     if ( ll.lon > trk->bbox.east )
 204       trk->bbox.east = ll.lon;
 205   }
 206 }
 207
 208 /**
 209  * vik_track_add_trackpoint:
 210  * @tr:          The track to which the trackpoint will be added
 211  * @tp:          The trackpoint to add
 212  * @recalculate: Whether to perform any associated properties recalculations
 213  *               Generally one should avoid recalculation via this method if adding lots of points
 214  *               (But ensure calculate_bounds() is called after adding all points!!)
 215  *
 216  * The trackpoint is added to the end of the existing trackpoint list
 217  */
 218 void vik_track_add_trackpoint ( VikTrack *tr, VikTrackpoint *tp, gboolean recalculate )
 219 {
 220   tr->trackpoints = g_list_append ( tr->trackpoints, tp );
 221   if ( recalculate )
 222     track_recalculate_bounds_last_tp ( tr );
 223 }
 224
 225 gdouble vik_track_get_length(const VikTrack *tr)
 226 {
 227   gdouble len = 0.0;
 228   if ( tr->trackpoints )
 229   {
 230     GList *iter = tr->trackpoints->next;
 231     while (iter)
 232     {
 233       if ( ! VIK_TRACKPOINT(iter->data)->newsegment )
 234         len += vik_coord_diff ( &(VIK_TRACKPOINT(iter->data)->coord),
 235                                 &(VIK_TRACKPOINT(iter->prev->data)->coord) );
 236       iter = iter->next;
 237     }
 238   }
 239   return len;
 240 }
 241
 242 gdouble vik_track_get_length_including_gaps(const VikTrack *tr)
 243 {
 244   gdouble len = 0.0;
 245   if ( tr->trackpoints )
 246   {
 247     GList *iter = tr->trackpoints->next;
 248     while (iter)
 249     {
 250       len += vik_coord_diff ( &(VIK_TRACKPOINT(iter->data)->coord),
 251                               &(VIK_TRACKPOINT(iter->prev->data)->coord) );
 252       iter = iter->next;
 253     }
 254   }
 255   return len;
 256 }
 257
 258 gulong vik_track_get_tp_count(const VikTrack *tr)
 259 {
 260   gulong num = 0;
 261   GList *iter = tr->trackpoints;
 262   while ( iter )
 263   {
 264     num++;
 265     iter = iter->next;
 266   }
 267   return num;
 268 }
 269
 270 gulong vik_track_get_dup_point_count ( const VikTrack *tr )
 271 {
 272   gulong num = 0;
 273   GList *iter = tr->trackpoints;
 274   while ( iter )
 275   {
 276     if ( iter->next && vik_coord_equals ( &(VIK_TRACKPOINT(iter->data)->coord),
 277                        &(VIK_TRACKPOINT(iter->next->data)->coord) ) )
 278       num++;
 279     iter = iter->next;
 280   }
 281   return num;
 282 }
 283
 284 /*
 285  * Deletes adjacent points that have the same position
 286  * Returns the number of points that were deleted
 287  */
 288 gulong vik_track_remove_dup_points ( VikTrack *tr )
 289 {
 290   gulong num = 0;
 291   GList *iter = tr->trackpoints;
 292   while ( iter )
 293   {
 294     if ( iter->next && vik_coord_equals ( &(VIK_TRACKPOINT(iter->data)->coord),
 295                        &(VIK_TRACKPOINT(iter->next->data)->coord) ) )
 296     {
 297       num++;
 298       // Maintain track segments
 299       if ( VIK_TRACKPOINT(iter->next->data)->newsegment && (iter->next)->next )
 300         VIK_TRACKPOINT(((iter->next)->next)->data)->newsegment = TRUE;
 301
 302       vik_trackpoint_free ( iter->next->data );
 303       tr->trackpoints = g_list_delete_link ( tr->trackpoints, iter->next );
 304     }
 305     else
 306       iter = iter->next;
 307   }
 308
 309   // NB isn't really be necessary as removing duplicate points shouldn't alter the bounds!
 310   vik_track_calculate_bounds ( tr );
 311
 312   return num;
 313 }
 314
 315 /*
 316  * Get a count of trackpoints with the same defined timestamp
 317  * Note is using timestamps with a resolution with 1 second
 318  */
 319 gulong vik_track_get_same_time_point_count ( const VikTrack *tr )
 320 {
 321   gulong num = 0;
 322   GList *iter = tr->trackpoints;
 323   while ( iter ) {
 324     if ( iter->next &&
 325          ( VIK_TRACKPOINT(iter->data)->has_timestamp &&
 326            VIK_TRACKPOINT(iter->next->data)->has_timestamp ) &&
 327          ( VIK_TRACKPOINT(iter->data)->timestamp ==
 328            VIK_TRACKPOINT(iter->next->data)->timestamp) )
 329       num++;
 330     iter = iter->next;
 331   }
 332   return num;
 333 }
 334
 335 /*
 336  * Deletes adjacent points that have the same defined timestamp
 337  * Returns the number of points that were deleted
 338  */
 339 gulong vik_track_remove_same_time_points ( VikTrack *tr )
 340 {
 341   gulong num = 0;
 342   GList *iter = tr->trackpoints;
 343   while ( iter ) {
 344     if ( iter->next &&
 345          ( VIK_TRACKPOINT(iter->data)->has_timestamp &&
 346            VIK_TRACKPOINT(iter->next->data)->has_timestamp ) &&
 347          ( VIK_TRACKPOINT(iter->data)->timestamp ==
 348            VIK_TRACKPOINT(iter->next->data)->timestamp) ) {
 349
 350       num++;
 351
 352       // Maintain track segments
 353       if ( VIK_TRACKPOINT(iter->next->data)->newsegment && (iter->next)->next )
 354         VIK_TRACKPOINT(((iter->next)->next)->data)->newsegment = TRUE;
 355
 356       vik_trackpoint_free ( iter->next->data );
 357       tr->trackpoints = g_list_delete_link ( tr->trackpoints, iter->next );
 358     }
 359     else
 360       iter = iter->next;
 361   }
 362
 363   vik_track_calculate_bounds ( tr );
 364
 365   return num;
 366 }
 367
 368 /*
 369  * Deletes all 'extra' trackpoint information
 370  *  such as time stamps, speed, course etc...
 371  */
 372 void vik_track_to_routepoints ( VikTrack *tr )
 373 {
 374   GList *iter = tr->trackpoints;
 375   while ( iter ) {
 376
 377     // c.f. with vik_trackpoint_new()
 378
 379     VIK_TRACKPOINT(iter->data)->has_timestamp = FALSE;
 380     VIK_TRACKPOINT(iter->data)->timestamp = 0;
 381     VIK_TRACKPOINT(iter->data)->speed = NAN;
 382     VIK_TRACKPOINT(iter->data)->course = NAN;
 383     VIK_TRACKPOINT(iter->data)->hdop = VIK_DEFAULT_DOP;
 384     VIK_TRACKPOINT(iter->data)->vdop = VIK_DEFAULT_DOP;
 385     VIK_TRACKPOINT(iter->data)->pdop = VIK_DEFAULT_DOP;
 386     VIK_TRACKPOINT(iter->data)->nsats = 0;
 387     VIK_TRACKPOINT(iter->data)->fix_mode = VIK_GPS_MODE_NOT_SEEN;
 388
 389     iter = iter->next;
 390   }
 391 }
 392
 393 guint vik_track_get_segment_count(const VikTrack *tr)
 394 {
 395   guint num = 1;
 396   GList *iter = tr->trackpoints;
 397   if ( !iter )
 398     return 0;
 399   while ( (iter = iter->next) )
 400   {
 401     if ( VIK_TRACKPOINT(iter->data)->newsegment )
 402       num++;
 403   }
 404   return num;
 405 }
 406
 407 VikTrack **vik_track_split_into_segments(VikTrack *t, guint *ret_len)
 408 {
 409   VikTrack **rv;
 410   VikTrack *tr;
 411   guint i;
 412   guint segs = vik_track_get_segment_count(t);
 413   GList *iter;
 414
 415   if ( segs < 2 )
 416   {
 417     *ret_len = 0;
 418     return NULL;
 419   }
 420
 421   rv = g_malloc ( segs * sizeof(VikTrack *) );
 422   tr = vik_track_copy ( t, TRUE );
 423   rv[0] = tr;
 424   iter = tr->trackpoints;
 425
 426   i = 1;
 427   while ( (iter = iter->next) )
 428   {
 429     if ( VIK_TRACKPOINT(iter->data)->newsegment )
 430     {
 431       iter->prev->next = NULL;
 432       iter->prev = NULL;
 433       rv[i] = vik_track_copy ( tr, FALSE );
 434       rv[i]->trackpoints = iter;
 435
 436       vik_track_calculate_bounds ( rv[i] );
 437
 438       i++;
 439     }
 440   }
 441   *ret_len = segs;
 442   return rv;
 443 }
 444
 445 /*
 446  * Simply remove any subsequent segment markers in a track to form one continuous track
 447  * Return the number of segments merged
 448  */
 449 guint vik_track_merge_segments(VikTrack *tr)
 450 {
 451   guint num = 0;
 452   GList *iter = tr->trackpoints;
 453   if ( !iter )
 454     return num;
 455
 456   // Always skip the first point as this should be the first segment
 457   iter = iter->next;
 458
 459   while ( (iter = iter->next) )
 460   {
 461     if ( VIK_TRACKPOINT(iter->data)->newsegment ) {
 462       VIK_TRACKPOINT(iter->data)->newsegment = FALSE;
 463       num++;
 464     }
 465   }
 466   return num;
 467 }
 468
 469 void vik_track_reverse ( VikTrack *tr )
 470 {
 471   if ( ! tr->trackpoints )
 472     return;
 473
 474   tr->trackpoints = g_list_reverse(tr->trackpoints);
 475
 476   /* fix 'newsegment' */
 477   GList *iter = g_list_last ( tr->trackpoints );
 478   while ( iter )
 479   {
 480     if ( ! iter->next ) /* last segment, was first, cancel newsegment. */
 481       VIK_TRACKPOINT(iter->data)->newsegment = FALSE;
 482     if ( ! iter->prev ) /* first segment by convention has newsegment flag. */
 483       VIK_TRACKPOINT(iter->data)->newsegment = TRUE;
 484     else if ( VIK_TRACKPOINT(iter->data)->newsegment && iter->next )
 485     {
 486       VIK_TRACKPOINT(iter->next->data)->newsegment = TRUE;
 487       VIK_TRACKPOINT(iter->data)->newsegment = FALSE;
 488     }
 489     iter = iter->prev;
 490   }
 491 }
 492
 493 gdouble vik_track_get_average_speed(const VikTrack *tr)
 494 {
 495   gdouble len = 0.0;
 496   guint32 time = 0;
 497   if ( tr->trackpoints )
 498   {
 499     GList *iter = tr->trackpoints->next;
 500     while (iter)
 501     {
 502       if ( VIK_TRACKPOINT(iter->data)->has_timestamp &&
 503           VIK_TRACKPOINT(iter->prev->data)->has_timestamp &&
 504           (! VIK_TRACKPOINT(iter->data)->newsegment) )
 505       {
 506         len += vik_coord_diff ( &(VIK_TRACKPOINT(iter->data)->coord),
 507                                 &(VIK_TRACKPOINT(iter->prev->data)->coord) );
 508         time += ABS(VIK_TRACKPOINT(iter->data)->timestamp - VIK_TRACKPOINT(iter->prev->data)->timestamp);
 509       }
 510       iter = iter->next;
 511     }
 512   }
 513   return (time == 0) ? 0 : ABS(len/time);
 514 }
 515
 516 /**
 517  * Based on a simple average speed, but with a twist - to give a moving average.
 518  *  . GPSs often report a moving average in their statistics output
 519  *  . bicycle speedos often don't factor in time when stopped - hence reporting a moving average for speed
 520  *
 521  * Often GPS track will record every second but not when stationary
 522  * This method doesn't use samples that differ over the specified time limit - effectively skipping that time chunk from the total time
 523  *
 524  * Suggest to use 60 seconds as the stop length (as the default used in the TrackWaypoint draw stops factor)
 525  */
 526 gdouble vik_track_get_average_speed_moving (const VikTrack *tr, int stop_length_seconds)
 527 {
 528   gdouble len = 0.0;
 529   guint32 time = 0;
 530   if ( tr->trackpoints )
 531   {
 532     GList *iter = tr->trackpoints->next;
 533     while (iter)
 534     {
 535       if ( VIK_TRACKPOINT(iter->data)->has_timestamp &&
 536           VIK_TRACKPOINT(iter->prev->data)->has_timestamp &&
 537           (! VIK_TRACKPOINT(iter->data)->newsegment) )
 538       {
 539         if ( ( VIK_TRACKPOINT(iter->data)->timestamp - VIK_TRACKPOINT(iter->prev->data)->timestamp ) < stop_length_seconds ) {
 540           len += vik_coord_diff ( &(VIK_TRACKPOINT(iter->data)->coord),
 541                                   &(VIK_TRACKPOINT(iter->prev->data)->coord) );
 542
 543           time += ABS(VIK_TRACKPOINT(iter->data)->timestamp - VIK_TRACKPOINT(iter->prev->data)->timestamp);
 544         }
 545       }
 546       iter = iter->next;
 547     }
 548   }
 549   return (time == 0) ? 0 : ABS(len/time);
 550 }
 551
 552 gdouble vik_track_get_max_speed(const VikTrack *tr)
 553 {
 554   gdouble maxspeed = 0.0, speed = 0.0;
 555   if ( tr->trackpoints )
 556   {
 557     GList *iter = tr->trackpoints->next;
 558     while (iter)
 559     {
 560       if ( VIK_TRACKPOINT(iter->data)->has_timestamp &&
 561           VIK_TRACKPOINT(iter->prev->data)->has_timestamp &&
 562           (! VIK_TRACKPOINT(iter->data)->newsegment) )
 563       {
 564         speed =  vik_coord_diff ( &(VIK_TRACKPOINT(iter->data)->coord), &(VIK_TRACKPOINT(iter->prev->data)->coord) )
 565                  / ABS(VIK_TRACKPOINT(iter->data)->timestamp - VIK_TRACKPOINT(iter->prev->data)->timestamp);
 566         if ( speed > maxspeed )
 567           maxspeed = speed;
 568       }
 569       iter = iter->next;
 570     }
 571   }
 572   return maxspeed;
 573 }
 574
 575 void vik_track_convert ( VikTrack *tr, VikCoordMode dest_mode )
 576 {
 577   GList *iter = tr->trackpoints;
 578   while (iter)
 579   {
 580     vik_coord_convert ( &(VIK_TRACKPOINT(iter->data)->coord), dest_mode );
 581     iter = iter->next;
 582   }
 583 }
 584
 585 /* I understood this when I wrote it ... maybe ... Basically it eats up the
 586  * proper amounts of length on the track and averages elevation over that. */
 587 gdouble *vik_track_make_elevation_map ( const VikTrack *tr, guint16 num_chunks )
 588 {
 589   gdouble *pts;
 590   gdouble total_length, chunk_length, current_dist, current_area_under_curve, current_seg_length, dist_along_seg = 0.0;
 591   gdouble altitude1, altitude2;
 592   guint16 current_chunk;
 593   gboolean ignore_it = FALSE;
 594
 595   GList *iter = tr->trackpoints;
 596
 597   if (!iter || !iter->next) /* zero- or one-point track */
 598           return NULL;
 599
 600   { /* test if there's anything worth calculating */
 601     gboolean okay = FALSE;
 602     while ( iter )
 603     {
 604       // Sometimes a GPS device (or indeed any random file) can have stupid numbers for elevations
 605       // Since when is 9.9999e+24 a valid elevation!!
 606       // This can happen when a track (with no elevations) is uploaded to a GPS device and then redownloaded (e.g. using a Garmin Legend EtrexHCx)
 607       // Some protection against trying to work with crazily massive numbers (otherwise get SIGFPE, Arithmetic exception)
 608       if ( VIK_TRACKPOINT(iter->data)->altitude != VIK_DEFAULT_ALTITUDE &&
 609            VIK_TRACKPOINT(iter->data)->altitude < 1E9 ) {
 610         okay = TRUE; break;
 611       }
 612       iter = iter->next;
 613     }
 614     if ( ! okay )
 615       return NULL;
 616   }
 617
 618   iter = tr->trackpoints;
 619
 620   g_assert ( num_chunks < 16000 );
 621
 622   pts = g_malloc ( sizeof(gdouble) * num_chunks );
 623
 624   total_length = vik_track_get_length_including_gaps ( tr );
 625   chunk_length = total_length / num_chunks;
 626
 627   /* Zero chunk_length (eg, track of 2 tp with the same loc) will cause crash */
 628   if (chunk_length <= 0) {
 629     g_free(pts);
 630     return NULL;
 631   }
 632
 633   current_dist = 0.0;
 634   current_area_under_curve = 0;
 635   current_chunk = 0;
 636   current_seg_length = 0;
 637
 638   current_seg_length = vik_coord_diff ( &(VIK_TRACKPOINT(iter->data)->coord),
 639       &(VIK_TRACKPOINT(iter->next->data)->coord) );
 640   altitude1 = VIK_TRACKPOINT(iter->data)->altitude;
 641   altitude2 = VIK_TRACKPOINT(iter->next->data)->altitude;
 642   dist_along_seg = 0;
 643
 644   while ( current_chunk < num_chunks ) {
 645
 646     /* go along current seg */
 647     if ( current_seg_length && (current_seg_length - dist_along_seg) > chunk_length ) {
 648       dist_along_seg += chunk_length;
 649
 650       /*        /
 651        *   pt2 *
 652        *      /x       altitude = alt_at_pt_1 + alt_at_pt_2 / 2 = altitude1 + slope * dist_value_of_pt_inbetween_pt1_and_pt2
 653        *     /xx   avg altitude = area under curve / chunk len
 654        *pt1 *xxx   avg altitude = altitude1 + (altitude2-altitude1)/(current_seg_length)*(dist_along_seg + (chunk_len/2))
 655        *   / xxx
 656        *  /  xxx
 657        **/
 658
 659       if ( ignore_it )
 660         // Seemly can't determine average for this section - so use last known good value (much better than just sticking in zero)
 661         pts[current_chunk] = altitude1;
 662       else
 663         pts[current_chunk] = altitude1 + (altitude2-altitude1)*((dist_along_seg - (chunk_length/2))/current_seg_length);
 664
 665       current_chunk++;
 666     } else {
 667       /* finish current seg */
 668       if ( current_seg_length ) {
 669         gdouble altitude_at_dist_along_seg = altitude1 + (altitude2-altitude1)/(current_seg_length)*dist_along_seg;
 670         current_dist = current_seg_length - dist_along_seg;
 671         current_area_under_curve = current_dist*(altitude_at_dist_along_seg + altitude2)*0.5;
 672       } else { current_dist = current_area_under_curve = 0; } /* should only happen if first current_seg_length == 0 */
 673
 674       /* get intervening segs */
 675       iter = iter->next;
 676       while ( iter && iter->next ) {
 677         current_seg_length = vik_coord_diff ( &(VIK_TRACKPOINT(iter->data)->coord),
 678             &(VIK_TRACKPOINT(iter->next->data)->coord) );
 679         altitude1 = VIK_TRACKPOINT(iter->data)->altitude;
 680         altitude2 = VIK_TRACKPOINT(iter->next->data)->altitude;
 681         ignore_it = VIK_TRACKPOINT(iter->next->data)->newsegment;
 682
 683         if ( chunk_length - current_dist >= current_seg_length ) {
 684           current_dist += current_seg_length;
 685           current_area_under_curve += current_seg_length * (altitude1+altitude2) * 0.5;
 686           iter = iter->next;
 687         } else {
 688           break;
 689         }
 690       }
 691
 692       /* final seg */
 693       dist_along_seg = chunk_length - current_dist;
 694       if ( ignore_it || ( iter && !iter->next ) ) {
 695         pts[current_chunk] = current_area_under_curve / current_dist;
 696         if (!iter->next) {
 697           int i;
 698           for (i = current_chunk + 1; i < num_chunks; i++)
 699             pts[i] = pts[current_chunk];
 700           break;
 701         }
 702       }
 703       else {
 704         current_area_under_curve += dist_along_seg * (altitude1 + (altitude2 - altitude1)*dist_along_seg/current_seg_length);
 705         pts[current_chunk] = current_area_under_curve / chunk_length;
 706       }
 707
 708       current_dist = 0;
 709       current_chunk++;
 710     }
 711   }
 712
 713   return pts;
 714 }
 715
 716
 717 void vik_track_get_total_elevation_gain(const VikTrack *tr, gdouble *up, gdouble *down)
 718 {
 719   gdouble diff;
 720   *up = *down = 0;
 721   if ( tr->trackpoints && VIK_TRACKPOINT(tr->trackpoints->data)->altitude != VIK_DEFAULT_ALTITUDE )
 722   {
 723     GList *iter = tr->trackpoints->next;
 724     while (iter)
 725     {
 726       diff = VIK_TRACKPOINT(iter->data)->altitude - VIK_TRACKPOINT(iter->prev->data)->altitude;
 727       if ( diff > 0 )
 728         *up += diff;
 729       else
 730         *down -= diff;
 731       iter = iter->next;
 732     }
 733   } else
 734     *up = *down = VIK_DEFAULT_ALTITUDE;
 735 }
 736
 737 gdouble *vik_track_make_gradient_map ( const VikTrack *tr, guint16 num_chunks )
 738 {
 739   gdouble *pts;
 740   gdouble *altitudes;
 741   gdouble total_length, chunk_length, current_gradient;
 742   gdouble altitude1, altitude2;
 743   guint16 current_chunk;
 744
 745   g_assert ( num_chunks < 16000 );
 746
 747   total_length = vik_track_get_length_including_gaps ( tr );
 748   chunk_length = total_length / num_chunks;
 749
 750   /* Zero chunk_length (eg, track of 2 tp with the same loc) will cause crash */
 751   if (chunk_length <= 0) {
 752     return NULL;
 753   }
 754
 755   altitudes = vik_track_make_elevation_map (tr, num_chunks);
 756   if (altitudes == NULL) {
 757     return NULL;
 758   }
 759
 760   current_gradient = 0.0;
 761   pts = g_malloc ( sizeof(gdouble) * num_chunks );
 762   for (current_chunk = 0; current_chunk < (num_chunks - 1); current_chunk++) {
 763     altitude1 = altitudes[current_chunk];
 764     altitude2 = altitudes[current_chunk + 1];
 765     current_gradient = 100.0 * (altitude2 - altitude1) / chunk_length;
 766
 767     pts[current_chunk] = current_gradient;
 768   }
 769
 770   pts[current_chunk] = current_gradient;
 771
 772   g_free ( altitudes );
 773
 774   return pts;
 775 }
 776
 777 /* by Alex Foobarian */
 778 gdouble *vik_track_make_speed_map ( const VikTrack *tr, guint16 num_chunks )
 779 {
 780   gdouble *v, *s, *t;
 781   gdouble duration, chunk_dur;
 782   time_t t1, t2;
 783   int i, pt_count, numpts, index;
 784   GList *iter;
 785
 786   if ( ! tr->trackpoints )
 787     return NULL;
 788
 789   g_assert ( num_chunks < 16000 );
 790
 791   t1 = VIK_TRACKPOINT(tr->trackpoints->data)->timestamp;
 792   t2 = VIK_TRACKPOINT(g_list_last(tr->trackpoints)->data)->timestamp;
 793   duration = t2 - t1;
 794
 795   if ( !t1 || !t2 || !duration )
 796     return NULL;
 797
 798   if (duration < 0) {
 799     g_warning("negative duration: unsorted trackpoint timestamps?");
 800     return NULL;
 801   }
 802   pt_count = vik_track_get_tp_count(tr);
 803
 804   v = g_malloc ( sizeof(gdouble) * num_chunks );
 805   chunk_dur = duration / num_chunks;
 806
 807   s = g_malloc(sizeof(double) * pt_count);
 808   t = g_malloc(sizeof(double) * pt_count);
 809
 810   iter = tr->trackpoints->next;
 811   numpts = 0;
 812   s[0] = 0;
 813   t[0] = VIK_TRACKPOINT(tr->trackpoints->data)->timestamp;
 814   numpts++;
 815   while (iter) {
 816     s[numpts] = s[numpts-1] + vik_coord_diff ( &(VIK_TRACKPOINT(iter->prev->data)->coord), &(VIK_TRACKPOINT(iter->data)->coord) );
 817     t[numpts] = VIK_TRACKPOINT(iter->data)->timestamp;
 818     numpts++;
 819     iter = iter->next;
 820   }
 821
 822   /* In the following computation, we iterate through periods of time of duration chunk_dur.
 823    * The first period begins at the beginning of the track.  The last period ends at the end of the track.
 824    */
 825   index = 0; /* index of the current trackpoint. */
 826   for (i = 0; i < num_chunks; i++) {
 827     /* we are now covering the interval from t[0] + i*chunk_dur to t[0] + (i+1)*chunk_dur.
 828      * find the first trackpoint outside the current interval, averaging the speeds between intermediate trackpoints.
 829      */
 830     if (t[0] + i*chunk_dur >= t[index]) {
 831       gdouble acc_t = 0, acc_s = 0;
 832       while (t[0] + i*chunk_dur >= t[index]) {
 833         acc_s += (s[index+1]-s[index]);
 834         acc_t += (t[index+1]-t[index]);
 835         index++;
 836       }
 837       v[i] = acc_s/acc_t;
 838     }
 839     else if (i) {
 840       v[i] = v[i-1];
 841     }
 842     else {
 843       v[i] = 0;
 844     }
 845   }
 846   g_free(s);
 847   g_free(t);
 848   return v;
 849 }
 850
 851 /**
 852  * Make a distance/time map, heavily based on the vik_track_make_speed_map method
 853  */
 854 gdouble *vik_track_make_distance_map ( const VikTrack *tr, guint16 num_chunks )
 855 {
 856   gdouble *v, *s, *t;
 857   gdouble duration, chunk_dur;
 858   time_t t1, t2;
 859   int i, pt_count, numpts, index;
 860   GList *iter;
 861
 862   if ( ! tr->trackpoints )
 863     return NULL;
 864
 865   t1 = VIK_TRACKPOINT(tr->trackpoints->data)->timestamp;
 866   t2 = VIK_TRACKPOINT(g_list_last(tr->trackpoints)->data)->timestamp;
 867   duration = t2 - t1;
 868
 869   if ( !t1 || !t2 || !duration )
 870     return NULL;
 871
 872   if (duration < 0) {
 873     g_warning("negative duration: unsorted trackpoint timestamps?");
 874     return NULL;
 875   }
 876   pt_count = vik_track_get_tp_count(tr);
 877
 878   v = g_malloc ( sizeof(gdouble) * num_chunks );
 879   chunk_dur = duration / num_chunks;
 880
 881   s = g_malloc(sizeof(double) * pt_count);
 882   t = g_malloc(sizeof(double) * pt_count);
 883
 884   iter = tr->trackpoints->next;
 885   numpts = 0;
 886   s[0] = 0;
 887   t[0] = VIK_TRACKPOINT(tr->trackpoints->data)->timestamp;
 888   numpts++;
 889   while (iter) {
 890     s[numpts] = s[numpts-1] + vik_coord_diff ( &(VIK_TRACKPOINT(iter->prev->data)->coord), &(VIK_TRACKPOINT(iter->data)->coord) );
 891     t[numpts] = VIK_TRACKPOINT(iter->data)->timestamp;
 892     numpts++;
 893     iter = iter->next;
 894   }
 895
 896   /* In the following computation, we iterate through periods of time of duration chunk_dur.
 897    * The first period begins at the beginning of the track.  The last period ends at the end of the track.
 898    */
 899   index = 0; /* index of the current trackpoint. */
 900   for (i = 0; i < num_chunks; i++) {
 901     /* we are now covering the interval from t[0] + i*chunk_dur to t[0] + (i+1)*chunk_dur.
 902      * find the first trackpoint outside the current interval, averaging the distance between intermediate trackpoints.
 903      */
 904     if (t[0] + i*chunk_dur >= t[index]) {
 905       gdouble acc_s = 0; // No need for acc_t
 906       while (t[0] + i*chunk_dur >= t[index]) {
 907         acc_s += (s[index+1]-s[index]);
 908         index++;
 909       }
 910       // The only bit that's really different from the speed map - just keep an accululative record distance
 911       v[i] = i ? v[i-1]+acc_s : acc_s;
 912     }
 913     else if (i) {
 914       v[i] = v[i-1];
 915     }
 916     else {
 917       v[i] = 0;
 918     }
 919   }
 920   g_free(s);
 921   g_free(t);
 922   return v;
 923 }
 924
 925 /**
 926  * This uses the 'time' based method to make the graph, (which is a simpler compared to the elevation/distance)
 927  * This results in a slightly blocky graph when it does not have many trackpoints: <60
 928  * NB Somehow the elevation/distance applies some kind of smoothing algorithm,
 929  *   but I don't think any one understands it any more (I certainly don't ATM)
 930  */
 931 gdouble *vik_track_make_elevation_time_map ( const VikTrack *tr, guint16 num_chunks )
 932 {
 933   time_t t1, t2;
 934   gdouble duration, chunk_dur;
 935   GList *iter = tr->trackpoints;
 936
 937   if (!iter || !iter->next) /* zero- or one-point track */
 938     return NULL;
 939
 940   /* test if there's anything worth calculating */
 941   gboolean okay = FALSE;
 942   while ( iter ) {
 943     if ( VIK_TRACKPOINT(iter->data)->altitude != VIK_DEFAULT_ALTITUDE ) {
 944       okay = TRUE;
 945       break;
 946     }
 947     iter = iter->next;
 948   }
 949   if ( ! okay )
 950     return NULL;
 951
 952   t1 = VIK_TRACKPOINT(tr->trackpoints->data)->timestamp;
 953   t2 = VIK_TRACKPOINT(g_list_last(tr->trackpoints)->data)->timestamp;
 954   duration = t2 - t1;
 955
 956   if ( !t1 || !t2 || !duration )
 957     return NULL;
 958
 959   if (duration < 0) {
 960     g_warning("negative duration: unsorted trackpoint timestamps?");
 961     return NULL;
 962   }
 963   gint pt_count = vik_track_get_tp_count(tr);
 964
 965   // Reset iterator back to the beginning
 966   iter = tr->trackpoints;
 967
 968   gdouble *pts = g_malloc ( sizeof(gdouble) * num_chunks ); // The return altitude values
 969   gdouble *s = g_malloc(sizeof(double) * pt_count); // calculation altitudes
 970   gdouble *t = g_malloc(sizeof(double) * pt_count); // calculation times
 971
 972   chunk_dur = duration / num_chunks;
 973
 974   s[0] = VIK_TRACKPOINT(iter->data)->altitude;
 975   t[0] = VIK_TRACKPOINT(iter->data)->timestamp;
 976   iter = tr->trackpoints->next;
 977   gint numpts = 1;
 978   while (iter) {
 979     s[numpts] = VIK_TRACKPOINT(iter->data)->altitude;
 980     t[numpts] = VIK_TRACKPOINT(iter->data)->timestamp;
 981     numpts++;
 982     iter = iter->next;
 983   }
 984
 985  /* In the following computation, we iterate through periods of time of duration chunk_dur.
 986    * The first period begins at the beginning of the track.  The last period ends at the end of the track.
 987    */
 988   gint index = 0; /* index of the current trackpoint. */
 989   gint i;
 990   for (i = 0; i < num_chunks; i++) {
 991     /* we are now covering the interval from t[0] + i*chunk_dur to t[0] + (i+1)*chunk_dur.
 992      * find the first trackpoint outside the current interval, averaging the heights between intermediate trackpoints.
 993      */
 994     if (t[0] + i*chunk_dur >= t[index]) {
 995       gdouble acc_s = s[index]; // initialise to first point
 996       while (t[0] + i*chunk_dur >= t[index]) {
 997         acc_s += (s[index+1]-s[index]);
 998         index++;
 999       }
1000       pts[i] = acc_s;
1001     }
1002     else if (i) {
1003       pts[i] = pts[i-1];
1004     }
1005     else {
1006       pts[i] = 0;
1007     }
1008   }
1009   g_free(s);
1010   g_free(t);
1011
1012   return pts;
1013 }
1014
1015 /**
1016  * Make a speed/distance map
1017  */
1018 gdouble *vik_track_make_speed_dist_map ( const VikTrack *tr, guint16 num_chunks )
1019 {
1020   gdouble *v, *s, *t;
1021   time_t t1, t2;
1022   gint i, pt_count, numpts, index;
1023   GList *iter;
1024   gdouble duration, total_length, chunk_length;
1025
1026   if ( ! tr->trackpoints )
1027     return NULL;
1028
1029   t1 = VIK_TRACKPOINT(tr->trackpoints->data)->timestamp;
1030   t2 = VIK_TRACKPOINT(g_list_last(tr->trackpoints)->data)->timestamp;
1031   duration = t2 - t1;
1032
1033   if ( !t1 || !t2 || !duration )
1034     return NULL;
1035
1036   if (duration < 0) {
1037     g_warning("negative duration: unsorted trackpoint timestamps?");
1038     return NULL;
1039   }
1040
1041   total_length = vik_track_get_length_including_gaps ( tr );
1042   chunk_length = total_length / num_chunks;
1043   pt_count = vik_track_get_tp_count(tr);
1044
1045   if (chunk_length <= 0) {
1046     return NULL;
1047   }
1048
1049   v = g_malloc ( sizeof(gdouble) * num_chunks );
1050   s = g_malloc ( sizeof(double) * pt_count );
1051   t = g_malloc ( sizeof(double) * pt_count );
1052
1053   // No special handling of segments ATM...
1054   iter = tr->trackpoints->next;
1055   numpts = 0;
1056   s[0] = 0;
1057   t[0] = VIK_TRACKPOINT(tr->trackpoints->data)->timestamp;
1058   numpts++;
1059   while (iter) {
1060     s[numpts] = s[numpts-1] + vik_coord_diff ( &(VIK_TRACKPOINT(iter->prev->data)->coord), &(VIK_TRACKPOINT(iter->data)->coord) );
1061     t[numpts] = VIK_TRACKPOINT(iter->data)->timestamp;
1062     numpts++;
1063     iter = iter->next;
1064   }
1065
1066   // Iterate through a portion of the track to get an average speed for that part
1067   // This will essentially interpolate between segments, which I think is right given the usage of 'get_length_including_gaps'
1068   index = 0; /* index of the current trackpoint. */
1069   for (i = 0; i < num_chunks; i++) {
1070     // Similar to the make_speed_map, but instead of using a time chunk, use a distance chunk
1071     if (s[0] + i*chunk_length >= s[index]) {
1072       gdouble acc_t = 0, acc_s = 0;
1073       while (s[0] + i*chunk_length >= s[index]) {
1074         acc_s += (s[index+1]-s[index]);
1075         acc_t += (t[index+1]-t[index]);
1076         index++;
1077       }
1078       v[i] = acc_s/acc_t;
1079     }
1080     else if (i) {
1081       v[i] = v[i-1];
1082     }
1083     else {
1084       v[i] = 0;
1085     }
1086   }
1087   g_free(s);
1088   g_free(t);
1089   return v;
1090 }
1091
1092 /**
1093  * vik_track_get_tp_by_dist:
1094  * @trk:                  The Track on which to find a Trackpoint
1095  * @meters_from_start:    The distance along a track that the trackpoint returned is near
1096  * @get_next_point:       Since there is a choice of trackpoints, this determines which one to return
1097  * @tp_metres_from_start: For the returned Trackpoint, returns the distance along the track
1098  *
1099  * TODO: Consider changing the boolean get_next_point into an enum with these options PREVIOUS, NEXT, NEAREST
1100  *
1101  * Returns: The #VikTrackpoint fitting the criteria or NULL
1102  */
1103 VikTrackpoint *vik_track_get_tp_by_dist ( VikTrack *trk, gdouble meters_from_start, gboolean get_next_point, gdouble *tp_metres_from_start )
1104 {
1105   gdouble current_dist = 0.0;
1106   gdouble current_inc = 0.0;
1107   if ( tp_metres_from_start )
1108     *tp_metres_from_start = 0.0;
1109
1110   if ( trk->trackpoints ) {
1111     GList *iter = g_list_next ( g_list_first ( trk->trackpoints ) );
1112     while (iter) {
1113       current_inc = vik_coord_diff ( &(VIK_TRACKPOINT(iter->data)->coord),
1114                                      &(VIK_TRACKPOINT(iter->prev->data)->coord) );
1115       current_dist += current_inc;
1116       if ( current_dist >= meters_from_start )
1117         break;
1118       iter = g_list_next ( iter );
1119     }
1120     // passed the end of the track
1121     if ( !iter )
1122       return NULL;
1123
1124     if ( tp_metres_from_start )
1125       *tp_metres_from_start = current_dist;
1126
1127     // we've gone past the distance already, is the previous trackpoint wanted?
1128     if ( !get_next_point ) {
1129       if ( iter->prev ) {
1130         if ( tp_metres_from_start )
1131           *tp_metres_from_start = current_dist-current_inc;
1132         return VIK_TRACKPOINT(iter->prev->data);
1133       }
1134     }
1135     return VIK_TRACKPOINT(iter->data);
1136   }
1137
1138   return NULL;
1139 }
1140
1141 /* by Alex Foobarian */
1142 VikTrackpoint *vik_track_get_closest_tp_by_percentage_dist ( VikTrack *tr, gdouble reldist, gdouble *meters_from_start )
1143 {
1144   gdouble dist = vik_track_get_length_including_gaps(tr) * reldist;
1145   gdouble current_dist = 0.0;
1146   gdouble current_inc = 0.0;
1147   if ( tr->trackpoints )
1148   {
1149     GList *iter = tr->trackpoints->next;
1150     GList *last_iter = NULL;
1151     gdouble last_dist = 0.0;
1152     while (iter)
1153     {
1154       current_inc = vik_coord_diff ( &(VIK_TRACKPOINT(iter->data)->coord),
1155                                      &(VIK_TRACKPOINT(iter->prev->data)->coord) );
1156       last_dist = current_dist;
1157       current_dist += current_inc;
1158       if ( current_dist >= dist )
1159         break;
1160       last_iter = iter;
1161       iter = iter->next;
1162     }
1163     if (!iter) { /* passing the end the track */
1164       if (last_iter) {
1165         if (meters_from_start)
1166           *meters_from_start = last_dist;
1167         return(VIK_TRACKPOINT(last_iter->data));
1168       }
1169       else
1170         return NULL;
1171     }
1172     /* we've gone past the dist already, was prev trackpoint closer? */
1173     /* should do a vik_coord_average_weighted() thingy. */
1174     if ( iter->prev && abs(current_dist-current_inc-dist) < abs(current_dist-dist) ) {
1175       if (meters_from_start)
1176         *meters_from_start = last_dist;
1177       iter = iter->prev;
1178     }
1179     else
1180       if (meters_from_start)
1181         *meters_from_start = current_dist;
1182
1183     return VIK_TRACKPOINT(iter->data);
1184
1185   }
1186   return NULL;
1187 }
1188
1189 VikTrackpoint *vik_track_get_closest_tp_by_percentage_time ( VikTrack *tr, gdouble reltime, time_t *seconds_from_start )
1190 {
1191   time_t t_pos, t_start, t_end, t_total;
1192   t_start = VIK_TRACKPOINT(tr->trackpoints->data)->timestamp;
1193   t_end = VIK_TRACKPOINT(g_list_last(tr->trackpoints)->data)->timestamp;
1194   t_total = t_end - t_start;
1195
1196   t_pos = t_start + t_total * reltime;
1197
1198   if ( !tr->trackpoints )
1199     return NULL;
1200
1201   GList *iter = tr->trackpoints;
1202
1203   while (iter) {
1204     if (VIK_TRACKPOINT(iter->data)->timestamp == t_pos)
1205       break;
1206     if (VIK_TRACKPOINT(iter->data)->timestamp > t_pos) {
1207       if (iter->prev == NULL)  /* first trackpoint */
1208         break;
1209       time_t t_before = t_pos - VIK_TRACKPOINT(iter->prev->data)->timestamp;
1210       time_t t_after = VIK_TRACKPOINT(iter->data)->timestamp - t_pos;
1211       if (t_before <= t_after)
1212         iter = iter->prev;
1213       break;
1214     }
1215     else if ((iter->next == NULL) && (t_pos < (VIK_TRACKPOINT(iter->data)->timestamp + 3))) /* last trackpoint: accommodate for round-off */
1216       break;
1217     iter = iter->next;
1218   }
1219
1220   if (!iter)
1221     return NULL;
1222   if (seconds_from_start)
1223     *seconds_from_start = VIK_TRACKPOINT(iter->data)->timestamp - VIK_TRACKPOINT(tr->trackpoints->data)->timestamp;
1224   return VIK_TRACKPOINT(iter->data);
1225 }
1226
1227 VikTrackpoint* vik_track_get_tp_by_max_speed ( const VikTrack *tr )
1228 {
1229   gdouble maxspeed = 0.0, speed = 0.0;
1230
1231   if ( !tr->trackpoints )
1232     return NULL;
1233
1234   GList *iter = tr->trackpoints;
1235   VikTrackpoint *max_speed_tp = NULL;
1236
1237   while (iter) {
1238     if (iter->prev) {
1239       if ( VIK_TRACKPOINT(iter->data)->has_timestamp &&
1240            VIK_TRACKPOINT(iter->prev->data)->has_timestamp &&
1241            (! VIK_TRACKPOINT(iter->data)->newsegment) ) {
1242         speed =  vik_coord_diff ( &(VIK_TRACKPOINT(iter->data)->coord), &(VIK_TRACKPOINT(iter->prev->data)->coord) )
1243           / ABS(VIK_TRACKPOINT(iter->data)->timestamp - VIK_TRACKPOINT(iter->prev->data)->timestamp);
1244         if ( speed > maxspeed ) {
1245           maxspeed = speed;
1246           max_speed_tp = VIK_TRACKPOINT(iter->data);
1247         }
1248       }
1249     }
1250     iter = iter->next;
1251   }
1252
1253   if (!max_speed_tp)
1254     return NULL;
1255
1256   return max_speed_tp;
1257 }
1258
1259 VikTrackpoint* vik_track_get_tp_by_max_alt ( const VikTrack *tr )
1260 {
1261   gdouble maxalt = -5000.0;
1262   if ( !tr->trackpoints )
1263     return NULL;
1264
1265   GList *iter = tr->trackpoints;
1266   VikTrackpoint *max_alt_tp = NULL;
1267
1268   while (iter) {
1269     if ( VIK_TRACKPOINT(iter->data)->altitude > maxalt ) {
1270       maxalt = VIK_TRACKPOINT(iter->data)->altitude;
1271       max_alt_tp = VIK_TRACKPOINT(iter->data);
1272     }
1273     iter = iter->next;
1274   }
1275
1276   if (!max_alt_tp)
1277     return NULL;
1278
1279   return max_alt_tp;
1280 }
1281
1282 VikTrackpoint* vik_track_get_tp_by_min_alt ( const VikTrack *tr )
1283 {
1284   gdouble minalt = 25000.0;
1285   if ( !tr->trackpoints )
1286     return NULL;
1287
1288   GList *iter = tr->trackpoints;
1289   VikTrackpoint *min_alt_tp = NULL;
1290
1291   while (iter) {
1292     if ( VIK_TRACKPOINT(iter->data)->altitude < minalt ) {
1293       minalt = VIK_TRACKPOINT(iter->data)->altitude;
1294       min_alt_tp = VIK_TRACKPOINT(iter->data);
1295     }
1296     iter = iter->next;
1297   }
1298
1299   if (!min_alt_tp)
1300     return NULL;
1301
1302   return min_alt_tp;
1303 }
1304
1305 gboolean vik_track_get_minmax_alt ( const VikTrack *tr, gdouble *min_alt, gdouble *max_alt )
1306 {
1307   *min_alt = 25000;
1308   *max_alt = -5000;
1309   if ( tr && tr->trackpoints && tr->trackpoints->data && (VIK_TRACKPOINT(tr->trackpoints->data)->altitude != VIK_DEFAULT_ALTITUDE) ) {
1310     GList *iter = tr->trackpoints->next;
1311     gdouble tmp_alt;
1312     while (iter)
1313     {
1314       tmp_alt = VIK_TRACKPOINT(iter->data)->altitude;
1315       if ( tmp_alt > *max_alt )
1316         *max_alt = tmp_alt;
1317       if ( tmp_alt < *min_alt )
1318         *min_alt = tmp_alt;
1319       iter = iter->next;
1320     }
1321     return TRUE;
1322   }
1323   return FALSE;
1324 }
1325
1326 void vik_track_marshall ( VikTrack *tr, guint8 **data, guint *datalen)
1327 {
1328   GList *tps;
1329   GByteArray *b = g_byte_array_new();
1330   guint len;
1331   guint intp, ntp;
1332
1333   g_byte_array_append(b, (guint8 *)tr, sizeof(*tr));
1334
1335   /* we'll fill out number of trackpoints later */
1336   intp = b->len;
1337   g_byte_array_append(b, (guint8 *)&len, sizeof(len));
1338
1339   tps = tr->trackpoints;
1340   ntp = 0;
1341   while (tps) {
1342     g_byte_array_append(b, (guint8 *)tps->data, sizeof(VikTrackpoint));
1343     tps = tps->next;
1344     ntp++;
1345   }
1346   *(guint *)(b->data + intp) = ntp;
1347
1348   // This allocates space for variant sized strings
1349   //  and copies that amount of data from the track to byte array
1350 #define vtm_append(s) \
1351   len = (s) ? strlen(s)+1 : 0; \
1352   g_byte_array_append(b, (guint8 *)&len, sizeof(len)); \
1353   if (s) g_byte_array_append(b, (guint8 *)s, len);
1354
1355   vtm_append(tr->name);
1356   vtm_append(tr->comment);
1357   vtm_append(tr->description);
1358
1359   *data = b->data;
1360   *datalen = b->len;
1361   g_byte_array_free(b, FALSE);
1362 }
1363
1364 /*
1365  * Take a byte array and convert it into a Track
1366  */
1367 VikTrack *vik_track_unmarshall (guint8 *data, guint datalen)
1368 {
1369   guint len;
1370   VikTrack *new_tr = vik_track_new();
1371   VikTrackpoint *new_tp;
1372   guint ntp;
1373   gint i;
1374
1375   /* basic properties: */
1376   new_tr->visible = ((VikTrack *)data)->visible;
1377   new_tr->is_route = ((VikTrack *)data)->is_route;
1378   new_tr->has_color = ((VikTrack *)data)->has_color;
1379   new_tr->color = ((VikTrack *)data)->color;
1380   new_tr->bbox = ((VikTrack *)data)->bbox;
1381
1382   data += sizeof(*new_tr);
1383
1384   ntp = *(guint *)data;
1385   data += sizeof(ntp);
1386
1387   for (i=0; i<ntp; i++) {
1388     new_tp = vik_trackpoint_new();
1389     memcpy(new_tp, data, sizeof(*new_tp));
1390     data += sizeof(*new_tp);
1391     new_tr->trackpoints = g_list_append(new_tr->trackpoints, new_tp);
1392   }
1393
1394 #define vtu_get(s) \
1395   len = *(guint *)data; \
1396   data += sizeof(len); \
1397   if (len) { \
1398     (s) = g_strdup((gchar *)data); \
1399   } else { \
1400     (s) = NULL; \
1401   } \
1402   data += len;
1403
1404   vtu_get(new_tr->name);
1405   vtu_get(new_tr->comment);
1406   vtu_get(new_tr->description);
1407
1408   return new_tr;
1409 }
1410
1411 /**
1412  * (Re)Calculate the bounds of the given track,
1413  *  updating the track's bounds data.
1414  * This should be called whenever a track's trackpoints are changed
1415  */
1416 void vik_track_calculate_bounds ( VikTrack *trk )
1417 {
1418   GList *tp_iter;
1419   tp_iter = trk->trackpoints;
1420
1421   struct LatLon topleft, bottomright, ll;
1422
1423   // Set bounds to first point
1424   if ( tp_iter ) {
1425     vik_coord_to_latlon ( &(VIK_TRACKPOINT(tp_iter->data)->coord), &topleft );
1426     vik_coord_to_latlon ( &(VIK_TRACKPOINT(tp_iter->data)->coord), &bottomright );
1427   }
1428   while ( tp_iter ) {
1429
1430     // See if this trackpoint increases the track bounds.
1431
1432     vik_coord_to_latlon ( &(VIK_TRACKPOINT(tp_iter->data)->coord), &ll );
1433
1434     if ( ll.lat > topleft.lat) topleft.lat = ll.lat;
1435     if ( ll.lon < topleft.lon) topleft.lon = ll.lon;
1436     if ( ll.lat < bottomright.lat) bottomright.lat = ll.lat;
1437     if ( ll.lon > bottomright.lon) bottomright.lon = ll.lon;
1438
1439     tp_iter = tp_iter->next;
1440   }
1441
1442   g_debug ( "Bounds of track: '%s' is: %f,%f to: %f,%f", trk->name, topleft.lat, topleft.lon, bottomright.lat, bottomright.lon );
1443
1444   trk->bbox.north = topleft.lat;
1445   trk->bbox.east = bottomright.lon;
1446   trk->bbox.south = bottomright.lat;
1447   trk->bbox.west = topleft.lon;
1448 }
1449
1450 /**
1451  *
1452  */
1453 void vik_track_apply_dem_data ( VikTrack *tr )
1454 {
1455   GList *tp_iter;
1456   gint16 elev;
1457   tp_iter = tr->trackpoints;
1458   while ( tp_iter ) {
1459     /* TODO: of the 4 possible choices we have for choosing an elevation
1460      * (trackpoint in between samples), choose the one with the least elevation change
1461      * as the last */
1462     elev = a_dems_get_elev_by_coord ( &(VIK_TRACKPOINT(tp_iter->data)->coord), VIK_DEM_INTERPOL_BEST );
1463     if ( elev != VIK_DEM_INVALID_ELEVATION )
1464       VIK_TRACKPOINT(tp_iter->data)->altitude = elev;
1465     tp_iter = tp_iter->next;
1466   }
1467 }
1468
1469 /**
1470  * vik_track_apply_dem_data_last_trackpoint:
1471  * Apply DEM data (if available) - to only the last trackpoint
1472  */
1473 void vik_track_apply_dem_data_last_trackpoint ( VikTrack *tr )
1474 {
1475   gint16 elev;
1476   if ( tr->trackpoints ) {
1477     /* As in vik_track_apply_dem_data above - use 'best' interpolation method */
1478     elev = a_dems_get_elev_by_coord ( &(VIK_TRACKPOINT(g_list_last(tr->trackpoints)->data)->coord), VIK_DEM_INTERPOL_BEST );
1479     if ( elev != VIK_DEM_INVALID_ELEVATION )
1480       VIK_TRACKPOINT(g_list_last(tr->trackpoints)->data)->altitude = elev;
1481   }
1482 }
1483
1484 /**
1485  * vik_track_steal_and_append_trackpoints:
1486  *
1487  * appends t2 to t1, leaving t2 with no trackpoints
1488  */
1489 void vik_track_steal_and_append_trackpoints ( VikTrack *t1, VikTrack *t2 )
1490 {
1491   if ( t1->trackpoints ) {
1492     t1->trackpoints = g_list_concat ( t1->trackpoints, t2->trackpoints );
1493   } else
1494     t1->trackpoints = t2->trackpoints;
1495   t2->trackpoints = NULL;
1496
1497   // Trackpoints updated - so update the bounds
1498   vik_track_calculate_bounds ( t1 );
1499 }
1500
1501 /**
1502  * vik_track_cut_back_to_double_point:
1503  *
1504  * starting at the end, looks backwards for the last "double point", a duplicate trackpoint.
1505  * If there is no double point, deletes all the trackpoints.
1506  *
1507  * Returns: the new end of the track (or the start if there are no double points)
1508  */
1509 VikCoord *vik_track_cut_back_to_double_point ( VikTrack *tr )
1510 {
1511   GList *iter = tr->trackpoints;
1512   VikCoord *rv;
1513
1514   if ( !iter )
1515     return NULL;
1516   while ( iter->next )
1517     iter = iter->next;
1518
1519
1520   while ( iter->prev ) {
1521     if ( vik_coord_equals((VikCoord *)iter->data, (VikCoord *)iter->prev->data) ) {
1522       GList *prev = iter->prev;
1523
1524       rv = g_malloc(sizeof(VikCoord));
1525       *rv = *((VikCoord *) iter->data);
1526
1527       /* truncate trackpoint list */
1528       iter->prev = NULL; /* pretend it's the end */
1529       g_list_foreach ( iter, (GFunc) g_free, NULL );
1530       g_list_free( iter );
1531
1532       prev->next = NULL;
1533
1534       return rv;
1535     }
1536     iter = iter->prev;
1537   }
1538
1539   /* no double point found! */
1540   rv = g_malloc(sizeof(VikCoord));
1541   *rv = *((VikCoord *) tr->trackpoints->data);
1542   g_list_foreach ( tr->trackpoints, (GFunc) g_free, NULL );
1543   g_list_free( tr->trackpoints );
1544   tr->trackpoints = NULL;
1545   return rv;
1546 }
1547