trunk/src/segments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/segments.c,v 1.10 2009-01-18 09:09:28 amb Exp $

 Segment data type functions.
 ******************/ /******************
 Written by Andrew M. Bishop

 This file Copyright 2008,2009 Andrew M. Bishop
 It may be distributed under the GNU Public License, version 2, or
 any higher version.  See section COPYING of the GNU Public license
 for conditions under which this file may be redistributed.
 ***************************************/


#include <assert.h>
#include <math.h>
#include <stdlib.h>

#include "nodes.h"
#include "segments.h"
#include "functions.h"


/* Functions */

static int sort_by_id(Segment *a,Segment *b);


/*++++++++++++++++++++++++++++++++++++++
  Allocate a new segment list.

  SegmentsMem *NewSegmentList Returns the segment list.
  ++++++++++++++++++++++++++++++++++++++*/

SegmentsMem *NewSegmentList(void)
{
 SegmentsMem *segments;

 segments=(SegmentsMem*)malloc(sizeof(SegmentsMem));

 segments->alloced=INCREMENT_SEGMENTS;
 segments->number=0;
 segments->sorted=0;

 segments->segments=(Segments*)malloc(sizeof(Segments)+segments->alloced*sizeof(Segment));

 return(segments);
}


/*++++++++++++++++++++++++++++++++++++++
  Load in a segment list from a file.

  Segments* SaveSegmentList Returns the segment list that has just been loaded.

  const char *filename The name of the file to load.
  ++++++++++++++++++++++++++++++++++++++*/

Segments *LoadSegmentList(const char *filename)
{
 return((Segments*)MapFile(filename));
}


/*++++++++++++++++++++++++++++++++++++++
  Save the segment list to a file.

  Segments* SaveSegmentList Returns the segment list that has just been saved.

  SegmentsMem* segments The set of segments to save.

  const char *filename The name of the file to save.
  ++++++++++++++++++++++++++++++++++++++*/

Segments *SaveSegmentList(SegmentsMem* segments,const char *filename)
{
 assert(segments->sorted);      /* Must be sorted */

 if(WriteFile(filename,(void*)segments->segments,sizeof(Segments)-sizeof(segments->segments->segments)+segments->number*sizeof(Segment)))
    assert(0);

 free(segments->segments);
 free(segments);

 return(LoadSegmentList(filename));
}


/*++++++++++++++++++++++++++++++++++++++
  Find the first segment with a particular starting node.

  Segment *FindFirstSegment Returns a pointer to the first segment with the specified id.

  Segments* segments The set of segments to process.

  node_t node The node to look for.
  ++++++++++++++++++++++++++++++++++++++*/

Segment *FindFirstSegment(Segments* segments,node_t node)
{
#ifdef NBINS_SEGMENTS
 int bin=node%NBINS_SEGMENTS;
 int start=segments->offset[bin];
 int end=segments->offset[bin+1]-1;
#else
 int start=0;
 int end=segments->number-1;
#endif
 int mid;
 int found;

 /* Binary search - search key exact match only is required.
  *
  *  # <- start  |  Check mid and move start or end if it doesn't match
  *  #           |
  *  #           |  Since an exact match is wanted we can set end=mid-1
  *  # <- mid    |  or start=mid+1 because we know that mid doesn't match.
  *  #           |
  *  #           |  Eventually either end=start or end=start+1 and one of
  *  # <- end    |  start or end is the wanted one.
  */

 if(end<start)                                 /* There are no nodes */
    return(NULL);
 else if(node<segments->segments[start].node1) /* Check key is not before start */
    return(NULL);
 else if(node>segments->segments[end].node1)   /* Check key is not after end */
    return(NULL);
 else
   {
    do
      {
       mid=(start+end)/2;                          /* Choose mid point */

       if(segments->segments[mid].node1<node)      /* Mid point is too low */
          start=mid;
       else if(segments->segments[mid].node1>node) /* Mid point is too high */
          end=mid;
       else                                        /* Mid point is correct */
         {found=mid; goto found;}
      }
    while((end-start)>1);

    if(segments->segments[start].node1==node)      /* Start is correct */
         {found=start; goto found;}

    if(segments->segments[end].node1==node)        /* End is correct */
         {found=end; goto found;}
   }

 return(NULL);

 found:

 while(found>0 && segments->segments[found-1].node1==node)
    found--;

 return(&segments->segments[found]);
}


/*++++++++++++++++++++++++++++++++++++++
  Find the next segment with a particular starting node.

  Segment *FindNextSegment Returns a pointer to the next segment with the same id.

  Segments* segments The set of segments to process.

  Segment *segment The current segment.
  ++++++++++++++++++++++++++++++++++++++*/

Segment *FindNextSegment(Segments* segments,Segment *segment)
{
 Segment *next=segment+1;

 if((next-segments->segments)==segments->number)
    return(NULL);

 if(next->node1==segment->node1)
    return(next);

 return(NULL);
}


/*++++++++++++++++++++++++++++++++++++++
  Append a segment to a newly created segment list (unsorted).

  Segment *AppendSegment Returns the appended segment.

  SegmentsMem* segments The set of segments to process.

  node_t node1 The first node in the segment.

  node_t node2 The second node in the segment.

  way_t way The way that the pair of segments are connected by.
  ++++++++++++++++++++++++++++++++++++++*/

Segment *AppendSegment(SegmentsMem* segments,node_t node1,node_t node2,way_t way)
{
 /* Check that the array has enough space. */

 if(segments->number==segments->alloced)
   {
    segments->alloced+=INCREMENT_SEGMENTS;

    segments->segments=(Segments*)realloc((void*)segments->segments,sizeof(Segments)+segments->alloced*sizeof(Segment));
   }

 /* Insert the segment */

 segments->segments->segments[segments->number].node1=node1;
 segments->segments->segments[segments->number].node2=node2;
 segments->segments->segments[segments->number].way=way;
 segments->segments->segments[segments->number].distance=0;
 segments->segments->segments[segments->number].duration=0;

 segments->number++;

 segments->sorted=0;

 return(&segments->segments->segments[segments->number-1]);
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the segment list.

  SegmentsMem* segments The set of segments to process.
  ++++++++++++++++++++++++++++++++++++++*/

void SortSegmentList(SegmentsMem* segments)
{
#ifdef NBINS_SEGMENTS
 int i,bin=0;
#endif

 qsort(segments->segments->segments,segments->number,sizeof(Segment),(int (*)(const void*,const void*))sort_by_id);

 while(segments->segments->segments[segments->number-1].node1==~0)
    segments->number--;

 segments->sorted=1;

 /* Make it searchable */

 segments->segments->number=segments->number;

#ifdef NBINS_SEGMENTS
 for(i=0;i<segments->number;i++)
    for(;bin<=(segments->segments->segments[i].node1%NBINS_SEGMENTS);bin++)
       segments->segments->offset[bin]=i;

 for(;bin<=NBINS_SEGMENTS;bin++)
    segments->segments->offset[bin]=segments->number;
#endif
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the segments into id order.

  int sort_by_id Returns the comparison of the node fields.

  Segment *a The first Segment.

  Segment *b The second Segment.
  ++++++++++++++++++++++++++++++++++++++*/

static int sort_by_id(Segment *a,Segment *b)
{
 node_t a_id1=a->node1,a_id2=a->node2;
 node_t b_id1=b->node1,b_id2=b->node2;

#ifdef NBINS_SEGMENTS
 int a_bin=a->node1%NBINS_SEGMENTS;
 int b_bin=b->node1%NBINS_SEGMENTS;

 if(a_bin!=b_bin)
    return(a_bin-b_bin);
#endif

 if(a_id1<b_id1)
    return(-1);
 else if(a_id1>b_id1)
    return(1);
 else /* if(a_id1==b_id1) */
   {
    if(a_id2<b_id2)
       return(-1);
    else if(a_id2>b_id2)
       return(1);
    else
       return(0);
   }
}


/*++++++++++++++++++++++++++++++++++++++
  Remove bad segments (zero length or duplicated).

  SegmentsMem *segments The segments to modify.
  ++++++++++++++++++++++++++++++++++++++*/

void RemoveBadSegments(SegmentsMem *segments)
{
 int i;
 int duplicate=0,loop=0;
 node_t node1=~0,node2=~0;

 for(i=0;i<segments->number;i++)
   {
    Segment *segment=&segments->segments->segments[i];

    if(segment->node1==node1 && segment->node2==node2)
      {
       duplicate++;
       segment->node1=~0;
      }
    else if(segment->node1==segment->node2)
      {
       loop++;
       segment->node1=~0;
      }

    node1=segment->node1;
    node2=segment->node2;

    if(!((i+1)%10000))
      {
       printf("\rChecking: Segments=%d Duplicate=%d Loop=%d",i+1,duplicate,loop);
       fflush(stdout);
      }
   }

 printf("\rChecked: Segments=%d Duplicate=%d Loop=%d  \n",segments->number,duplicate,loop);
 fflush(stdout);
}


/*++++++++++++++++++++++++++++++++++++++
  Assign the lengths and durations to all of the segments.

  SegmentsMem* segments The set of segments to process.

  Nodes *nodes The list of nodes to use.

  Ways *ways The list of ways to use.
  ++++++++++++++++++++++++++++++++++++++*/

void FixupSegmentLengths(SegmentsMem* segments,Nodes *nodes,Ways *ways)
{
 int i;

 assert(segments->sorted);      /* Must be sorted */

 for(i=0;i<segments->number;i++)
   {
    speed_t    speed;
    distance_t distance=INVALID_SHORT_DISTANCE;
    duration_t duration=INVALID_SHORT_DURATION;
    Node *node1=FindNode(nodes,segments->segments->segments[i].node1);
    Node *node2=FindNode(nodes,segments->segments->segments[i].node2);
    Way  *way=FindWay(ways,segments->segments->segments[i].way);

    if(way->limit)
       speed=way->limit;
    else
       speed=way->speed;

    if(Way_TYPE(way->type)<Way_Service &&
       segments->segments->segments[i].distance!=INVALID_SHORT_DISTANCE)
      {
       distance=Distance(node1,node2);
       duration=hours_to_duration(distance_to_km(distance)/speed);

       if(distance>=INVALID_SHORT_DISTANCE)
         {
          fprintf(stderr,"\nSegment too long (%d->%d) = %.1f km\n",node1->id,node2->id,distance_to_km(distance));
          distance=INVALID_SHORT_DISTANCE;
         }

       if(duration>=INVALID_SHORT_DURATION)
         {
          fprintf(stderr,"\nSegment too long (%d->%d) = %.1f mins\n",node1->id,node2->id,duration_to_minutes(duration));
          duration=INVALID_SHORT_DURATION;
         }
      }

    segments->segments->segments[i].distance=distance;
    segments->segments->segments[i].duration=duration;
   }
}


/*++++++++++++++++++++++++++++++++++++++
  Calculate the distance between two nodes.

  distance_t Distance Returns the distance between the nodes.

  Node *node1 The starting node.

  Node *node2 The end node.
  ++++++++++++++++++++++++++++++++++++++*/

distance_t Distance(Node *node1,Node *node2)
{
 double radiant = M_PI / 180;

 double dlon = radiant * (node1->longitude - node2->longitude);
 double dlat = radiant * (node1->latitude  - node2->latitude);

 double a1,a2,a,sa,c,d;

 if(dlon==0 && dlat==0)
   return 0;

 a1 = sin (dlat / 2);
 a2 = sin (dlon / 2);
 a = (a1 * a1) + cos (node1->latitude * radiant) * cos (node2->latitude * radiant) * a2 * a2;
 sa = sqrt (a);
 if (sa <= 1.0)
   {c = 2 * asin (sa);}
 else
   {c = 2 * asin (1.0);}
 d = 6378.137 * c;

 return km_to_distance(d);
}
1	amb	2	/***************************************
2	amb	53	$Header: /home/amb/CVS/routino/src/segments.c,v 1.10 2009-01-18 09:09:28 amb Exp $
3	amb	2
4			Segment data type functions.
5			****************/ /****************
6			Written by Andrew M. Bishop
7
8	amb	4	This file Copyright 2008,2009 Andrew M. Bishop
9	amb	2	It may be distributed under the GNU Public License, version 2, or
10			any higher version. See section COPYING of the GNU Public license
11			for conditions under which this file may be redistributed.
12			***************************************/
13
14
15	amb	8	#include <assert.h>
16	amb	2	#include <math.h>
17			#include <stdlib.h>
18
19	amb	39	#include "nodes.h"
20	amb	26	#include "segments.h"
21	amb	2	#include "functions.h"
22
23
24	amb	23	/* Functions */
25	amb	2
26	amb	23	static int sort_by_id(Segment a,Segment b);
27	amb	2
28	amb	8
29	amb	23	/*++++++++++++++++++++++++++++++++++++++
30			Allocate a new segment list.
31	amb	8
32	amb	23	SegmentsMem *NewSegmentList Returns the segment list.
33			++++++++++++++++++++++++++++++++++++++*/
34	amb	2
35	amb	23	SegmentsMem *NewSegmentList(void)
36			{
37			SegmentsMem *segments;
38	amb	2
39	amb	23	segments=(SegmentsMem*)malloc(sizeof(SegmentsMem));
40	amb	2
41	amb	23	segments->alloced=INCREMENT_SEGMENTS;
42			segments->number=0;
43			segments->sorted=0;
44
45			segments->segments=(Segments)malloc(sizeof(Segments)+segments->allocedsizeof(Segment));
46
47			return(segments);
48			}
49
50
51	amb	2	/*++++++++++++++++++++++++++++++++++++++
52			Load in a segment list from a file.
53
54	amb	23	Segments* SaveSegmentList Returns the segment list that has just been loaded.
55
56	amb	2	const char *filename The name of the file to load.
57			++++++++++++++++++++++++++++++++++++++*/
58
59	amb	23	Segments LoadSegmentList(const char filename)
60	amb	2	{
61	amb	23	return((Segments*)MapFile(filename));
62	amb	2	}
63
64
65			/*++++++++++++++++++++++++++++++++++++++
66			Save the segment list to a file.
67
68	amb	23	Segments* SaveSegmentList Returns the segment list that has just been saved.
69
70			SegmentsMem* segments The set of segments to save.
71
72	amb	2	const char *filename The name of the file to save.
73			++++++++++++++++++++++++++++++++++++++*/
74
75	amb	23	Segments SaveSegmentList(SegmentsMem segments,const char *filename)
76	amb	2	{
77	amb	23	assert(segments->sorted); /* Must be sorted */
78	amb	2
79	amb	23	if(WriteFile(filename,(void)segments->segments,sizeof(Segments)-sizeof(segments->segments->segments)+segments->numbersizeof(Segment)))
80			assert(0);
81
82			free(segments->segments);
83			free(segments);
84
85			return(LoadSegmentList(filename));
86	amb	2	}
87
88
89			/*++++++++++++++++++++++++++++++++++++++
90			Find the first segment with a particular starting node.
91
92			Segment *FindFirstSegment Returns a pointer to the first segment with the specified id.
93
94	amb	23	Segments* segments The set of segments to process.
95
96	amb	2	node_t node The node to look for.
97			++++++++++++++++++++++++++++++++++++++*/
98
99	amb	23	Segment FindFirstSegment(Segments segments,node_t node)
100	amb	2	{
101	amb	23	#ifdef NBINS_SEGMENTS
102			int bin=node%NBINS_SEGMENTS;
103			int start=segments->offset[bin];
104			int end=segments->offset[bin+1]-1;
105			#else
106	amb	2	int start=0;
107	amb	23	int end=segments->number-1;
108			#endif
109	amb	2	int mid;
110			int found;
111
112			/* Binary search - search key exact match only is required.
113			*
114			* # <- start \| Check mid and move start or end if it doesn't match
115			* # \|
116			* # \| Since an exact match is wanted we can set end=mid-1
117			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
118			* # \|
119			* # \| Eventually either end=start or end=start+1 and one of
120			* # <- end \| start or end is the wanted one.
121			*/
122
123	amb	23	if(end<start) /* There are no nodes */
124	amb	2	return(NULL);
125	amb	23	else if(node<segments->segments[start].node1) /* Check key is not before start */
126	amb	2	return(NULL);
127	amb	23	else if(node>segments->segments[end].node1) /* Check key is not after end */
128	amb	2	return(NULL);
129			else
130			{
131			do
132			{
133	amb	23	mid=(start+end)/2; /* Choose mid point */
134	amb	2
135	amb	23	if(segments->segments[mid].node1<node) /* Mid point is too low */
136	amb	2	start=mid;
137	amb	23	else if(segments->segments[mid].node1>node) /* Mid point is too high */
138	amb	2	end=mid;
139	amb	23	else /* Mid point is correct */
140	amb	2	{found=mid; goto found;}
141			}
142			while((end-start)>1);
143
144	amb	23	if(segments->segments[start].node1==node) /* Start is correct */
145	amb	2	{found=start; goto found;}
146
147	amb	23	if(segments->segments[end].node1==node) /* End is correct */
148	amb	2	{found=end; goto found;}
149			}
150
151			return(NULL);
152
153			found:
154
155	amb	23	while(found>0 && segments->segments[found-1].node1==node)
156	amb	2	found--;
157
158	amb	23	return(&segments->segments[found]);
159	amb	2	}
160
161
162			/*++++++++++++++++++++++++++++++++++++++
163			Find the next segment with a particular starting node.
164
165	amb	23	Segment *FindNextSegment Returns a pointer to the next segment with the same id.
166	amb	2
167	amb	23	Segments* segments The set of segments to process.
168
169	amb	2	Segment *segment The current segment.
170			++++++++++++++++++++++++++++++++++++++*/
171
172	amb	23	Segment FindNextSegment(Segments segments,Segment *segment)
173	amb	2	{
174			Segment *next=segment+1;
175
176	amb	23	if((next-segments->segments)==segments->number)
177			return(NULL);
178	amb	2
179			if(next->node1==segment->node1)
180			return(next);
181
182			return(NULL);
183			}
184
185
186			/*++++++++++++++++++++++++++++++++++++++
187			Append a segment to a newly created segment list (unsorted).
188
189	amb	31	Segment *AppendSegment Returns the appended segment.
190
191	amb	23	SegmentsMem* segments The set of segments to process.
192
193	amb	2	node_t node1 The first node in the segment.
194
195			node_t node2 The second node in the segment.
196
197	amb	5	way_t way The way that the pair of segments are connected by.
198	amb	2	++++++++++++++++++++++++++++++++++++++*/
199
200	amb	31	Segment AppendSegment(SegmentsMem segments,node_t node1,node_t node2,way_t way)
201	amb	2	{
202	amb	23	/* Check that the array has enough space. */
203	amb	8
204	amb	23	if(segments->number==segments->alloced)
205	amb	4	{
206	amb	23	segments->alloced+=INCREMENT_SEGMENTS;
207	amb	4
208	amb	23	segments->segments=(Segments)realloc((void)segments->segments,sizeof(Segments)+segments->alloced*sizeof(Segment));
209	amb	4	}
210
211			/* Insert the segment */
212
213	amb	23	segments->segments->segments[segments->number].node1=node1;
214			segments->segments->segments[segments->number].node2=node2;
215			segments->segments->segments[segments->number].way=way;
216			segments->segments->segments[segments->number].distance=0;
217			segments->segments->segments[segments->number].duration=0;
218	amb	2
219	amb	23	segments->number++;
220	amb	2
221	amb	23	segments->sorted=0;
222	amb	31
223			return(&segments->segments->segments[segments->number-1]);
224	amb	2	}
225
226
227			/*++++++++++++++++++++++++++++++++++++++
228			Sort the segment list.
229	amb	23
230			SegmentsMem* segments The set of segments to process.
231	amb	2	++++++++++++++++++++++++++++++++++++++*/
232
233	amb	23	void SortSegmentList(SegmentsMem* segments)
234	amb	2	{
235	amb	39	#ifdef NBINS_SEGMENTS
236			int i,bin=0;
237			#endif
238
239	amb	23	qsort(segments->segments->segments,segments->number,sizeof(Segment),(int ()(const void,const void*))sort_by_id);
240	amb	8
241	amb	39	while(segments->segments->segments[segments->number-1].node1==~0)
242			segments->number--;
243
244	amb	23	segments->sorted=1;
245	amb	39
246			/* Make it searchable */
247
248			segments->segments->number=segments->number;
249
250			#ifdef NBINS_SEGMENTS
251			for(i=0;i<segments->number;i++)
252			for(;bin<=(segments->segments->segments[i].node1%NBINS_SEGMENTS);bin++)
253			segments->segments->offset[bin]=i;
254
255			for(;bin<=NBINS_SEGMENTS;bin++)
256			segments->segments->offset[bin]=segments->number;
257			#endif
258	amb	2	}
259
260
261			/*++++++++++++++++++++++++++++++++++++++
262			Sort the segments into id order.
263
264			int sort_by_id Returns the comparison of the node fields.
265
266			Segment *a The first Segment.
267
268			Segment *b The second Segment.
269			++++++++++++++++++++++++++++++++++++++*/
270
271			static int sort_by_id(Segment a,Segment b)
272			{
273			node_t a_id1=a->node1,a_id2=a->node2;
274			node_t b_id1=b->node1,b_id2=b->node2;
275
276	amb	23	#ifdef NBINS_SEGMENTS
277			int a_bin=a->node1%NBINS_SEGMENTS;
278			int b_bin=b->node1%NBINS_SEGMENTS;
279
280			if(a_bin!=b_bin)
281			return(a_bin-b_bin);
282			#endif
283
284	amb	39	if(a_id1<b_id1)
285			return(-1);
286			else if(a_id1>b_id1)
287			return(1);
288			else /* if(a_id1==b_id1) */
289			{
290			if(a_id2<b_id2)
291			return(-1);
292			else if(a_id2>b_id2)
293			return(1);
294			else
295			return(0);
296			}
297	amb	2	}
298
299
300			/*++++++++++++++++++++++++++++++++++++++
301	amb	39	Remove bad segments (zero length or duplicated).
302
303			SegmentsMem *segments The segments to modify.
304			++++++++++++++++++++++++++++++++++++++*/
305
306			void RemoveBadSegments(SegmentsMem *segments)
307			{
308			int i;
309			int duplicate=0,loop=0;
310			node_t node1=~0,node2=~0;
311
312			for(i=0;i<segments->number;i++)
313			{
314			Segment *segment=&segments->segments->segments[i];
315
316			if(segment->node1==node1 && segment->node2==node2)
317			{
318			duplicate++;
319			segment->node1=~0;
320			}
321			else if(segment->node1==segment->node2)
322			{
323			loop++;
324			segment->node1=~0;
325			}
326
327			node1=segment->node1;
328			node2=segment->node2;
329
330			if(!((i+1)%10000))
331			{
332			printf("\rChecking: Segments=%d Duplicate=%d Loop=%d",i+1,duplicate,loop);
333			fflush(stdout);
334			}
335			}
336
337			printf("\rChecked: Segments=%d Duplicate=%d Loop=%d \n",segments->number,duplicate,loop);
338			fflush(stdout);
339			}
340
341
342			/*++++++++++++++++++++++++++++++++++++++
343	amb	8	Assign the lengths and durations to all of the segments.
344	amb	23
345			SegmentsMem* segments The set of segments to process.
346
347			Nodes *nodes The list of nodes to use.
348
349			Ways *ways The list of ways to use.
350	amb	8	++++++++++++++++++++++++++++++++++++++*/
351	amb	2
352	amb	23	void FixupSegmentLengths(SegmentsMem* segments,Nodes nodes,Ways ways)
353	amb	8	{
354			int i;
355	amb	2
356	amb	23	assert(segments->sorted); /* Must be sorted */
357	amb	8
358	amb	23	for(i=0;i<segments->number;i++)
359	amb	8	{
360	amb	30	speed_t speed;
361	amb	39	distance_t distance=INVALID_SHORT_DISTANCE;
362			duration_t duration=INVALID_SHORT_DURATION;
363	amb	23	Node *node1=FindNode(nodes,segments->segments->segments[i].node1);
364			Node *node2=FindNode(nodes,segments->segments->segments[i].node2);
365			Way *way=FindWay(ways,segments->segments->segments[i].way);
366	amb	8
367	amb	30	if(way->limit)
368			speed=way->limit;
369			else
370			speed=way->speed;
371	amb	8
372	amb	53	if(Way_TYPE(way->type)<Way_Service &&
373			segments->segments->segments[i].distance!=INVALID_SHORT_DISTANCE)
374	amb	30	{
375			distance=Distance(node1,node2);
376			duration=hours_to_duration(distance_to_km(distance)/speed);
377	amb	26
378	amb	39	if(distance>=INVALID_SHORT_DISTANCE)
379	amb	30	{
380			fprintf(stderr,"\nSegment too long (%d->%d) = %.1f km\n",node1->id,node2->id,distance_to_km(distance));
381	amb	39	distance=INVALID_SHORT_DISTANCE;
382	amb	30	}
383
384	amb	39	if(duration>=INVALID_SHORT_DURATION)
385	amb	30	{
386			fprintf(stderr,"\nSegment too long (%d->%d) = %.1f mins\n",node1->id,node2->id,duration_to_minutes(duration));
387	amb	39	duration=INVALID_SHORT_DURATION;
388	amb	30	}
389	amb	26	}
390
391	amb	23	segments->segments->segments[i].distance=distance;
392			segments->segments->segments[i].duration=duration;
393	amb	8	}
394			}
395
396
397			/*++++++++++++++++++++++++++++++++++++++
398			Calculate the distance between two nodes.
399
400			distance_t Distance Returns the distance between the nodes.
401
402	amb	2	Node *node1 The starting node.
403
404			Node *node2 The end node.
405			++++++++++++++++++++++++++++++++++++++*/
406
407	amb	8	distance_t Distance(Node node1,Node node2)
408	amb	2	{
409			double radiant = M_PI / 180;
410
411			double dlon = radiant * (node1->longitude - node2->longitude);
412			double dlat = radiant * (node1->latitude - node2->latitude);
413
414			double a1,a2,a,sa,c,d;
415
416			if(dlon==0 && dlat==0)
417			return 0;
418
419			a1 = sin (dlat / 2);
420			a2 = sin (dlon / 2);
421			a = (a1 * a1) + cos (node1->latitude * radiant) * cos (node2->latitude * radiant) * a2 * a2;
422			sa = sqrt (a);
423			if (sa <= 1.0)
424			{c = 2 * asin (sa);}
425			else
426			{c = 2 * asin (1.0);}
427	amb	5	d = 6378.137 * c;
428	amb	2
429	amb	5	return km_to_distance(d);
430	amb	2	}