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 222 -
(hide annotations)
(download)
(as text)
Thu Jul 9 18:24:40 2009 UTC (15 years, 8 months ago) by amb
File MIME type: text/x-csrc
File size: 17234 byte(s)
Thu Jul 9 18:24:40 2009 UTC (15 years, 8 months ago) by amb
File MIME type: text/x-csrc
File size: 17234 byte(s)
Free memory correctly.
1 | amb | 110 | /*************************************** |
2 | amb | 222 | $Header: /home/amb/CVS/routino/src/segmentsx.c,v 1.22 2009-07-09 18:24:40 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 | |||
36 | |||
37 | /* Constants */ | ||
38 | |||
39 | amb | 216 | /*+ The array size increment for SegmentsX (UK is ~14.1M raw segments, this is ~53 increments). +*/ |
40 | #define INCREMENT_SEGMENTSX (256*1024) | ||
41 | amb | 110 | |
42 | |||
43 | /* Functions */ | ||
44 | |||
45 | amb | 204 | static int sort_by_id_and_distance(SegmentX **a,SegmentX **b); |
46 | amb | 110 | |
47 | |||
48 | /*++++++++++++++++++++++++++++++++++++++ | ||
49 | Allocate a new segment list. | ||
50 | |||
51 | SegmentsX *NewSegmentList Returns the segment list. | ||
52 | ++++++++++++++++++++++++++++++++++++++*/ | ||
53 | |||
54 | SegmentsX *NewSegmentList(void) | ||
55 | { | ||
56 | SegmentsX *segmentsx; | ||
57 | |||
58 | amb | 213 | segmentsx=(SegmentsX*)calloc(1,sizeof(SegmentsX)); |
59 | amb | 110 | |
60 | amb | 216 | segmentsx->row=-1; |
61 | |||
62 | amb | 110 | return(segmentsx); |
63 | } | ||
64 | |||
65 | |||
66 | /*++++++++++++++++++++++++++++++++++++++ | ||
67 | amb | 213 | Free a segment list (needed by planetsplitter for temporary super-segment lists). |
68 | amb | 110 | |
69 | SegmentsX *segmentsx The list to be freed. | ||
70 | ++++++++++++++++++++++++++++++++++++++*/ | ||
71 | |||
72 | void FreeSegmentList(SegmentsX *segmentsx) | ||
73 | { | ||
74 | amb | 209 | if(segmentsx->sdata) |
75 | free(segmentsx->sdata); | ||
76 | amb | 213 | if(segmentsx->ndata) |
77 | free(segmentsx->ndata); | ||
78 | if(segmentsx->xdata) | ||
79 | amb | 222 | { |
80 | int i; | ||
81 | for(i=0;i<segmentsx->row;i++) | ||
82 | free(segmentsx->xdata[i]); | ||
83 | amb | 213 | free(segmentsx->xdata); |
84 | amb | 222 | } |
85 | amb | 110 | free(segmentsx); |
86 | } | ||
87 | |||
88 | |||
89 | /*++++++++++++++++++++++++++++++++++++++ | ||
90 | Save the segment list to a file. | ||
91 | |||
92 | SegmentsX* segmentsx The set of segments to save. | ||
93 | |||
94 | const char *filename The name of the file to save. | ||
95 | ++++++++++++++++++++++++++++++++++++++*/ | ||
96 | |||
97 | void SaveSegmentList(SegmentsX* segmentsx,const char *filename) | ||
98 | { | ||
99 | amb | 214 | index_t i; |
100 | amb | 110 | int fd; |
101 | Segments *segments=calloc(1,sizeof(Segments)); | ||
102 | |||
103 | assert(segmentsx->sorted); /* Must be sorted */ | ||
104 | amb | 213 | assert(segmentsx->sdata); /* Must have sdata filled in */ |
105 | amb | 110 | |
106 | /* Fill in a Segments structure with the offset of the real data in the file after | ||
107 | the Segment structure itself. */ | ||
108 | |||
109 | segments->number=segmentsx->number; | ||
110 | segments->data=NULL; | ||
111 | segments->segments=(void*)sizeof(Segments); | ||
112 | |||
113 | /* Write out the Segments structure and then the real data. */ | ||
114 | |||
115 | fd=OpenFile(filename); | ||
116 | |||
117 | WriteFile(fd,segments,sizeof(Segments)); | ||
118 | |||
119 | amb | 203 | for(i=0;i<segments->number;i++) |
120 | amb | 132 | { |
121 | amb | 209 | WriteFile(fd,&segmentsx->sdata[i],sizeof(Segment)); |
122 | amb | 110 | |
123 | amb | 132 | if(!((i+1)%10000)) |
124 | { | ||
125 | printf("\rWriting Segments: Segments=%d",i+1); | ||
126 | fflush(stdout); | ||
127 | } | ||
128 | } | ||
129 | |||
130 | amb | 203 | printf("\rWrote Segments: Segments=%d \n",segments->number); |
131 | amb | 132 | fflush(stdout); |
132 | |||
133 | amb | 110 | CloseFile(fd); |
134 | |||
135 | /* Free the fake Segments */ | ||
136 | |||
137 | free(segments); | ||
138 | } | ||
139 | |||
140 | |||
141 | /*++++++++++++++++++++++++++++++++++++++ | ||
142 | Find the first segment with a particular starting node. | ||
143 | |||
144 | SegmentX **FindFirstSegmentX Returns a pointer to the first extended segment with the specified id. | ||
145 | |||
146 | SegmentsX* segmentsx The set of segments to process. | ||
147 | |||
148 | node_t node The node to look for. | ||
149 | ++++++++++++++++++++++++++++++++++++++*/ | ||
150 | |||
151 | SegmentX **FindFirstSegmentX(SegmentsX* segmentsx,node_t node) | ||
152 | { | ||
153 | int start=0; | ||
154 | int end=segmentsx->number-1; | ||
155 | int mid; | ||
156 | int found; | ||
157 | |||
158 | assert(segmentsx->sorted); /* Must be sorted */ | ||
159 | amb | 213 | assert(segmentsx->ndata); /* Must have ndata filled in */ |
160 | amb | 110 | |
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 | amb | 206 | else if(node<segmentsx->ndata[start]->node1) /* Check key is not before start */ |
175 | amb | 110 | return(NULL); |
176 | amb | 206 | else if(node>segmentsx->ndata[end]->node1) /* Check key is not after end */ |
177 | amb | 110 | return(NULL); |
178 | else | ||
179 | { | ||
180 | do | ||
181 | { | ||
182 | mid=(start+end)/2; /* Choose mid point */ | ||
183 | |||
184 | amb | 206 | if(segmentsx->ndata[mid]->node1<node) /* Mid point is too low */ |
185 | amb | 110 | start=mid; |
186 | amb | 206 | else if(segmentsx->ndata[mid]->node1>node) /* Mid point is too high */ |
187 | amb | 110 | end=mid; |
188 | else /* Mid point is correct */ | ||
189 | {found=mid; goto found;} | ||
190 | } | ||
191 | while((end-start)>1); | ||
192 | |||
193 | amb | 206 | if(segmentsx->ndata[start]->node1==node) /* Start is correct */ |
194 | amb | 110 | {found=start; goto found;} |
195 | |||
196 | amb | 206 | if(segmentsx->ndata[end]->node1==node) /* End is correct */ |
197 | amb | 110 | {found=end; goto found;} |
198 | } | ||
199 | |||
200 | return(NULL); | ||
201 | |||
202 | found: | ||
203 | |||
204 | amb | 206 | while(found>0 && segmentsx->ndata[found-1]->node1==node) |
205 | amb | 110 | found--; |
206 | |||
207 | amb | 206 | return(&segmentsx->ndata[found]); |
208 | amb | 110 | } |
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 | amb | 206 | if((next-segmentsx->ndata)==segmentsx->number) |
226 | amb | 110 | 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 | amb | 203 | way_t way The way that the segment belongs to. |
241 | |||
242 | amb | 110 | node_t node1 The first node in the segment. |
243 | |||
244 | node_t node2 The second node in the segment. | ||
245 | ++++++++++++++++++++++++++++++++++++++*/ | ||
246 | |||
247 | amb | 209 | void AppendSegment(SegmentsX* segmentsx,way_t way,node_t node1,node_t node2,distance_t distance) |
248 | amb | 110 | { |
249 | /* Check that the array has enough space. */ | ||
250 | |||
251 | amb | 216 | if(segmentsx->row==-1 || segmentsx->col==INCREMENT_SEGMENTSX) |
252 | amb | 110 | { |
253 | amb | 216 | segmentsx->row++; |
254 | segmentsx->col=0; | ||
255 | amb | 110 | |
256 | amb | 216 | if((segmentsx->row%16)==0) |
257 | segmentsx->xdata=(SegmentX**)realloc((void*)segmentsx->xdata,(segmentsx->row+16)*sizeof(SegmentX*)); | ||
258 | |||
259 | segmentsx->xdata[segmentsx->row]=(SegmentX*)malloc(INCREMENT_SEGMENTSX*sizeof(SegmentX)); | ||
260 | amb | 110 | } |
261 | |||
262 | /* Insert the segment */ | ||
263 | |||
264 | amb | 216 | segmentsx->xdata[segmentsx->row][segmentsx->col].way=way; |
265 | segmentsx->xdata[segmentsx->row][segmentsx->col].node1=node1; | ||
266 | segmentsx->xdata[segmentsx->row][segmentsx->col].node2=node2; | ||
267 | segmentsx->xdata[segmentsx->row][segmentsx->col].distance=distance; | ||
268 | amb | 110 | |
269 | amb | 216 | segmentsx->col++; |
270 | amb | 110 | |
271 | segmentsx->sorted=0; | ||
272 | } | ||
273 | |||
274 | |||
275 | /*++++++++++++++++++++++++++++++++++++++ | ||
276 | Sort the segment list. | ||
277 | |||
278 | SegmentsX* segmentsx The set of segments to process. | ||
279 | ++++++++++++++++++++++++++++++++++++++*/ | ||
280 | |||
281 | void SortSegmentList(SegmentsX* segmentsx) | ||
282 | { | ||
283 | amb | 214 | index_t i; |
284 | amb | 110 | |
285 | amb | 213 | assert(segmentsx->xdata); /* Must have xdata filled in */ |
286 | |||
287 | amb | 132 | printf("Sorting Segments"); fflush(stdout); |
288 | |||
289 | amb | 213 | /* Allocate the array of pointers and sort them */ |
290 | amb | 110 | |
291 | amb | 216 | segmentsx->ndata=(SegmentX**)realloc(segmentsx->ndata,(segmentsx->row*INCREMENT_SEGMENTSX+segmentsx->col)*sizeof(SegmentX*)); |
292 | amb | 110 | |
293 | segmentsx->number=0; | ||
294 | |||
295 | amb | 216 | for(i=0;i<(segmentsx->row*INCREMENT_SEGMENTSX+segmentsx->col);i++) |
296 | if(segmentsx->xdata[i/INCREMENT_SEGMENTSX][i%INCREMENT_SEGMENTSX].node1!=NO_NODE) | ||
297 | amb | 110 | { |
298 | amb | 216 | segmentsx->ndata[segmentsx->number]=&segmentsx->xdata[i/INCREMENT_SEGMENTSX][i%INCREMENT_SEGMENTSX]; |
299 | amb | 110 | segmentsx->number++; |
300 | } | ||
301 | |||
302 | amb | 206 | qsort(segmentsx->ndata,segmentsx->number,sizeof(SegmentX*),(int (*)(const void*,const void*))sort_by_id_and_distance); |
303 | amb | 110 | |
304 | amb | 213 | printf("\rSorted Segments \n"); fflush(stdout); |
305 | |||
306 | amb | 110 | segmentsx->sorted=1; |
307 | } | ||
308 | |||
309 | |||
310 | /*++++++++++++++++++++++++++++++++++++++ | ||
311 | amb | 204 | Sort the segments into id order and then distance order. |
312 | amb | 110 | |
313 | amb | 204 | int sort_by_id_and_distance Returns the comparison of the node fields. |
314 | amb | 110 | |
315 | SegmentX **a The first Segment. | ||
316 | |||
317 | SegmentX **b The second Segment. | ||
318 | ++++++++++++++++++++++++++++++++++++++*/ | ||
319 | |||
320 | amb | 204 | static int sort_by_id_and_distance(SegmentX **a,SegmentX **b) |
321 | amb | 110 | { |
322 | node_t a_id1=(*a)->node1; | ||
323 | node_t b_id1=(*b)->node1; | ||
324 | |||
325 | if(a_id1<b_id1) | ||
326 | return(-1); | ||
327 | else if(a_id1>b_id1) | ||
328 | return(1); | ||
329 | else /* if(a_id1==b_id1) */ | ||
330 | { | ||
331 | node_t a_id2=(*a)->node2; | ||
332 | node_t b_id2=(*b)->node2; | ||
333 | |||
334 | if(a_id2<b_id2) | ||
335 | return(-1); | ||
336 | else if(a_id2>b_id2) | ||
337 | return(1); | ||
338 | else | ||
339 | { | ||
340 | amb | 209 | distance_t a_distance=DISTANCE((*a)->distance); |
341 | distance_t b_distance=DISTANCE((*b)->distance); | ||
342 | amb | 110 | |
343 | if(a_distance<b_distance) | ||
344 | return(-1); | ||
345 | else if(a_distance>b_distance) | ||
346 | return(1); | ||
347 | else | ||
348 | return(0); | ||
349 | } | ||
350 | } | ||
351 | } | ||
352 | |||
353 | |||
354 | /*++++++++++++++++++++++++++++++++++++++ | ||
355 | Remove bad segments (zero length or duplicated). | ||
356 | |||
357 | amb | 195 | NodesX *nodesx The nodes to check. |
358 | |||
359 | amb | 110 | SegmentsX *segmentsx The segments to modify. |
360 | ++++++++++++++++++++++++++++++++++++++*/ | ||
361 | |||
362 | amb | 204 | void RemoveBadSegments(NodesX *nodesx,SegmentsX *segmentsx) |
363 | amb | 110 | { |
364 | amb | 214 | index_t i; |
365 | amb | 195 | int duplicate=0,loop=0,missing=0; |
366 | amb | 110 | |
367 | amb | 213 | assert(segmentsx->ndata); /* Must have ndata filled in */ |
368 | amb | 110 | |
369 | for(i=0;i<segmentsx->number;i++) | ||
370 | { | ||
371 | amb | 206 | if(i && segmentsx->ndata[i]->node1==segmentsx->ndata[i-1]->node1 && |
372 | segmentsx->ndata[i]->node2==segmentsx->ndata[i-1]->node2) | ||
373 | amb | 110 | { |
374 | duplicate++; | ||
375 | amb | 206 | segmentsx->ndata[i-1]->node1=NO_NODE; |
376 | amb | 110 | } |
377 | amb | 206 | else if(segmentsx->ndata[i]->node1==segmentsx->ndata[i]->node2) |
378 | amb | 110 | { |
379 | loop++; | ||
380 | amb | 206 | segmentsx->ndata[i]->node1=NO_NODE; |
381 | amb | 110 | } |
382 | amb | 206 | else if(!FindNodeX(nodesx,segmentsx->ndata[i]->node1) || |
383 | !FindNodeX(nodesx,segmentsx->ndata[i]->node2)) | ||
384 | amb | 195 | { |
385 | missing++; | ||
386 | amb | 206 | segmentsx->ndata[i]->node1=NO_NODE; |
387 | amb | 195 | } |
388 | amb | 110 | |
389 | if(!((i+1)%10000)) | ||
390 | { | ||
391 | amb | 195 | printf("\rChecking: Segments=%d Duplicate=%d Loop=%d Missing-Node=%d",i+1,duplicate,loop,missing); |
392 | amb | 110 | fflush(stdout); |
393 | } | ||
394 | } | ||
395 | |||
396 | amb | 195 | printf("\rChecked: Segments=%d Duplicate=%d Loop=%d Missing-Node=%d \n",segmentsx->number,duplicate,loop,missing); |
397 | amb | 110 | fflush(stdout); |
398 | } | ||
399 | |||
400 | |||
401 | /*++++++++++++++++++++++++++++++++++++++ | ||
402 | Measure the segments. | ||
403 | |||
404 | SegmentsX* segmentsx The set of segments to process. | ||
405 | |||
406 | NodesX *nodesx The list of nodes to use. | ||
407 | ++++++++++++++++++++++++++++++++++++++*/ | ||
408 | |||
409 | void MeasureSegments(SegmentsX* segmentsx,NodesX *nodesx) | ||
410 | { | ||
411 | amb | 214 | index_t i; |
412 | amb | 110 | |
413 | amb | 213 | assert(segmentsx->ndata); /* Must have ndata filled in */ |
414 | amb | 110 | |
415 | for(i=0;i<segmentsx->number;i++) | ||
416 | { | ||
417 | amb | 212 | NodeX **nodex1=FindNodeX(nodesx,segmentsx->ndata[i]->node1); |
418 | NodeX **nodex2=FindNodeX(nodesx,segmentsx->ndata[i]->node2); | ||
419 | amb | 110 | |
420 | /* Set the distance but preserve the ONEWAY_* flags */ | ||
421 | |||
422 | amb | 212 | segmentsx->ndata[i]->distance|=DISTANCE(DistanceX(*nodex1,*nodex2)); |
423 | amb | 110 | |
424 | if(!((i+1)%10000)) | ||
425 | { | ||
426 | printf("\rMeasuring Segments: Segments=%d",i+1); | ||
427 | fflush(stdout); | ||
428 | } | ||
429 | } | ||
430 | |||
431 | printf("\rMeasured Segments: Segments=%d \n",segmentsx->number); | ||
432 | fflush(stdout); | ||
433 | } | ||
434 | |||
435 | |||
436 | /*++++++++++++++++++++++++++++++++++++++ | ||
437 | Make the segments all point the same way (node1<node2). | ||
438 | |||
439 | SegmentsX* segmentsx The set of segments to process. | ||
440 | ++++++++++++++++++++++++++++++++++++++*/ | ||
441 | |||
442 | amb | 212 | void RotateSegments(SegmentsX* segmentsx) |
443 | amb | 110 | { |
444 | amb | 214 | index_t i; |
445 | int rotated=0; | ||
446 | amb | 110 | |
447 | amb | 213 | assert(segmentsx->ndata); /* Must have ndata filled in */ |
448 | amb | 110 | |
449 | for(i=0;i<segmentsx->number;i++) | ||
450 | { | ||
451 | amb | 206 | if(segmentsx->ndata[i]->node1>segmentsx->ndata[i]->node2) |
452 | amb | 110 | { |
453 | amb | 206 | segmentsx->ndata[i]->node1^=segmentsx->ndata[i]->node2; |
454 | segmentsx->ndata[i]->node2^=segmentsx->ndata[i]->node1; | ||
455 | segmentsx->ndata[i]->node1^=segmentsx->ndata[i]->node2; | ||
456 | amb | 110 | |
457 | amb | 209 | if(segmentsx->ndata[i]->distance&(ONEWAY_2TO1|ONEWAY_1TO2)) |
458 | segmentsx->ndata[i]->distance^=ONEWAY_2TO1|ONEWAY_1TO2; | ||
459 | amb | 110 | |
460 | rotated++; | ||
461 | } | ||
462 | |||
463 | if(!((i+1)%10000)) | ||
464 | { | ||
465 | printf("\rRotating Segments: Segments=%d Rotated=%d",i+1,rotated); | ||
466 | fflush(stdout); | ||
467 | } | ||
468 | } | ||
469 | |||
470 | printf("\rRotated Segments: Segments=%d Rotated=%d \n",segmentsx->number,rotated); | ||
471 | fflush(stdout); | ||
472 | } | ||
473 | |||
474 | |||
475 | /*++++++++++++++++++++++++++++++++++++++ | ||
476 | Mark the duplicate segments. | ||
477 | |||
478 | SegmentsX* segmentsx The set of segments to process. | ||
479 | |||
480 | WaysX *waysx The list of ways to use. | ||
481 | ++++++++++++++++++++++++++++++++++++++*/ | ||
482 | |||
483 | amb | 212 | void DeduplicateSegments(SegmentsX* segmentsx,WaysX *waysx) |
484 | amb | 110 | { |
485 | amb | 214 | index_t i; |
486 | int duplicate=0; | ||
487 | amb | 110 | |
488 | amb | 213 | assert(segmentsx->ndata); /* Must have ndata filled in */ |
489 | amb | 110 | |
490 | for(i=1;i<segmentsx->number;i++) | ||
491 | { | ||
492 | amb | 206 | if(segmentsx->ndata[i]->node1==segmentsx->ndata[i-1]->node1 && |
493 | segmentsx->ndata[i]->node2==segmentsx->ndata[i-1]->node2 && | ||
494 | amb | 221 | DISTFLAG(segmentsx->ndata[i]->distance)==DISTFLAG(segmentsx->ndata[i-1]->distance)) |
495 | amb | 110 | { |
496 | amb | 206 | WayX *wayx1=FindWayX(waysx,segmentsx->ndata[i-1]->way); |
497 | WayX *wayx2=FindWayX(waysx,segmentsx->ndata[i ]->way); | ||
498 | amb | 110 | |
499 | amb | 204 | if(!WaysCompare(wayx1->way,wayx2->way)) |
500 | amb | 110 | { |
501 | amb | 206 | segmentsx->ndata[i-1]->node1=NO_NODE; |
502 | segmentsx->ndata[i-1]->node2=NO_NODE; | ||
503 | amb | 110 | |
504 | duplicate++; | ||
505 | } | ||
506 | } | ||
507 | |||
508 | if(!((i+1)%10000)) | ||
509 | { | ||
510 | printf("\rDeduplicating Segments: Segments=%d Duplicate=%d",i+1,duplicate); | ||
511 | fflush(stdout); | ||
512 | } | ||
513 | } | ||
514 | |||
515 | printf("\rDeduplicated Segments: Segments=%d Duplicate=%d \n",segmentsx->number,duplicate); | ||
516 | fflush(stdout); | ||
517 | } | ||
518 | |||
519 | |||
520 | /*++++++++++++++++++++++++++++++++++++++ | ||
521 | amb | 209 | Create the real segments data. |
522 | |||
523 | SegmentsX* segmentsx The set of segments to use. | ||
524 | |||
525 | WaysX* waysx The set of ways to use. | ||
526 | ++++++++++++++++++++++++++++++++++++++*/ | ||
527 | |||
528 | void CreateRealSegments(SegmentsX *segmentsx,WaysX *waysx) | ||
529 | { | ||
530 | amb | 214 | index_t i; |
531 | amb | 209 | |
532 | amb | 213 | assert(segmentsx->ndata); /* Must have ndata filled in */ |
533 | |||
534 | amb | 209 | /* Allocate the memory */ |
535 | |||
536 | segmentsx->sdata=(Segment*)malloc(segmentsx->number*sizeof(Segment)); | ||
537 | |||
538 | /* Loop through and allocate. */ | ||
539 | |||
540 | for(i=0;i<segmentsx->number;i++) | ||
541 | { | ||
542 | WayX *wayx=FindWayX(waysx,segmentsx->ndata[i]->way); | ||
543 | |||
544 | segmentsx->sdata[i].node1=0; | ||
545 | segmentsx->sdata[i].node2=0; | ||
546 | segmentsx->sdata[i].next2=NO_NODE; | ||
547 | amb | 216 | segmentsx->sdata[i].way=IndexWayInWaysX(waysx,wayx); |
548 | amb | 209 | segmentsx->sdata[i].distance=segmentsx->ndata[i]->distance; |
549 | |||
550 | if(!((i+1)%10000)) | ||
551 | { | ||
552 | printf("\rCreating Real Segments: Segments=%d",i+1); | ||
553 | fflush(stdout); | ||
554 | } | ||
555 | } | ||
556 | |||
557 | printf("\rCreating Real Segments: Segments=%d \n",segmentsx->number); | ||
558 | fflush(stdout); | ||
559 | } | ||
560 | |||
561 | |||
562 | /*++++++++++++++++++++++++++++++++++++++ | ||
563 | amb | 110 | Assign the nodes indexes to the segments. |
564 | |||
565 | SegmentsX* segmentsx The set of segments to process. | ||
566 | |||
567 | NodesX *nodesx The list of nodes to use. | ||
568 | ++++++++++++++++++++++++++++++++++++++*/ | ||
569 | |||
570 | void IndexSegments(SegmentsX* segmentsx,NodesX *nodesx) | ||
571 | { | ||
572 | amb | 214 | index_t i; |
573 | amb | 110 | |
574 | assert(segmentsx->sorted); /* Must be sorted */ | ||
575 | amb | 213 | assert(segmentsx->ndata); /* Must have ndata filled in */ |
576 | assert(segmentsx->sdata); /* Must have sdata filled in */ | ||
577 | amb | 110 | assert(nodesx->sorted); /* Must be sorted */ |
578 | amb | 213 | assert(nodesx->gdata); /* Must have gdata filled in */ |
579 | amb | 110 | |
580 | /* Index the segments */ | ||
581 | |||
582 | for(i=0;i<nodesx->number;i++) | ||
583 | { | ||
584 | amb | 212 | NodeX **nodex=FindNodeX(nodesx,nodesx->gdata[i]->id); |
585 | Node *node =&nodesx->ndata[nodex-nodesx->idata]; | ||
586 | index_t index=SEGMENT(node->firstseg); | ||
587 | amb | 110 | |
588 | do | ||
589 | { | ||
590 | amb | 209 | if(segmentsx->ndata[index]->node1==nodesx->gdata[i]->id) |
591 | amb | 110 | { |
592 | amb | 209 | segmentsx->sdata[index].node1=i; |
593 | amb | 110 | |
594 | amb | 209 | index++; |
595 | amb | 128 | |
596 | amb | 209 | if(index>=segmentsx->number || segmentsx->ndata[index]->node1!=nodesx->gdata[i]->id) |
597 | break; | ||
598 | amb | 110 | } |
599 | else | ||
600 | { | ||
601 | amb | 209 | segmentsx->sdata[index].node2=i; |
602 | amb | 110 | |
603 | amb | 209 | if(segmentsx->sdata[index].next2==NO_NODE) |
604 | break; | ||
605 | amb | 110 | else |
606 | amb | 209 | index=segmentsx->sdata[index].next2; |
607 | amb | 110 | } |
608 | } | ||
609 | amb | 209 | while(1); |
610 | amb | 110 | |
611 | if(!((i+1)%10000)) | ||
612 | { | ||
613 | printf("\rIndexing Nodes: Nodes=%d",i+1); | ||
614 | fflush(stdout); | ||
615 | } | ||
616 | } | ||
617 | |||
618 | printf("\rIndexed Nodes: Nodes=%d \n",nodesx->number); | ||
619 | fflush(stdout); | ||
620 | } | ||
621 | |||
622 | |||
623 | /*++++++++++++++++++++++++++++++++++++++ | ||
624 | Calculate the distance between two nodes. | ||
625 | |||
626 | distance_t DistanceX Returns the distance between the extended nodes. | ||
627 | |||
628 | NodeX *nodex1 The starting node. | ||
629 | |||
630 | NodeX *nodex2 The end node. | ||
631 | ++++++++++++++++++++++++++++++++++++++*/ | ||
632 | |||
633 | distance_t DistanceX(NodeX *nodex1,NodeX *nodex2) | ||
634 | { | ||
635 | amb | 219 | double dlon = latlong_to_radians(nodex1->xlongitude) - latlong_to_radians(nodex2->xlongitude); |
636 | double dlat = latlong_to_radians(nodex1->xlatitude) - latlong_to_radians(nodex2->xlatitude); | ||
637 | double lat1 = latlong_to_radians(nodex1->xlatitude); | ||
638 | double lat2 = latlong_to_radians(nodex2->xlatitude); | ||
639 | amb | 110 | |
640 | amb | 219 | double a1,a2,a,sa,c,d; |
641 | amb | 110 | |
642 | if(dlon==0 && dlat==0) | ||
643 | return 0; | ||
644 | |||
645 | amb | 219 | a1 = sin (dlat / 2); |
646 | a2 = sin (dlon / 2); | ||
647 | a = (a1 * a1) + cos (lat1) * cos (lat2) * a2 * a2; | ||
648 | sa = sqrt (a); | ||
649 | amb | 110 | if (sa <= 1.0) |
650 | amb | 219 | {c = 2 * asin (sa);} |
651 | amb | 110 | else |
652 | amb | 219 | {c = 2 * asin (1.0);} |
653 | amb | 110 | d = 6378.137 * c; |
654 | |||
655 | return km_to_distance(d); | ||
656 | } |
Properties
Name | Value |
---|---|
cvs:description | Extended segments functions. |