trunk/src/segments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/segments.c,v 1.13 2009-01-21 19:35:52 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->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++)
   {
    Node *node1=FindNode(nodes,segments->segments->segments[i].node1);
    Node *node2=FindNode(nodes,segments->segments->segments[i].node2);

    if(segments->segments->segments[i].distance!=INVALID_DISTANCE)
       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);
}


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

  AllowType transport The type of transport being used.
  ++++++++++++++++++++++++++++++++++++++*/

duration_t Duration(Segment *segment,Way *way,AllowType transport)
{
 speed_t    speed=WaySpeed(way);
 distance_t distance=segment->distance;

 if(transport==Allow_Foot)
    speed=5;
 else if(transport==Allow_Horse)
    speed=8;
 else if(transport==Allow_Bicycle)
    speed=20;

 return hours_to_duration(distance_to_km(distance)/speed);
}
1	/***************************************
2	$Header: /home/amb/CVS/routino/src/segments.c,v 1.13 2009-01-21 19:35:52 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 <math.h>
17	#include <stdlib.h>
18
19	#include "nodes.h"
20	#include "segments.h"
21	#include "functions.h"
22
23
24	/* Functions */
25
26	static int sort_by_id(Segment a,Segment b);
27
28
29	/*++++++++++++++++++++++++++++++++++++++
30	Allocate a new segment list.
31
32	SegmentsMem *NewSegmentList Returns the segment list.
33	++++++++++++++++++++++++++++++++++++++*/
34
35	SegmentsMem *NewSegmentList(void)
36	{
37	SegmentsMem *segments;
38
39	segments=(SegmentsMem*)malloc(sizeof(SegmentsMem));
40
41	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	/*++++++++++++++++++++++++++++++++++++++
52	Load in a segment list from a file.
53
54	Segments* SaveSegmentList Returns the segment list that has just been loaded.
55
56	const char *filename The name of the file to load.
57	++++++++++++++++++++++++++++++++++++++*/
58
59	Segments LoadSegmentList(const char filename)
60	{
61	return((Segments*)MapFile(filename));
62	}
63
64
65	/*++++++++++++++++++++++++++++++++++++++
66	Save the segment list to a file.
67
68	Segments* SaveSegmentList Returns the segment list that has just been saved.
69
70	SegmentsMem* segments The set of segments to save.
71
72	const char *filename The name of the file to save.
73	++++++++++++++++++++++++++++++++++++++*/
74
75	Segments SaveSegmentList(SegmentsMem segments,const char *filename)
76	{
77	assert(segments->sorted); /* Must be sorted */
78
79	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	}
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	Segments* segments The set of segments to process.
95
96	node_t node The node to look for.
97	++++++++++++++++++++++++++++++++++++++*/
98
99	Segment FindFirstSegment(Segments segments,node_t node)
100	{
101	#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	int start=0;
107	int end=segments->number-1;
108	#endif
109	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	if(end<start) /* There are no nodes */
124	return(NULL);
125	else if(node<segments->segments[start].node1) /* Check key is not before start */
126	return(NULL);
127	else if(node>segments->segments[end].node1) /* Check key is not after end */
128	return(NULL);
129	else
130	{
131	do
132	{
133	mid=(start+end)/2; /* Choose mid point */
134
135	if(segments->segments[mid].node1<node) /* Mid point is too low */
136	start=mid;
137	else if(segments->segments[mid].node1>node) /* Mid point is too high */
138	end=mid;
139	else /* Mid point is correct */
140	{found=mid; goto found;}
141	}
142	while((end-start)>1);
143
144	if(segments->segments[start].node1==node) /* Start is correct */
145	{found=start; goto found;}
146
147	if(segments->segments[end].node1==node) /* End is correct */
148	{found=end; goto found;}
149	}
150
151	return(NULL);
152
153	found:
154
155	while(found>0 && segments->segments[found-1].node1==node)
156	found--;
157
158	return(&segments->segments[found]);
159	}
160
161
162	/*++++++++++++++++++++++++++++++++++++++
163	Find the next segment with a particular starting node.
164
165	Segment *FindNextSegment Returns a pointer to the next segment with the same id.
166
167	Segments* segments The set of segments to process.
168
169	Segment *segment The current segment.
170	++++++++++++++++++++++++++++++++++++++*/
171
172	Segment FindNextSegment(Segments segments,Segment *segment)
173	{
174	Segment *next=segment+1;
175
176	if((next-segments->segments)==segments->number)
177	return(NULL);
178
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	Segment *AppendSegment Returns the appended segment.
190
191	SegmentsMem* segments The set of segments to process.
192
193	node_t node1 The first node in the segment.
194
195	node_t node2 The second node in the segment.
196
197	way_t way The way that the pair of segments are connected by.
198	++++++++++++++++++++++++++++++++++++++*/
199
200	Segment AppendSegment(SegmentsMem segments,node_t node1,node_t node2,way_t way)
201	{
202	/* Check that the array has enough space. */
203
204	if(segments->number==segments->alloced)
205	{
206	segments->alloced+=INCREMENT_SEGMENTS;
207
208	segments->segments=(Segments)realloc((void)segments->segments,sizeof(Segments)+segments->alloced*sizeof(Segment));
209	}
210
211	/* Insert the segment */
212
213	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
218	segments->number++;
219
220	segments->sorted=0;
221
222	return(&segments->segments->segments[segments->number-1]);
223	}
224
225
226	/*++++++++++++++++++++++++++++++++++++++
227	Sort the segment list.
228
229	SegmentsMem* segments The set of segments to process.
230	++++++++++++++++++++++++++++++++++++++*/
231
232	void SortSegmentList(SegmentsMem* segments)
233	{
234	#ifdef NBINS_SEGMENTS
235	int i,bin=0;
236	#endif
237
238	qsort(segments->segments->segments,segments->number,sizeof(Segment),(int ()(const void,const void*))sort_by_id);
239
240	while(segments->segments->segments[segments->number-1].node1==~0)
241	segments->number--;
242
243	segments->sorted=1;
244
245	/* Make it searchable */
246
247	segments->segments->number=segments->number;
248
249	#ifdef NBINS_SEGMENTS
250	for(i=0;i<segments->number;i++)
251	for(;bin<=(segments->segments->segments[i].node1%NBINS_SEGMENTS);bin++)
252	segments->segments->offset[bin]=i;
253
254	for(;bin<=NBINS_SEGMENTS;bin++)
255	segments->segments->offset[bin]=segments->number;
256	#endif
257	}
258
259
260	/*++++++++++++++++++++++++++++++++++++++
261	Sort the segments into id order.
262
263	int sort_by_id Returns the comparison of the node fields.
264
265	Segment *a The first Segment.
266
267	Segment *b The second Segment.
268	++++++++++++++++++++++++++++++++++++++*/
269
270	static int sort_by_id(Segment a,Segment b)
271	{
272	node_t a_id1=a->node1,a_id2=a->node2;
273	node_t b_id1=b->node1,b_id2=b->node2;
274
275	#ifdef NBINS_SEGMENTS
276	int a_bin=a->node1%NBINS_SEGMENTS;
277	int b_bin=b->node1%NBINS_SEGMENTS;
278
279	if(a_bin!=b_bin)
280	return(a_bin-b_bin);
281	#endif
282
283	if(a_id1<b_id1)
284	return(-1);
285	else if(a_id1>b_id1)
286	return(1);
287	else /* if(a_id1==b_id1) */
288	{
289	if(a_id2<b_id2)
290	return(-1);
291	else if(a_id2>b_id2)
292	return(1);
293	else
294	return(0);
295	}
296	}
297
298
299	/*++++++++++++++++++++++++++++++++++++++
300	Remove bad segments (zero length or duplicated).
301
302	SegmentsMem *segments The segments to modify.
303	++++++++++++++++++++++++++++++++++++++*/
304
305	void RemoveBadSegments(SegmentsMem *segments)
306	{
307	int i;
308	int duplicate=0,loop=0;
309	node_t node1=~0,node2=~0;
310
311	for(i=0;i<segments->number;i++)
312	{
313	Segment *segment=&segments->segments->segments[i];
314
315	if(segment->node1==node1 && segment->node2==node2)
316	{
317	duplicate++;
318	segment->node1=~0;
319	}
320	else if(segment->node1==segment->node2)
321	{
322	loop++;
323	segment->node1=~0;
324	}
325
326	node1=segment->node1;
327	node2=segment->node2;
328
329	if(!((i+1)%10000))
330	{
331	printf("\rChecking: Segments=%d Duplicate=%d Loop=%d",i+1,duplicate,loop);
332	fflush(stdout);
333	}
334	}
335
336	printf("\rChecked: Segments=%d Duplicate=%d Loop=%d \n",segments->number,duplicate,loop);
337	fflush(stdout);
338	}
339
340
341	/*++++++++++++++++++++++++++++++++++++++
342	Assign the lengths and durations to all of the segments.
343
344	SegmentsMem* segments The set of segments to process.
345
346	Nodes *nodes The list of nodes to use.
347
348	Ways *ways The list of ways to use.
349	++++++++++++++++++++++++++++++++++++++*/
350
351	void FixupSegmentLengths(SegmentsMem* segments,Nodes nodes,Ways ways)
352	{
353	int i;
354
355	assert(segments->sorted); /* Must be sorted */
356
357	for(i=0;i<segments->number;i++)
358	{
359	Node *node1=FindNode(nodes,segments->segments->segments[i].node1);
360	Node *node2=FindNode(nodes,segments->segments->segments[i].node2);
361
362	if(segments->segments->segments[i].distance!=INVALID_DISTANCE)
363	segments->segments->segments[i].distance=Distance(node1,node2);
364
365	if(!((i+1)%10000))
366	{
367	printf("\rMeasuring Segments: Segments=%d",i+1);
368	fflush(stdout);
369	}
370	}
371
372	printf("\rMeasured Segments: Segments=%d \n",segments->number);
373	fflush(stdout);
374	}
375
376
377	/*++++++++++++++++++++++++++++++++++++++
378	Calculate the distance between two nodes.
379
380	distance_t Distance Returns the distance between the nodes.
381
382	Node *node1 The starting node.
383
384	Node *node2 The end node.
385	++++++++++++++++++++++++++++++++++++++*/
386
387	distance_t Distance(Node node1,Node node2)
388	{
389	double radiant = M_PI / 180;
390
391	double dlon = radiant * (node1->longitude - node2->longitude);
392	double dlat = radiant * (node1->latitude - node2->latitude);
393
394	double a1,a2,a,sa,c,d;
395
396	if(dlon==0 && dlat==0)
397	return 0;
398
399	a1 = sin (dlat / 2);
400	a2 = sin (dlon / 2);
401	a = (a1 * a1) + cos (node1->latitude * radiant) * cos (node2->latitude * radiant) * a2 * a2;
402	sa = sqrt (a);
403	if (sa <= 1.0)
404	{c = 2 * asin (sa);}
405	else
406	{c = 2 * asin (1.0);}
407	d = 6378.137 * c;
408
409	return km_to_distance(d);
410	}
411
412
413	/*++++++++++++++++++++++++++++++++++++++
414	Calculate the duration of segment.
415
416	duration_t Duration Returns the duration of travel between the nodes.
417
418	Segment *segment The segment to traverse.
419
420	Way *way The way that the segment belongs to.
421
422	AllowType transport The type of transport being used.
423	++++++++++++++++++++++++++++++++++++++*/
424
425	duration_t Duration(Segment segment,Way way,AllowType transport)
426	{
427	speed_t speed=WaySpeed(way);
428	distance_t distance=segment->distance;
429
430	if(transport==Allow_Foot)
431	speed=5;
432	else if(transport==Allow_Horse)
433	speed=8;
434	else if(transport==Allow_Bicycle)
435	speed=20;
436
437	return hours_to_duration(distance_to_km(distance)/speed);
438	}