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 209 - (show annotations) (download) (as text)
Tue Jun 30 18:32:42 2009 UTC (15 years, 8 months ago) by amb
File MIME type: text/x-csrc
File size: 16313 byte(s) 
Remove the Segment structure from the SegmentX structure to save memory.
1 /***************************************
2 $Header: /home/amb/CVS/routino/src/segmentsx.c,v 1.15 2009-06-30 18:32:42 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 segmentsx->number=0;
65
66 segmentsx->xdata=(SegmentX*)malloc(segmentsx->alloced*sizeof(SegmentX));
67 segmentsx->ndata=NULL;
68
69 segmentsx->sdata=NULL;
70
71 return(segmentsx);
72 }
73
74
75 /*++++++++++++++++++++++++++++++++++++++
76 Free a segment list.
77
78 SegmentsX *segmentsx The list to be freed.
79 ++++++++++++++++++++++++++++++++++++++*/
80
81 void FreeSegmentList(SegmentsX *segmentsx)
82 {
83 if(segmentsx->sdata)
84 free(segmentsx->sdata);
85 free(segmentsx->xdata);
86 free(segmentsx->ndata);
87 free(segmentsx);
88 }
89
90
91 /*++++++++++++++++++++++++++++++++++++++
92 Save the segment list to a file.
93
94 SegmentsX* segmentsx The set of segments to save.
95
96 const char *filename The name of the file to save.
97 ++++++++++++++++++++++++++++++++++++++*/
98
99 void SaveSegmentList(SegmentsX* segmentsx,const char *filename)
100 {
101 int i;
102 int fd;
103 Segments *segments=calloc(1,sizeof(Segments));
104
105 assert(segmentsx->sorted); /* Must be sorted */
106
107 /* Fill in a Segments structure with the offset of the real data in the file after
108 the Segment structure itself. */
109
110 segments->number=segmentsx->number;
111 segments->data=NULL;
112 segments->segments=(void*)sizeof(Segments);
113
114 /* Write out the Segments structure and then the real data. */
115
116 fd=OpenFile(filename);
117
118 WriteFile(fd,segments,sizeof(Segments));
119
120 for(i=0;i<segments->number;i++)
121 {
122 WriteFile(fd,&segmentsx->sdata[i],sizeof(Segment));
123
124 if(!((i+1)%10000))
125 {
126 printf("\rWriting Segments: Segments=%d",i+1);
127 fflush(stdout);
128 }
129 }
130
131 printf("\rWrote Segments: Segments=%d \n",segments->number);
132 fflush(stdout);
133
134 CloseFile(fd);
135
136 /* Free the fake Segments */
137
138 free(segments);
139 }
140
141
142 /*++++++++++++++++++++++++++++++++++++++
143 Find the first segment with a particular starting node.
144
145 SegmentX **FindFirstSegmentX Returns a pointer to the first extended segment with the specified id.
146
147 SegmentsX* segmentsx The set of segments to process.
148
149 node_t node The node to look for.
150 ++++++++++++++++++++++++++++++++++++++*/
151
152 SegmentX **FindFirstSegmentX(SegmentsX* segmentsx,node_t node)
153 {
154 int start=0;
155 int end=segmentsx->number-1;
156 int mid;
157 int found;
158
159 assert(segmentsx->sorted); /* Must be sorted */
160
161 /* Binary search - search key exact match only is required.
162 *
163 * # <- start | Check mid and move start or end if it doesn't match
164 * # |
165 * # | Since an exact match is wanted we can set end=mid-1
166 * # <- mid | or start=mid+1 because we know that mid doesn't match.
167 * # |
168 * # | Eventually either end=start or end=start+1 and one of
169 * # <- end | start or end is the wanted one.
170 */
171
172 if(end<start) /* There are no nodes */
173 return(NULL);
174 else if(node<segmentsx->ndata[start]->node1) /* Check key is not before start */
175 return(NULL);
176 else if(node>segmentsx->ndata[end]->node1) /* Check key is not after end */
177 return(NULL);
178 else
179 {
180 do
181 {
182 mid=(start+end)/2; /* Choose mid point */
183
184 if(segmentsx->ndata[mid]->node1<node) /* Mid point is too low */
185 start=mid;
186 else if(segmentsx->ndata[mid]->node1>node) /* Mid point is too high */
187 end=mid;
188 else /* Mid point is correct */
189 {found=mid; goto found;}
190 }
191 while((end-start)>1);
192
193 if(segmentsx->ndata[start]->node1==node) /* Start is correct */
194 {found=start; goto found;}
195
196 if(segmentsx->ndata[end]->node1==node) /* End is correct */
197 {found=end; goto found;}
198 }
199
200 return(NULL);
201
202 found:
203
204 while(found>0 && segmentsx->ndata[found-1]->node1==node)
205 found--;
206
207 return(&segmentsx->ndata[found]);
208 }
209
210
211 /*++++++++++++++++++++++++++++++++++++++
212 Find the next segment with a particular starting node.
213
214 SegmentX **FindNextSegmentX Returns a pointer to the next segment with the same id.
215
216 SegmentsX* segmentsx The set of segments to process.
217
218 SegmentX **segmentx The current segment.
219 ++++++++++++++++++++++++++++++++++++++*/
220
221 SegmentX **FindNextSegmentX(SegmentsX* segmentsx,SegmentX **segmentx)
222 {
223 SegmentX **next=segmentx+1;
224
225 if((next-segmentsx->ndata)==segmentsx->number)
226 return(NULL);
227
228 if((*next)->node1==(*segmentx)->node1)
229 return(next);
230
231 return(NULL);
232 }
233
234
235 /*++++++++++++++++++++++++++++++++++++++
236 Append a segment to a segment list.
237
238 SegmentsX* segmentsx The set of segments to process.
239
240 way_t way The way that the segment belongs to.
241
242 node_t node1 The first node in the segment.
243
244 node_t node2 The second node in the segment.
245 ++++++++++++++++++++++++++++++++++++++*/
246
247 void AppendSegment(SegmentsX* segmentsx,way_t way,node_t node1,node_t node2,distance_t distance)
248 {
249 /* Check that the array has enough space. */
250
251 if(segmentsx->xnumber==segmentsx->alloced)
252 {
253 segmentsx->alloced+=INCREMENT_SEGMENTS;
254
255 segmentsx->xdata=(SegmentX*)realloc((void*)segmentsx->xdata,segmentsx->alloced*sizeof(SegmentX));
256 }
257
258 /* Insert the segment */
259
260 segmentsx->xdata[segmentsx->xnumber].way=way;
261 segmentsx->xdata[segmentsx->xnumber].node1=node1;
262 segmentsx->xdata[segmentsx->xnumber].node2=node2;
263 segmentsx->xdata[segmentsx->xnumber].distance=distance;
264
265 segmentsx->xnumber++;
266
267 segmentsx->sorted=0;
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->ndata=realloc(segmentsx->ndata,segmentsx->xnumber*sizeof(SegmentX*));
287 else
288 segmentsx->ndata=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->ndata[segmentsx->number]=&segmentsx->xdata[i];
296 segmentsx->number++;
297 }
298
299 qsort(segmentsx->ndata,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=DISTANCE((*a)->distance);
338 distance_t b_distance=DISTANCE((*b)->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->ndata[i]->node1==segmentsx->ndata[i-1]->node1 &&
369 segmentsx->ndata[i]->node2==segmentsx->ndata[i-1]->node2)
370 {
371 duplicate++;
372 segmentsx->ndata[i-1]->node1=NO_NODE;
373 }
374 else if(segmentsx->ndata[i]->node1==segmentsx->ndata[i]->node2)
375 {
376 loop++;
377 segmentsx->ndata[i]->node1=NO_NODE;
378 }
379 else if(!FindNodeX(nodesx,segmentsx->ndata[i]->node1) ||
380 !FindNodeX(nodesx,segmentsx->ndata[i]->node2))
381 {
382 missing++;
383 segmentsx->ndata[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->ndata[i]->node1);
415 NodeX *node2=FindNodeX(nodesx,segmentsx->ndata[i]->node2);
416
417 /* Set the distance but preserve the ONEWAY_* flags */
418
419 segmentsx->ndata[i]->distance|=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->ndata[i]->node1>segmentsx->ndata[i]->node2)
450 {
451 segmentsx->ndata[i]->node1^=segmentsx->ndata[i]->node2;
452 segmentsx->ndata[i]->node2^=segmentsx->ndata[i]->node1;
453 segmentsx->ndata[i]->node1^=segmentsx->ndata[i]->node2;
454
455 if(segmentsx->ndata[i]->distance&(ONEWAY_2TO1|ONEWAY_1TO2))
456 segmentsx->ndata[i]->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->ndata[i]->node1==segmentsx->ndata[i-1]->node1 &&
492 segmentsx->ndata[i]->node2==segmentsx->ndata[i-1]->node2 &&
493 segmentsx->ndata[i]->distance==segmentsx->ndata[i-1]->distance)
494 {
495 WayX *wayx1=FindWayX(waysx,segmentsx->ndata[i-1]->way);
496 WayX *wayx2=FindWayX(waysx,segmentsx->ndata[i ]->way);
497
498 if(!WaysCompare(wayx1->way,wayx2->way))
499 {
500 segmentsx->ndata[i-1]->node1=NO_NODE;
501 segmentsx->ndata[i-1]->node2=NO_NODE;
502
503 duplicate++;
504 }
505 }
506
507 if(!((i+1)%10000))
508 {
509 printf("\rDeduplicating Segments: Segments=%d Duplicate=%d",i+1,duplicate);
510 fflush(stdout);
511 }
512 }
513
514 printf("\rDeduplicated Segments: Segments=%d Duplicate=%d \n",segmentsx->number,duplicate);
515 fflush(stdout);
516 }
517
518
519 /*++++++++++++++++++++++++++++++++++++++
520 Create the real segments data.
521
522 SegmentsX* segmentsx The set of segments to use.
523
524 WaysX* waysx The set of ways to use.
525 ++++++++++++++++++++++++++++++++++++++*/
526
527 void CreateRealSegments(SegmentsX *segmentsx,WaysX *waysx)
528 {
529 int i;
530
531 /* Allocate the memory */
532
533 segmentsx->sdata=(Segment*)malloc(segmentsx->number*sizeof(Segment));
534
535 /* Loop through and allocate. */
536
537 for(i=0;i<segmentsx->number;i++)
538 {
539 WayX *wayx=FindWayX(waysx,segmentsx->ndata[i]->way);
540
541 segmentsx->sdata[i].node1=0;
542 segmentsx->sdata[i].node2=0;
543 segmentsx->sdata[i].next2=NO_NODE;
544 segmentsx->sdata[i].way=wayx->way-waysx->wdata;
545 segmentsx->sdata[i].distance=segmentsx->ndata[i]->distance;
546
547 if(!((i+1)%10000))
548 {
549 printf("\rCreating Real Segments: Segments=%d",i+1);
550 fflush(stdout);
551 }
552 }
553
554 printf("\rCreating Real Segments: Segments=%d \n",segmentsx->number);
555 fflush(stdout);
556 }
557
558
559 /*++++++++++++++++++++++++++++++++++++++
560 Assign the nodes indexes to the segments.
561
562 SegmentsX* segmentsx The set of segments to process.
563
564 NodesX *nodesx The list of nodes to use.
565 ++++++++++++++++++++++++++++++++++++++*/
566
567 void IndexSegments(SegmentsX* segmentsx,NodesX *nodesx)
568 {
569 int i;
570
571 assert(segmentsx->sorted); /* Must be sorted */
572 assert(segmentsx->sdata); /* Must have real segments */
573 assert(nodesx->sorted); /* Must be sorted */
574
575 /* Index the segments */
576
577 for(i=0;i<nodesx->number;i++)
578 {
579 index_t index=SEGMENT(nodesx->gdata[i]->node.firstseg);
580
581 do
582 {
583 if(segmentsx->ndata[index]->node1==nodesx->gdata[i]->id)
584 {
585 segmentsx->sdata[index].node1=i;
586
587 index++;
588
589 if(index>=segmentsx->number || segmentsx->ndata[index]->node1!=nodesx->gdata[i]->id)
590 break;
591 }
592 else
593 {
594 segmentsx->sdata[index].node2=i;
595
596 if(segmentsx->sdata[index].next2==NO_NODE)
597 break;
598 else
599 index=segmentsx->sdata[index].next2;
600 }
601 }
602 while(1);
603
604 if(!((i+1)%10000))
605 {
606 printf("\rIndexing Nodes: Nodes=%d",i+1);
607 fflush(stdout);
608 }
609 }
610
611 printf("\rIndexed Nodes: Nodes=%d \n",nodesx->number);
612 fflush(stdout);
613 }
614
615
616 /*++++++++++++++++++++++++++++++++++++++
617 Calculate the distance between two nodes.
618
619 distance_t DistanceX Returns the distance between the extended nodes.
620
621 NodeX *nodex1 The starting node.
622
623 NodeX *nodex2 The end node.
624 ++++++++++++++++++++++++++++++++++++++*/
625
626 distance_t DistanceX(NodeX *nodex1,NodeX *nodex2)
627 {
628 float dlon = nodex1->longitude - nodex2->longitude;
629 float dlat = nodex1->latitude - nodex2->latitude;
630
631 float a1,a2,a,sa,c,d;
632
633 if(dlon==0 && dlat==0)
634 return 0;
635
636 a1 = sinf (dlat / 2);
637 a2 = sinf (dlon / 2);
638 a = (a1 * a1) + cosf (nodex1->latitude) * cosf (nodex2->latitude) * a2 * a2;
639 sa = sqrtf (a);
640 if (sa <= 1.0)
641 {c = 2 * asinf (sa);}
642 else
643 {c = 2 * asinf (1.0);}
644 d = 6378.137 * c;
645
646 return km_to_distance(d);
647 }

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