Routino SVN Repository Browser

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

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.