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

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