trunk/src/segments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/segments.c,v 1.16 2009-01-23 16:09:08 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 INVALID_DISTANCE 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);
}


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

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

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

 if(transport==Transport_Foot)
    speed=5;
 else if(transport==Transport_Horse)
    speed=8;
 else if(transport==Transport_Bicycle)
    speed=20;

 return hours_to_duration(distance_to_km(distance)/speed);
}
1	/***************************************
2	$Header: /home/amb/CVS/routino/src/segments.c,v 1.16 2009-01-23 16:09:08 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	int bin=node%NBINS_SEGMENTS;
102	int start=segments->offset[bin];
103	int end=segments->offset[bin+1]-1; /* &offset[NBINS+1] == &number */
104	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	if(end<start) /* There are no nodes */
119	return(NULL);
120	else if(node<segments->segments[start].node1) /* Check key is not before start */
121	return(NULL);
122	else if(node>segments->segments[end].node1) /* Check key is not after end */
123	return(NULL);
124	else
125	{
126	do
127	{
128	mid=(start+end)/2; /* Choose mid point */
129
130	if(segments->segments[mid].node1<node) /* Mid point is too low */
131	start=mid;
132	else if(segments->segments[mid].node1>node) /* Mid point is too high */
133	end=mid;
134	else /* Mid point is correct */
135	{found=mid; goto found;}
136	}
137	while((end-start)>1);
138
139	if(segments->segments[start].node1==node) /* Start is correct */
140	{found=start; goto found;}
141
142	if(segments->segments[end].node1==node) /* End is correct */
143	{found=end; goto found;}
144	}
145
146	return(NULL);
147
148	found:
149
150	while(found>0 && segments->segments[found-1].node1==node)
151	found--;
152
153	return(&segments->segments[found]);
154	}
155
156
157	/*++++++++++++++++++++++++++++++++++++++
158	Find the next segment with a particular starting node.
159
160	Segment *FindNextSegment Returns a pointer to the next segment with the same id.
161
162	Segments* segments The set of segments to process.
163
164	Segment *segment The current segment.
165	++++++++++++++++++++++++++++++++++++++*/
166
167	Segment FindNextSegment(Segments segments,Segment *segment)
168	{
169	Segment *next=segment+1;
170
171	if((next-segments->segments)==segments->number)
172	return(NULL);
173
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	Segment *AppendSegment Returns the appended segment.
185
186	SegmentsMem* segments The set of segments to process.
187
188	node_t node1 The first node in the segment.
189
190	node_t node2 The second node in the segment.
191
192	way_t way The way that the pair of segments are connected by.
193	++++++++++++++++++++++++++++++++++++++*/
194
195	Segment AppendSegment(SegmentsMem segments,node_t node1,node_t node2,way_t way)
196	{
197	/* Check that the array has enough space. */
198
199	if(segments->number==segments->alloced)
200	{
201	segments->alloced+=INCREMENT_SEGMENTS;
202
203	segments->segments=(Segments)realloc((void)segments->segments,sizeof(Segments)+segments->alloced*sizeof(Segment));
204	}
205
206	/* Insert the segment */
207
208	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
213	segments->number++;
214
215	segments->sorted=0;
216
217	return(&segments->segments->segments[segments->number-1]);
218	}
219
220
221	/*++++++++++++++++++++++++++++++++++++++
222	Sort the segment list.
223
224	SegmentsMem* segments The set of segments to process.
225	++++++++++++++++++++++++++++++++++++++*/
226
227	void SortSegmentList(SegmentsMem* segments)
228	{
229	int i,bin=0;
230
231	qsort(segments->segments->segments,segments->number,sizeof(Segment),(int ()(const void,const void*))sort_by_id);
232
233	while(segments->segments->segments[segments->number-1].node1==~0)
234	segments->number--;
235
236	segments->sorted=1;
237
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	for(;bin<NBINS_SEGMENTS;bin++)
247	segments->segments->offset[bin]=segments->number;
248	}
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	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	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	}
286
287
288	/*++++++++++++++++++++++++++++++++++++++
289	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	Assign the lengths and durations to all of the segments.
332
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	++++++++++++++++++++++++++++++++++++++*/
339
340	void FixupSegmentLengths(SegmentsMem* segments,Nodes nodes,Ways ways)
341	{
342	int i;
343
344	assert(segments->sorted); /* Must be sorted */
345
346	for(i=0;i<segments->number;i++)
347	{
348	Node *node1=FindNode(nodes,segments->segments->segments[i].node1);
349	Node *node2=FindNode(nodes,segments->segments->segments[i].node2);
350
351	/* Set the distance but preserve the INVALID_DISTANCE flag */
352
353	segments->segments->segments[i].distance\|=Distance(node1,node2);
354
355	if(!((i+1)%10000))
356	{
357	printf("\rMeasuring Segments: Segments=%d",i+1);
358	fflush(stdout);
359	}
360	}
361
362	printf("\rMeasured Segments: Segments=%d \n",segments->number);
363	fflush(stdout);
364	}
365
366
367	/*++++++++++++++++++++++++++++++++++++++
368	Calculate the distance between two nodes.
369
370	distance_t Distance Returns the distance between the nodes.
371
372	Node *node1 The starting node.
373
374	Node *node2 The end node.
375	++++++++++++++++++++++++++++++++++++++*/
376
377	distance_t Distance(Node node1,Node node2)
378	{
379	double radiant = M_PI / 180;
380
381	double dlon = radiant * (node1->longitude - node2->longitude);
382	double dlat = radiant * (node1->latitude - node2->latitude);
383
384	double a1,a2,a,sa,c,d;
385
386	if(dlon==0 && dlat==0)
387	return 0;
388
389	a1 = sin (dlat / 2);
390	a2 = sin (dlon / 2);
391	a = (a1 * a1) + cos (node1->latitude * radiant) * cos (node2->latitude * radiant) * a2 * a2;
392	sa = sqrt (a);
393	if (sa <= 1.0)
394	{c = 2 * asin (sa);}
395	else
396	{c = 2 * asin (1.0);}
397	d = 6378.137 * c;
398
399	return km_to_distance(d);
400	}
401
402
403	/*++++++++++++++++++++++++++++++++++++++
404	Calculate the duration of segment.
405
406	duration_t Duration Returns the duration of travel between the nodes.
407
408	Segment *segment The segment to traverse.
409
410	Way *way The way that the segment belongs to.
411
412	Transport transport The type of transport being used.
413	++++++++++++++++++++++++++++++++++++++*/
414
415	duration_t Duration(Segment segment,Way way,Transport transport)
416	{
417	speed_t speed=WaySpeed(way);
418	distance_t distance=segment->distance;
419
420	if(transport==Transport_Foot)
421	speed=5;
422	else if(transport==Transport_Horse)
423	speed=8;
424	else if(transport==Transport_Bicycle)
425	speed=20;
426
427	return hours_to_duration(distance_to_km(distance)/speed);
428	}