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 176 - (show annotations) (download) (as text)
Thu May 14 18:02:30 2009 UTC (15 years, 10 months ago) by amb
File MIME type: text/x-csrc
File size: 15136 byte(s) 
Replace ~0 or 0 with NO_NODE value for "no node" condition.
1 /***************************************
2 $Header: /home/amb/CVS/routino/src/segmentsx.c,v 1.8 2009-05-14 18:02:30 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 SegmentsX *segmentsx The segments to modify.
352 ++++++++++++++++++++++++++++++++++++++*/
353
354 void RemoveBadSegments(SegmentsX *segmentsx)
355 {
356 int i;
357 int duplicate=0,loop=0;
358
359 assert(segmentsx->sorted); /* Must be sorted */
360
361 for(i=0;i<segmentsx->number;i++)
362 {
363 if(i && segmentsx->sdata[i]->node1==segmentsx->sdata[i-1]->node1 &&
364 segmentsx->sdata[i]->node2==segmentsx->sdata[i-1]->node2)
365 {
366 duplicate++;
367 segmentsx->sdata[i-1]->node1=NO_NODE;
368 }
369 else if(segmentsx->sdata[i]->node1==segmentsx->sdata[i]->node2)
370 {
371 loop++;
372 segmentsx->sdata[i]->node1=NO_NODE;
373 }
374
375 if(!((i+1)%10000))
376 {
377 printf("\rChecking: Segments=%d Duplicate=%d Loop=%d",i+1,duplicate,loop);
378 fflush(stdout);
379 }
380 }
381
382 printf("\rChecked: Segments=%d Duplicate=%d Loop=%d \n",segmentsx->number,duplicate,loop);
383 fflush(stdout);
384 }
385
386
387 /*++++++++++++++++++++++++++++++++++++++
388 Measure the segments.
389
390 SegmentsX* segmentsx The set of segments to process.
391
392 NodesX *nodesx The list of nodes to use.
393 ++++++++++++++++++++++++++++++++++++++*/
394
395 void MeasureSegments(SegmentsX* segmentsx,NodesX *nodesx)
396 {
397 int i;
398
399 assert(segmentsx->sorted); /* Must be sorted */
400
401 for(i=0;i<segmentsx->number;i++)
402 {
403 NodeX *node1=FindNodeX(nodesx,segmentsx->sdata[i]->node1);
404 NodeX *node2=FindNodeX(nodesx,segmentsx->sdata[i]->node2);
405
406 /* Set the distance but preserve the ONEWAY_* flags */
407
408 segmentsx->sdata[i]->segment.distance|=DistanceX(node1,node2);
409
410 if(!((i+1)%10000))
411 {
412 printf("\rMeasuring Segments: Segments=%d",i+1);
413 fflush(stdout);
414 }
415 }
416
417 printf("\rMeasured Segments: Segments=%d \n",segmentsx->number);
418 fflush(stdout);
419 }
420
421
422 /*++++++++++++++++++++++++++++++++++++++
423 Make the segments all point the same way (node1<node2).
424
425 SegmentsX* segmentsx The set of segments to process.
426
427 NodesX *nodesx The list of nodes to use.
428 ++++++++++++++++++++++++++++++++++++++*/
429
430 void RotateSegments(SegmentsX* segmentsx,NodesX *nodesx)
431 {
432 int i,rotated=0;
433
434 assert(segmentsx->sorted); /* Must be sorted */
435
436 for(i=0;i<segmentsx->number;i++)
437 {
438 if(segmentsx->sdata[i]->node1>segmentsx->sdata[i]->node2)
439 {
440 segmentsx->sdata[i]->node1^=segmentsx->sdata[i]->node2;
441 segmentsx->sdata[i]->node2^=segmentsx->sdata[i]->node1;
442 segmentsx->sdata[i]->node1^=segmentsx->sdata[i]->node2;
443
444 if(segmentsx->sdata[i]->segment.distance&(ONEWAY_2TO1|ONEWAY_1TO2))
445 segmentsx->sdata[i]->segment.distance^=ONEWAY_2TO1|ONEWAY_1TO2;
446
447 rotated++;
448 }
449
450 if(!((i+1)%10000))
451 {
452 printf("\rRotating Segments: Segments=%d Rotated=%d",i+1,rotated);
453 fflush(stdout);
454 }
455 }
456
457 printf("\rRotated Segments: Segments=%d Rotated=%d \n",segmentsx->number,rotated);
458 fflush(stdout);
459 }
460
461
462 /*++++++++++++++++++++++++++++++++++++++
463 Mark the duplicate segments.
464
465 SegmentsX* segmentsx The set of segments to process.
466
467 NodesX *nodesx The list of nodes to use.
468
469 WaysX *waysx The list of ways to use.
470 ++++++++++++++++++++++++++++++++++++++*/
471
472 void DeduplicateSegments(SegmentsX* segmentsx,NodesX *nodesx,WaysX *waysx)
473 {
474 int i,duplicate=0;
475
476 assert(segmentsx->sorted); /* Must be sorted */
477
478 for(i=1;i<segmentsx->number;i++)
479 {
480 if(segmentsx->sdata[i]->node1==segmentsx->sdata[i-1]->node1 &&
481 segmentsx->sdata[i]->node2==segmentsx->sdata[i-1]->node2 &&
482 segmentsx->sdata[i]->segment.node1==segmentsx->sdata[i-1]->segment.node1 &&
483 segmentsx->sdata[i]->segment.node2==segmentsx->sdata[i-1]->segment.node2 &&
484 segmentsx->sdata[i]->segment.distance==segmentsx->sdata[i-1]->segment.distance)
485 {
486 WayX *wayx1=LookupWayX(waysx,segmentsx->sdata[i-1]->segment.way);
487 WayX *wayx2=LookupWayX(waysx,segmentsx->sdata[i]->segment.way);
488
489 if(wayx1==wayx2 || WaysSame(&wayx1->way,&wayx2->way))
490 {
491 segmentsx->sdata[i-1]->node1=NO_NODE;
492 segmentsx->sdata[i-1]->node2=NO_NODE;
493
494 duplicate++;
495 }
496 }
497
498 if(!((i+1)%10000))
499 {
500 printf("\rDeduplicating Segments: Segments=%d Duplicate=%d",i+1,duplicate);
501 fflush(stdout);
502 }
503 }
504
505 printf("\rDeduplicated Segments: Segments=%d Duplicate=%d \n",segmentsx->number,duplicate);
506 fflush(stdout);
507 }
508
509
510 /*++++++++++++++++++++++++++++++++++++++
511 Assign the nodes indexes to the segments.
512
513 SegmentsX* segmentsx The set of segments to process.
514
515 NodesX *nodesx The list of nodes to use.
516 ++++++++++++++++++++++++++++++++++++++*/
517
518 void IndexSegments(SegmentsX* segmentsx,NodesX *nodesx)
519 {
520 int i;
521
522 assert(segmentsx->sorted); /* Must be sorted */
523 assert(nodesx->sorted); /* Must be sorted */
524
525 /* Index the segments */
526
527 for(i=0;i<nodesx->number;i++)
528 {
529 SegmentX **segmentx=LookupSegmentX(segmentsx,SEGMENT(nodesx->gdata[i]->node.firstseg));
530
531 do
532 {
533 if((*segmentx)->node1==nodesx->gdata[i]->id)
534 {
535 (*segmentx)->segment.node1|=i;
536
537 segmentx++;
538
539 if((*segmentx)->node1!=nodesx->gdata[i]->id || (segmentx-segmentsx->sdata)>=segmentsx->number)
540 segmentx=NULL;
541 }
542 else
543 {
544 (*segmentx)->segment.node2|=i;
545
546 if((*segmentx)->segment.next2==NO_NODE)
547 segmentx=NULL;
548 else
549 segmentx=LookupSegmentX(segmentsx,(*segmentx)->segment.next2);
550 }
551 }
552 while(segmentx);
553
554 if(!((i+1)%10000))
555 {
556 printf("\rIndexing Nodes: Nodes=%d",i+1);
557 fflush(stdout);
558 }
559 }
560
561 printf("\rIndexed Nodes: Nodes=%d \n",nodesx->number);
562 fflush(stdout);
563 }
564
565
566 /*++++++++++++++++++++++++++++++++++++++
567 Calculate the distance between two nodes.
568
569 distance_t DistanceX Returns the distance between the extended nodes.
570
571 NodeX *nodex1 The starting node.
572
573 NodeX *nodex2 The end node.
574 ++++++++++++++++++++++++++++++++++++++*/
575
576 distance_t DistanceX(NodeX *nodex1,NodeX *nodex2)
577 {
578 float dlon = nodex1->longitude - nodex2->longitude;
579 float dlat = nodex1->latitude - nodex2->latitude;
580
581 float a1,a2,a,sa,c,d;
582
583 if(dlon==0 && dlat==0)
584 return 0;
585
586 a1 = sinf (dlat / 2);
587 a2 = sinf (dlon / 2);
588 a = (a1 * a1) + cosf (nodex1->latitude) * cosf (nodex2->latitude) * a2 * a2;
589 sa = sqrtf (a);
590 if (sa <= 1.0)
591 {c = 2 * asinf (sa);}
592 else
593 {c = 2 * asinf (1.0);}
594 d = 6378.137 * c;
595
596 return km_to_distance(d);
597 }

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.2 (destination-access branch) Version 3.4.2 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