Routino SVN Repository Browser

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

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

Contents of /trunk/src/segmentsx.c

Parent Directory Parent Directory | Revision Log Revision Log

Revision 227 - (show annotations) (download) (as text)
Sun Jul 12 08:38:12 2009 UTC (15 years, 8 months ago) by amb
File MIME type: text/x-csrc
File size: 17644 byte(s) 
Check all print statements and made them more consistent and/or accurate.
1 /***************************************
2 $Header: /home/amb/CVS/routino/src/segmentsx.c,v 1.26 2009-07-12 08:38:12 amb Exp $
3
4 Extended Segment data type functions.
5
6 Part of the Routino routing software.
7 ******************/ /******************
8 This file Copyright 2008,2009 Andrew M. Bishop
9
10 This program is free software: you can redistribute it and/or modify
11 it under the terms of the GNU Affero General Public License as published by
12 the Free Software Foundation, either version 3 of the License, or
13 (at your option) any later version.
14
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU Affero General Public License for more details.
19
20 You should have received a copy of the GNU Affero General Public License
21 along with this program. If not, see <http://www.gnu.org/licenses/>.
22 ***************************************/
23
24
25 #include <assert.h>
26 #include <math.h>
27 #include <stdlib.h>
28 #include <stdio.h>
29
30 #include "types.h"
31 #include "functions.h"
32 #include "nodesx.h"
33 #include "segmentsx.h"
34 #include "waysx.h"
35
36
37 /* Constants */
38
39 /*+ The array size increment for SegmentsX (UK is ~14.1M raw segments, this is ~53 increments). +*/
40 #define INCREMENT_SEGMENTSX (256*1024)
41
42
43 /* Functions */
44
45 static int sort_by_id_and_distance(SegmentX **a,SegmentX **b);
46
47
48 /*++++++++++++++++++++++++++++++++++++++
49 Allocate a new segment list.
50
51 SegmentsX *NewSegmentList Returns the segment list.
52 ++++++++++++++++++++++++++++++++++++++*/
53
54 SegmentsX *NewSegmentList(void)
55 {
56 SegmentsX *segmentsx;
57
58 segmentsx=(SegmentsX*)calloc(1,sizeof(SegmentsX));
59
60 segmentsx->row=-1;
61
62 return(segmentsx);
63 }
64
65
66 /*++++++++++++++++++++++++++++++++++++++
67 Free a segment list.
68
69 SegmentsX *segmentsx The list to be freed.
70 ++++++++++++++++++++++++++++++++++++++*/
71
72 void FreeSegmentList(SegmentsX *segmentsx)
73 {
74 if(segmentsx->xdata)
75 {
76 int i;
77 for(i=0;i<=segmentsx->row;i++)
78 free(segmentsx->xdata[i]);
79 free(segmentsx->xdata);
80 }
81
82 if(segmentsx->ndata)
83 free(segmentsx->ndata);
84
85 if(segmentsx->sdata)
86 free(segmentsx->sdata);
87
88 free(segmentsx);
89 }
90
91
92 /*++++++++++++++++++++++++++++++++++++++
93 Save the segment list to a file.
94
95 SegmentsX* segmentsx The set of segments to save.
96
97 const char *filename The name of the file to save.
98 ++++++++++++++++++++++++++++++++++++++*/
99
100 void SaveSegmentList(SegmentsX* segmentsx,const char *filename)
101 {
102 index_t i;
103 int fd;
104 Segments *segments=calloc(1,sizeof(Segments));
105
106 assert(segmentsx->sorted); /* Must be sorted */
107 assert(segmentsx->sdata); /* Must have sdata filled in */
108
109 printf("Writing Segments: Segments=0");
110 fflush(stdout);
111
112 /* Fill in a Segments structure with the offset of the real data in the file after
113 the Segment structure itself. */
114
115 segments->number=segmentsx->number;
116 segments->data=NULL;
117 segments->segments=(void*)sizeof(Segments);
118
119 /* Write out the Segments structure and then the real data. */
120
121 fd=OpenFile(filename);
122
123 WriteFile(fd,segments,sizeof(Segments));
124
125 for(i=0;i<segments->number;i++)
126 {
127 WriteFile(fd,&segmentsx->sdata[i],sizeof(Segment));
128
129 if(!((i+1)%10000))
130 {
131 printf("\rWriting Segments: Segments=%d",i+1);
132 fflush(stdout);
133 }
134 }
135
136 printf("\rWrote Segments: Segments=%d \n",segments->number);
137 fflush(stdout);
138
139 CloseFile(fd);
140
141 /* Free the fake Segments */
142
143 free(segments);
144 }
145
146
147 /*++++++++++++++++++++++++++++++++++++++
148 Find the first segment with a particular starting node.
149
150 SegmentX **FindFirstSegmentX Returns a pointer to the first extended segment with the specified id.
151
152 SegmentsX* segmentsx The set of segments to process.
153
154 node_t node The node to look for.
155 ++++++++++++++++++++++++++++++++++++++*/
156
157 SegmentX **FindFirstSegmentX(SegmentsX* segmentsx,node_t node)
158 {
159 int start=0;
160 int end=segmentsx->number-1;
161 int mid;
162 int found;
163
164 assert(segmentsx->sorted); /* Must be sorted */
165 assert(segmentsx->ndata); /* Must have ndata filled in */
166
167 /* Binary search - search key exact match only is required.
168 *
169 * # <- start | Check mid and move start or end if it doesn't match
170 * # |
171 * # | Since an exact match is wanted we can set end=mid-1
172 * # <- mid | or start=mid+1 because we know that mid doesn't match.
173 * # |
174 * # | Eventually either end=start or end=start+1 and one of
175 * # <- end | start or end is the wanted one.
176 */
177
178 if(end<start) /* There are no nodes */
179 return(NULL);
180 else if(node<segmentsx->ndata[start]->node1) /* Check key is not before start */
181 return(NULL);
182 else if(node>segmentsx->ndata[end]->node1) /* Check key is not after end */
183 return(NULL);
184 else
185 {
186 do
187 {
188 mid=(start+end)/2; /* Choose mid point */
189
190 if(segmentsx->ndata[mid]->node1<node) /* Mid point is too low */
191 start=mid;
192 else if(segmentsx->ndata[mid]->node1>node) /* Mid point is too high */
193 end=mid;
194 else /* Mid point is correct */
195 {found=mid; goto found;}
196 }
197 while((end-start)>1);
198
199 if(segmentsx->ndata[start]->node1==node) /* Start is correct */
200 {found=start; goto found;}
201
202 if(segmentsx->ndata[end]->node1==node) /* End is correct */
203 {found=end; goto found;}
204 }
205
206 return(NULL);
207
208 found:
209
210 while(found>0 && segmentsx->ndata[found-1]->node1==node)
211 found--;
212
213 return(&segmentsx->ndata[found]);
214 }
215
216
217 /*++++++++++++++++++++++++++++++++++++++
218 Find the next segment with a particular starting node.
219
220 SegmentX **FindNextSegmentX Returns a pointer to the next segment with the same id.
221
222 SegmentsX* segmentsx The set of segments to process.
223
224 SegmentX **segmentx The current segment.
225 ++++++++++++++++++++++++++++++++++++++*/
226
227 SegmentX **FindNextSegmentX(SegmentsX* segmentsx,SegmentX **segmentx)
228 {
229 SegmentX **next=segmentx+1;
230
231 if((next-segmentsx->ndata)==segmentsx->number)
232 return(NULL);
233
234 if((*next)->node1==(*segmentx)->node1)
235 return(next);
236
237 return(NULL);
238 }
239
240
241 /*++++++++++++++++++++++++++++++++++++++
242 Append a segment to a segment list.
243
244 SegmentsX* segmentsx The set of segments to process.
245
246 way_t way The way that the segment belongs to.
247
248 node_t node1 The first node in the segment.
249
250 node_t node2 The second node in the segment.
251 ++++++++++++++++++++++++++++++++++++++*/
252
253 void AppendSegment(SegmentsX* segmentsx,way_t way,node_t node1,node_t node2,distance_t distance)
254 {
255 /* Check that the array has enough space. */
256
257 if(segmentsx->row==-1 || segmentsx->col==INCREMENT_SEGMENTSX)
258 {
259 segmentsx->row++;
260 segmentsx->col=0;
261
262 if((segmentsx->row%16)==0)
263 segmentsx->xdata=(SegmentX**)realloc((void*)segmentsx->xdata,(segmentsx->row+16)*sizeof(SegmentX*));
264
265 segmentsx->xdata[segmentsx->row]=(SegmentX*)malloc(INCREMENT_SEGMENTSX*sizeof(SegmentX));
266 }
267
268 /* Insert the segment */
269
270 segmentsx->xdata[segmentsx->row][segmentsx->col].way=way;
271 segmentsx->xdata[segmentsx->row][segmentsx->col].node1=node1;
272 segmentsx->xdata[segmentsx->row][segmentsx->col].node2=node2;
273 segmentsx->xdata[segmentsx->row][segmentsx->col].distance=distance;
274
275 segmentsx->col++;
276
277 segmentsx->sorted=0;
278 }
279
280
281 /*++++++++++++++++++++++++++++++++++++++
282 Sort the segment list.
283
284 SegmentsX* segmentsx The set of segments to process.
285 ++++++++++++++++++++++++++++++++++++++*/
286
287 void SortSegmentList(SegmentsX* segmentsx)
288 {
289 index_t i;
290
291 assert(segmentsx->xdata); /* Must have xdata filled in */
292
293 printf("Sorting Segments");
294 fflush(stdout);
295
296 /* Allocate the array of pointers and sort them */
297
298 segmentsx->ndata=(SegmentX**)realloc(segmentsx->ndata,(segmentsx->row*INCREMENT_SEGMENTSX+segmentsx->col)*sizeof(SegmentX*));
299
300 segmentsx->number=0;
301
302 for(i=0;i<(segmentsx->row*INCREMENT_SEGMENTSX+segmentsx->col);i++)
303 if(segmentsx->xdata[i/INCREMENT_SEGMENTSX][i%INCREMENT_SEGMENTSX].node1!=NO_NODE)
304 {
305 segmentsx->ndata[segmentsx->number]=&segmentsx->xdata[i/INCREMENT_SEGMENTSX][i%INCREMENT_SEGMENTSX];
306 segmentsx->number++;
307 }
308
309 qsort(segmentsx->ndata,segmentsx->number,sizeof(SegmentX*),(int (*)(const void*,const void*))sort_by_id_and_distance);
310
311 printf("\rSorted Segments \n");
312 fflush(stdout);
313
314 segmentsx->sorted=1;
315 }
316
317
318 /*++++++++++++++++++++++++++++++++++++++
319 Sort the segments into id order and then distance order.
320
321 int sort_by_id_and_distance Returns the comparison of the node fields.
322
323 SegmentX **a The first Segment.
324
325 SegmentX **b The second Segment.
326 ++++++++++++++++++++++++++++++++++++++*/
327
328 static int sort_by_id_and_distance(SegmentX **a,SegmentX **b)
329 {
330 node_t a_id1=(*a)->node1;
331 node_t b_id1=(*b)->node1;
332
333 if(a_id1<b_id1)
334 return(-1);
335 else if(a_id1>b_id1)
336 return(1);
337 else /* if(a_id1==b_id1) */
338 {
339 node_t a_id2=(*a)->node2;
340 node_t b_id2=(*b)->node2;
341
342 if(a_id2<b_id2)
343 return(-1);
344 else if(a_id2>b_id2)
345 return(1);
346 else
347 {
348 distance_t a_distance=DISTANCE((*a)->distance);
349 distance_t b_distance=DISTANCE((*b)->distance);
350
351 if(a_distance<b_distance)
352 return(-1);
353 else if(a_distance>b_distance)
354 return(1);
355 else
356 return(0);
357 }
358 }
359 }
360
361
362 /*++++++++++++++++++++++++++++++++++++++
363 Remove bad segments (zero length or duplicated).
364
365 NodesX *nodesx The nodes to check.
366
367 SegmentsX *segmentsx The segments to modify.
368 ++++++++++++++++++++++++++++++++++++++*/
369
370 void RemoveBadSegments(NodesX *nodesx,SegmentsX *segmentsx)
371 {
372 index_t i;
373 int duplicate=0,loop=0,missing=0;
374
375 assert(segmentsx->ndata); /* Must have ndata filled in */
376
377 printf("Checking: Segments=0 Duplicate=0 Loop=0 Missing-Node=0");
378 fflush(stdout);
379
380 for(i=0;i<segmentsx->number;i++)
381 {
382 if(i && segmentsx->ndata[i]->node1==segmentsx->ndata[i-1]->node1 &&
383 segmentsx->ndata[i]->node2==segmentsx->ndata[i-1]->node2)
384 {
385 duplicate++;
386 segmentsx->ndata[i-1]->node1=NO_NODE;
387 }
388 else if(segmentsx->ndata[i]->node1==segmentsx->ndata[i]->node2)
389 {
390 loop++;
391 segmentsx->ndata[i]->node1=NO_NODE;
392 }
393 else if(!FindNodeX(nodesx,segmentsx->ndata[i]->node1) ||
394 !FindNodeX(nodesx,segmentsx->ndata[i]->node2))
395 {
396 missing++;
397 segmentsx->ndata[i]->node1=NO_NODE;
398 }
399
400 if(!((i+1)%10000))
401 {
402 printf("\rChecking: Segments=%d Duplicate=%d Loop=%d Missing-Node=%d",i+1,duplicate,loop,missing);
403 fflush(stdout);
404 }
405 }
406
407 printf("\rChecked: Segments=%d Duplicate=%d Loop=%d Missing-Node=%d \n",segmentsx->number,duplicate,loop,missing);
408 fflush(stdout);
409 }
410
411
412 /*++++++++++++++++++++++++++++++++++++++
413 Measure the segments.
414
415 SegmentsX* segmentsx The set of segments to process.
416
417 NodesX *nodesx The list of nodes to use.
418 ++++++++++++++++++++++++++++++++++++++*/
419
420 void MeasureSegments(SegmentsX* segmentsx,NodesX *nodesx)
421 {
422 index_t i;
423
424 assert(segmentsx->ndata); /* Must have ndata filled in */
425
426 printf("Measuring Segments: Segments=0");
427 fflush(stdout);
428
429 for(i=0;i<segmentsx->number;i++)
430 {
431 NodeX **nodex1=FindNodeX(nodesx,segmentsx->ndata[i]->node1);
432 NodeX **nodex2=FindNodeX(nodesx,segmentsx->ndata[i]->node2);
433
434 /* Set the distance but preserve the ONEWAY_* flags */
435
436 segmentsx->ndata[i]->distance|=DISTANCE(DistanceX(*nodex1,*nodex2));
437
438 if(!((i+1)%10000))
439 {
440 printf("\rMeasuring Segments: Segments=%d",i+1);
441 fflush(stdout);
442 }
443 }
444
445 printf("\rMeasured Segments: Segments=%d \n",segmentsx->number);
446 fflush(stdout);
447 }
448
449
450 /*++++++++++++++++++++++++++++++++++++++
451 Make the segments all point the same way (node1<node2).
452
453 SegmentsX* segmentsx The set of segments to process.
454 ++++++++++++++++++++++++++++++++++++++*/
455
456 void RotateSegments(SegmentsX* segmentsx)
457 {
458 index_t i;
459 int rotated=0;
460
461 assert(segmentsx->ndata); /* Must have ndata filled in */
462
463 printf("Rotating Segments: Segments=0 Rotated=0");
464 fflush(stdout);
465
466 for(i=0;i<segmentsx->number;i++)
467 {
468 if(segmentsx->ndata[i]->node1>segmentsx->ndata[i]->node2)
469 {
470 segmentsx->ndata[i]->node1^=segmentsx->ndata[i]->node2;
471 segmentsx->ndata[i]->node2^=segmentsx->ndata[i]->node1;
472 segmentsx->ndata[i]->node1^=segmentsx->ndata[i]->node2;
473
474 if(segmentsx->ndata[i]->distance&(ONEWAY_2TO1|ONEWAY_1TO2))
475 segmentsx->ndata[i]->distance^=ONEWAY_2TO1|ONEWAY_1TO2;
476
477 rotated++;
478 }
479
480 if(!((i+1)%10000))
481 {
482 printf("\rRotating Segments: Segments=%d Rotated=%d",i+1,rotated);
483 fflush(stdout);
484 }
485 }
486
487 printf("\rRotated Segments: Segments=%d Rotated=%d \n",segmentsx->number,rotated);
488 fflush(stdout);
489 }
490
491
492 /*++++++++++++++++++++++++++++++++++++++
493 Mark the duplicate segments.
494
495 SegmentsX* segmentsx The set of segments to process.
496
497 WaysX *waysx The list of ways to use.
498 ++++++++++++++++++++++++++++++++++++++*/
499
500 void DeduplicateSegments(SegmentsX* segmentsx,WaysX *waysx)
501 {
502 index_t i;
503 int duplicate=0;
504
505 assert(segmentsx->ndata); /* Must have ndata filled in */
506
507 printf("Deduplicating Segments: Segments=0 Duplicate=0");
508 fflush(stdout);
509
510 for(i=1;i<segmentsx->number;i++)
511 {
512 if(segmentsx->ndata[i]->node1==segmentsx->ndata[i-1]->node1 &&
513 segmentsx->ndata[i]->node2==segmentsx->ndata[i-1]->node2 &&
514 DISTFLAG(segmentsx->ndata[i]->distance)==DISTFLAG(segmentsx->ndata[i-1]->distance))
515 {
516 WayX *wayx1=FindWayX(waysx,segmentsx->ndata[i-1]->way);
517 WayX *wayx2=FindWayX(waysx,segmentsx->ndata[i ]->way);
518
519 if(!WaysCompare(wayx1->way,wayx2->way))
520 {
521 segmentsx->ndata[i-1]->node1=NO_NODE;
522 segmentsx->ndata[i-1]->node2=NO_NODE;
523
524 duplicate++;
525 }
526 }
527
528 if(!((i+1)%10000))
529 {
530 printf("\rDeduplicating Segments: Segments=%d Duplicate=%d",i+1,duplicate);
531 fflush(stdout);
532 }
533 }
534
535 printf("\rDeduplicated Segments: Segments=%d Duplicate=%d \n",segmentsx->number,duplicate);
536 fflush(stdout);
537 }
538
539
540 /*++++++++++++++++++++++++++++++++++++++
541 Create the real segments data.
542
543 SegmentsX* segmentsx The set of segments to use.
544
545 WaysX* waysx The set of ways to use.
546 ++++++++++++++++++++++++++++++++++++++*/
547
548 void CreateRealSegments(SegmentsX *segmentsx,WaysX *waysx)
549 {
550 index_t i;
551
552 assert(segmentsx->ndata); /* Must have ndata filled in */
553
554 printf("Creating Real Segments: Segments=0");
555 fflush(stdout);
556
557 /* Allocate the memory */
558
559 segmentsx->sdata=(Segment*)malloc(segmentsx->number*sizeof(Segment));
560
561 /* Loop through and allocate. */
562
563 for(i=0;i<segmentsx->number;i++)
564 {
565 WayX *wayx=FindWayX(waysx,segmentsx->ndata[i]->way);
566
567 segmentsx->sdata[i].node1=0;
568 segmentsx->sdata[i].node2=0;
569 segmentsx->sdata[i].next2=NO_NODE;
570 segmentsx->sdata[i].way=IndexWayInWaysX(waysx,wayx);
571 segmentsx->sdata[i].distance=segmentsx->ndata[i]->distance;
572
573 if(!((i+1)%10000))
574 {
575 printf("\rCreating Real Segments: Segments=%d",i+1);
576 fflush(stdout);
577 }
578 }
579
580 printf("\rCreating Real Segments: Segments=%d \n",segmentsx->number);
581 fflush(stdout);
582 }
583
584
585 /*++++++++++++++++++++++++++++++++++++++
586 Assign the nodes indexes to the segments.
587
588 SegmentsX* segmentsx The set of segments to process.
589
590 NodesX *nodesx The list of nodes to use.
591 ++++++++++++++++++++++++++++++++++++++*/
592
593 void IndexSegments(SegmentsX* segmentsx,NodesX *nodesx)
594 {
595 index_t i;
596
597 assert(segmentsx->sorted); /* Must be sorted */
598 assert(segmentsx->ndata); /* Must have ndata filled in */
599 assert(segmentsx->sdata); /* Must have sdata filled in */
600 assert(nodesx->sorted); /* Must be sorted */
601 assert(nodesx->gdata); /* Must have gdata filled in */
602
603 printf("Indexing Nodes: Nodes=0");
604 fflush(stdout);
605
606 /* Index the segments */
607
608 for(i=0;i<nodesx->number;i++)
609 {
610 NodeX **nodex=FindNodeX(nodesx,nodesx->gdata[i]->id);
611 Node *node =&nodesx->ndata[nodex-nodesx->idata];
612 index_t index=SEGMENT(node->firstseg);
613
614 do
615 {
616 if(segmentsx->ndata[index]->node1==nodesx->gdata[i]->id)
617 {
618 segmentsx->sdata[index].node1=i;
619
620 index++;
621
622 if(index>=segmentsx->number || segmentsx->ndata[index]->node1!=nodesx->gdata[i]->id)
623 break;
624 }
625 else
626 {
627 segmentsx->sdata[index].node2=i;
628
629 if(segmentsx->sdata[index].next2==NO_NODE)
630 break;
631 else
632 index=segmentsx->sdata[index].next2;
633 }
634 }
635 while(1);
636
637 if(!((i+1)%10000))
638 {
639 printf("\rIndexing Nodes: Nodes=%d",i+1);
640 fflush(stdout);
641 }
642 }
643
644 printf("\rIndexed Nodes: Nodes=%d \n",nodesx->number);
645 fflush(stdout);
646 }
647
648
649 /*++++++++++++++++++++++++++++++++++++++
650 Calculate the distance between two nodes.
651
652 distance_t DistanceX Returns the distance between the extended nodes.
653
654 NodeX *nodex1 The starting node.
655
656 NodeX *nodex2 The end node.
657 ++++++++++++++++++++++++++++++++++++++*/
658
659 distance_t DistanceX(NodeX *nodex1,NodeX *nodex2)
660 {
661 double dlon = latlong_to_radians(nodex1->longitude) - latlong_to_radians(nodex2->longitude);
662 double dlat = latlong_to_radians(nodex1->latitude) - latlong_to_radians(nodex2->latitude);
663 double lat1 = latlong_to_radians(nodex1->latitude);
664 double lat2 = latlong_to_radians(nodex2->latitude);
665
666 double a1,a2,a,sa,c,d;
667
668 if(dlon==0 && dlat==0)
669 return 0;
670
671 a1 = sin (dlat / 2);
672 a2 = sin (dlon / 2);
673 a = (a1 * a1) + cos (lat1) * cos (lat2) * a2 * a2;
674 sa = sqrt (a);
675 if (sa <= 1.0)
676 {c = 2 * asin (sa);}
677 else
678 {c = 2 * asin (1.0);}
679 d = 6378.137 * c;
680
681 return km_to_distance(d);
682 }

Properties

Name Value
cvs:description Extended segments functions.
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