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 195 - (show annotations) (download) (as text)
Sat Jun 13 13:02:12 2009 UTC (15 years, 9 months ago) by amb
File MIME type: text/x-csrc
File size: 15443 byte(s) 
Handle nodes that are missing from the .osm file (ignore the segment).
1 /***************************************
2 $Header: /home/amb/CVS/routino/src/segmentsx.c,v 1.9 2009-06-13 13:02: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 <string.h>
28 #include <stdlib.h>
29 #include <stdio.h>
30
31 #include "types.h"
32 #include "functions.h"
33 #include "nodesx.h"
34 #include "segmentsx.h"
35 #include "waysx.h"
36
37
38 /* Constants */
39
40 /*+ The array size increment for segments - expect ~8,000,000 segments. +*/
41 #define INCREMENT_SEGMENTS 1024*1024
42
43
44 /* Functions */
45
46 static int sort_by_id(SegmentX **a,SegmentX **b);
47
48
49 /*++++++++++++++++++++++++++++++++++++++
50 Allocate a new segment list.
51
52 SegmentsX *NewSegmentList Returns the segment list.
53 ++++++++++++++++++++++++++++++++++++++*/
54
55 SegmentsX *NewSegmentList(void)
56 {
57 SegmentsX *segmentsx;
58
59 segmentsx=(SegmentsX*)malloc(sizeof(SegmentsX));
60
61 segmentsx->sorted=0;
62 segmentsx->alloced=INCREMENT_SEGMENTS;
63 segmentsx->xnumber=0;
64
65 segmentsx->xdata=(SegmentX*)malloc(segmentsx->alloced*sizeof(SegmentX));
66 segmentsx->sdata=NULL;
67
68 return(segmentsx);
69 }
70
71
72 /*++++++++++++++++++++++++++++++++++++++
73 Free a segment list.
74
75 SegmentsX *segmentsx The list to be freed.
76 ++++++++++++++++++++++++++++++++++++++*/
77
78 void FreeSegmentList(SegmentsX *segmentsx)
79 {
80 free(segmentsx->xdata);
81 free(segmentsx->sdata);
82 free(segmentsx);
83 }
84
85
86 /*++++++++++++++++++++++++++++++++++++++
87 Save the segment list to a file.
88
89 SegmentsX* segmentsx The set of segments to save.
90
91 const char *filename The name of the file to save.
92 ++++++++++++++++++++++++++++++++++++++*/
93
94 void SaveSegmentList(SegmentsX* segmentsx,const char *filename)
95 {
96 int i;
97 int fd;
98 Segments *segments=calloc(1,sizeof(Segments));
99
100 assert(segmentsx->sorted); /* Must be sorted */
101
102 /* Fill in a Segments structure with the offset of the real data in the file after
103 the Segment structure itself. */
104
105 segments->number=segmentsx->number;
106 segments->data=NULL;
107 segments->segments=(void*)sizeof(Segments);
108
109 /* Write out the Segments structure and then the real data. */
110
111 fd=OpenFile(filename);
112
113 WriteFile(fd,segments,sizeof(Segments));
114
115 for(i=0;i<segmentsx->number;i++)
116 {
117 WriteFile(fd,&segmentsx->sdata[i]->segment,sizeof(Segment));
118
119 if(!((i+1)%10000))
120 {
121 printf("\rWriting Segments: Segments=%d",i+1);
122 fflush(stdout);
123 }
124 }
125
126 printf("\rWrote Segments: Segments=%d \n",segmentsx->number);
127 fflush(stdout);
128
129 CloseFile(fd);
130
131 /* Free the fake Segments */
132
133 free(segments);
134 }
135
136
137 /*++++++++++++++++++++++++++++++++++++++
138 Find the first segment with a particular starting node.
139
140 SegmentX **FindFirstSegmentX Returns a pointer to the first extended segment with the specified id.
141
142 SegmentsX* segmentsx The set of segments to process.
143
144 node_t node The node to look for.
145 ++++++++++++++++++++++++++++++++++++++*/
146
147 SegmentX **FindFirstSegmentX(SegmentsX* segmentsx,node_t node)
148 {
149 int start=0;
150 int end=segmentsx->number-1;
151 int mid;
152 int found;
153
154 assert(segmentsx->sorted); /* Must be sorted */
155
156 /* Binary search - search key exact match only is required.
157 *
158 * # <- start | Check mid and move start or end if it doesn't match
159 * # |
160 * # | Since an exact match is wanted we can set end=mid-1
161 * # <- mid | or start=mid+1 because we know that mid doesn't match.
162 * # |
163 * # | Eventually either end=start or end=start+1 and one of
164 * # <- end | start or end is the wanted one.
165 */
166
167 if(end<start) /* There are no nodes */
168 return(NULL);
169 else if(node<segmentsx->sdata[start]->node1) /* Check key is not before start */
170 return(NULL);
171 else if(node>segmentsx->sdata[end]->node1) /* Check key is not after end */
172 return(NULL);
173 else
174 {
175 do
176 {
177 mid=(start+end)/2; /* Choose mid point */
178
179 if(segmentsx->sdata[mid]->node1<node) /* Mid point is too low */
180 start=mid;
181 else if(segmentsx->sdata[mid]->node1>node) /* Mid point is too high */
182 end=mid;
183 else /* Mid point is correct */
184 {found=mid; goto found;}
185 }
186 while((end-start)>1);
187
188 if(segmentsx->sdata[start]->node1==node) /* Start is correct */
189 {found=start; goto found;}
190
191 if(segmentsx->sdata[end]->node1==node) /* End is correct */
192 {found=end; goto found;}
193 }
194
195 return(NULL);
196
197 found:
198
199 while(found>0 && segmentsx->sdata[found-1]->node1==node)
200 found--;
201
202 return(&segmentsx->sdata[found]);
203 }
204
205
206 /*++++++++++++++++++++++++++++++++++++++
207 Find the next segment with a particular starting node.
208
209 SegmentX **FindNextSegmentX Returns a pointer to the next segment with the same id.
210
211 SegmentsX* segmentsx The set of segments to process.
212
213 SegmentX **segmentx The current segment.
214 ++++++++++++++++++++++++++++++++++++++*/
215
216 SegmentX **FindNextSegmentX(SegmentsX* segmentsx,SegmentX **segmentx)
217 {
218 SegmentX **next=segmentx+1;
219
220 if((next-segmentsx->sdata)==segmentsx->number)
221 return(NULL);
222
223 if((*next)->node1==(*segmentx)->node1)
224 return(next);
225
226 return(NULL);
227 }
228
229
230 /*++++++++++++++++++++++++++++++++++++++
231 Append a segment to a segment list.
232
233 Segment *AppendSegment Returns the appended segment.
234
235 SegmentsX* segmentsx The set of segments to process.
236
237 node_t node1 The first node in the segment.
238
239 node_t node2 The second node in the segment.
240 ++++++++++++++++++++++++++++++++++++++*/
241
242 Segment *AppendSegment(SegmentsX* segmentsx,node_t node1,node_t node2)
243 {
244 /* Check that the array has enough space. */
245
246 if(segmentsx->xnumber==segmentsx->alloced)
247 {
248 segmentsx->alloced+=INCREMENT_SEGMENTS;
249
250 segmentsx->xdata=(SegmentX*)realloc((void*)segmentsx->xdata,segmentsx->alloced*sizeof(SegmentX));
251 }
252
253 /* Insert the segment */
254
255 segmentsx->xdata[segmentsx->xnumber].node1=node1;
256 segmentsx->xdata[segmentsx->xnumber].node2=node2;
257
258 memset(&segmentsx->xdata[segmentsx->xnumber].segment,0,sizeof(Segment));
259
260 segmentsx->xnumber++;
261
262 segmentsx->sorted=0;
263
264 return(&segmentsx->xdata[segmentsx->xnumber-1].segment);
265 }
266
267
268 /*++++++++++++++++++++++++++++++++++++++
269 Sort the segment list.
270
271 SegmentsX* segmentsx The set of segments to process.
272 ++++++++++++++++++++++++++++++++++++++*/
273
274 void SortSegmentList(SegmentsX* segmentsx)
275 {
276 int i;
277
278 printf("Sorting Segments"); fflush(stdout);
279
280 /* Allocate the arrays of pointers */
281
282 if(segmentsx->sorted)
283 segmentsx->sdata=realloc(segmentsx->sdata,segmentsx->xnumber*sizeof(SegmentX*));
284 else
285 segmentsx->sdata=malloc(segmentsx->xnumber*sizeof(SegmentX*));
286
287 segmentsx->number=0;
288
289 for(i=0;i<segmentsx->xnumber;i++)
290 if(segmentsx->xdata[i].node1!=NO_NODE)
291 {
292 segmentsx->sdata[segmentsx->number]=&segmentsx->xdata[i];
293 segmentsx->number++;
294 }
295
296 qsort(segmentsx->sdata,segmentsx->number,sizeof(SegmentX*),(int (*)(const void*,const void*))sort_by_id);
297
298 segmentsx->sorted=1;
299
300 printf("\rSorted Segments \n"); fflush(stdout);
301 }
302
303
304 /*++++++++++++++++++++++++++++++++++++++
305 Sort the segments into id order.
306
307 int sort_by_id Returns the comparison of the node fields.
308
309 SegmentX **a The first Segment.
310
311 SegmentX **b The second Segment.
312 ++++++++++++++++++++++++++++++++++++++*/
313
314 static int sort_by_id(SegmentX **a,SegmentX **b)
315 {
316 node_t a_id1=(*a)->node1;
317 node_t b_id1=(*b)->node1;
318
319 if(a_id1<b_id1)
320 return(-1);
321 else if(a_id1>b_id1)
322 return(1);
323 else /* if(a_id1==b_id1) */
324 {
325 node_t a_id2=(*a)->node2;
326 node_t b_id2=(*b)->node2;
327
328 if(a_id2<b_id2)
329 return(-1);
330 else if(a_id2>b_id2)
331 return(1);
332 else
333 {
334 distance_t a_distance=(*a)->segment.distance;
335 distance_t b_distance=(*b)->segment.distance;
336
337 if(a_distance<b_distance)
338 return(-1);
339 else if(a_distance>b_distance)
340 return(1);
341 else
342 return(0);
343 }
344 }
345 }
346
347
348 /*++++++++++++++++++++++++++++++++++++++
349 Remove bad segments (zero length or duplicated).
350
351 NodesX *nodesx The nodes to check.
352
353 SegmentsX *segmentsx The segments to modify.
354 ++++++++++++++++++++++++++++++++++++++*/
355
356 void RemoveBadSegments(NodesX *nodesx,SegmentsX *segmentsx)
357 {
358 int i;
359 int duplicate=0,loop=0,missing=0;
360
361 assert(segmentsx->sorted); /* Must be sorted */
362
363 for(i=0;i<segmentsx->number;i++)
364 {
365 if(i && segmentsx->sdata[i]->node1==segmentsx->sdata[i-1]->node1 &&
366 segmentsx->sdata[i]->node2==segmentsx->sdata[i-1]->node2)
367 {
368 duplicate++;
369 segmentsx->sdata[i-1]->node1=NO_NODE;
370 }
371 else if(segmentsx->sdata[i]->node1==segmentsx->sdata[i]->node2)
372 {
373 loop++;
374 segmentsx->sdata[i]->node1=NO_NODE;
375 }
376 else if(!FindNodeX(nodesx,segmentsx->sdata[i]->node1) ||
377 !FindNodeX(nodesx,segmentsx->sdata[i]->node2))
378 {
379 missing++;
380 segmentsx->sdata[i]->node1=NO_NODE;
381 }
382
383 if(!((i+1)%10000))
384 {
385 printf("\rChecking: Segments=%d Duplicate=%d Loop=%d Missing-Node=%d",i+1,duplicate,loop,missing);
386 fflush(stdout);
387 }
388 }
389
390 printf("\rChecked: Segments=%d Duplicate=%d Loop=%d Missing-Node=%d \n",segmentsx->number,duplicate,loop,missing);
391 fflush(stdout);
392 }
393
394
395 /*++++++++++++++++++++++++++++++++++++++
396 Measure the segments.
397
398 SegmentsX* segmentsx The set of segments to process.
399
400 NodesX *nodesx The list of nodes to use.
401 ++++++++++++++++++++++++++++++++++++++*/
402
403 void MeasureSegments(SegmentsX* segmentsx,NodesX *nodesx)
404 {
405 int i;
406
407 assert(segmentsx->sorted); /* Must be sorted */
408
409 for(i=0;i<segmentsx->number;i++)
410 {
411 NodeX *node1=FindNodeX(nodesx,segmentsx->sdata[i]->node1);
412 NodeX *node2=FindNodeX(nodesx,segmentsx->sdata[i]->node2);
413
414 /* Set the distance but preserve the ONEWAY_* flags */
415
416 segmentsx->sdata[i]->segment.distance|=DistanceX(node1,node2);
417
418 if(!((i+1)%10000))
419 {
420 printf("\rMeasuring Segments: Segments=%d",i+1);
421 fflush(stdout);
422 }
423 }
424
425 printf("\rMeasured Segments: Segments=%d \n",segmentsx->number);
426 fflush(stdout);
427 }
428
429
430 /*++++++++++++++++++++++++++++++++++++++
431 Make the segments all point the same way (node1<node2).
432
433 SegmentsX* segmentsx The set of segments to process.
434
435 NodesX *nodesx The list of nodes to use.
436 ++++++++++++++++++++++++++++++++++++++*/
437
438 void RotateSegments(SegmentsX* segmentsx,NodesX *nodesx)
439 {
440 int i,rotated=0;
441
442 assert(segmentsx->sorted); /* Must be sorted */
443
444 for(i=0;i<segmentsx->number;i++)
445 {
446 if(segmentsx->sdata[i]->node1>segmentsx->sdata[i]->node2)
447 {
448 segmentsx->sdata[i]->node1^=segmentsx->sdata[i]->node2;
449 segmentsx->sdata[i]->node2^=segmentsx->sdata[i]->node1;
450 segmentsx->sdata[i]->node1^=segmentsx->sdata[i]->node2;
451
452 if(segmentsx->sdata[i]->segment.distance&(ONEWAY_2TO1|ONEWAY_1TO2))
453 segmentsx->sdata[i]->segment.distance^=ONEWAY_2TO1|ONEWAY_1TO2;
454
455 rotated++;
456 }
457
458 if(!((i+1)%10000))
459 {
460 printf("\rRotating Segments: Segments=%d Rotated=%d",i+1,rotated);
461 fflush(stdout);
462 }
463 }
464
465 printf("\rRotated Segments: Segments=%d Rotated=%d \n",segmentsx->number,rotated);
466 fflush(stdout);
467 }
468
469
470 /*++++++++++++++++++++++++++++++++++++++
471 Mark the duplicate segments.
472
473 SegmentsX* segmentsx The set of segments to process.
474
475 NodesX *nodesx The list of nodes to use.
476
477 WaysX *waysx The list of ways to use.
478 ++++++++++++++++++++++++++++++++++++++*/
479
480 void DeduplicateSegments(SegmentsX* segmentsx,NodesX *nodesx,WaysX *waysx)
481 {
482 int i,duplicate=0;
483
484 assert(segmentsx->sorted); /* Must be sorted */
485
486 for(i=1;i<segmentsx->number;i++)
487 {
488 if(segmentsx->sdata[i]->node1==segmentsx->sdata[i-1]->node1 &&
489 segmentsx->sdata[i]->node2==segmentsx->sdata[i-1]->node2 &&
490 segmentsx->sdata[i]->segment.node1==segmentsx->sdata[i-1]->segment.node1 &&
491 segmentsx->sdata[i]->segment.node2==segmentsx->sdata[i-1]->segment.node2 &&
492 segmentsx->sdata[i]->segment.distance==segmentsx->sdata[i-1]->segment.distance)
493 {
494 WayX *wayx1=LookupWayX(waysx,segmentsx->sdata[i-1]->segment.way);
495 WayX *wayx2=LookupWayX(waysx,segmentsx->sdata[i]->segment.way);
496
497 if(wayx1==wayx2 || WaysSame(&wayx1->way,&wayx2->way))
498 {
499 segmentsx->sdata[i-1]->node1=NO_NODE;
500 segmentsx->sdata[i-1]->node2=NO_NODE;
501
502 duplicate++;
503 }
504 }
505
506 if(!((i+1)%10000))
507 {
508 printf("\rDeduplicating Segments: Segments=%d Duplicate=%d",i+1,duplicate);
509 fflush(stdout);
510 }
511 }
512
513 printf("\rDeduplicated Segments: Segments=%d Duplicate=%d \n",segmentsx->number,duplicate);
514 fflush(stdout);
515 }
516
517
518 /*++++++++++++++++++++++++++++++++++++++
519 Assign the nodes indexes to the segments.
520
521 SegmentsX* segmentsx The set of segments to process.
522
523 NodesX *nodesx The list of nodes to use.
524 ++++++++++++++++++++++++++++++++++++++*/
525
526 void IndexSegments(SegmentsX* segmentsx,NodesX *nodesx)
527 {
528 int i;
529
530 assert(segmentsx->sorted); /* Must be sorted */
531 assert(nodesx->sorted); /* Must be sorted */
532
533 /* Index the segments */
534
535 for(i=0;i<nodesx->number;i++)
536 {
537 SegmentX **segmentx=LookupSegmentX(segmentsx,SEGMENT(nodesx->gdata[i]->node.firstseg));
538
539 do
540 {
541 if((*segmentx)->node1==nodesx->gdata[i]->id)
542 {
543 (*segmentx)->segment.node1|=i;
544
545 segmentx++;
546
547 if((*segmentx)->node1!=nodesx->gdata[i]->id || (segmentx-segmentsx->sdata)>=segmentsx->number)
548 segmentx=NULL;
549 }
550 else
551 {
552 (*segmentx)->segment.node2|=i;
553
554 if((*segmentx)->segment.next2==NO_NODE)
555 segmentx=NULL;
556 else
557 segmentx=LookupSegmentX(segmentsx,(*segmentx)->segment.next2);
558 }
559 }
560 while(segmentx);
561
562 if(!((i+1)%10000))
563 {
564 printf("\rIndexing Nodes: Nodes=%d",i+1);
565 fflush(stdout);
566 }
567 }
568
569 printf("\rIndexed Nodes: Nodes=%d \n",nodesx->number);
570 fflush(stdout);
571 }
572
573
574 /*++++++++++++++++++++++++++++++++++++++
575 Calculate the distance between two nodes.
576
577 distance_t DistanceX Returns the distance between the extended nodes.
578
579 NodeX *nodex1 The starting node.
580
581 NodeX *nodex2 The end node.
582 ++++++++++++++++++++++++++++++++++++++*/
583
584 distance_t DistanceX(NodeX *nodex1,NodeX *nodex2)
585 {
586 float dlon = nodex1->longitude - nodex2->longitude;
587 float dlat = nodex1->latitude - nodex2->latitude;
588
589 float a1,a2,a,sa,c,d;
590
591 if(dlon==0 && dlat==0)
592 return 0;
593
594 a1 = sinf (dlat / 2);
595 a2 = sinf (dlon / 2);
596 a = (a1 * a1) + cosf (nodex1->latitude) * cosf (nodex2->latitude) * a2 * a2;
597 sa = sqrtf (a);
598 if (sa <= 1.0)
599 {c = 2 * asinf (sa);}
600 else
601 {c = 2 * asinf (1.0);}
602 d = 6378.137 * c;
603
604 return km_to_distance(d);
605 }

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