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

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