]> git.street.me.uk Git - andy/viking.git/blob - src/viktrack.c
Add new graph type Elevation/Time in the track properties window.
[andy/viking.git] / 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  *
6  * This program is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation; either version 2 of the License, or
9  * (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
19  *
20  */
21 #ifdef HAVE_CONFIG_H
22 #include "config.h"
23 #endif
24
25 #include <glib.h>
26 #include <time.h>
27 #include <stdlib.h>
28 #ifdef HAVE_STRING_H
29 #include <string.h>
30 #endif
31 #ifdef HAVE_MATH_H
32 #include <math.h>
33 #endif
34
35 #include "coords.h"
36 #include "vikcoord.h"
37 #include "viktrack.h"
38 #include "globals.h"
39 #include "dems.h"
40
41 VikTrack *vik_track_new()
42 {
43   VikTrack *tr = g_malloc0 ( sizeof ( VikTrack ) );
44   tr->ref_count = 1;
45   return tr;
46 }
47
48 void vik_track_set_comment_no_copy(VikTrack *tr, gchar *comment)
49 {
50   if ( tr->comment )
51     g_free ( tr->comment );
52   tr->comment = comment;
53 }
54
55
56 void vik_track_set_comment(VikTrack *tr, const gchar *comment)
57 {
58   if ( tr->comment )
59     g_free ( tr->comment );
60
61   if ( comment && comment[0] != '\0' )
62     tr->comment = g_strdup(comment);
63   else
64     tr->comment = NULL;
65 }
66
67 void vik_track_ref(VikTrack *tr)
68 {
69   tr->ref_count++;
70 }
71
72 void vik_track_set_property_dialog(VikTrack *tr, GtkWidget *dialog)
73 {
74   /* Warning: does not check for existing dialog */
75   tr->property_dialog = dialog;
76 }
77
78 void vik_track_clear_property_dialog(VikTrack *tr)
79 {
80   tr->property_dialog = NULL;
81 }
82
83 void vik_track_free(VikTrack *tr)
84 {
85   if ( tr->ref_count-- > 1 )
86     return;
87
88   if ( tr->comment )
89     g_free ( tr->comment );
90   g_list_foreach ( tr->trackpoints, (GFunc) g_free, NULL );
91   g_list_free( tr->trackpoints );
92   if (tr->property_dialog)
93     if ( GTK_IS_WIDGET(tr->property_dialog) )
94       gtk_widget_destroy ( GTK_WIDGET(tr->property_dialog) );
95   g_free ( tr );
96 }
97
98 VikTrack *vik_track_copy ( const VikTrack *tr )
99 {
100   VikTrack *new_tr = vik_track_new();
101   VikTrackpoint *new_tp;
102   GList *tp_iter = tr->trackpoints;
103   new_tr->visible = tr->visible;
104   new_tr->trackpoints = NULL;
105   while ( tp_iter )
106   {
107     new_tp = g_malloc ( sizeof ( VikTrackpoint ) );
108     *new_tp = *((VikTrackpoint *)(tp_iter->data));
109     new_tr->trackpoints = g_list_append ( new_tr->trackpoints, new_tp );
110     tp_iter = tp_iter->next;
111   }
112   vik_track_set_comment(new_tr,tr->comment);
113   return new_tr;
114 }
115
116 VikTrackpoint *vik_trackpoint_new()
117 {
118   VikTrackpoint *tp = g_malloc0(sizeof(VikTrackpoint));
119   tp->speed = NAN;
120   tp->course = NAN;
121   tp->altitude = VIK_DEFAULT_ALTITUDE;
122   tp->hdop = VIK_DEFAULT_DOP;
123   tp->vdop = VIK_DEFAULT_DOP;
124   tp->pdop = VIK_DEFAULT_DOP;
125   return tp;
126 }
127
128 void vik_trackpoint_free(VikTrackpoint *tp)
129 {
130   g_free(tp);
131 }
132
133 VikTrackpoint *vik_trackpoint_copy(VikTrackpoint *tp)
134 {
135   VikTrackpoint *rv = vik_trackpoint_new();
136   *rv = *tp;
137   return rv;
138 }
139
140 gdouble vik_track_get_length(const VikTrack *tr)
141 {
142   gdouble len = 0.0;
143   if ( tr->trackpoints )
144   {
145     GList *iter = tr->trackpoints->next;
146     while (iter)
147     {
148       if ( ! VIK_TRACKPOINT(iter->data)->newsegment )
149         len += vik_coord_diff ( &(VIK_TRACKPOINT(iter->data)->coord),
150                                 &(VIK_TRACKPOINT(iter->prev->data)->coord) );
151       iter = iter->next;
152     }
153   }
154   return len;
155 }
156
157 gdouble vik_track_get_length_including_gaps(const VikTrack *tr)
158 {
159   gdouble len = 0.0;
160   if ( tr->trackpoints )
161   {
162     GList *iter = tr->trackpoints->next;
163     while (iter)
164     {
165       len += vik_coord_diff ( &(VIK_TRACKPOINT(iter->data)->coord),
166                               &(VIK_TRACKPOINT(iter->prev->data)->coord) );
167       iter = iter->next;
168     }
169   }
170   return len;
171 }
172
173 gulong vik_track_get_tp_count(const VikTrack *tr)
174 {
175   gulong num = 0;
176   GList *iter = tr->trackpoints;
177   while ( iter )
178   {
179     num++;
180     iter = iter->next;
181   }
182   return num;
183 }
184
185 gulong vik_track_get_dup_point_count ( const VikTrack *tr )
186 {
187   gulong num = 0;
188   GList *iter = tr->trackpoints;
189   while ( iter )
190   {
191     if ( iter->next && vik_coord_equals ( &(VIK_TRACKPOINT(iter->data)->coord),
192                        &(VIK_TRACKPOINT(iter->next->data)->coord) ) )
193       num++;
194     iter = iter->next;
195   }
196   return num;
197 }
198
199 void vik_track_remove_dup_points ( VikTrack *tr )
200 {
201   GList *iter = tr->trackpoints;
202   while ( iter )
203   {
204     if ( iter->next && vik_coord_equals ( &(VIK_TRACKPOINT(iter->data)->coord),
205                        &(VIK_TRACKPOINT(iter->next->data)->coord) ) )
206     {
207       g_free ( iter->next->data );
208       tr->trackpoints = g_list_delete_link ( tr->trackpoints, iter->next );
209     }
210     else
211       iter = iter->next;
212   }
213 }
214
215 guint vik_track_get_segment_count(const VikTrack *tr)
216 {
217   guint num = 1;
218   GList *iter = tr->trackpoints;
219   if ( !iter )
220     return 0;
221   while ( (iter = iter->next) )
222   {
223     if ( VIK_TRACKPOINT(iter->data)->newsegment )
224       num++;
225   }
226   return num;
227 }
228
229 VikTrack **vik_track_split_into_segments(VikTrack *t, guint *ret_len)
230 {
231   VikTrack **rv;
232   VikTrack *tr;
233   guint i;
234   guint segs = vik_track_get_segment_count(t);
235   GList *iter;
236
237   if ( segs < 2 )
238   {
239     *ret_len = 0;
240     return NULL;
241   }
242
243   rv = g_malloc ( segs * sizeof(VikTrack *) );
244   tr = vik_track_copy ( t );
245   rv[0] = tr;
246   iter = tr->trackpoints;
247
248   i = 1;
249   while ( (iter = iter->next) )
250   {
251     if ( VIK_TRACKPOINT(iter->data)->newsegment )
252     {
253       iter->prev->next = NULL;
254       iter->prev = NULL;
255       rv[i] = vik_track_new();
256       if ( tr->comment )
257         vik_track_set_comment ( rv[i], tr->comment );
258       rv[i]->visible = tr->visible;
259       rv[i]->trackpoints = iter;
260       i++;
261     }
262   }
263   *ret_len = segs;
264   return rv;
265 }
266
267 void vik_track_reverse ( VikTrack *tr )
268 {
269   GList *iter;
270   tr->trackpoints = g_list_reverse(tr->trackpoints);
271
272   /* fix 'newsegment' */
273   iter = g_list_last ( tr->trackpoints );
274   while ( iter )
275   {
276     if ( ! iter->next ) /* last segment, was first, cancel newsegment. */
277       VIK_TRACKPOINT(iter->data)->newsegment = FALSE;
278     if ( ! iter->prev ) /* first segment by convention has newsegment flag. */
279       VIK_TRACKPOINT(iter->data)->newsegment = TRUE;
280     else if ( VIK_TRACKPOINT(iter->data)->newsegment && iter->next )
281     {
282       VIK_TRACKPOINT(iter->next->data)->newsegment = TRUE;
283       VIK_TRACKPOINT(iter->data)->newsegment = FALSE;
284     }
285     iter = iter->prev;
286   }
287 }
288
289 gdouble vik_track_get_average_speed(const VikTrack *tr)
290 {
291   gdouble len = 0.0;
292   guint32 time = 0;
293   if ( tr->trackpoints )
294   {
295     GList *iter = tr->trackpoints->next;
296     while (iter)
297     {
298       if ( VIK_TRACKPOINT(iter->data)->has_timestamp && 
299           VIK_TRACKPOINT(iter->prev->data)->has_timestamp &&
300           (! VIK_TRACKPOINT(iter->data)->newsegment) )
301       {
302         len += vik_coord_diff ( &(VIK_TRACKPOINT(iter->data)->coord),
303                                 &(VIK_TRACKPOINT(iter->prev->data)->coord) );
304         time += ABS(VIK_TRACKPOINT(iter->data)->timestamp - VIK_TRACKPOINT(iter->prev->data)->timestamp);
305       }
306       iter = iter->next;
307     }
308   }
309   return (time == 0) ? 0 : ABS(len/time);
310 }
311
312 gdouble vik_track_get_max_speed(const VikTrack *tr)
313 {
314   gdouble maxspeed = 0.0, speed = 0.0;
315   if ( tr->trackpoints )
316   {
317     GList *iter = tr->trackpoints->next;
318     while (iter)
319     {
320       if ( VIK_TRACKPOINT(iter->data)->has_timestamp && 
321           VIK_TRACKPOINT(iter->prev->data)->has_timestamp &&
322           (! VIK_TRACKPOINT(iter->data)->newsegment) )
323       {
324         speed =  vik_coord_diff ( &(VIK_TRACKPOINT(iter->data)->coord), &(VIK_TRACKPOINT(iter->prev->data)->coord) )
325                  / ABS(VIK_TRACKPOINT(iter->data)->timestamp - VIK_TRACKPOINT(iter->prev->data)->timestamp);
326         if ( speed > maxspeed )
327           maxspeed = speed;
328       }
329       iter = iter->next;
330     }
331   }
332   return maxspeed;
333 }
334
335 void vik_track_convert ( VikTrack *tr, VikCoordMode dest_mode )
336 {
337   GList *iter = tr->trackpoints;
338   while (iter)
339   {
340     vik_coord_convert ( &(VIK_TRACKPOINT(iter->data)->coord), dest_mode );
341     iter = iter->next;
342   }
343 }
344
345 /* I understood this when I wrote it ... maybe ... Basically it eats up the
346  * proper amounts of length on the track and averages elevation over that. */
347 gdouble *vik_track_make_elevation_map ( const VikTrack *tr, guint16 num_chunks )
348 {
349   gdouble *pts;
350   gdouble total_length, chunk_length, current_dist, current_area_under_curve, current_seg_length, dist_along_seg = 0.0;
351   gdouble altitude1, altitude2;
352   guint16 current_chunk;
353   gboolean ignore_it = FALSE;
354
355   GList *iter = tr->trackpoints;
356
357   if (!iter || !iter->next) /* zero- or one-point track */
358           return NULL;
359
360   { /* test if there's anything worth calculating */
361     gboolean okay = FALSE;
362     while ( iter )
363     {
364       if ( VIK_TRACKPOINT(iter->data)->altitude != VIK_DEFAULT_ALTITUDE ) {
365         okay = TRUE; break;
366       }
367       iter = iter->next;
368     }
369     if ( ! okay )
370       return NULL;
371   }
372
373   iter = tr->trackpoints;
374
375   g_assert ( num_chunks < 16000 );
376
377   pts = g_malloc ( sizeof(gdouble) * num_chunks );
378
379   total_length = vik_track_get_length_including_gaps ( tr );
380   chunk_length = total_length / num_chunks;
381
382   /* Zero chunk_length (eg, track of 2 tp with the same loc) will cause crash */
383   if (chunk_length <= 0) {
384     g_free(pts);
385     return NULL;
386   }
387
388   current_dist = 0.0;
389   current_area_under_curve = 0;
390   current_chunk = 0;
391   current_seg_length = 0;
392
393   current_seg_length = vik_coord_diff ( &(VIK_TRACKPOINT(iter->data)->coord),
394       &(VIK_TRACKPOINT(iter->next->data)->coord) );
395   altitude1 = VIK_TRACKPOINT(iter->data)->altitude;
396   altitude2 = VIK_TRACKPOINT(iter->next->data)->altitude;
397   dist_along_seg = 0;
398
399   while ( current_chunk < num_chunks ) {
400
401     /* go along current seg */
402     if ( current_seg_length && (current_seg_length - dist_along_seg) > chunk_length ) {
403       dist_along_seg += chunk_length;
404
405       /*        /
406        *   pt2 *
407        *      /x       altitude = alt_at_pt_1 + alt_at_pt_2 / 2 = altitude1 + slope * dist_value_of_pt_inbetween_pt1_and_pt2
408        *     /xx   avg altitude = area under curve / chunk len
409        *pt1 *xxx   avg altitude = altitude1 + (altitude2-altitude1)/(current_seg_length)*(dist_along_seg + (chunk_len/2))
410        *   / xxx
411        *  /  xxx
412        **/
413
414       if ( ignore_it )
415         pts[current_chunk] = VIK_DEFAULT_ALTITUDE;
416       else
417         pts[current_chunk] = altitude1 + (altitude2-altitude1)*((dist_along_seg - (chunk_length/2))/current_seg_length);
418
419       current_chunk++;
420     } else {
421       /* finish current seg */
422       if ( current_seg_length ) {
423         gdouble altitude_at_dist_along_seg = altitude1 + (altitude2-altitude1)/(current_seg_length)*dist_along_seg;
424         current_dist = current_seg_length - dist_along_seg;
425         current_area_under_curve = current_dist*(altitude_at_dist_along_seg + altitude2)*0.5;
426       } else { current_dist = current_area_under_curve = 0; } /* should only happen if first current_seg_length == 0 */
427
428       /* get intervening segs */
429       iter = iter->next;
430       while ( iter && iter->next ) {
431         current_seg_length = vik_coord_diff ( &(VIK_TRACKPOINT(iter->data)->coord),
432             &(VIK_TRACKPOINT(iter->next->data)->coord) );
433         altitude1 = VIK_TRACKPOINT(iter->data)->altitude;
434         altitude2 = VIK_TRACKPOINT(iter->next->data)->altitude;
435         ignore_it = VIK_TRACKPOINT(iter->next->data)->newsegment;
436
437         if ( chunk_length - current_dist >= current_seg_length ) {
438           current_dist += current_seg_length;
439           current_area_under_curve += current_seg_length * (altitude1+altitude2) * 0.5;
440           iter = iter->next;
441         } else {
442           break;
443         }
444       }
445
446       /* final seg */
447       dist_along_seg = chunk_length - current_dist;
448       if ( ignore_it || !iter->next ) {
449         pts[current_chunk] = current_area_under_curve / current_dist;
450         if (!iter->next) {
451           int i;
452           for (i = current_chunk + 1; i < num_chunks; i++)
453             pts[i] = pts[current_chunk];
454           break;
455         }
456       } 
457       else {
458         current_area_under_curve += dist_along_seg * (altitude1 + (altitude2 - altitude1)*dist_along_seg/current_seg_length);
459         pts[current_chunk] = current_area_under_curve / chunk_length;
460       }
461
462       current_dist = 0;
463       current_chunk++;
464     }
465   }
466
467   return pts;
468 }
469
470
471 void vik_track_get_total_elevation_gain(const VikTrack *tr, gdouble *up, gdouble *down)
472 {
473   gdouble diff;
474   *up = *down = 0;
475   if ( tr->trackpoints && VIK_TRACKPOINT(tr->trackpoints->data)->altitude != VIK_DEFAULT_ALTITUDE )
476   {
477     GList *iter = tr->trackpoints->next;
478     while (iter)
479     {
480       diff = VIK_TRACKPOINT(iter->data)->altitude - VIK_TRACKPOINT(iter->prev->data)->altitude;
481       if ( diff > 0 )
482         *up += diff;
483       else
484         *down -= diff;
485       iter = iter->next;
486     }
487   } else
488     *up = *down = VIK_DEFAULT_ALTITUDE;
489 }
490
491
492 /* by Alex Foobarian */
493 gdouble *vik_track_make_speed_map ( const VikTrack *tr, guint16 num_chunks )
494 {
495   gdouble *v, *s, *t;
496   gdouble duration, chunk_dur;
497   time_t t1, t2;
498   int i, pt_count, numpts, index;
499   GList *iter;
500
501   if ( ! tr->trackpoints )
502     return NULL;
503
504   g_assert ( num_chunks < 16000 );
505
506   t1 = VIK_TRACKPOINT(tr->trackpoints->data)->timestamp;
507   t2 = VIK_TRACKPOINT(g_list_last(tr->trackpoints)->data)->timestamp;
508   duration = t2 - t1;
509
510   if ( !t1 || !t2 || !duration )
511     return NULL;
512
513   if (duration < 0) {
514     g_warning("negative duration: unsorted trackpoint timestamps?");
515     return NULL;
516   }
517   pt_count = vik_track_get_tp_count(tr);
518
519   v = g_malloc ( sizeof(gdouble) * num_chunks );
520   chunk_dur = duration / num_chunks;
521
522   s = g_malloc(sizeof(double) * pt_count);
523   t = g_malloc(sizeof(double) * pt_count);
524
525   iter = tr->trackpoints->next;
526   numpts = 0;
527   s[0] = 0;
528   t[0] = VIK_TRACKPOINT(iter->prev->data)->timestamp;
529   numpts++;
530   while (iter) {
531     s[numpts] = s[numpts-1] + vik_coord_diff ( &(VIK_TRACKPOINT(iter->prev->data)->coord), &(VIK_TRACKPOINT(iter->data)->coord) );
532     t[numpts] = VIK_TRACKPOINT(iter->data)->timestamp;
533     numpts++;
534     iter = iter->next;
535   }
536
537   /* In the following computation, we iterate through periods of time of duration chunk_dur.
538    * The first period begins at the beginning of the track.  The last period ends at the end of the track.
539    */
540   index = 0; /* index of the current trackpoint. */
541   for (i = 0; i < num_chunks; i++) {
542     /* we are now covering the interval from t[0] + i*chunk_dur to t[0] + (i+1)*chunk_dur.
543      * find the first trackpoint outside the current interval, averaging the speeds between intermediate trackpoints.
544      */
545     if (t[0] + i*chunk_dur >= t[index]) {
546       gdouble acc_t = 0, acc_s = 0;
547       while (t[0] + i*chunk_dur >= t[index]) {
548         acc_s += (s[index+1]-s[index]);
549         acc_t += (t[index+1]-t[index]);
550         index++;
551       }
552       v[i] = acc_s/acc_t;
553     } 
554     else if (i) {
555       v[i] = v[i-1];
556     }
557     else {
558       v[i] = 0;
559     }
560   }
561   g_free(s);
562   g_free(t);
563   return v;
564 }
565
566 /**
567  * Make a distance/time map, heavily based on the vik_track_make_speed_map method
568  */
569 gdouble *vik_track_make_distance_map ( const VikTrack *tr, guint16 num_chunks )
570 {
571   gdouble *v, *s, *t;
572   gdouble duration, chunk_dur;
573   time_t t1, t2;
574   int i, pt_count, numpts, index;
575   GList *iter;
576
577   if ( ! tr->trackpoints )
578     return NULL;
579
580   t1 = VIK_TRACKPOINT(tr->trackpoints->data)->timestamp;
581   t2 = VIK_TRACKPOINT(g_list_last(tr->trackpoints)->data)->timestamp;
582   duration = t2 - t1;
583
584   if ( !t1 || !t2 || !duration )
585     return NULL;
586
587   if (duration < 0) {
588     g_warning("negative duration: unsorted trackpoint timestamps?");
589     return NULL;
590   }
591   pt_count = vik_track_get_tp_count(tr);
592
593   v = g_malloc ( sizeof(gdouble) * num_chunks );
594   chunk_dur = duration / num_chunks;
595
596   s = g_malloc(sizeof(double) * pt_count);
597   t = g_malloc(sizeof(double) * pt_count);
598
599   iter = tr->trackpoints->next;
600   numpts = 0;
601   s[0] = 0;
602   t[0] = VIK_TRACKPOINT(iter->prev->data)->timestamp;
603   numpts++;
604   while (iter) {
605     s[numpts] = s[numpts-1] + vik_coord_diff ( &(VIK_TRACKPOINT(iter->prev->data)->coord), &(VIK_TRACKPOINT(iter->data)->coord) );
606     t[numpts] = VIK_TRACKPOINT(iter->data)->timestamp;
607     numpts++;
608     iter = iter->next;
609   }
610
611   /* In the following computation, we iterate through periods of time of duration chunk_dur.
612    * The first period begins at the beginning of the track.  The last period ends at the end of the track.
613    */
614   index = 0; /* index of the current trackpoint. */
615   for (i = 0; i < num_chunks; i++) {
616     /* we are now covering the interval from t[0] + i*chunk_dur to t[0] + (i+1)*chunk_dur.
617      * find the first trackpoint outside the current interval, averaging the distance between intermediate trackpoints.
618      */
619     if (t[0] + i*chunk_dur >= t[index]) {
620       gdouble acc_s = 0; // No need for acc_t
621       while (t[0] + i*chunk_dur >= t[index]) {
622         acc_s += (s[index+1]-s[index]);
623         index++;
624       }
625       // The only bit that's really different from the speed map - just keep an accululative record distance
626       v[i] = i ? v[i-1]+acc_s : acc_s;
627     }
628     else if (i) {
629       v[i] = v[i-1];
630     }
631     else {
632       v[i] = 0;
633     }
634   }
635   g_free(s);
636   g_free(t);
637   return v;
638 }
639
640 /**
641  * This uses the 'time' based method to make the graph, (which is a simpler compared to the elevation/distance)
642  * This results in a slightly blocky graph when it does not have many trackpoints: <60
643  * NB Somehow the elevation/distance applies some kind of smoothing algorithm,
644  *   but I don't think any one understands it any more (I certainly don't ATM)
645  */
646 gdouble *vik_track_make_elevation_time_map ( const VikTrack *tr, guint16 num_chunks )
647 {
648   time_t t1, t2;
649   gdouble duration, chunk_dur;
650   GList *iter = tr->trackpoints;
651
652   if (!iter || !iter->next) /* zero- or one-point track */
653     return NULL;
654
655   /* test if there's anything worth calculating */
656   gboolean okay = FALSE;
657   while ( iter ) {
658     if ( VIK_TRACKPOINT(iter->data)->altitude != VIK_DEFAULT_ALTITUDE ) {
659       okay = TRUE;
660       break;
661     }
662     iter = iter->next;
663   }
664   if ( ! okay )
665     return NULL;
666
667   t1 = VIK_TRACKPOINT(tr->trackpoints->data)->timestamp;
668   t2 = VIK_TRACKPOINT(g_list_last(tr->trackpoints)->data)->timestamp;
669   duration = t2 - t1;
670
671   if ( !t1 || !t2 || !duration )
672     return NULL;
673
674   if (duration < 0) {
675     g_warning("negative duration: unsorted trackpoint timestamps?");
676     return NULL;
677   }
678   gint pt_count = vik_track_get_tp_count(tr);
679
680   // Reset iterator back to the beginning
681   iter = tr->trackpoints;
682
683   gdouble *pts = g_malloc ( sizeof(gdouble) * num_chunks ); // The return altitude values
684   gdouble *s = g_malloc(sizeof(double) * pt_count); // calculation altitudes
685   gdouble *t = g_malloc(sizeof(double) * pt_count); // calculation times
686
687   chunk_dur = duration / num_chunks;
688
689   s[0] = VIK_TRACKPOINT(iter->data)->altitude;
690   t[0] = VIK_TRACKPOINT(iter->data)->timestamp;
691   iter = tr->trackpoints->next;
692   gint numpts = 1;
693   while (iter) {
694     s[numpts] = VIK_TRACKPOINT(iter->data)->altitude;
695     t[numpts] = VIK_TRACKPOINT(iter->data)->timestamp;
696     numpts++;
697     iter = iter->next;
698   }
699
700  /* In the following computation, we iterate through periods of time of duration chunk_dur.
701    * The first period begins at the beginning of the track.  The last period ends at the end of the track.
702    */
703   gint index = 0; /* index of the current trackpoint. */
704   gint i;
705   for (i = 0; i < num_chunks; i++) {
706     /* we are now covering the interval from t[0] + i*chunk_dur to t[0] + (i+1)*chunk_dur.
707      * find the first trackpoint outside the current interval, averaging the heights between intermediate trackpoints.
708      */
709     if (t[0] + i*chunk_dur >= t[index]) {
710       gdouble acc_s = s[index]; // initialise to first point
711       while (t[0] + i*chunk_dur >= t[index]) {
712         acc_s += (s[index+1]-s[index]);
713         index++;
714       }
715       pts[i] = acc_s;
716     }
717     else if (i) {
718       pts[i] = pts[i-1];
719     }
720     else {
721       pts[i] = 0;
722     }
723   }
724   g_free(s);
725   g_free(t);
726
727   return pts;
728 }
729
730 /* by Alex Foobarian */
731 VikTrackpoint *vik_track_get_closest_tp_by_percentage_dist ( VikTrack *tr, gdouble reldist, gdouble *meters_from_start )
732 {
733   gdouble dist = vik_track_get_length_including_gaps(tr) * reldist;
734   gdouble current_dist = 0.0;
735   gdouble current_inc = 0.0;
736   if ( tr->trackpoints )
737   {
738     GList *iter = tr->trackpoints->next;
739     GList *last_iter = NULL;
740     gdouble last_dist = 0.0;
741     while (iter)
742     {
743       current_inc = vik_coord_diff ( &(VIK_TRACKPOINT(iter->data)->coord),
744                                      &(VIK_TRACKPOINT(iter->prev->data)->coord) );
745       last_dist = current_dist;
746       current_dist += current_inc;
747       if ( current_dist >= dist )
748         break;
749       last_iter = iter;
750       iter = iter->next;
751     }
752     if (!iter) { /* passing the end the track */
753       if (last_iter) {
754         if (meters_from_start)
755           *meters_from_start = last_dist;
756         return(VIK_TRACKPOINT(last_iter->data));
757       }
758       else
759         return NULL;
760     }
761     /* we've gone past the dist already, was prev trackpoint closer? */
762     /* should do a vik_coord_average_weighted() thingy. */
763     if ( iter->prev && abs(current_dist-current_inc-dist) < abs(current_dist-dist) ) {
764       if (meters_from_start)
765         *meters_from_start = last_dist;
766       iter = iter->prev;
767     }
768     else
769       if (meters_from_start)
770         *meters_from_start = current_dist;
771
772     return VIK_TRACKPOINT(iter->data);
773
774   }
775   return NULL;
776 }
777
778 VikTrackpoint *vik_track_get_closest_tp_by_percentage_time ( VikTrack *tr, gdouble reltime, time_t *seconds_from_start )
779 {
780   time_t t_pos, t_start, t_end, t_total;
781   t_start = VIK_TRACKPOINT(tr->trackpoints->data)->timestamp;
782   t_end = VIK_TRACKPOINT(g_list_last(tr->trackpoints)->data)->timestamp;
783   t_total = t_end - t_start;
784
785   t_pos = t_start + t_total * reltime;
786
787   if ( !tr->trackpoints )
788     return NULL;
789
790   GList *iter = tr->trackpoints;
791
792   while (iter) {
793     if (VIK_TRACKPOINT(iter->data)->timestamp == t_pos)
794       break;
795     if (VIK_TRACKPOINT(iter->data)->timestamp > t_pos) {
796       if (iter->prev == NULL)  /* first trackpoint */
797         break;
798       time_t t_before = t_pos - VIK_TRACKPOINT(iter->prev)->timestamp;
799       time_t t_after = VIK_TRACKPOINT(iter->data)->timestamp - t_pos;
800       if (t_before <= t_after)
801         iter = iter->prev;
802       break;
803     }
804     else if ((iter->next == NULL) && (t_pos < (VIK_TRACKPOINT(iter->data)->timestamp + 3))) /* last trackpoint: accommodate for round-off */
805       break;
806     iter = iter->next;
807   }
808
809   if (!iter)
810     return NULL;
811   if (seconds_from_start)
812     *seconds_from_start = VIK_TRACKPOINT(iter->data)->timestamp - VIK_TRACKPOINT(tr->trackpoints->data)->timestamp;
813   return VIK_TRACKPOINT(iter->data);
814 }
815
816 VikTrackpoint* vik_track_get_tp_by_max_speed ( const VikTrack *tr )
817 {
818   gdouble maxspeed = 0.0, speed = 0.0;
819
820   if ( !tr->trackpoints )
821     return NULL;
822
823   GList *iter = tr->trackpoints;
824   VikTrackpoint *max_speed_tp = NULL;
825
826   while (iter) {
827     if (iter->prev) {
828       if ( VIK_TRACKPOINT(iter->data)->has_timestamp &&
829            VIK_TRACKPOINT(iter->prev->data)->has_timestamp &&
830            (! VIK_TRACKPOINT(iter->data)->newsegment) ) {
831         speed =  vik_coord_diff ( &(VIK_TRACKPOINT(iter->data)->coord), &(VIK_TRACKPOINT(iter->prev->data)->coord) )
832           / ABS(VIK_TRACKPOINT(iter->data)->timestamp - VIK_TRACKPOINT(iter->prev->data)->timestamp);
833         if ( speed > maxspeed ) {
834           maxspeed = speed;
835           max_speed_tp = VIK_TRACKPOINT(iter->data);
836         }
837       }
838     }
839     iter = iter->next;
840   }
841   
842   if (!max_speed_tp)
843     return NULL;
844
845   return max_speed_tp;
846 }
847
848 VikTrackpoint* vik_track_get_tp_by_max_alt ( const VikTrack *tr )
849 {
850   gdouble maxalt = -5000.0;
851   if ( !tr->trackpoints )
852     return NULL;
853
854   GList *iter = tr->trackpoints;
855   VikTrackpoint *max_alt_tp = NULL;
856
857   while (iter) {
858     if ( VIK_TRACKPOINT(iter->data)->altitude > maxalt ) {
859       maxalt = VIK_TRACKPOINT(iter->data)->altitude;
860       max_alt_tp = VIK_TRACKPOINT(iter->data);
861     }
862     iter = iter->next;
863   }
864
865   if (!max_alt_tp)
866     return NULL;
867
868   return max_alt_tp;
869 }
870
871 VikTrackpoint* vik_track_get_tp_by_min_alt ( const VikTrack *tr )
872 {
873   gdouble minalt = 25000.0;
874   if ( !tr->trackpoints )
875     return NULL;
876
877   GList *iter = tr->trackpoints;
878   VikTrackpoint *min_alt_tp = NULL;
879
880   while (iter) {
881     if ( VIK_TRACKPOINT(iter->data)->altitude < minalt ) {
882       minalt = VIK_TRACKPOINT(iter->data)->altitude;
883       min_alt_tp = VIK_TRACKPOINT(iter->data);
884     }
885     iter = iter->next;
886   }
887
888   if (!min_alt_tp)
889     return NULL;
890
891   return min_alt_tp;
892 }
893
894 gboolean vik_track_get_minmax_alt ( const VikTrack *tr, gdouble *min_alt, gdouble *max_alt )
895 {
896   *min_alt = 25000;
897   *max_alt = -5000;
898   if ( tr && tr->trackpoints && tr->trackpoints->data && (VIK_TRACKPOINT(tr->trackpoints->data)->altitude != VIK_DEFAULT_ALTITUDE) ) {
899     GList *iter = tr->trackpoints->next;
900     gdouble tmp_alt;
901     while (iter)
902     {
903       tmp_alt = VIK_TRACKPOINT(iter->data)->altitude;
904       if ( tmp_alt > *max_alt )
905         *max_alt = tmp_alt;
906       if ( tmp_alt < *min_alt )
907         *min_alt = tmp_alt;
908       iter = iter->next;
909     }
910     return TRUE;
911   }
912   return FALSE;
913 }
914
915 void vik_track_marshall ( VikTrack *tr, guint8 **data, guint *datalen)
916 {
917   GList *tps;
918   GByteArray *b = g_byte_array_new();
919   guint len;
920   guint intp, ntp;
921
922   g_byte_array_append(b, (guint8 *)tr, sizeof(*tr));
923
924   /* we'll fill out number of trackpoints later */
925   intp = b->len;
926   g_byte_array_append(b, (guint8 *)&len, sizeof(len));
927
928   tps = tr->trackpoints;
929   ntp = 0;
930   while (tps) {
931     g_byte_array_append(b, (guint8 *)tps->data, sizeof(VikTrackpoint));
932     tps = tps->next;
933     ntp++;
934   }
935   *(guint *)(b->data + intp) = ntp;
936
937   len = (tr->comment) ? strlen(tr->comment)+1 : 0; 
938   g_byte_array_append(b, (guint8 *)&len, sizeof(len)); 
939   if (tr->comment) g_byte_array_append(b, (guint8 *)tr->comment, len);
940
941   *data = b->data;
942   *datalen = b->len;
943   g_byte_array_free(b, FALSE);
944 }
945
946 VikTrack *vik_track_unmarshall (guint8 *data, guint datalen)
947 {
948   guint len;
949   VikTrack *new_tr = vik_track_new();
950   VikTrackpoint *new_tp;
951   guint ntp;
952   gint i;
953
954   /* only the visibility is needed */
955   new_tr->visible = ((VikTrack *)data)->visible;
956   data += sizeof(*new_tr);
957
958   ntp = *(guint *)data;
959   data += sizeof(ntp);
960
961   for (i=0; i<ntp; i++) {
962     new_tp = vik_trackpoint_new();
963     memcpy(new_tp, data, sizeof(*new_tp));
964     data += sizeof(*new_tp);
965     new_tr->trackpoints = g_list_append(new_tr->trackpoints, new_tp);
966   }
967
968   len = *(guint *)data;
969   data += sizeof(len);
970   if (len) {
971     new_tr->comment = g_strdup((gchar *)data);
972   }
973   return new_tr;
974 }
975
976 void vik_track_apply_dem_data ( VikTrack *tr )
977 {
978   GList *tp_iter;
979   gint16 elev;
980   tp_iter = tr->trackpoints;
981   while ( tp_iter ) {
982     /* TODO: of the 4 possible choices we have for choosing an elevation
983      * (trackpoint in between samples), choose the one with the least elevation change
984      * as the last */
985     elev = a_dems_get_elev_by_coord ( &(VIK_TRACKPOINT(tp_iter->data)->coord), VIK_DEM_INTERPOL_BEST );
986     if ( elev != VIK_DEM_INVALID_ELEVATION )
987       VIK_TRACKPOINT(tp_iter->data)->altitude = elev;
988     tp_iter = tp_iter->next;
989   }
990 }
991
992 /* appends t2 to t1, leaving t2 with no trackpoints */
993 void vik_track_steal_and_append_trackpoints ( VikTrack *t1, VikTrack *t2 )
994 {
995   if ( t1->trackpoints ) {
996     GList *tpiter = t1->trackpoints;
997     while ( tpiter->next )
998       tpiter = tpiter->next;
999     tpiter->next = t2->trackpoints;
1000     t2->trackpoints->prev = tpiter;
1001   } else
1002     t1->trackpoints = t2->trackpoints;
1003   t2->trackpoints = NULL;
1004 }
1005
1006 /* starting at the end, looks backwards for the last "double point", a duplicate trackpoint.
1007  * this is indicative of magic scissors continued use. If there is no double point,
1008  * deletes all the trackpoints. Returns the new end of the track (or the start if
1009  * there are no double points
1010  */
1011 VikCoord *vik_track_cut_back_to_double_point ( VikTrack *tr )
1012 {
1013   GList *iter = tr->trackpoints;
1014   VikCoord *rv;
1015
1016   if ( !iter )
1017     return NULL;
1018   while ( iter->next )
1019     iter = iter->next;
1020
1021
1022   while ( iter->prev ) {
1023     if ( vik_coord_equals((VikCoord *)iter->data, (VikCoord *)iter->prev->data) ) {
1024       GList *prev = iter->prev;
1025
1026       rv = g_malloc(sizeof(VikCoord));
1027       *rv = *((VikCoord *) iter->data);
1028
1029       /* truncate trackpoint list */
1030       iter->prev = NULL; /* pretend it's the end */
1031       g_list_foreach ( iter, (GFunc) g_free, NULL );
1032       g_list_free( iter );
1033
1034       prev->next = NULL;
1035
1036       return rv;
1037     }
1038     iter = iter->prev;
1039   }
1040
1041   /* no double point found! */
1042   rv = g_malloc(sizeof(VikCoord));
1043   *rv = *((VikCoord *) tr->trackpoints->data);
1044   g_list_foreach ( tr->trackpoints, (GFunc) g_free, NULL );
1045   g_list_free( tr->trackpoints );
1046   tr->trackpoints = NULL;
1047   return rv;
1048 }
1049