Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino
Annotation of /trunk/src/segmentsx.c
Parent Directory
|
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)
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. |