trunk/src/segments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/segments.c,v 1.18 2009-01-25 12:09:15 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)
{
 int bin=node%NBINS_SEGMENTS;
 int start=segments->offset[bin];
 int end=segments->offset[bin+1]-1; /* &offset[NBINS+1] == &number */
 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->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)
{
 int i,bin=0;

 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;

 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;
}


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

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

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

 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++)
   {
    Node *node1=FindNode(nodes,segments->segments->segments[i].node1);
    Node *node2=FindNode(nodes,segments->segments->segments[i].node2);

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

    segments->segments->segments[i].distance|=Distance(node1,node2);

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

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


/*++++++++++++++++++++++++++++++++++++++
  Change the segment to contain the index of the way, not the id.

  SegmentsMem* segments The set of segments to process.

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

void LinkSegmentToWay(SegmentsMem* segments,Ways *ways)
{
 int i;

 for(i=0;i<segments->number;i++)
   {
    Way *way=FindWay(ways,segments->segments->segments[i].way);

    segments->segments->segments[i].way=IndexWay(ways,way);
   }
}


/*++++++++++++++++++++++++++++++++++++++
  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 hours_to_duration(distance_to_km(distance)/speed);
}
1	amb	2	/***************************************
2	amb	84	$Header: /home/amb/CVS/routino/src/segments.c,v 1.18 2009-01-25 12:09:15 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	int bin=node%NBINS_SEGMENTS;
102			int start=segments->offset[bin];
103	amb	65	int end=segments->offset[bin+1]-1; /* &offset[NBINS+1] == &number */
104	amb	2	int mid;
105			int found;
106
107			/* Binary search - search key exact match only is required.
108			*
109			* # <- start \| Check mid and move start or end if it doesn't match
110			* # \|
111			* # \| Since an exact match is wanted we can set end=mid-1
112			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
113			* # \|
114			* # \| Eventually either end=start or end=start+1 and one of
115			* # <- end \| start or end is the wanted one.
116			*/
117
118	amb	23	if(end<start) /* There are no nodes */
119	amb	2	return(NULL);
120	amb	23	else if(node<segments->segments[start].node1) /* Check key is not before start */
121	amb	2	return(NULL);
122	amb	23	else if(node>segments->segments[end].node1) /* Check key is not after end */
123	amb	2	return(NULL);
124			else
125			{
126			do
127			{
128	amb	23	mid=(start+end)/2; /* Choose mid point */
129	amb	2
130	amb	23	if(segments->segments[mid].node1<node) /* Mid point is too low */
131	amb	2	start=mid;
132	amb	23	else if(segments->segments[mid].node1>node) /* Mid point is too high */
133	amb	2	end=mid;
134	amb	23	else /* Mid point is correct */
135	amb	2	{found=mid; goto found;}
136			}
137			while((end-start)>1);
138
139	amb	23	if(segments->segments[start].node1==node) /* Start is correct */
140	amb	2	{found=start; goto found;}
141
142	amb	23	if(segments->segments[end].node1==node) /* End is correct */
143	amb	2	{found=end; goto found;}
144			}
145
146			return(NULL);
147
148			found:
149
150	amb	23	while(found>0 && segments->segments[found-1].node1==node)
151	amb	2	found--;
152
153	amb	23	return(&segments->segments[found]);
154	amb	2	}
155
156
157			/*++++++++++++++++++++++++++++++++++++++
158			Find the next segment with a particular starting node.
159
160	amb	23	Segment *FindNextSegment Returns a pointer to the next segment with the same id.
161	amb	2
162	amb	23	Segments* segments The set of segments to process.
163
164	amb	2	Segment *segment The current segment.
165			++++++++++++++++++++++++++++++++++++++*/
166
167	amb	23	Segment FindNextSegment(Segments segments,Segment *segment)
168	amb	2	{
169			Segment *next=segment+1;
170
171	amb	23	if((next-segments->segments)==segments->number)
172			return(NULL);
173	amb	2
174			if(next->node1==segment->node1)
175			return(next);
176
177			return(NULL);
178			}
179
180
181			/*++++++++++++++++++++++++++++++++++++++
182			Append a segment to a newly created segment list (unsorted).
183
184	amb	31	Segment *AppendSegment Returns the appended segment.
185
186	amb	23	SegmentsMem* segments The set of segments to process.
187
188	amb	2	node_t node1 The first node in the segment.
189
190			node_t node2 The second node in the segment.
191
192	amb	5	way_t way The way that the pair of segments are connected by.
193	amb	2	++++++++++++++++++++++++++++++++++++++*/
194
195	amb	31	Segment AppendSegment(SegmentsMem segments,node_t node1,node_t node2,way_t way)
196	amb	2	{
197	amb	23	/* Check that the array has enough space. */
198	amb	8
199	amb	23	if(segments->number==segments->alloced)
200	amb	4	{
201	amb	23	segments->alloced+=INCREMENT_SEGMENTS;
202	amb	4
203	amb	23	segments->segments=(Segments)realloc((void)segments->segments,sizeof(Segments)+segments->alloced*sizeof(Segment));
204	amb	4	}
205
206			/* Insert the segment */
207
208	amb	23	segments->segments->segments[segments->number].node1=node1;
209			segments->segments->segments[segments->number].node2=node2;
210			segments->segments->segments[segments->number].way=way;
211			segments->segments->segments[segments->number].distance=0;
212	amb	2
213	amb	23	segments->number++;
214	amb	2
215	amb	23	segments->sorted=0;
216	amb	31
217			return(&segments->segments->segments[segments->number-1]);
218	amb	2	}
219
220
221			/*++++++++++++++++++++++++++++++++++++++
222			Sort the segment list.
223	amb	23
224			SegmentsMem* segments The set of segments to process.
225	amb	2	++++++++++++++++++++++++++++++++++++++*/
226
227	amb	23	void SortSegmentList(SegmentsMem* segments)
228	amb	2	{
229	amb	39	int i,bin=0;
230
231	amb	23	qsort(segments->segments->segments,segments->number,sizeof(Segment),(int ()(const void,const void*))sort_by_id);
232	amb	8
233	amb	39	while(segments->segments->segments[segments->number-1].node1==~0)
234			segments->number--;
235
236	amb	23	segments->sorted=1;
237	amb	39
238			/* Make it searchable */
239
240			segments->segments->number=segments->number;
241
242			for(i=0;i<segments->number;i++)
243			for(;bin<=(segments->segments->segments[i].node1%NBINS_SEGMENTS);bin++)
244			segments->segments->offset[bin]=i;
245
246	amb	65	for(;bin<NBINS_SEGMENTS;bin++)
247	amb	39	segments->segments->offset[bin]=segments->number;
248	amb	2	}
249
250
251			/*++++++++++++++++++++++++++++++++++++++
252			Sort the segments into id order.
253
254			int sort_by_id Returns the comparison of the node fields.
255
256			Segment *a The first Segment.
257
258			Segment *b The second Segment.
259			++++++++++++++++++++++++++++++++++++++*/
260
261			static int sort_by_id(Segment a,Segment b)
262			{
263			node_t a_id1=a->node1,a_id2=a->node2;
264			node_t b_id1=b->node1,b_id2=b->node2;
265
266	amb	23	int a_bin=a->node1%NBINS_SEGMENTS;
267			int b_bin=b->node1%NBINS_SEGMENTS;
268
269			if(a_bin!=b_bin)
270			return(a_bin-b_bin);
271
272	amb	39	if(a_id1<b_id1)
273			return(-1);
274			else if(a_id1>b_id1)
275			return(1);
276			else /* if(a_id1==b_id1) */
277			{
278			if(a_id2<b_id2)
279			return(-1);
280			else if(a_id2>b_id2)
281			return(1);
282			else
283			return(0);
284			}
285	amb	2	}
286
287
288			/*++++++++++++++++++++++++++++++++++++++
289	amb	39	Remove bad segments (zero length or duplicated).
290
291			SegmentsMem *segments The segments to modify.
292			++++++++++++++++++++++++++++++++++++++*/
293
294			void RemoveBadSegments(SegmentsMem *segments)
295			{
296			int i;
297			int duplicate=0,loop=0;
298			node_t node1=~0,node2=~0;
299
300			for(i=0;i<segments->number;i++)
301			{
302			Segment *segment=&segments->segments->segments[i];
303
304			if(segment->node1==node1 && segment->node2==node2)
305			{
306			duplicate++;
307			segment->node1=~0;
308			}
309			else if(segment->node1==segment->node2)
310			{
311			loop++;
312			segment->node1=~0;
313			}
314
315			node1=segment->node1;
316			node2=segment->node2;
317
318			if(!((i+1)%10000))
319			{
320			printf("\rChecking: Segments=%d Duplicate=%d Loop=%d",i+1,duplicate,loop);
321			fflush(stdout);
322			}
323			}
324
325			printf("\rChecked: Segments=%d Duplicate=%d Loop=%d \n",segments->number,duplicate,loop);
326			fflush(stdout);
327			}
328
329
330			/*++++++++++++++++++++++++++++++++++++++
331	amb	8	Assign the lengths and durations to all of the segments.
332	amb	23
333			SegmentsMem* segments The set of segments to process.
334
335			Nodes *nodes The list of nodes to use.
336
337			Ways *ways The list of ways to use.
338	amb	8	++++++++++++++++++++++++++++++++++++++*/
339	amb	2
340	amb	23	void FixupSegmentLengths(SegmentsMem* segments,Nodes nodes,Ways ways)
341	amb	8	{
342			int i;
343	amb	2
344	amb	23	assert(segments->sorted); /* Must be sorted */
345	amb	8
346	amb	23	for(i=0;i<segments->number;i++)
347	amb	8	{
348	amb	23	Node *node1=FindNode(nodes,segments->segments->segments[i].node1);
349			Node *node2=FindNode(nodes,segments->segments->segments[i].node2);
350	amb	8
351	amb	82	/* Set the distance but preserve the ONEWAY_OPPOSITE flag */
352	amb	8
353	amb	69	segments->segments->segments[i].distance\|=Distance(node1,node2);
354
355	amb	54	if(!((i+1)%10000))
356			{
357			printf("\rMeasuring Segments: Segments=%d",i+1);
358			fflush(stdout);
359			}
360	amb	8	}
361	amb	54
362			printf("\rMeasured Segments: Segments=%d \n",segments->number);
363			fflush(stdout);
364	amb	8	}
365
366
367			/*++++++++++++++++++++++++++++++++++++++
368	amb	84	Change the segment to contain the index of the way, not the id.
369
370			SegmentsMem* segments The set of segments to process.
371
372			Ways *ways The list of ways to use.
373			++++++++++++++++++++++++++++++++++++++*/
374
375			void LinkSegmentToWay(SegmentsMem* segments,Ways *ways)
376			{
377			int i;
378
379			for(i=0;i<segments->number;i++)
380			{
381			Way *way=FindWay(ways,segments->segments->segments[i].way);
382
383			segments->segments->segments[i].way=IndexWay(ways,way);
384			}
385			}
386
387
388			/*++++++++++++++++++++++++++++++++++++++
389	amb	8	Calculate the distance between two nodes.
390
391			distance_t Distance Returns the distance between the nodes.
392
393	amb	2	Node *node1 The starting node.
394
395			Node *node2 The end node.
396			++++++++++++++++++++++++++++++++++++++*/
397
398	amb	8	distance_t Distance(Node node1,Node node2)
399	amb	2	{
400			double radiant = M_PI / 180;
401
402			double dlon = radiant * (node1->longitude - node2->longitude);
403			double dlat = radiant * (node1->latitude - node2->latitude);
404
405			double a1,a2,a,sa,c,d;
406
407			if(dlon==0 && dlat==0)
408			return 0;
409
410			a1 = sin (dlat / 2);
411			a2 = sin (dlon / 2);
412			a = (a1 * a1) + cos (node1->latitude * radiant) * cos (node2->latitude * radiant) * a2 * a2;
413			sa = sqrt (a);
414			if (sa <= 1.0)
415			{c = 2 * asin (sa);}
416			else
417			{c = 2 * asin (1.0);}
418	amb	5	d = 6378.137 * c;
419	amb	2
420	amb	5	return km_to_distance(d);
421	amb	2	}
422	amb	63
423
424			/*++++++++++++++++++++++++++++++++++++++
425			Calculate the duration of segment.
426
427			duration_t Duration Returns the duration of travel between the nodes.
428
429			Segment *segment The segment to traverse.
430
431			Way *way The way that the segment belongs to.
432
433	amb	82	Profile *profile The profile of the transport being used.
434	amb	63	++++++++++++++++++++++++++++++++++++++*/
435
436	amb	82	duration_t Duration(Segment segment,Way way,Profile *profile)
437	amb	63	{
438	amb	82	speed_t speed=profile->speed[HIGHWAY(way->type)];
439	amb	63	distance_t distance=segment->distance;
440
441			return hours_to_duration(distance_to_km(distance)/speed);
442			}