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 100 - (show annotations) (download) (as text)
Wed Feb 4 18:26:29 2009 UTC (16 years, 1 month ago) by amb
File MIME type: text/x-csrc
File size: 15197 byte(s) 
Make sure that nodes, segments and ways could be loaded.
1 /***************************************
2 $Header: /home/amb/CVS/routino/src/segments.c,v 1.29 2009-02-04 18:26:29 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 /* Constants */
25
26 /*+ The array size increment for segments - expect ~8,000,000 segments. +*/
27 #define INCREMENT_SEGMENTS 1024*1024
28
29
30 /* Functions */
31
32 static int sort_by_id(SegmentX *a,SegmentX *b);
33
34
35 /*++++++++++++++++++++++++++++++++++++++
36 Load in a segment list from a file.
37
38 Segments* SaveSegmentList Returns the segment list that has just been loaded.
39
40 const char *filename The name of the file to load.
41 ++++++++++++++++++++++++++++++++++++++*/
42
43 Segments *LoadSegmentList(const char *filename)
44 {
45 void *data;
46 Segments *segments;
47
48 segments=(Segments*)malloc(sizeof(Segments));
49
50 data=MapFile(filename);
51
52 if(!data)
53 return(NULL);
54
55 /* Copy the Segments structure from the loaded data */
56
57 *segments=*((Segments*)data);
58
59 /* Adjust the pointers in the Segments structure. */
60
61 segments->data =data;
62 segments->segments=(Segment*)(data+(off_t)segments->segments);
63
64 return(segments);
65 }
66
67
68 /*++++++++++++++++++++++++++++++++++++++
69 Allocate a new segment list.
70
71 SegmentsX *NewSegmentList Returns the segment list.
72 ++++++++++++++++++++++++++++++++++++++*/
73
74 SegmentsX *NewSegmentList(void)
75 {
76 SegmentsX *segmentsx;
77
78 segmentsx=(SegmentsX*)malloc(sizeof(SegmentsX));
79
80 segmentsx->sorted=0;
81 segmentsx->alloced=INCREMENT_SEGMENTS;
82 segmentsx->number=0;
83
84 segmentsx->xdata=(SegmentX*)malloc(segmentsx->alloced*sizeof(SegmentX));
85
86 return(segmentsx);
87 }
88
89
90 /*++++++++++++++++++++++++++++++++++++++
91 Free a segment list.
92
93 SegmentsX *segmentsx The list to be freed.
94 ++++++++++++++++++++++++++++++++++++++*/
95
96 void FreeSegmentList(SegmentsX *segmentsx)
97 {
98 free(segmentsx->xdata);
99 free(segmentsx);
100 }
101
102
103 /*++++++++++++++++++++++++++++++++++++++
104 Save the segment list to a file.
105
106 SegmentsX* segmentsx The set of segments to save.
107
108 const char *filename The name of the file to save.
109 ++++++++++++++++++++++++++++++++++++++*/
110
111 void SaveSegmentList(SegmentsX* segmentsx,const char *filename)
112 {
113 int i;
114 int fd;
115 Segments *segments=calloc(1,sizeof(Segments));
116
117 assert(segmentsx->sorted); /* Must be sorted */
118
119 /* Fill in a Segments structure with the offset of the real data in the file after
120 the Segment structure itself. */
121
122 segments->number=segmentsx->number;
123 segments->data=NULL;
124 segments->segments=(void*)sizeof(Segments);
125
126 /* Write out the Segments structure and then the real data. */
127
128 fd=OpenFile(filename);
129
130 WriteFile(fd,segments,sizeof(Segments));
131
132 for(i=0;i<segmentsx->number;i++)
133 WriteFile(fd,&segmentsx->xdata[i].segment,sizeof(Segment));
134
135 CloseFile(fd);
136
137 /* Free the fake Segments */
138
139 free(segments);
140 }
141
142
143 /*++++++++++++++++++++++++++++++++++++++
144 Find the first segment with a particular starting node.
145
146 SegmentX *FindFirstSegmentX Returns the first extended segment with the specified id.
147
148 SegmentsX* segmentsx The set of segments to process.
149
150 node_t node The node to look for.
151 ++++++++++++++++++++++++++++++++++++++*/
152
153 SegmentX *FindFirstSegmentX(SegmentsX* segmentsx,node_t node)
154 {
155 int start=0;
156 int end=segmentsx->number-1;
157 int mid;
158 int found;
159
160 /* Binary search - search key exact match only is required.
161 *
162 * # <- start | Check mid and move start or end if it doesn't match
163 * # |
164 * # | Since an exact match is wanted we can set end=mid-1
165 * # <- mid | or start=mid+1 because we know that mid doesn't match.
166 * # |
167 * # | Eventually either end=start or end=start+1 and one of
168 * # <- end | start or end is the wanted one.
169 */
170
171 if(end<start) /* There are no nodes */
172 return(NULL);
173 else if(node<segmentsx->xdata[start].node1) /* Check key is not before start */
174 return(NULL);
175 else if(node>segmentsx->xdata[end].node1) /* Check key is not after end */
176 return(NULL);
177 else
178 {
179 do
180 {
181 mid=(start+end)/2; /* Choose mid point */
182
183 if(segmentsx->xdata[mid].node1<node) /* Mid point is too low */
184 start=mid;
185 else if(segmentsx->xdata[mid].node1>node) /* Mid point is too high */
186 end=mid;
187 else /* Mid point is correct */
188 {found=mid; goto found;}
189 }
190 while((end-start)>1);
191
192 if(segmentsx->xdata[start].node1==node) /* Start is correct */
193 {found=start; goto found;}
194
195 if(segmentsx->xdata[end].node1==node) /* End is correct */
196 {found=end; goto found;}
197 }
198
199 return(NULL);
200
201 found:
202
203 while(found>0 && segmentsx->xdata[found-1].node1==node)
204 found--;
205
206 return(&segmentsx->xdata[found]);
207 }
208
209
210 /*++++++++++++++++++++++++++++++++++++++
211 Find the next segment with a particular starting node.
212
213 SegmentX *FindNextSegmentX Returns a pointer to the next segment with the same id.
214
215 SegmentsX* segmentss The set of segments to process.
216
217 SegmentX *segmentx The current segment.
218 ++++++++++++++++++++++++++++++++++++++*/
219
220 SegmentX *FindNextSegmentX(SegmentsX* segmentsx,SegmentX *segmentx)
221 {
222 SegmentX *next=segmentx+1;
223
224 if(IndexSegmentX(segmentsx,next)==segmentsx->number)
225 return(NULL);
226
227 if(next->node1==segmentx->node1)
228 return(next);
229
230 return(NULL);
231 }
232
233
234 /*++++++++++++++++++++++++++++++++++++++
235 Find the next segment with a particular starting node.
236
237 Segment *NextSegment Returns a pointer to the next segment with the same id.
238
239 Segments* segments The set of segments to process.
240
241 Segment *segment The current segment.
242 ++++++++++++++++++++++++++++++++++++++*/
243
244 Segment *NextSegment(Segments* segments,Segment *segment)
245 {
246 Segment *next=segment+1;
247
248 if(IndexSegment(segments,next)==segments->number)
249 return(NULL);
250
251 if(NODE(next->node1)==NODE(segment->node1))
252 return(next);
253
254 return(NULL);
255 }
256
257
258 /*++++++++++++++++++++++++++++++++++++++
259 Append a segment to a segment list.
260
261 Segment *AppendSegmentX Returns the appended segment.
262
263 SegmentsX* segmentsx The set of segments to process.
264
265 node_t node1 The first node in the segment.
266
267 node_t node2 The second node in the segment.
268 ++++++++++++++++++++++++++++++++++++++*/
269
270 Segment *AppendSegment(SegmentsX* segmentsx,node_t node1,node_t node2)
271 {
272 /* Check that the array has enough space. */
273
274 if(segmentsx->number==segmentsx->alloced)
275 {
276 segmentsx->alloced+=INCREMENT_SEGMENTS;
277
278 segmentsx->xdata=(SegmentX*)realloc((void*)segmentsx->xdata,segmentsx->alloced*sizeof(SegmentX));
279 }
280
281 /* Insert the segment */
282
283 segmentsx->xdata[segmentsx->number].node1=node1;
284 segmentsx->xdata[segmentsx->number].node2=node2;
285
286 segmentsx->xdata[segmentsx->number].segment.distance=0;
287
288 segmentsx->number++;
289
290 segmentsx->sorted=0;
291
292 return(&segmentsx->xdata[segmentsx->number-1].segment);
293 }
294
295
296 /*++++++++++++++++++++++++++++++++++++++
297 Sort the segment list.
298
299 SegmentsX* segmentsx The set of segments to process.
300 ++++++++++++++++++++++++++++++++++++++*/
301
302 void SortSegmentList(SegmentsX* segmentsx)
303 {
304 qsort(segmentsx->xdata,segmentsx->number,sizeof(SegmentX),(int (*)(const void*,const void*))sort_by_id);
305
306 while(segmentsx->xdata[segmentsx->number-1].node1==~0)
307 segmentsx->number--;
308
309 segmentsx->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 SegmentX *a The first Segment.
319
320 SegmentX *b The second Segment.
321 ++++++++++++++++++++++++++++++++++++++*/
322
323 static int sort_by_id(SegmentX *a,SegmentX *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 SegmentsX *segmentsx The segments to modify.
346 ++++++++++++++++++++++++++++++++++++++*/
347
348 void RemoveBadSegments(SegmentsX *segmentsx)
349 {
350 int i;
351 int duplicate=0,loop=0;
352 node_t node1=~0,node2=~0;
353
354 for(i=0;i<segmentsx->number;i++)
355 {
356 if(segmentsx->xdata[i].node1==node1 && segmentsx->xdata[i].node2==node2)
357 {
358 duplicate++;
359 segmentsx->xdata[i].node1=~0;
360 }
361 else if(segmentsx->xdata[i].node1==segmentsx->xdata[i].node2)
362 {
363 loop++;
364 segmentsx->xdata[i].node1=~0;
365 }
366
367 node1=segmentsx->xdata[i].node1;
368 node2=segmentsx->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",segmentsx->number,duplicate,loop);
378 fflush(stdout);
379 }
380
381
382 /*++++++++++++++++++++++++++++++++++++++
383 Measure the segments.
384
385 SegmentsX* segmentsx The set of segments to process.
386
387 NodesX *nodesx The list of nodes to use.
388 ++++++++++++++++++++++++++++++++++++++*/
389
390 void MeasureSegments(SegmentsX* segmentsx,NodesX *nodesx)
391 {
392 int i;
393
394 assert(segmentsx->sorted); /* Must be sorted */
395
396 for(i=0;i<segmentsx->number;i++)
397 {
398 NodeX *node1=FindNodeX(nodesx,segmentsx->xdata[i].node1);
399 NodeX *node2=FindNodeX(nodesx,segmentsx->xdata[i].node2);
400
401 /* Set the distance but preserve the ONEWAY_OPPOSITE flag */
402
403 segmentsx->xdata[i].segment.distance|=DistanceX(node1,node2);
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",segmentsx->number);
413 fflush(stdout);
414 }
415
416
417 /*++++++++++++++++++++++++++++++++++++++
418 Fix the segment indexes to the nodes.
419
420 SegmentsX* segmentsx The set of segments to process.
421
422 NodesX *nodesx The list of nodes to use.
423
424 SegmentsX* supersegmentsx The set of super-segments to append.
425 ++++++++++++++++++++++++++++++++++++++*/
426
427 void FixupSegments(SegmentsX* segmentsx,NodesX *nodesx,SegmentsX* supersegmentsx)
428 {
429 int i,j,n;
430
431 assert(segmentsx->sorted); /* Must be sorted */
432 assert(supersegmentsx->sorted); /* Must be sorted */
433
434 for(i=0;i<segmentsx->number;i++)
435 {
436 NodeX *node1=FindNodeX(nodesx,segmentsx->xdata[i].node1);
437 NodeX *node2=FindNodeX(nodesx,segmentsx->xdata[i].node2);
438
439 segmentsx->xdata[i].segment.node1=IndexNodeX(nodesx,node1)|SUPER_FLAG;
440 segmentsx->xdata[i].segment.node2=IndexNodeX(nodesx,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",segmentsx->number);
450 fflush(stdout);
451
452 for(i=0;i<supersegmentsx->number;i++)
453 {
454 NodeX *node1=FindNodeX(nodesx,supersegmentsx->xdata[i].node1);
455 NodeX *node2=FindNodeX(nodesx,supersegmentsx->xdata[i].node2);
456
457 supersegmentsx->xdata[i].segment.node1=IndexNodeX(nodesx,node1);
458 supersegmentsx->xdata[i].segment.node2=IndexNodeX(nodesx,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",supersegmentsx->number);
468 fflush(stdout);
469
470 n=segmentsx->number;
471
472 for(i=0,j=0;i<n;i++)
473 {
474 while(j<supersegmentsx->number)
475 {
476 if(segmentsx->xdata[i].node1==supersegmentsx->xdata[j].node1 &&
477 segmentsx->xdata[i].node2==supersegmentsx->xdata[j].node2)
478 {
479 segmentsx->xdata[i].segment.node2|=SUPER_FLAG;
480 j++;
481 break;
482 }
483 else if(segmentsx->xdata[i].node1==supersegmentsx->xdata[j].node1 &&
484 segmentsx->xdata[i].node2>supersegmentsx->xdata[j].node2)
485 {
486 Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->xdata[j].node1,supersegmentsx->xdata[j].node2);
487
488 *supersegment=supersegmentsx->xdata[j].segment;
489 }
490 else if(segmentsx->xdata[i].node1>supersegmentsx->xdata[j].node1)
491 {
492 Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->xdata[j].node1,supersegmentsx->xdata[j].node2);
493
494 *supersegment=supersegmentsx->xdata[j].segment;
495 }
496 else
497 break;
498
499 j++;
500 }
501
502 if(!((i+1)%10000))
503 {
504 printf("\rMerging Segments: Segments=%d Super-Segment=%d Total=%d",i+1,j+1,segmentsx->number);
505 fflush(stdout);
506 }
507 }
508
509 printf("\rMerged Segments: Segments=%d Super-Segment=%d Total=%d \n",n,supersegmentsx->number,segmentsx->number);
510 fflush(stdout);
511 }
512
513
514 /*++++++++++++++++++++++++++++++++++++++
515 Calculate the distance between two locations.
516
517 float Distance Returns the distance between the locations.
518
519 float lat1 The latitude of the first location.
520
521 float lon1 The longitude of the first location.
522
523 float lat2 The latitude of the second location.
524
525 float lon2 The longitude of the second location.
526 ++++++++++++++++++++++++++++++++++++++*/
527
528 float Distance(float lat1,float lon1,float lat2,float lon2)
529 {
530 double radiant = M_PI / 180;
531
532 double dlon = radiant * (lon1 - lon2);
533 double dlat = radiant * (lat1 - lat2);
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 (lat1 * radiant) * cos (lat2 * 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 d;
551 }
552
553
554 /*++++++++++++++++++++++++++++++++++++++
555 Calculate the distance between two nodes.
556
557 distance_t DistanceX Returns the distance between the extended nodes.
558
559 NodeX *nodex1 The starting node.
560
561 NodeX *nodex2 The end node.
562 ++++++++++++++++++++++++++++++++++++++*/
563
564 distance_t DistanceX(NodeX *nodex1,NodeX *nodex2)
565 {
566 double radiant = M_PI / 180;
567
568 double dlon = radiant * (nodex1->longitude - nodex2->longitude);
569 double dlat = radiant * (nodex1->latitude - nodex2->latitude);
570
571 double a1,a2,a,sa,c,d;
572
573 if(dlon==0 && dlat==0)
574 return 0;
575
576 a1 = sin (dlat / 2);
577 a2 = sin (dlon / 2);
578 a = (a1 * a1) + cos (nodex1->latitude * radiant) * cos (nodex2->latitude * radiant) * a2 * a2;
579 sa = sqrt (a);
580 if (sa <= 1.0)
581 {c = 2 * asin (sa);}
582 else
583 {c = 2 * asin (1.0);}
584 d = 6378.137 * c;
585
586 return km_to_distance(d);
587 }
588
589
590 /*++++++++++++++++++++++++++++++++++++++
591 Calculate the duration of segment.
592
593 duration_t Duration Returns the duration of travel between the nodes.
594
595 Segment *segment The segment to traverse.
596
597 Way *way The way that the segment belongs to.
598
599 Profile *profile The profile of the transport being used.
600 ++++++++++++++++++++++++++++++++++++++*/
601
602 duration_t Duration(Segment *segment,Way *way,Profile *profile)
603 {
604 speed_t speed=profile->speed[HIGHWAY(way->type)];
605 distance_t distance=DISTANCE(segment->distance);
606
607 return distance_speed_to_duration(distance,speed);
608 }

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.2 (destination-access branch) Version 3.4.2 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