trunk/src/segments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/segments.c,v 1.21 2009-01-27 18:22:37 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 <unistd.h>
#include <math.h>
#include <stdlib.h>

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


/* Functions */

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


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

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

SegmentsMem *NewSegmentList(void)
{
 SegmentsMem *segmentsmem;

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

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

 segmentsmem->xdata=(SegmentEx*)malloc(segmentsmem->alloced*sizeof(SegmentEx));

 return(segmentsmem);
}


/*++++++++++++++++++++++++++++++++++++++
  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)
{
 void *data;
 Segments *segments;

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

 data=MapFile(filename);

 /* Copy the Segments structure from the loaded data */

 *segments=*((Segments*)data);

 /* Adjust the pointers in the Segments structure. */

 segments->data =data;
 segments->segments=(Segment*)(data+(off_t)segments->segments);

 return(segments);
}


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

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

  SegmentsMem* segmentsmem The set of segments to save.

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

Segments *SaveSegmentList(SegmentsMem* segmentsmem,const char *filename)
{
 int i;
 int fd;
 Segments *segments=calloc(1,sizeof(Segments));

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

 /* Fill in a Segments structure with the offset of the real data in the file after
    the Segment structure itself. */

 segments->number=segmentsmem->number;
 segments->data=NULL;
 segments->segments=(void*)sizeof(Segments);

 /* Write out the Segments structure and then the real data. */

 fd=OpenFile(filename);

 write(fd,segments,sizeof(Segments));

 for(i=0;i<segmentsmem->number;i++)
    write(fd,&segmentsmem->xdata[i].segment,sizeof(Segment));

 close(fd);

 /* Free the fake Segments and the input SegmentsMem */

 free(segments);

 free(segmentsmem->xdata);
 free(segmentsmem);

 return(LoadSegmentList(filename));
}


/*++++++++++++++++++++++++++++++++++++++
  Delete a segment list that was loaded from a file.

  Segment* segments The segment list.
  ++++++++++++++++++++++++++++++++++++++*/

void DropSegmentList(Segments *segments)
{
 UnMapFile(segments->data);

 free(segments);
}


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

  uint32_t FindFirstSegment Returns the index of the first segment with the specified id.

  SegmentsMem* segmentsmem The set of segments to process.

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

uint32_t FindFirstSegment(SegmentsMem* segmentsmem,node_t node)
{
 int start=0;
 int end=segmentsmem->number-1;
 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(~0);
 else if(node<segmentsmem->xdata[start].node1) /* Check key is not before start */
    return(~0);
 else if(node>segmentsmem->xdata[end].node1)   /* Check key is not after end */
    return(~0);
 else
   {
    do
      {
       mid=(start+end)/2;                          /* Choose mid point */

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

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

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

 return(~0);

 found:

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

 return(found);
}


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

  Segment *NextSegment 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 *NextSegment(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* segmentsmem The set of segments to process.

  node_t node1 The first node in the segment.

  node_t node2 The second node in the segment.

  uint32_t wayindex The index of the way that the pair of segments are connected by.
  ++++++++++++++++++++++++++++++++++++++*/

Segment *AppendSegment(SegmentsMem* segmentsmem,node_t node1,node_t node2,uint32_t wayindex)
{
 /* Check that the array has enough space. */

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

    segmentsmem->xdata=(SegmentEx*)realloc((void*)segmentsmem->xdata,segmentsmem->alloced*sizeof(SegmentEx));
   }

 /* Insert the segment */

 segmentsmem->xdata[segmentsmem->number].node1=node1;
 segmentsmem->xdata[segmentsmem->number].node2=node2;
 segmentsmem->xdata[segmentsmem->number].segment.wayindex=wayindex;
 segmentsmem->xdata[segmentsmem->number].segment.distance=0;

 segmentsmem->number++;

 segmentsmem->sorted=0;

 return(&segmentsmem->xdata[segmentsmem->number-1].segment);
}


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

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

void SortSegmentList(SegmentsMem* segmentsmem)
{
 qsort(segmentsmem->xdata,segmentsmem->number,sizeof(SegmentEx),(int (*)(const void*,const void*))sort_by_id);

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

 segmentsmem->sorted=1;
}


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

  int sort_by_id Returns the comparison of the node fields.

  SegmentEx *a The first Segment.

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

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

 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
       return(1);
   }
}


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

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

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

 for(i=0;i<segmentsmem->number;i++)
   {
    if(segmentsmem->xdata[i].node1==node1 && segmentsmem->xdata[i].node2==node2)
      {
       duplicate++;
       segmentsmem->xdata[i].node1=~0;
      }
    else if(segmentsmem->xdata[i].node1==segmentsmem->xdata[i].node2)
      {
       loop++;
       segmentsmem->xdata[i].node1=~0;
      }

    node1=segmentsmem->xdata[i].node1;
    node2=segmentsmem->xdata[i].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",segmentsmem->number,duplicate,loop);
 fflush(stdout);
}


/*++++++++++++++++++++++++++++++++++++++
  Fix the segment indexes to the nodes and assign the distance to all of the segments.

  SegmentsMem* segmentsmem The set of segments to process.

  NodesMem *nodesmem The list of nodes to use.
  ++++++++++++++++++++++++++++++++++++++*/

void FixupSegments(SegmentsMem* segmentsmem,NodesMem *nodesmem)
{
 int i;

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

 for(i=0;i<segmentsmem->number;i++)
   {
    uint32_t node1=FindNode(nodesmem,segmentsmem->xdata[i].node1);
    uint32_t node2=FindNode(nodesmem,segmentsmem->xdata[i].node2);

    segmentsmem->xdata[i].segment.node1=node1;
    segmentsmem->xdata[i].segment.node2=node2;

    /* Set the distance but preserve the ONEWAY_OPPOSITE flag */

    segmentsmem->xdata[i].segment.distance|=Distance(&nodesmem->xdata[node1].node,&nodesmem->xdata[node2].node);

    if(!((i+1)%10000))
      {
       printf("\rFixing Segments: Segments=%d",i+1);
       fflush(stdout);
      }
   }

 printf("\rFixing Segments: Segments=%d \n",segmentsmem->number);
 fflush(stdout);
}


/*++++++++++++++++++++++++++++++++++++++
  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);
}


/*++++++++++++++++++++++++++++++++++++++
  Calculate the duration of segment.

  duration_t Duration Returns the duration of travel between the nodes.

  Segment *segment The segment to traverse.

  Way *way The way that the segment belongs to.

  Profile *profile The profile of the transport being used.
  ++++++++++++++++++++++++++++++++++++++*/

duration_t Duration(Segment *segment,Way *way,Profile *profile)
{
 speed_t    speed=profile->speed[HIGHWAY(way->type)];
 distance_t distance=segment->distance;

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