Routino SVN Repository Browser

Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino

ViewVC logotype

Annotation of /trunk/src/segments.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 84 - (hide annotations) (download) (as text)
Sun Jan 25 12:09:15 2009 UTC (16 years, 1 month ago) by amb
File MIME type: text/x-csrc
File size: 11215 byte(s)
Change the segment->way so that it contains the index of the way, not the id.

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->alloced*sizeof(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->number*sizeof(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     }

Properties

Name Value
cvs:description Segment data type.