Routino SVN Repository Browser

Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino

ViewVC logotype

Annotation of /trunk/src/segmentsx.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 252 - (hide annotations) (download) (as text)
Sat Sep 5 09:37:31 2009 UTC (15 years, 6 months ago) by amb
File MIME type: text/x-csrc
File size: 22549 byte(s)
Improve slim mode for nodes so that no data is not loaded into RAM at all.

1 amb 110 /***************************************
2 amb 252 $Header: /home/amb/CVS/routino/src/segmentsx.c,v 1.32 2009-09-05 09:37:31 amb Exp $
3 amb 110
4     Extended Segment data type functions.
5 amb 151
6     Part of the Routino routing software.
7 amb 110 ******************/ /******************
8 amb 151 This file Copyright 2008,2009 Andrew M. Bishop
9 amb 110
10 amb 151 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 amb 110 ***************************************/
23    
24    
25     #include <assert.h>
26     #include <math.h>
27     #include <stdlib.h>
28     #include <stdio.h>
29    
30     #include "types.h"
31     #include "functions.h"
32     #include "nodesx.h"
33     #include "segmentsx.h"
34     #include "waysx.h"
35 amb 228 #include "nodes.h"
36     #include "segments.h"
37     #include "ways.h"
38 amb 110
39    
40     /* Constants */
41    
42 amb 229 /*+ The array size increment for SegmentsX (UK is ~7.1M raw segments, this is ~53 increments). +*/
43     #define INCREMENT_SEGMENTSX (128*1024)
44 amb 110
45    
46 amb 228 /* Local Functions */
47 amb 110
48 amb 229 static int sort_by_id1_and_distance(SegmentX **a,SegmentX **b);
49     static int sort_by_id2_and_distance(SegmentX **a,SegmentX **b);
50     static SegmentX **find_first1_segmentx(SegmentsX* segmentsx,node_t node);
51     static SegmentX **find_first2_segmentx(SegmentsX* segmentsx,node_t node);
52 amb 228 static distance_t DistanceX(NodeX *nodex1,NodeX *nodex2);
53 amb 110
54    
55     /*++++++++++++++++++++++++++++++++++++++
56     Allocate a new segment list.
57    
58     SegmentsX *NewSegmentList Returns the segment list.
59     ++++++++++++++++++++++++++++++++++++++*/
60    
61     SegmentsX *NewSegmentList(void)
62     {
63     SegmentsX *segmentsx;
64    
65 amb 213 segmentsx=(SegmentsX*)calloc(1,sizeof(SegmentsX));
66 amb 110
67 amb 243 assert(segmentsx); /* Check calloc() worked */
68    
69 amb 216 segmentsx->row=-1;
70    
71 amb 110 return(segmentsx);
72     }
73    
74    
75     /*++++++++++++++++++++++++++++++++++++++
76 amb 226 Free a segment list.
77 amb 110
78     SegmentsX *segmentsx The list to be freed.
79     ++++++++++++++++++++++++++++++++++++++*/
80    
81     void FreeSegmentList(SegmentsX *segmentsx)
82     {
83 amb 213 if(segmentsx->xdata)
84 amb 222 {
85     int i;
86 amb 225 for(i=0;i<=segmentsx->row;i++)
87 amb 222 free(segmentsx->xdata[i]);
88 amb 213 free(segmentsx->xdata);
89 amb 222 }
90 amb 226
91 amb 229 if(segmentsx->n1data)
92     free(segmentsx->n1data);
93 amb 226
94 amb 229 if(segmentsx->n2data)
95     free(segmentsx->n2data);
96    
97 amb 226 if(segmentsx->sdata)
98     free(segmentsx->sdata);
99    
100 amb 110 free(segmentsx);
101     }
102    
103    
104     /*++++++++++++++++++++++++++++++++++++++
105     Save the segment list to a file.
106    
107     SegmentsX* segmentsx The set of segments to save.
108    
109     const char *filename The name of the file to save.
110     ++++++++++++++++++++++++++++++++++++++*/
111    
112     void SaveSegmentList(SegmentsX* segmentsx,const char *filename)
113     {
114 amb 214 index_t i;
115 amb 110 int fd;
116 amb 243 Segments *segments;
117 amb 232 int super_number=0,normal_number=0;
118 amb 110
119 amb 243 assert(segmentsx->sdata); /* Must have sdata filled in => real segments */
120 amb 110
121 amb 227 printf("Writing Segments: Segments=0");
122     fflush(stdout);
123    
124 amb 232 for(i=0;i<segmentsx->number;i++)
125     {
126     if(IsSuperSegment(&segmentsx->sdata[i]))
127     super_number++;
128     if(IsNormalSegment(&segmentsx->sdata[i]))
129     normal_number++;
130     }
131    
132 amb 110 /* Fill in a Segments structure with the offset of the real data in the file after
133     the Segment structure itself. */
134    
135 amb 243 segments=calloc(1,sizeof(Segments));
136    
137     assert(segments); /* Check calloc() worked */
138    
139 amb 110 segments->number=segmentsx->number;
140 amb 232 segments->snumber=super_number;
141     segments->nnumber=normal_number;
142    
143 amb 110 segments->data=NULL;
144 amb 232
145 amb 110 segments->segments=(void*)sizeof(Segments);
146    
147     /* Write out the Segments structure and then the real data. */
148    
149     fd=OpenFile(filename);
150    
151     WriteFile(fd,segments,sizeof(Segments));
152    
153 amb 203 for(i=0;i<segments->number;i++)
154 amb 132 {
155 amb 209 WriteFile(fd,&segmentsx->sdata[i],sizeof(Segment));
156 amb 110
157 amb 132 if(!((i+1)%10000))
158     {
159     printf("\rWriting Segments: Segments=%d",i+1);
160     fflush(stdout);
161     }
162     }
163    
164 amb 203 printf("\rWrote Segments: Segments=%d \n",segments->number);
165 amb 132 fflush(stdout);
166    
167 amb 110 CloseFile(fd);
168    
169     /* Free the fake Segments */
170    
171     free(segments);
172     }
173    
174    
175     /*++++++++++++++++++++++++++++++++++++++
176     Find the first segment with a particular starting node.
177    
178     SegmentX **FindFirstSegmentX Returns a pointer to the first extended segment with the specified id.
179    
180     SegmentsX* segmentsx The set of segments to process.
181    
182     node_t node The node to look for.
183     ++++++++++++++++++++++++++++++++++++++*/
184    
185     SegmentX **FindFirstSegmentX(SegmentsX* segmentsx,node_t node)
186     {
187 amb 229 SegmentX **first=find_first1_segmentx(segmentsx,node);
188    
189     if(first)
190     return(first);
191    
192     return(find_first2_segmentx(segmentsx,node));
193     }
194    
195    
196     /*++++++++++++++++++++++++++++++++++++++
197     Find the first segment with a particular starting node in either n1data or n2data.
198    
199     SegmentX **find_first1_segmentx Returns a pointer to the first extended segment with the specified id.
200    
201     SegmentsX* segmentsx The set of segments to process.
202    
203     node_t node The node to look for.
204     ++++++++++++++++++++++++++++++++++++++*/
205    
206     static SegmentX **find_first1_segmentx(SegmentsX* segmentsx,node_t node)
207     {
208 amb 110 int start=0;
209     int end=segmentsx->number-1;
210     int mid;
211     int found;
212    
213 amb 243 assert(segmentsx->n1data); /* Must have n1data filled in => sorted by node 1 */
214 amb 110
215     /* Binary search - search key exact match only is required.
216     *
217     * # <- start | Check mid and move start or end if it doesn't match
218     * # |
219     * # | Since an exact match is wanted we can set end=mid-1
220     * # <- mid | or start=mid+1 because we know that mid doesn't match.
221     * # |
222     * # | Eventually either end=start or end=start+1 and one of
223     * # <- end | start or end is the wanted one.
224     */
225    
226 amb 229 if(end<start) /* There are no nodes */
227 amb 110 return(NULL);
228 amb 229 else if(node<segmentsx->n1data[start]->node1) /* Check key is not before start */
229 amb 110 return(NULL);
230 amb 229 else if(node>segmentsx->n1data[end]->node1) /* Check key is not after end */
231 amb 110 return(NULL);
232     else
233     {
234     do
235     {
236 amb 229 mid=(start+end)/2; /* Choose mid point */
237 amb 110
238 amb 229 if(segmentsx->n1data[mid]->node1<node) /* Mid point is too low */
239 amb 110 start=mid;
240 amb 229 else if(segmentsx->n1data[mid]->node1>node) /* Mid point is too high */
241 amb 110 end=mid;
242 amb 229 else /* Mid point is correct */
243 amb 110 {found=mid; goto found;}
244     }
245     while((end-start)>1);
246    
247 amb 229 if(segmentsx->n1data[start]->node1==node) /* Start is correct */
248 amb 110 {found=start; goto found;}
249    
250 amb 229 if(segmentsx->n1data[end]->node1==node) /* End is correct */
251 amb 110 {found=end; goto found;}
252     }
253    
254     return(NULL);
255    
256     found:
257    
258 amb 229 while(found>0 && segmentsx->n1data[found-1]->node1==node)
259 amb 110 found--;
260    
261 amb 229 return(&segmentsx->n1data[found]);
262 amb 110 }
263    
264    
265     /*++++++++++++++++++++++++++++++++++++++
266 amb 229 Find the first segment with a particular starting node in node2.
267    
268     SegmentX **find_first2_segmentx Returns a pointer to the first extended segment with the specified id.
269    
270     SegmentsX* segmentsx The set of segments to process.
271    
272     node_t node The node to look for.
273     ++++++++++++++++++++++++++++++++++++++*/
274    
275     static SegmentX **find_first2_segmentx(SegmentsX* segmentsx,node_t node)
276     {
277     int start=0;
278     int end=segmentsx->number-1;
279     int mid;
280     int found;
281    
282 amb 243 assert(segmentsx->n2data); /* Must have n2data filled in => sorted by node 2 */
283 amb 229
284     /* Binary search - search key exact match only is required.
285     *
286     * # <- start | Check mid and move start or end if it doesn't match
287     * # |
288     * # | Since an exact match is wanted we can set end=mid-1
289     * # <- mid | or start=mid+1 because we know that mid doesn't match.
290     * # |
291     * # | Eventually either end=start or end=start+1 and one of
292     * # <- end | start or end is the wanted one.
293     */
294    
295     if(end<start) /* There are no nodes */
296     return(NULL);
297     else if(node<segmentsx->n2data[start]->node2) /* Check key is not before start */
298     return(NULL);
299     else if(node>segmentsx->n2data[end]->node2) /* Check key is not after end */
300     return(NULL);
301     else
302     {
303     do
304     {
305     mid=(start+end)/2; /* Choose mid point */
306    
307     if(segmentsx->n2data[mid]->node2<node) /* Mid point is too low */
308     start=mid;
309     else if(segmentsx->n2data[mid]->node2>node) /* Mid point is too high */
310     end=mid;
311     else /* Mid point is correct */
312     {found=mid; goto found;}
313     }
314     while((end-start)>1);
315    
316     if(segmentsx->n2data[start]->node2==node) /* Start is correct */
317     {found=start; goto found;}
318    
319     if(segmentsx->n2data[end]->node2==node) /* End is correct */
320     {found=end; goto found;}
321     }
322    
323     return(NULL);
324    
325     found:
326    
327     while(found>0 && segmentsx->n2data[found-1]->node2==node)
328     found--;
329    
330     return(&segmentsx->n2data[found]);
331     }
332    
333    
334     /*++++++++++++++++++++++++++++++++++++++
335 amb 110 Find the next segment with a particular starting node.
336    
337     SegmentX **FindNextSegmentX Returns a pointer to the next segment with the same id.
338    
339     SegmentsX* segmentsx The set of segments to process.
340    
341     SegmentX **segmentx The current segment.
342     ++++++++++++++++++++++++++++++++++++++*/
343    
344     SegmentX **FindNextSegmentX(SegmentsX* segmentsx,SegmentX **segmentx)
345     {
346 amb 229 if((segmentsx->n1data<segmentsx->n2data && segmentx<segmentsx->n2data) ||
347     (segmentsx->n1data>segmentsx->n2data && segmentx>segmentsx->n1data))
348     {
349     SegmentX **next=segmentx+1;
350 amb 110
351 amb 229 if((next-segmentsx->n1data)==segmentsx->number)
352     return(find_first2_segmentx(segmentsx,(*segmentx)->node1));
353 amb 110
354 amb 229 if((*next)->node1==(*segmentx)->node1)
355     return(next);
356 amb 110
357 amb 229 return(find_first2_segmentx(segmentsx,(*segmentx)->node1));
358     }
359     else
360     {
361     SegmentX **next=segmentx+1;
362    
363     if((next-segmentsx->n2data)==segmentsx->number)
364     return(NULL);
365    
366     if((*next)->node2==(*segmentx)->node2)
367     return(next);
368    
369     return(NULL);
370     }
371 amb 110 }
372    
373    
374     /*++++++++++++++++++++++++++++++++++++++
375     Append a segment to a segment list.
376    
377     SegmentsX* segmentsx The set of segments to process.
378    
379 amb 203 way_t way The way that the segment belongs to.
380    
381 amb 110 node_t node1 The first node in the segment.
382    
383     node_t node2 The second node in the segment.
384 amb 228
385     distance_t distance The distance between the nodes (or just the flags).
386 amb 110 ++++++++++++++++++++++++++++++++++++++*/
387    
388 amb 209 void AppendSegment(SegmentsX* segmentsx,way_t way,node_t node1,node_t node2,distance_t distance)
389 amb 110 {
390     /* Check that the array has enough space. */
391    
392 amb 216 if(segmentsx->row==-1 || segmentsx->col==INCREMENT_SEGMENTSX)
393 amb 110 {
394 amb 216 segmentsx->row++;
395     segmentsx->col=0;
396 amb 110
397 amb 216 if((segmentsx->row%16)==0)
398 amb 243 {
399 amb 216 segmentsx->xdata=(SegmentX**)realloc((void*)segmentsx->xdata,(segmentsx->row+16)*sizeof(SegmentX*));
400    
401 amb 243 assert(segmentsx->xdata); /* Check realloc() worked */
402     }
403    
404 amb 216 segmentsx->xdata[segmentsx->row]=(SegmentX*)malloc(INCREMENT_SEGMENTSX*sizeof(SegmentX));
405 amb 243
406     assert(segmentsx->xdata[segmentsx->row]); /* Check malloc() worked */
407 amb 110 }
408    
409     /* Insert the segment */
410    
411 amb 216 segmentsx->xdata[segmentsx->row][segmentsx->col].way=way;
412     segmentsx->xdata[segmentsx->row][segmentsx->col].distance=distance;
413 amb 110
414 amb 229 if(node1>node2)
415     {
416     segmentsx->xdata[segmentsx->row][segmentsx->col].node1=node2;
417     segmentsx->xdata[segmentsx->row][segmentsx->col].node2=node1;
418     if(distance&(ONEWAY_2TO1|ONEWAY_1TO2))
419     segmentsx->xdata[segmentsx->row][segmentsx->col].distance^=(ONEWAY_2TO1|ONEWAY_1TO2);
420     }
421     else
422     {
423     segmentsx->xdata[segmentsx->row][segmentsx->col].node1=node1;
424     segmentsx->xdata[segmentsx->row][segmentsx->col].node2=node2;
425     }
426    
427 amb 216 segmentsx->col++;
428 amb 110 }
429    
430    
431     /*++++++++++++++++++++++++++++++++++++++
432     Sort the segment list.
433    
434     SegmentsX* segmentsx The set of segments to process.
435     ++++++++++++++++++++++++++++++++++++++*/
436    
437     void SortSegmentList(SegmentsX* segmentsx)
438     {
439 amb 214 index_t i;
440 amb 110
441 amb 213 assert(segmentsx->xdata); /* Must have xdata filled in */
442    
443 amb 227 printf("Sorting Segments");
444     fflush(stdout);
445 amb 132
446 amb 213 /* Allocate the array of pointers and sort them */
447 amb 110
448 amb 229 segmentsx->n1data=(SegmentX**)realloc(segmentsx->n1data,(segmentsx->row*INCREMENT_SEGMENTSX+segmentsx->col)*sizeof(SegmentX*));
449     segmentsx->n2data=(SegmentX**)realloc(segmentsx->n2data,(segmentsx->row*INCREMENT_SEGMENTSX+segmentsx->col)*sizeof(SegmentX*));
450 amb 110
451 amb 243 assert(segmentsx->n1data); /* Check realloc() worked */
452     assert(segmentsx->n2data); /* Check realloc() worked */
453    
454 amb 110 segmentsx->number=0;
455    
456 amb 216 for(i=0;i<(segmentsx->row*INCREMENT_SEGMENTSX+segmentsx->col);i++)
457     if(segmentsx->xdata[i/INCREMENT_SEGMENTSX][i%INCREMENT_SEGMENTSX].node1!=NO_NODE)
458 amb 110 {
459 amb 229 segmentsx->n1data[segmentsx->number]=&segmentsx->xdata[i/INCREMENT_SEGMENTSX][i%INCREMENT_SEGMENTSX];
460     segmentsx->n2data[segmentsx->number]=&segmentsx->xdata[i/INCREMENT_SEGMENTSX][i%INCREMENT_SEGMENTSX];
461 amb 110 segmentsx->number++;
462     }
463    
464 amb 229 qsort(segmentsx->n1data,segmentsx->number,sizeof(SegmentX*),(int (*)(const void*,const void*))sort_by_id1_and_distance);
465     qsort(segmentsx->n2data,segmentsx->number,sizeof(SegmentX*),(int (*)(const void*,const void*))sort_by_id2_and_distance);
466 amb 110
467 amb 227 printf("\rSorted Segments \n");
468     fflush(stdout);
469 amb 110 }
470    
471    
472     /*++++++++++++++++++++++++++++++++++++++
473 amb 229 Sort the segments into id order (node1 then node2) and then distance order.
474 amb 110
475 amb 229 int sort_by_id1_and_distance Returns the comparison of the node fields.
476 amb 110
477     SegmentX **a The first Segment.
478    
479     SegmentX **b The second Segment.
480     ++++++++++++++++++++++++++++++++++++++*/
481    
482 amb 229 static int sort_by_id1_and_distance(SegmentX **a,SegmentX **b)
483 amb 110 {
484     node_t a_id1=(*a)->node1;
485     node_t b_id1=(*b)->node1;
486    
487     if(a_id1<b_id1)
488     return(-1);
489     else if(a_id1>b_id1)
490     return(1);
491     else /* if(a_id1==b_id1) */
492     {
493     node_t a_id2=(*a)->node2;
494     node_t b_id2=(*b)->node2;
495    
496     if(a_id2<b_id2)
497     return(-1);
498     else if(a_id2>b_id2)
499     return(1);
500     else
501     {
502 amb 229 distance_t a_distance=(*a)->distance;
503     distance_t b_distance=(*b)->distance;
504 amb 110
505     if(a_distance<b_distance)
506     return(-1);
507     else if(a_distance>b_distance)
508     return(1);
509     else
510     return(0);
511     }
512     }
513     }
514    
515    
516     /*++++++++++++++++++++++++++++++++++++++
517 amb 229 Sort the segments into id order (node2 then node1) and then distance order.
518    
519     int sort_by_id2_and_distance Returns the comparison of the node fields.
520    
521     SegmentX **a The first Segment.
522    
523     SegmentX **b The second Segment.
524     ++++++++++++++++++++++++++++++++++++++*/
525    
526     static int sort_by_id2_and_distance(SegmentX **a,SegmentX **b)
527     {
528     node_t a_id2=(*a)->node2;
529     node_t b_id2=(*b)->node2;
530    
531     if(a_id2<b_id2)
532     return(-1);
533     else if(a_id2>b_id2)
534     return(1);
535     else /* if(a_id2==b_id2) */
536     {
537     node_t a_id1=(*a)->node1;
538     node_t b_id1=(*b)->node1;
539    
540     if(a_id1<b_id1)
541     return(-1);
542     else if(a_id1>b_id1)
543     return(1);
544     else
545     {
546     distance_t a_distance=(*a)->distance;
547     distance_t b_distance=(*b)->distance;
548    
549     if(a_distance<b_distance)
550     return(-1);
551     else if(a_distance>b_distance)
552     return(1);
553     else
554     return(0);
555     }
556     }
557     }
558    
559    
560     /*++++++++++++++++++++++++++++++++++++++
561 amb 110 Remove bad segments (zero length or duplicated).
562    
563 amb 195 NodesX *nodesx The nodes to check.
564    
565 amb 110 SegmentsX *segmentsx The segments to modify.
566     ++++++++++++++++++++++++++++++++++++++*/
567    
568 amb 204 void RemoveBadSegments(NodesX *nodesx,SegmentsX *segmentsx)
569 amb 110 {
570 amb 214 index_t i;
571 amb 195 int duplicate=0,loop=0,missing=0;
572 amb 110
573 amb 243 assert(segmentsx->n1data); /* Must have n1data filled in => sorted by node 1 */
574 amb 110
575 amb 227 printf("Checking: Segments=0 Duplicate=0 Loop=0 Missing-Node=0");
576     fflush(stdout);
577    
578 amb 110 for(i=0;i<segmentsx->number;i++)
579     {
580 amb 229 if(i && segmentsx->n1data[i]->node1==segmentsx->n1data[i-1]->node1 &&
581     segmentsx->n1data[i]->node2==segmentsx->n1data[i-1]->node2)
582 amb 110 {
583     duplicate++;
584 amb 229 segmentsx->n1data[i-1]->node1=NO_NODE;
585 amb 110 }
586 amb 229 else if(segmentsx->n1data[i]->node1==segmentsx->n1data[i]->node2)
587 amb 110 {
588     loop++;
589 amb 229 segmentsx->n1data[i]->node1=NO_NODE;
590 amb 110 }
591 amb 249 else if(IndexNodeX(nodesx,segmentsx->n1data[i]->node1)==NO_NODE ||
592     IndexNodeX(nodesx,segmentsx->n1data[i]->node2)==NO_NODE)
593 amb 195 {
594     missing++;
595 amb 229 segmentsx->n1data[i]->node1=NO_NODE;
596 amb 195 }
597 amb 110
598     if(!((i+1)%10000))
599     {
600 amb 195 printf("\rChecking: Segments=%d Duplicate=%d Loop=%d Missing-Node=%d",i+1,duplicate,loop,missing);
601 amb 110 fflush(stdout);
602     }
603     }
604    
605 amb 195 printf("\rChecked: Segments=%d Duplicate=%d Loop=%d Missing-Node=%d \n",segmentsx->number,duplicate,loop,missing);
606 amb 110 fflush(stdout);
607     }
608    
609    
610     /*++++++++++++++++++++++++++++++++++++++
611     Measure the segments.
612    
613     SegmentsX* segmentsx The set of segments to process.
614    
615     NodesX *nodesx The list of nodes to use.
616     ++++++++++++++++++++++++++++++++++++++*/
617    
618     void MeasureSegments(SegmentsX* segmentsx,NodesX *nodesx)
619     {
620 amb 214 index_t i;
621 amb 110
622 amb 243 assert(segmentsx->n1data); /* Must have n1data filled in => sorted by node 1 */
623 amb 110
624 amb 227 printf("Measuring Segments: Segments=0");
625     fflush(stdout);
626    
627 amb 110 for(i=0;i<segmentsx->number;i++)
628     {
629 amb 252 NodeX *nodex1=FindNodeX(nodesx,segmentsx->n1data[i]->node1);
630     NodeX *nodex2=FindNodeX(nodesx,segmentsx->n1data[i]->node2);
631 amb 110
632     /* Set the distance but preserve the ONEWAY_* flags */
633    
634 amb 249 segmentsx->n1data[i]->distance|=DISTANCE(DistanceX(nodex1,nodex2));
635 amb 110
636     if(!((i+1)%10000))
637     {
638     printf("\rMeasuring Segments: Segments=%d",i+1);
639     fflush(stdout);
640     }
641     }
642    
643     printf("\rMeasured Segments: Segments=%d \n",segmentsx->number);
644     fflush(stdout);
645     }
646    
647    
648     /*++++++++++++++++++++++++++++++++++++++
649     Mark the duplicate segments.
650    
651     SegmentsX* segmentsx The set of segments to process.
652    
653     WaysX *waysx The list of ways to use.
654     ++++++++++++++++++++++++++++++++++++++*/
655    
656 amb 212 void DeduplicateSegments(SegmentsX* segmentsx,WaysX *waysx)
657 amb 110 {
658 amb 214 index_t i;
659     int duplicate=0;
660 amb 110
661 amb 243 assert(segmentsx->n1data); /* Must have n1data filled in => sorted by node 1 */
662 amb 110
663 amb 227 printf("Deduplicating Segments: Segments=0 Duplicate=0");
664     fflush(stdout);
665    
666 amb 110 for(i=1;i<segmentsx->number;i++)
667     {
668 amb 229 if(segmentsx->n1data[i]->node1==segmentsx->n1data[i-1]->node1 &&
669     segmentsx->n1data[i]->node2==segmentsx->n1data[i-1]->node2 &&
670     DISTFLAG(segmentsx->n1data[i]->distance)==DISTFLAG(segmentsx->n1data[i-1]->distance))
671 amb 110 {
672 amb 229 WayX *wayx1=FindWayX(waysx,segmentsx->n1data[i-1]->way);
673     WayX *wayx2=FindWayX(waysx,segmentsx->n1data[i ]->way);
674 amb 110
675 amb 204 if(!WaysCompare(wayx1->way,wayx2->way))
676 amb 110 {
677 amb 229 segmentsx->n1data[i-1]->node1=NO_NODE;
678 amb 110
679     duplicate++;
680     }
681     }
682    
683     if(!((i+1)%10000))
684     {
685     printf("\rDeduplicating Segments: Segments=%d Duplicate=%d",i+1,duplicate);
686     fflush(stdout);
687     }
688     }
689    
690 amb 229 printf("\rDeduplicated Segments: Segments=%d Duplicate=%d Unique=%d\n",segmentsx->number,duplicate,segmentsx->number-duplicate);
691 amb 110 fflush(stdout);
692     }
693    
694    
695     /*++++++++++++++++++++++++++++++++++++++
696 amb 209 Create the real segments data.
697    
698     SegmentsX* segmentsx The set of segments to use.
699    
700     WaysX* waysx The set of ways to use.
701     ++++++++++++++++++++++++++++++++++++++*/
702    
703     void CreateRealSegments(SegmentsX *segmentsx,WaysX *waysx)
704     {
705 amb 214 index_t i;
706 amb 209
707 amb 243 assert(segmentsx->n1data); /* Must have n1data filled in => sorted by node 1 */
708     assert(!segmentsx->sdata); /* Must not have sdata filled in => no real segments */
709 amb 213
710 amb 227 printf("Creating Real Segments: Segments=0");
711     fflush(stdout);
712    
713 amb 209 /* Allocate the memory */
714    
715     segmentsx->sdata=(Segment*)malloc(segmentsx->number*sizeof(Segment));
716    
717 amb 243 assert(segmentsx->sdata); /* Check malloc() worked */
718    
719 amb 209 /* Loop through and allocate. */
720    
721     for(i=0;i<segmentsx->number;i++)
722     {
723 amb 229 WayX *wayx=FindWayX(waysx,segmentsx->n1data[i]->way);
724 amb 209
725     segmentsx->sdata[i].node1=0;
726     segmentsx->sdata[i].node2=0;
727     segmentsx->sdata[i].next2=NO_NODE;
728 amb 216 segmentsx->sdata[i].way=IndexWayInWaysX(waysx,wayx);
729 amb 229 segmentsx->sdata[i].distance=segmentsx->n1data[i]->distance;
730 amb 209
731     if(!((i+1)%10000))
732     {
733     printf("\rCreating Real Segments: Segments=%d",i+1);
734     fflush(stdout);
735     }
736     }
737    
738     printf("\rCreating Real Segments: Segments=%d \n",segmentsx->number);
739     fflush(stdout);
740     }
741    
742    
743     /*++++++++++++++++++++++++++++++++++++++
744 amb 110 Assign the nodes indexes to the segments.
745    
746     SegmentsX* segmentsx The set of segments to process.
747    
748     NodesX *nodesx The list of nodes to use.
749     ++++++++++++++++++++++++++++++++++++++*/
750    
751     void IndexSegments(SegmentsX* segmentsx,NodesX *nodesx)
752     {
753 amb 214 index_t i;
754 amb 110
755 amb 243 assert(segmentsx->n1data); /* Must have n1data filled in => sorted by node 1 */
756     assert(segmentsx->sdata); /* Must have sdata filled in => real segments */
757     assert(nodesx->gdata); /* Must have gdata filled in => sorted geographically */
758 amb 110
759 amb 227 printf("Indexing Nodes: Nodes=0");
760     fflush(stdout);
761    
762 amb 110 /* Index the segments */
763    
764     for(i=0;i<nodesx->number;i++)
765     {
766 amb 252 Node *node =&nodesx->ndata[IndexNodeX(nodesx,nodesx->gdata[i])];
767 amb 212 index_t index=SEGMENT(node->firstseg);
768 amb 110
769     do
770     {
771 amb 252 if(segmentsx->n1data[index]->node1==nodesx->gdata[i])
772 amb 110 {
773 amb 209 segmentsx->sdata[index].node1=i;
774 amb 110
775 amb 209 index++;
776 amb 128
777 amb 252 if(index>=segmentsx->number || segmentsx->n1data[index]->node1!=nodesx->gdata[i])
778 amb 209 break;
779 amb 110 }
780     else
781     {
782 amb 209 segmentsx->sdata[index].node2=i;
783 amb 110
784 amb 209 if(segmentsx->sdata[index].next2==NO_NODE)
785     break;
786 amb 110 else
787 amb 209 index=segmentsx->sdata[index].next2;
788 amb 110 }
789     }
790 amb 209 while(1);
791 amb 110
792     if(!((i+1)%10000))
793     {
794     printf("\rIndexing Nodes: Nodes=%d",i+1);
795     fflush(stdout);
796     }
797     }
798    
799     printf("\rIndexed Nodes: Nodes=%d \n",nodesx->number);
800     fflush(stdout);
801     }
802    
803    
804     /*++++++++++++++++++++++++++++++++++++++
805     Calculate the distance between two nodes.
806    
807     distance_t DistanceX Returns the distance between the extended nodes.
808    
809     NodeX *nodex1 The starting node.
810    
811     NodeX *nodex2 The end node.
812     ++++++++++++++++++++++++++++++++++++++*/
813    
814 amb 228 static distance_t DistanceX(NodeX *nodex1,NodeX *nodex2)
815 amb 110 {
816 amb 223 double dlon = latlong_to_radians(nodex1->longitude) - latlong_to_radians(nodex2->longitude);
817     double dlat = latlong_to_radians(nodex1->latitude) - latlong_to_radians(nodex2->latitude);
818     double lat1 = latlong_to_radians(nodex1->latitude);
819     double lat2 = latlong_to_radians(nodex2->latitude);
820 amb 110
821 amb 219 double a1,a2,a,sa,c,d;
822 amb 110
823     if(dlon==0 && dlat==0)
824     return 0;
825    
826 amb 219 a1 = sin (dlat / 2);
827     a2 = sin (dlon / 2);
828     a = (a1 * a1) + cos (lat1) * cos (lat2) * a2 * a2;
829     sa = sqrt (a);
830 amb 110 if (sa <= 1.0)
831 amb 219 {c = 2 * asin (sa);}
832 amb 110 else
833 amb 219 {c = 2 * asin (1.0);}
834 amb 110 d = 6378.137 * c;
835    
836     return km_to_distance(d);
837     }

Properties

Name Value
cvs:description Extended segments functions.