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 204 - (show annotations) (download) (as text)
Thu Jun 25 18:17:58 2009 UTC (15 years, 9 months ago) by amb
File MIME type: text/x-csrc
File size: 15593 byte(s) 
Undo part of the previous change - only update the Segment way index at the end.
1 /***************************************
2 $Header: /home/amb/CVS/routino/src/segmentsx.c,v 1.12 2009-06-25 18:17:58 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_and_distance(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<segments->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",segments->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 way_t way The way that the segment belongs to.
238
239 node_t node1 The first node in the segment.
240
241 node_t node2 The second node in the segment.
242 ++++++++++++++++++++++++++++++++++++++*/
243
244 Segment *AppendSegment(SegmentsX* segmentsx,way_t way,node_t node1,node_t node2)
245 {
246 /* Check that the array has enough space. */
247
248 if(segmentsx->xnumber==segmentsx->alloced)
249 {
250 segmentsx->alloced+=INCREMENT_SEGMENTS;
251
252 segmentsx->xdata=(SegmentX*)realloc((void*)segmentsx->xdata,segmentsx->alloced*sizeof(SegmentX));
253 }
254
255 /* Insert the segment */
256
257 segmentsx->xdata[segmentsx->xnumber].way=way;
258 segmentsx->xdata[segmentsx->xnumber].node1=node1;
259 segmentsx->xdata[segmentsx->xnumber].node2=node2;
260
261 memset(&segmentsx->xdata[segmentsx->xnumber].segment,0,sizeof(Segment));
262
263 segmentsx->xnumber++;
264
265 segmentsx->sorted=0;
266
267 return(&segmentsx->xdata[segmentsx->xnumber-1].segment);
268 }
269
270
271 /*++++++++++++++++++++++++++++++++++++++
272 Sort the segment list.
273
274 SegmentsX* segmentsx The set of segments to process.
275 ++++++++++++++++++++++++++++++++++++++*/
276
277 void SortSegmentList(SegmentsX* segmentsx)
278 {
279 int i;
280
281 printf("Sorting Segments"); fflush(stdout);
282
283 /* Allocate the arrays of pointers */
284
285 if(segmentsx->sorted)
286 segmentsx->sdata=realloc(segmentsx->sdata,segmentsx->xnumber*sizeof(SegmentX*));
287 else
288 segmentsx->sdata=malloc(segmentsx->xnumber*sizeof(SegmentX*));
289
290 segmentsx->number=0;
291
292 for(i=0;i<segmentsx->xnumber;i++)
293 if(segmentsx->xdata[i].node1!=NO_NODE)
294 {
295 segmentsx->sdata[segmentsx->number]=&segmentsx->xdata[i];
296 segmentsx->number++;
297 }
298
299 qsort(segmentsx->sdata,segmentsx->number,sizeof(SegmentX*),(int (*)(const void*,const void*))sort_by_id_and_distance);
300
301 segmentsx->sorted=1;
302
303 printf("\rSorted Segments \n"); fflush(stdout);
304 }
305
306
307 /*++++++++++++++++++++++++++++++++++++++
308 Sort the segments into id order and then distance order.
309
310 int sort_by_id_and_distance Returns the comparison of the node fields.
311
312 SegmentX **a The first Segment.
313
314 SegmentX **b The second Segment.
315 ++++++++++++++++++++++++++++++++++++++*/
316
317 static int sort_by_id_and_distance(SegmentX **a,SegmentX **b)
318 {
319 node_t a_id1=(*a)->node1;
320 node_t b_id1=(*b)->node1;
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 node_t a_id2=(*a)->node2;
329 node_t b_id2=(*b)->node2;
330
331 if(a_id2<b_id2)
332 return(-1);
333 else if(a_id2>b_id2)
334 return(1);
335 else
336 {
337 distance_t a_distance=(*a)->segment.distance;
338 distance_t b_distance=(*b)->segment.distance;
339
340 if(a_distance<b_distance)
341 return(-1);
342 else if(a_distance>b_distance)
343 return(1);
344 else
345 return(0);
346 }
347 }
348 }
349
350
351 /*++++++++++++++++++++++++++++++++++++++
352 Remove bad segments (zero length or duplicated).
353
354 NodesX *nodesx The nodes to check.
355
356 SegmentsX *segmentsx The segments to modify.
357 ++++++++++++++++++++++++++++++++++++++*/
358
359 void RemoveBadSegments(NodesX *nodesx,SegmentsX *segmentsx)
360 {
361 int i;
362 int duplicate=0,loop=0,missing=0;
363
364 assert(segmentsx->sorted); /* Must be sorted */
365
366 for(i=0;i<segmentsx->number;i++)
367 {
368 if(i && segmentsx->sdata[i]->node1==segmentsx->sdata[i-1]->node1 &&
369 segmentsx->sdata[i]->node2==segmentsx->sdata[i-1]->node2)
370 {
371 duplicate++;
372 segmentsx->sdata[i-1]->node1=NO_NODE;
373 }
374 else if(segmentsx->sdata[i]->node1==segmentsx->sdata[i]->node2)
375 {
376 loop++;
377 segmentsx->sdata[i]->node1=NO_NODE;
378 }
379 else if(!FindNodeX(nodesx,segmentsx->sdata[i]->node1) ||
380 !FindNodeX(nodesx,segmentsx->sdata[i]->node2))
381 {
382 missing++;
383 segmentsx->sdata[i]->node1=NO_NODE;
384 }
385
386 if(!((i+1)%10000))
387 {
388 printf("\rChecking: Segments=%d Duplicate=%d Loop=%d Missing-Node=%d",i+1,duplicate,loop,missing);
389 fflush(stdout);
390 }
391 }
392
393 printf("\rChecked: Segments=%d Duplicate=%d Loop=%d Missing-Node=%d \n",segmentsx->number,duplicate,loop,missing);
394 fflush(stdout);
395 }
396
397
398 /*++++++++++++++++++++++++++++++++++++++
399 Measure the segments.
400
401 SegmentsX* segmentsx The set of segments to process.
402
403 NodesX *nodesx The list of nodes to use.
404 ++++++++++++++++++++++++++++++++++++++*/
405
406 void MeasureSegments(SegmentsX* segmentsx,NodesX *nodesx)
407 {
408 int i;
409
410 assert(segmentsx->sorted); /* Must be sorted */
411
412 for(i=0;i<segmentsx->number;i++)
413 {
414 NodeX *node1=FindNodeX(nodesx,segmentsx->sdata[i]->node1);
415 NodeX *node2=FindNodeX(nodesx,segmentsx->sdata[i]->node2);
416
417 /* Set the distance but preserve the ONEWAY_* flags */
418
419 segmentsx->sdata[i]->segment.distance|=DistanceX(node1,node2);
420
421 if(!((i+1)%10000))
422 {
423 printf("\rMeasuring Segments: Segments=%d",i+1);
424 fflush(stdout);
425 }
426 }
427
428 printf("\rMeasured Segments: Segments=%d \n",segmentsx->number);
429 fflush(stdout);
430 }
431
432
433 /*++++++++++++++++++++++++++++++++++++++
434 Make the segments all point the same way (node1<node2).
435
436 SegmentsX* segmentsx The set of segments to process.
437
438 NodesX *nodesx The list of nodes to use.
439 ++++++++++++++++++++++++++++++++++++++*/
440
441 void RotateSegments(SegmentsX* segmentsx,NodesX *nodesx)
442 {
443 int i,rotated=0;
444
445 assert(segmentsx->sorted); /* Must be sorted */
446
447 for(i=0;i<segmentsx->number;i++)
448 {
449 if(segmentsx->sdata[i]->node1>segmentsx->sdata[i]->node2)
450 {
451 segmentsx->sdata[i]->node1^=segmentsx->sdata[i]->node2;
452 segmentsx->sdata[i]->node2^=segmentsx->sdata[i]->node1;
453 segmentsx->sdata[i]->node1^=segmentsx->sdata[i]->node2;
454
455 if(segmentsx->sdata[i]->segment.distance&(ONEWAY_2TO1|ONEWAY_1TO2))
456 segmentsx->sdata[i]->segment.distance^=ONEWAY_2TO1|ONEWAY_1TO2;
457
458 rotated++;
459 }
460
461 if(!((i+1)%10000))
462 {
463 printf("\rRotating Segments: Segments=%d Rotated=%d",i+1,rotated);
464 fflush(stdout);
465 }
466 }
467
468 printf("\rRotated Segments: Segments=%d Rotated=%d \n",segmentsx->number,rotated);
469 fflush(stdout);
470 }
471
472
473 /*++++++++++++++++++++++++++++++++++++++
474 Mark the duplicate segments.
475
476 SegmentsX* segmentsx The set of segments to process.
477
478 NodesX *nodesx The list of nodes to use.
479
480 WaysX *waysx The list of ways to use.
481 ++++++++++++++++++++++++++++++++++++++*/
482
483 void DeduplicateSegments(SegmentsX* segmentsx,NodesX *nodesx,WaysX *waysx)
484 {
485 int i,duplicate=0;
486
487 assert(segmentsx->sorted); /* Must be sorted */
488
489 for(i=1;i<segmentsx->number;i++)
490 {
491 if(segmentsx->sdata[i]->node1==segmentsx->sdata[i-1]->node1 &&
492 segmentsx->sdata[i]->node2==segmentsx->sdata[i-1]->node2 &&
493 segmentsx->sdata[i]->segment.node1==segmentsx->sdata[i-1]->segment.node1 &&
494 segmentsx->sdata[i]->segment.node2==segmentsx->sdata[i-1]->segment.node2 &&
495 segmentsx->sdata[i]->segment.distance==segmentsx->sdata[i-1]->segment.distance)
496 {
497 WayX *wayx1=FindWayX(waysx,segmentsx->sdata[i-1]->way);
498 WayX *wayx2=FindWayX(waysx,segmentsx->sdata[i ]->way);
499
500 if(!WaysCompare(wayx1->way,wayx2->way))
501 {
502 segmentsx->sdata[i-1]->node1=NO_NODE;
503 segmentsx->sdata[i-1]->node2=NO_NODE;
504
505 duplicate++;
506 }
507 }
508
509 if(!((i+1)%10000))
510 {
511 printf("\rDeduplicating Segments: Segments=%d Duplicate=%d",i+1,duplicate);
512 fflush(stdout);
513 }
514 }
515
516 printf("\rDeduplicated Segments: Segments=%d Duplicate=%d \n",segmentsx->number,duplicate);
517 fflush(stdout);
518 }
519
520
521 /*++++++++++++++++++++++++++++++++++++++
522 Assign the nodes indexes to the segments.
523
524 SegmentsX* segmentsx The set of segments to process.
525
526 NodesX *nodesx The list of nodes to use.
527 ++++++++++++++++++++++++++++++++++++++*/
528
529 void IndexSegments(SegmentsX* segmentsx,NodesX *nodesx)
530 {
531 int i;
532
533 assert(segmentsx->sorted); /* Must be sorted */
534 assert(nodesx->sorted); /* Must be sorted */
535
536 /* Index the segments */
537
538 for(i=0;i<nodesx->number;i++)
539 {
540 SegmentX **segmentx=LookupSegmentX(segmentsx,SEGMENT(nodesx->gdata[i]->node.firstseg));
541
542 do
543 {
544 if((*segmentx)->node1==nodesx->gdata[i]->id)
545 {
546 (*segmentx)->segment.node1|=i;
547
548 segmentx++;
549
550 if((*segmentx)->node1!=nodesx->gdata[i]->id || (segmentx-segmentsx->sdata)>=segmentsx->number)
551 segmentx=NULL;
552 }
553 else
554 {
555 (*segmentx)->segment.node2|=i;
556
557 if((*segmentx)->segment.next2==NO_NODE)
558 segmentx=NULL;
559 else
560 segmentx=LookupSegmentX(segmentsx,(*segmentx)->segment.next2);
561 }
562 }
563 while(segmentx);
564
565 if(!((i+1)%10000))
566 {
567 printf("\rIndexing Nodes: Nodes=%d",i+1);
568 fflush(stdout);
569 }
570 }
571
572 printf("\rIndexed Nodes: Nodes=%d \n",nodesx->number);
573 fflush(stdout);
574 }
575
576
577 /*++++++++++++++++++++++++++++++++++++++
578 Calculate the distance between two nodes.
579
580 distance_t DistanceX Returns the distance between the extended nodes.
581
582 NodeX *nodex1 The starting node.
583
584 NodeX *nodex2 The end node.
585 ++++++++++++++++++++++++++++++++++++++*/
586
587 distance_t DistanceX(NodeX *nodex1,NodeX *nodex2)
588 {
589 float dlon = nodex1->longitude - nodex2->longitude;
590 float dlat = nodex1->latitude - nodex2->latitude;
591
592 float a1,a2,a,sa,c,d;
593
594 if(dlon==0 && dlat==0)
595 return 0;
596
597 a1 = sinf (dlat / 2);
598 a2 = sinf (dlon / 2);
599 a = (a1 * a1) + cosf (nodex1->latitude) * cosf (nodex2->latitude) * a2 * a2;
600 sa = sqrtf (a);
601 if (sa <= 1.0)
602 {c = 2 * asinf (sa);}
603 else
604 {c = 2 * asinf (1.0);}
605 d = 6378.137 * c;
606
607 return km_to_distance(d);
608 }

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