trunk/src/segments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/segments.c,v 1.6 2009-01-10 11:53:48 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 "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)
{
#ifdef NBINS_SEGMENTS
 int i,bin=0;
#endif

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

 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

 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).

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

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

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

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

 /* Insert the segment */

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

 segments->number++;

 segments->sorted=0;
}


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

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

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

 segments->sorted=1;
}


/*++++++++++++++++++++++++++++++++++++++
  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(a_id2-b_id2);
 else
    return(a_id1-b_id1);
}


/*++++++++++++++++++++++++++++++++++++++
  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);
    Way  *way=FindWay(ways,segments->segments->segments[i].way);

    speed_t    speed=way->speed;
    distance_t distance=Distance(node1,node2);
    duration_t duration=hours_to_duration(distance_to_km(distance)/speed);

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

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

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


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

  distance_t Distance Returns the distance between the nodes.

  Node *node1 The starting node.

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

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

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

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

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

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

 return km_to_distance(d);
}
1	/***************************************
2	$Header: /home/amb/CVS/routino/src/segments.c,v 1.6 2009-01-10 11:53:48 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 "segments.h"
20	#include "functions.h"
21
22
23	/* Functions */
24
25	static int sort_by_id(Segment a,Segment b);
26
27
28	/*++++++++++++++++++++++++++++++++++++++
29	Allocate a new segment list.
30
31	SegmentsMem *NewSegmentList Returns the segment list.
32	++++++++++++++++++++++++++++++++++++++*/
33
34	SegmentsMem *NewSegmentList(void)
35	{
36	SegmentsMem *segments;
37
38	segments=(SegmentsMem*)malloc(sizeof(SegmentsMem));
39
40	segments->alloced=INCREMENT_SEGMENTS;
41	segments->number=0;
42	segments->sorted=0;
43
44	segments->segments=(Segments)malloc(sizeof(Segments)+segments->allocedsizeof(Segment));
45
46	return(segments);
47	}
48
49
50	/*++++++++++++++++++++++++++++++++++++++
51	Load in a segment list from a file.
52
53	Segments* SaveSegmentList Returns the segment list that has just been loaded.
54
55	const char *filename The name of the file to load.
56	++++++++++++++++++++++++++++++++++++++*/
57
58	Segments LoadSegmentList(const char filename)
59	{
60	return((Segments*)MapFile(filename));
61	}
62
63
64	/*++++++++++++++++++++++++++++++++++++++
65	Save the segment list to a file.
66
67	Segments* SaveSegmentList Returns the segment list that has just been saved.
68
69	SegmentsMem* segments The set of segments to save.
70
71	const char *filename The name of the file to save.
72	++++++++++++++++++++++++++++++++++++++*/
73
74	Segments SaveSegmentList(SegmentsMem segments,const char *filename)
75	{
76	#ifdef NBINS_SEGMENTS
77	int i,bin=0;
78	#endif
79
80	assert(segments->sorted); /* Must be sorted */
81
82	segments->segments->number=segments->number;
83
84	#ifdef NBINS_SEGMENTS
85	for(i=0;i<segments->number;i++)
86	for(;bin<=(segments->segments->segments[i].node1%NBINS_SEGMENTS);bin++)
87	segments->segments->offset[bin]=i;
88
89	for(;bin<=NBINS_SEGMENTS;bin++)
90	segments->segments->offset[bin]=segments->number;
91	#endif
92
93	if(WriteFile(filename,(void)segments->segments,sizeof(Segments)-sizeof(segments->segments->segments)+segments->numbersizeof(Segment)))
94	assert(0);
95
96	free(segments->segments);
97	free(segments);
98
99	return(LoadSegmentList(filename));
100	}
101
102
103	/*++++++++++++++++++++++++++++++++++++++
104	Find the first segment with a particular starting node.
105
106	Segment *FindFirstSegment Returns a pointer to the first segment with the specified id.
107
108	Segments* segments The set of segments to process.
109
110	node_t node The node to look for.
111	++++++++++++++++++++++++++++++++++++++*/
112
113	Segment FindFirstSegment(Segments segments,node_t node)
114	{
115	#ifdef NBINS_SEGMENTS
116	int bin=node%NBINS_SEGMENTS;
117	int start=segments->offset[bin];
118	int end=segments->offset[bin+1]-1;
119	#else
120	int start=0;
121	int end=segments->number-1;
122	#endif
123	int mid;
124	int found;
125
126	/* Binary search - search key exact match only is required.
127	*
128	* # <- start \| Check mid and move start or end if it doesn't match
129	* # \|
130	* # \| Since an exact match is wanted we can set end=mid-1
131	* # <- mid \| or start=mid+1 because we know that mid doesn't match.
132	* # \|
133	* # \| Eventually either end=start or end=start+1 and one of
134	* # <- end \| start or end is the wanted one.
135	*/
136
137	if(end<start) /* There are no nodes */
138	return(NULL);
139	else if(node<segments->segments[start].node1) /* Check key is not before start */
140	return(NULL);
141	else if(node>segments->segments[end].node1) /* Check key is not after end */
142	return(NULL);
143	else
144	{
145	do
146	{
147	mid=(start+end)/2; /* Choose mid point */
148
149	if(segments->segments[mid].node1<node) /* Mid point is too low */
150	start=mid;
151	else if(segments->segments[mid].node1>node) /* Mid point is too high */
152	end=mid;
153	else /* Mid point is correct */
154	{found=mid; goto found;}
155	}
156	while((end-start)>1);
157
158	if(segments->segments[start].node1==node) /* Start is correct */
159	{found=start; goto found;}
160
161	if(segments->segments[end].node1==node) /* End is correct */
162	{found=end; goto found;}
163	}
164
165	return(NULL);
166
167	found:
168
169	while(found>0 && segments->segments[found-1].node1==node)
170	found--;
171
172	return(&segments->segments[found]);
173	}
174
175
176	/*++++++++++++++++++++++++++++++++++++++
177	Find the next segment with a particular starting node.
178
179	Segment *FindNextSegment Returns a pointer to the next segment with the same id.
180
181	Segments* segments The set of segments to process.
182
183	Segment *segment The current segment.
184	++++++++++++++++++++++++++++++++++++++*/
185
186	Segment FindNextSegment(Segments segments,Segment *segment)
187	{
188	Segment *next=segment+1;
189
190	if((next-segments->segments)==segments->number)
191	return(NULL);
192
193	if(next->node1==segment->node1)
194	return(next);
195
196	return(NULL);
197	}
198
199
200	/*++++++++++++++++++++++++++++++++++++++
201	Append a segment to a newly created segment list (unsorted).
202
203	SegmentsMem* segments The set of segments to process.
204
205	node_t node1 The first node in the segment.
206
207	node_t node2 The second node in the segment.
208
209	way_t way The way that the pair of segments are connected by.
210	++++++++++++++++++++++++++++++++++++++*/
211
212	void AppendSegment(SegmentsMem* segments,node_t node1,node_t node2,way_t way)
213	{
214	/* Check that the array has enough space. */
215
216	if(segments->number==segments->alloced)
217	{
218	segments->alloced+=INCREMENT_SEGMENTS;
219
220	segments->segments=(Segments)realloc((void)segments->segments,sizeof(Segments)+segments->alloced*sizeof(Segment));
221	}
222
223	/* Insert the segment */
224
225	segments->segments->segments[segments->number].node1=node1;
226	segments->segments->segments[segments->number].node2=node2;
227	segments->segments->segments[segments->number].way=way;
228	segments->segments->segments[segments->number].distance=0;
229	segments->segments->segments[segments->number].duration=0;
230
231	segments->number++;
232
233	segments->sorted=0;
234	}
235
236
237	/*++++++++++++++++++++++++++++++++++++++
238	Sort the segment list.
239
240	SegmentsMem* segments The set of segments to process.
241	++++++++++++++++++++++++++++++++++++++*/
242
243	void SortSegmentList(SegmentsMem* segments)
244	{
245	qsort(segments->segments->segments,segments->number,sizeof(Segment),(int ()(const void,const void*))sort_by_id);
246
247	segments->sorted=1;
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	#ifdef NBINS_SEGMENTS
267	int a_bin=a->node1%NBINS_SEGMENTS;
268	int b_bin=b->node1%NBINS_SEGMENTS;
269
270	if(a_bin!=b_bin)
271	return(a_bin-b_bin);
272	#endif
273
274	if(a_id1==b_id1)
275	return(a_id2-b_id2);
276	else
277	return(a_id1-b_id1);
278	}
279
280
281	/*++++++++++++++++++++++++++++++++++++++
282	Assign the lengths and durations to all of the segments.
283
284	SegmentsMem* segments The set of segments to process.
285
286	Nodes *nodes The list of nodes to use.
287
288	Ways *ways The list of ways to use.
289	++++++++++++++++++++++++++++++++++++++*/
290
291	void FixupSegmentLengths(SegmentsMem* segments,Nodes nodes,Ways ways)
292	{
293	int i;
294
295	assert(segments->sorted); /* Must be sorted */
296
297	for(i=0;i<segments->number;i++)
298	{
299	Node *node1=FindNode(nodes,segments->segments->segments[i].node1);
300	Node *node2=FindNode(nodes,segments->segments->segments[i].node2);
301	Way *way=FindWay(ways,segments->segments->segments[i].way);
302
303	speed_t speed=way->speed;
304	distance_t distance=Distance(node1,node2);
305	duration_t duration=hours_to_duration(distance_to_km(distance)/speed);
306
307	if(distance>(distance_short_t)~0)
308	{
309	fprintf(stderr,"\nSegment too long (%d->%d) = %.1f km\n",node1->id,node2->id,distance_to_km(distance));
310	distance=(distance_short_t)~0;
311	}
312
313	if(duration>(duration_short_t)~0)
314	{
315	fprintf(stderr,"\nSegment too long (%d->%d) = %.1f mins\n",node1->id,node2->id,duration_to_minutes(duration));
316	duration=(duration_short_t)~0;
317	}
318
319	segments->segments->segments[i].distance=distance;
320	segments->segments->segments[i].duration=duration;
321	}
322	}
323
324
325	/*++++++++++++++++++++++++++++++++++++++
326	Calculate the distance between two nodes.
327
328	distance_t Distance Returns the distance between the nodes.
329
330	Node *node1 The starting node.
331
332	Node *node2 The end node.
333	++++++++++++++++++++++++++++++++++++++*/
334
335	distance_t Distance(Node node1,Node node2)
336	{
337	double radiant = M_PI / 180;
338
339	double dlon = radiant * (node1->longitude - node2->longitude);
340	double dlat = radiant * (node1->latitude - node2->latitude);
341
342	double a1,a2,a,sa,c,d;
343
344	if(dlon==0 && dlat==0)
345	return 0;
346
347	a1 = sin (dlat / 2);
348	a2 = sin (dlon / 2);
349	a = (a1 * a1) + cos (node1->latitude * radiant) * cos (node2->latitude * radiant) * a2 * a2;
350	sa = sqrt (a);
351	if (sa <= 1.0)
352	{c = 2 * asin (sa);}
353	else
354	{c = 2 * asin (1.0);}
355	d = 6378.137 * c;
356
357	return km_to_distance(d);
358	}