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

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