Routino SVN Repository Browser

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

/[routino]/trunk/src/segments.c
ViewVC logotype

Contents of /trunk/src/segments.c

Parent Directory Parent Directory | Revision Log Revision Log

Revision 96 - (show annotations) (download) (as text)
Sat Jan 31 15:32:42 2009 UTC (16 years, 1 month ago) by amb
File MIME type: text/x-csrc
File size: 15272 byte(s) 
Intermediate version during code cleanup.
1 /***************************************
2 $Header: /home/amb/CVS/routino/src/segments.c,v 1.25 2009-01-31 15:32:42 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 <unistd.h>
17 #include <math.h>
18 #include <stdlib.h>
19
20 #include "nodes.h"
21 #include "segments.h"
22 #include "functions.h"
23
24
25 /* Constants */
26
27 /*+ The array size increment for segments - expect ~8,000,000 segments. +*/
28 #define INCREMENT_SEGMENTS 1024*1024
29
30
31 /* Functions */
32
33 static int sort_by_id(SegmentEx *a,SegmentEx *b);
34
35
36 /*++++++++++++++++++++++++++++++++++++++
37 Allocate a new segment list.
38
39 SegmentsMem *NewSegmentList Returns the segment list.
40 ++++++++++++++++++++++++++++++++++++++*/
41
42 SegmentsMem *NewSegmentList(void)
43 {
44 SegmentsMem *segmentsmem;
45
46 segmentsmem=(SegmentsMem*)malloc(sizeof(SegmentsMem));
47
48 segmentsmem->sorted=0;
49 segmentsmem->alloced=INCREMENT_SEGMENTS;
50 segmentsmem->number=0;
51
52 segmentsmem->xdata=(SegmentEx*)malloc(segmentsmem->alloced*sizeof(SegmentEx));
53
54 return(segmentsmem);
55 }
56
57
58 /*++++++++++++++++++++++++++++++++++++++
59 Free a segment list.
60
61 SegmentsMem *segmentsmem The list to be freed.
62 ++++++++++++++++++++++++++++++++++++++*/
63
64 void FreeSegmentList(SegmentsMem *segmentsmem)
65 {
66 free(segmentsmem->xdata);
67 free(segmentsmem);
68 }
69
70
71 /*++++++++++++++++++++++++++++++++++++++
72 Load in a segment list from a file.
73
74 Segments* SaveSegmentList Returns the segment list that has just been loaded.
75
76 const char *filename The name of the file to load.
77 ++++++++++++++++++++++++++++++++++++++*/
78
79 Segments *LoadSegmentList(const char *filename)
80 {
81 void *data;
82 Segments *segments;
83
84 segments=(Segments*)malloc(sizeof(Segments));
85
86 data=MapFile(filename);
87
88 /* Copy the Segments structure from the loaded data */
89
90 *segments=*((Segments*)data);
91
92 /* Adjust the pointers in the Segments structure. */
93
94 segments->data =data;
95 segments->segments=(Segment*)(data+(off_t)segments->segments);
96
97 return(segments);
98 }
99
100
101 /*++++++++++++++++++++++++++++++++++++++
102 Save the segment list to a file.
103
104 SegmentsMem* segmentsmem The set of segments to save.
105
106 const char *filename The name of the file to save.
107 ++++++++++++++++++++++++++++++++++++++*/
108
109 void SaveSegmentList(SegmentsMem* segmentsmem,const char *filename)
110 {
111 int i;
112 int fd;
113 Segments *segments=calloc(1,sizeof(Segments));
114
115 assert(segmentsmem->sorted); /* Must be sorted */
116
117 /* Fill in a Segments structure with the offset of the real data in the file after
118 the Segment structure itself. */
119
120 segments->number=segmentsmem->number;
121 segments->data=NULL;
122 segments->segments=(void*)sizeof(Segments);
123
124 /* Write out the Segments structure and then the real data. */
125
126 fd=OpenFile(filename);
127
128 write(fd,segments,sizeof(Segments));
129
130 for(i=0;i<segmentsmem->number;i++)
131 write(fd,&segmentsmem->xdata[i].segment,sizeof(Segment));
132
133 close(fd);
134
135 /* Free the fake Segments */
136
137 free(segments);
138 }
139
140
141 /*++++++++++++++++++++++++++++++++++++++
142 Find the first segment with a particular starting node.
143
144 SegmentEx *FindFirstSegment Returns the first extended segment with the specified id.
145
146 SegmentsMem* segmentsmem The set of segments to process.
147
148 node_t node The node to look for.
149 ++++++++++++++++++++++++++++++++++++++*/
150
151 SegmentEx *FindFirstSegment(SegmentsMem* segmentsmem,node_t node)
152 {
153 int start=0;
154 int end=segmentsmem->number-1;
155 int mid;
156 int found;
157
158 /* Binary search - search key exact match only is required.
159 *
160 * # <- start | Check mid and move start or end if it doesn't match
161 * # |
162 * # | Since an exact match is wanted we can set end=mid-1
163 * # <- mid | or start=mid+1 because we know that mid doesn't match.
164 * # |
165 * # | Eventually either end=start or end=start+1 and one of
166 * # <- end | start or end is the wanted one.
167 */
168
169 if(end<start) /* There are no nodes */
170 return(NULL);
171 else if(node<segmentsmem->xdata[start].node1) /* Check key is not before start */
172 return(NULL);
173 else if(node>segmentsmem->xdata[end].node1) /* Check key is not after end */
174 return(NULL);
175 else
176 {
177 do
178 {
179 mid=(start+end)/2; /* Choose mid point */
180
181 if(segmentsmem->xdata[mid].node1<node) /* Mid point is too low */
182 start=mid;
183 else if(segmentsmem->xdata[mid].node1>node) /* Mid point is too high */
184 end=mid;
185 else /* Mid point is correct */
186 {found=mid; goto found;}
187 }
188 while((end-start)>1);
189
190 if(segmentsmem->xdata[start].node1==node) /* Start is correct */
191 {found=start; goto found;}
192
193 if(segmentsmem->xdata[end].node1==node) /* End is correct */
194 {found=end; goto found;}
195 }
196
197 return(NULL);
198
199 found:
200
201 while(found>0 && segmentsmem->xdata[found-1].node1==node)
202 found--;
203
204 return(&segmentsmem->xdata[found]);
205 }
206
207
208 /*++++++++++++++++++++++++++++++++++++++
209 Find the next segment with a particular starting node.
210
211 SegmentEx *NextSegment Returns a pointer to the next segment with the same id.
212
213 SegmentsMem* segments The set of segments to process.
214
215 SegmentEx *segmentex The current segment.
216 ++++++++++++++++++++++++++++++++++++++*/
217
218 SegmentEx *FindNextSegment(SegmentsMem* segmentsmem,SegmentEx *segmentex)
219 {
220 SegmentEx *next=segmentex+1;
221
222 if(IndexSegmentEx(segmentsmem,next)==segmentsmem->number)
223 return(NULL);
224
225 if(next->node1==segmentex->node1)
226 return(next);
227
228 return(NULL);
229 }
230
231
232 /*++++++++++++++++++++++++++++++++++++++
233 Find the next segment with a particular starting node.
234
235 Segment *NextSegment Returns a pointer to the next segment with the same id.
236
237 Segments* segments The set of segments to process.
238
239 Segment *segment The current segment.
240 ++++++++++++++++++++++++++++++++++++++*/
241
242 Segment *NextSegment(Segments* segments,Segment *segment)
243 {
244 Segment *next=segment+1;
245
246 if(IndexSegment(segments,next)==segments->number)
247 return(NULL);
248
249 if(NODE(next->node1)==NODE(segment->node1))
250 return(next);
251
252 return(NULL);
253 }
254
255
256 /*++++++++++++++++++++++++++++++++++++++
257 Append a segment to a newly created segment list (unsorted).
258
259 SegmentEx *AppendSegment Returns the appended segment.
260
261 SegmentsMem* segmentsmem The set of segments to process.
262
263 node_t node1 The first node in the segment.
264
265 node_t node2 The second node in the segment.
266
267 index_t way The index of the way that the pair of segments are connected by.
268 ++++++++++++++++++++++++++++++++++++++*/
269
270 SegmentEx *AppendSegment(SegmentsMem* segmentsmem,node_t node1,node_t node2,index_t way)
271 {
272 /* Check that the array has enough space. */
273
274 if(segmentsmem->number==segmentsmem->alloced)
275 {
276 segmentsmem->alloced+=INCREMENT_SEGMENTS;
277
278 segmentsmem->xdata=(SegmentEx*)realloc((void*)segmentsmem->xdata,segmentsmem->alloced*sizeof(SegmentEx));
279 }
280
281 /* Insert the segment */
282
283 segmentsmem->xdata[segmentsmem->number].node1=node1;
284 segmentsmem->xdata[segmentsmem->number].node2=node2;
285 segmentsmem->xdata[segmentsmem->number].segment.way=way;
286 segmentsmem->xdata[segmentsmem->number].segment.distance=0;
287
288 segmentsmem->number++;
289
290 segmentsmem->sorted=0;
291
292 return(&segmentsmem->xdata[segmentsmem->number-1]);
293 }
294
295
296 /*++++++++++++++++++++++++++++++++++++++
297 Sort the segment list.
298
299 SegmentsMem* segmentsmem The set of segments to process.
300 ++++++++++++++++++++++++++++++++++++++*/
301
302 void SortSegmentList(SegmentsMem* segmentsmem)
303 {
304 qsort(segmentsmem->xdata,segmentsmem->number,sizeof(SegmentEx),(int (*)(const void*,const void*))sort_by_id);
305
306 while(segmentsmem->xdata[segmentsmem->number-1].node1==~0)
307 segmentsmem->number--;
308
309 segmentsmem->sorted=1;
310 }
311
312
313 /*++++++++++++++++++++++++++++++++++++++
314 Sort the segments into id order.
315
316 int sort_by_id Returns the comparison of the node fields.
317
318 SegmentEx *a The first Segment.
319
320 SegmentEx *b The second Segment.
321 ++++++++++++++++++++++++++++++++++++++*/
322
323 static int sort_by_id(SegmentEx *a,SegmentEx *b)
324 {
325 node_t a_id1=a->node1,a_id2=a->node2;
326 node_t b_id1=b->node1,b_id2=b->node2;
327
328 if(a_id1<b_id1)
329 return(-1);
330 else if(a_id1>b_id1)
331 return(1);
332 else /* if(a_id1==b_id1) */
333 {
334 if(a_id2<b_id2)
335 return(-1);
336 else
337 return(1);
338 }
339 }
340
341
342 /*++++++++++++++++++++++++++++++++++++++
343 Remove bad segments (zero length or duplicated).
344
345 SegmentsMem *segmentsmem The segments to modify.
346 ++++++++++++++++++++++++++++++++++++++*/
347
348 void RemoveBadSegments(SegmentsMem *segmentsmem)
349 {
350 int i;
351 int duplicate=0,loop=0;
352 node_t node1=~0,node2=~0;
353
354 for(i=0;i<segmentsmem->number;i++)
355 {
356 if(segmentsmem->xdata[i].node1==node1 && segmentsmem->xdata[i].node2==node2)
357 {
358 duplicate++;
359 segmentsmem->xdata[i].node1=~0;
360 }
361 else if(segmentsmem->xdata[i].node1==segmentsmem->xdata[i].node2)
362 {
363 loop++;
364 segmentsmem->xdata[i].node1=~0;
365 }
366
367 node1=segmentsmem->xdata[i].node1;
368 node2=segmentsmem->xdata[i].node2;
369
370 if(!((i+1)%10000))
371 {
372 printf("\rChecking: Segments=%d Duplicate=%d Loop=%d",i+1,duplicate,loop);
373 fflush(stdout);
374 }
375 }
376
377 printf("\rChecked: Segments=%d Duplicate=%d Loop=%d \n",segmentsmem->number,duplicate,loop);
378 fflush(stdout);
379 }
380
381
382 /*++++++++++++++++++++++++++++++++++++++
383 Measure the segments.
384
385 SegmentsMem* segmentsmem The set of segments to process.
386
387 NodesMem *nodesmem The list of nodes to use.
388 ++++++++++++++++++++++++++++++++++++++*/
389
390 void MeasureSegments(SegmentsMem* segmentsmem,NodesMem *nodesmem)
391 {
392 int i;
393
394 assert(segmentsmem->sorted); /* Must be sorted */
395
396 for(i=0;i<segmentsmem->number;i++)
397 {
398 NodeEx *node1=FindNode(nodesmem,segmentsmem->xdata[i].node1);
399 NodeEx *node2=FindNode(nodesmem,segmentsmem->xdata[i].node2);
400
401 /* Set the distance but preserve the ONEWAY_OPPOSITE flag */
402
403 segmentsmem->xdata[i].segment.distance|=Distance(&node1->node,&node2->node);
404
405 if(!((i+1)%10000))
406 {
407 printf("\rMeasuring Segments: Segments=%d",i+1);
408 fflush(stdout);
409 }
410 }
411
412 printf("\rMeasured Segments: Segments=%d \n",segmentsmem->number);
413 fflush(stdout);
414 }
415
416
417 /*++++++++++++++++++++++++++++++++++++++
418 Fix the segment indexes to the nodes.
419
420 SegmentsMem* segmentsmem The set of segments to process.
421
422 NodesMem *nodesmem The list of nodes to use.
423
424 SegmentsMem* supersegmentsmem The set of super-segments to append.
425 ++++++++++++++++++++++++++++++++++++++*/
426
427 void FixupSegments(SegmentsMem* segmentsmem,NodesMem *nodesmem,SegmentsMem* supersegmentsmem)
428 {
429 int i,j,n;
430
431 assert(segmentsmem->sorted); /* Must be sorted */
432 assert(supersegmentsmem->sorted); /* Must be sorted */
433
434 for(i=0;i<segmentsmem->number;i++)
435 {
436 NodeEx *node1=FindNode(nodesmem,segmentsmem->xdata[i].node1);
437 NodeEx *node2=FindNode(nodesmem,segmentsmem->xdata[i].node2);
438
439 segmentsmem->xdata[i].segment.node1=IndexNodeEx(nodesmem,node1)|SUPER_FLAG;
440 segmentsmem->xdata[i].segment.node2=IndexNodeEx(nodesmem,node2);
441
442 if(!((i+1)%10000))
443 {
444 printf("\rFixing Segments: Segments=%d",i+1);
445 fflush(stdout);
446 }
447 }
448
449 printf("\rFixed Segments: Segments=%d \n",segmentsmem->number);
450 fflush(stdout);
451
452 for(i=0;i<supersegmentsmem->number;i++)
453 {
454 NodeEx *node1=FindNode(nodesmem,supersegmentsmem->xdata[i].node1);
455 NodeEx *node2=FindNode(nodesmem,supersegmentsmem->xdata[i].node2);
456
457 supersegmentsmem->xdata[i].segment.node1=IndexNodeEx(nodesmem,node1);
458 supersegmentsmem->xdata[i].segment.node2=IndexNodeEx(nodesmem,node2)|SUPER_FLAG;
459
460 if(!((i+1)%10000))
461 {
462 printf("\rFixing Super-Segments: Super-Segments=%d",i+1);
463 fflush(stdout);
464 }
465 }
466
467 printf("\rFixed Super-Segments: Super-Segments=%d \n",supersegmentsmem->number);
468 fflush(stdout);
469
470 n=segmentsmem->number;
471
472 for(i=0,j=0;i<n;i++)
473 {
474 while(j<supersegmentsmem->number)
475 {
476 if(segmentsmem->xdata[i].node1==supersegmentsmem->xdata[j].node1 &&
477 segmentsmem->xdata[i].node2==supersegmentsmem->xdata[j].node2)
478 {
479 segmentsmem->xdata[i].segment.node2|=SUPER_FLAG;
480 j++;
481 break;
482 }
483 else if(segmentsmem->xdata[i].node1==supersegmentsmem->xdata[j].node1 &&
484 segmentsmem->xdata[i].node2>supersegmentsmem->xdata[j].node2)
485 {
486 SegmentEx *supersegmentex=AppendSegment(segmentsmem,supersegmentsmem->xdata[j].node1,supersegmentsmem->xdata[j].node2,supersegmentsmem->xdata[j].segment.way);
487
488 supersegmentex->segment.node1=supersegmentsmem->xdata[j].segment.node1;
489 supersegmentex->segment.node2=supersegmentsmem->xdata[j].segment.node2;
490 supersegmentex->segment.distance=supersegmentsmem->xdata[j].segment.distance;
491 }
492 else if(segmentsmem->xdata[i].node1>supersegmentsmem->xdata[j].node1)
493 {
494 SegmentEx *supersegmentex=AppendSegment(segmentsmem,supersegmentsmem->xdata[j].node1,supersegmentsmem->xdata[j].node2,supersegmentsmem->xdata[j].segment.way);
495
496 supersegmentex->segment.node1=supersegmentsmem->xdata[j].segment.node1;
497 supersegmentex->segment.node2=supersegmentsmem->xdata[j].segment.node2;
498 supersegmentex->segment.distance=supersegmentsmem->xdata[j].segment.distance;
499 }
500 else
501 break;
502
503 j++;
504 }
505
506 if(!((i+1)%10000))
507 {
508 printf("\rMerging Segments: Segments=%d Super-Segment=%d Total=%d",i+1,j+1,segmentsmem->number);
509 fflush(stdout);
510 }
511 }
512
513 printf("\rMerged Segments: Segments=%d Super-Segment=%d Total=%d \n",n,supersegmentsmem->number,segmentsmem->number);
514 fflush(stdout);
515 }
516
517
518 /*++++++++++++++++++++++++++++++++++++++
519 Calculate the distance between two nodes.
520
521 distance_t Distance Returns the distance between the nodes.
522
523 Node *node1 The starting node.
524
525 Node *node2 The end node.
526 ++++++++++++++++++++++++++++++++++++++*/
527
528 distance_t Distance(Node *node1,Node *node2)
529 {
530 double radiant = M_PI / 180;
531
532 double dlon = radiant * (node1->longitude - node2->longitude);
533 double dlat = radiant * (node1->latitude - node2->latitude);
534
535 double a1,a2,a,sa,c,d;
536
537 if(dlon==0 && dlat==0)
538 return 0;
539
540 a1 = sin (dlat / 2);
541 a2 = sin (dlon / 2);
542 a = (a1 * a1) + cos (node1->latitude * radiant) * cos (node2->latitude * radiant) * a2 * a2;
543 sa = sqrt (a);
544 if (sa <= 1.0)
545 {c = 2 * asin (sa);}
546 else
547 {c = 2 * asin (1.0);}
548 d = 6378.137 * c;
549
550 return km_to_distance(d);
551 }
552
553
554 /*++++++++++++++++++++++++++++++++++++++
555 Calculate the duration of segment.
556
557 duration_t Duration Returns the duration of travel between the nodes.
558
559 Segment *segment The segment to traverse.
560
561 Way *way The way that the segment belongs to.
562
563 Profile *profile The profile of the transport being used.
564 ++++++++++++++++++++++++++++++++++++++*/
565
566 duration_t Duration(Segment *segment,Way *way,Profile *profile)
567 {
568 speed_t speed=profile->speed[HIGHWAY(way->type)];
569 distance_t distance=DISTANCE(segment->distance);
570
571 return distance_speed_to_duration(distance,speed);
572 }

Properties

Name Value
cvs:description Segment data type.
Index: This Site Routino Software Download Source Code Documentation XML Files Links
Index: View SVN Development Recent changes Development (destination-access branch) Version 3.4.1 (destination-access branch) Version 3.4.1 Version 3.4 (destination-access branch) Version 3.4 Version 3.3.3 (destination-access branch) Version 3.3.3 Version 3.3.2 (destination-access branch) Version 3.3.2 Version 3.3.1 (destination-access branch) Version 3.3.1 Version 3.3 (destination-access branch) Version 3.3 Version 3.2 Version 3.1.1 Version 3.1 Version 3.0 Version 2.7.3 Version 2.7.2 Version 2.7.1 Version 2.7 Version 2.6 Version 2.5.1 Version 2.5 Version 2.4.1 Version 2.4 Version 2.3.2 Version 2.3.1 Version 2.3 Version 2.2 Version 2.1.2 Version 2.1.1 Version 2.1 Version 2.0.3 Version 2.0.2 Version 2.0.1 Version 2.0 Version 1.5.1 Version 1.5 Version 1.4.1 Version 1.4 Version 1.3 Version 1.2 Version 1.1 Version 1.0
Powered by ViewVC 1.3.0-dev ViewVC Help
© Andrew M. Bishop = < amb @ ... >
Root