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 326 -
(hide annotations)
(download)
(as text)
Fri Mar 19 19:47:10 2010 UTC (15 years ago) by amb
File MIME type: text/x-csrc
File size: 24799 byte(s)
Fri Mar 19 19:47:10 2010 UTC (15 years ago) by amb
File MIME type: text/x-csrc
File size: 24799 byte(s)
Allow planetsplitter to be run with a --parse-only or --process-only option and append to existing file or read from existing file.
1 | amb | 110 | /*************************************** |
2 | amb | 326 | $Header: /home/amb/CVS/routino/src/segmentsx.c,v 1.49 2010-03-19 19:47:09 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 | 326 | This file Copyright 2008-2010 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 | amb | 256 | #include <string.h> |
30 | amb | 326 | #include <sys/stat.h> |
31 | amb | 110 | |
32 | #include "types.h" | ||
33 | #include "functions.h" | ||
34 | #include "nodesx.h" | ||
35 | #include "segmentsx.h" | ||
36 | #include "waysx.h" | ||
37 | amb | 228 | #include "nodes.h" |
38 | #include "segments.h" | ||
39 | #include "ways.h" | ||
40 | amb | 110 | |
41 | |||
42 | amb | 256 | /* Variables */ |
43 | amb | 110 | |
44 | amb | 289 | /*+ The command line '--slim' option. +*/ |
45 | amb | 256 | extern int option_slim; |
46 | amb | 289 | |
47 | /*+ The command line '--tmpdir' option or its default value. +*/ | ||
48 | amb | 284 | extern char *option_tmpdirname; |
49 | amb | 110 | |
50 | amb | 228 | /* Local Functions */ |
51 | amb | 110 | |
52 | amb | 275 | static int sort_by_id(SegmentX *a,SegmentX *b); |
53 | |||
54 | amb | 228 | static distance_t DistanceX(NodeX *nodex1,NodeX *nodex2); |
55 | amb | 110 | |
56 | |||
57 | /*++++++++++++++++++++++++++++++++++++++ | ||
58 | amb | 326 | Allocate a new segment list (create a new file or open an existing one). |
59 | amb | 110 | |
60 | SegmentsX *NewSegmentList Returns the segment list. | ||
61 | amb | 326 | |
62 | int append Set to 1 if the file is to be opened for appending (now or later). | ||
63 | amb | 110 | ++++++++++++++++++++++++++++++++++++++*/ |
64 | |||
65 | amb | 326 | SegmentsX *NewSegmentList(int append) |
66 | amb | 110 | { |
67 | SegmentsX *segmentsx; | ||
68 | |||
69 | amb | 213 | segmentsx=(SegmentsX*)calloc(1,sizeof(SegmentsX)); |
70 | amb | 110 | |
71 | amb | 243 | assert(segmentsx); /* Check calloc() worked */ |
72 | |||
73 | amb | 284 | segmentsx->filename=(char*)malloc(strlen(option_tmpdirname)+32); |
74 | amb | 216 | |
75 | amb | 326 | if(append) |
76 | sprintf(segmentsx->filename,"%s/segments.input.tmp",option_tmpdirname); | ||
77 | else | ||
78 | sprintf(segmentsx->filename,"%s/segments.%p.tmp",option_tmpdirname,segmentsx); | ||
79 | amb | 256 | |
80 | amb | 326 | if(append) |
81 | { | ||
82 | struct stat buf; | ||
83 | |||
84 | segmentsx->fd=AppendFile(segmentsx->filename); | ||
85 | |||
86 | fstat(segmentsx->fd,&buf); | ||
87 | |||
88 | segmentsx->xnumber=buf.st_size/sizeof(SegmentX); | ||
89 | } | ||
90 | else | ||
91 | segmentsx->fd=OpenFile(segmentsx->filename); | ||
92 | |||
93 | amb | 110 | return(segmentsx); |
94 | } | ||
95 | |||
96 | |||
97 | /*++++++++++++++++++++++++++++++++++++++ | ||
98 | amb | 226 | Free a segment list. |
99 | amb | 110 | |
100 | SegmentsX *segmentsx The list to be freed. | ||
101 | amb | 326 | |
102 | int keep Set to 1 if the file is to be kept. | ||
103 | amb | 110 | ++++++++++++++++++++++++++++++++++++++*/ |
104 | |||
105 | amb | 326 | void FreeSegmentList(SegmentsX *segmentsx,int keep) |
106 | amb | 110 | { |
107 | amb | 326 | if(!keep) |
108 | DeleteFile(segmentsx->filename); | ||
109 | |||
110 | amb | 283 | free(segmentsx->filename); |
111 | amb | 256 | |
112 | amb | 275 | if(segmentsx->idata) |
113 | free(segmentsx->idata); | ||
114 | amb | 226 | |
115 | amb | 279 | if(segmentsx->firstnode) |
116 | free(segmentsx->firstnode); | ||
117 | |||
118 | amb | 226 | if(segmentsx->sdata) |
119 | free(segmentsx->sdata); | ||
120 | |||
121 | amb | 110 | free(segmentsx); |
122 | } | ||
123 | |||
124 | |||
125 | /*++++++++++++++++++++++++++++++++++++++ | ||
126 | amb | 285 | Append a single segment to a segment list. |
127 | amb | 110 | |
128 | amb | 285 | SegmentsX* segmentsx The set of segments to process. |
129 | amb | 110 | |
130 | amb | 285 | way_t way The way that the segment belongs to. |
131 | |||
132 | node_t node1 The first node in the segment. | ||
133 | |||
134 | node_t node2 The second node in the segment. | ||
135 | |||
136 | distance_t distance The distance between the nodes (or just the flags). | ||
137 | amb | 110 | ++++++++++++++++++++++++++++++++++++++*/ |
138 | |||
139 | amb | 285 | void AppendSegment(SegmentsX* segmentsx,way_t way,node_t node1,node_t node2,distance_t distance) |
140 | amb | 110 | { |
141 | amb | 285 | SegmentX segmentx; |
142 | amb | 110 | |
143 | amb | 285 | assert(!segmentsx->idata); /* Must not have idata filled in => unsorted */ |
144 | amb | 281 | |
145 | amb | 285 | segmentx.node1=node1; |
146 | segmentx.node2=node2; | ||
147 | segmentx.way=way; | ||
148 | segmentx.distance=distance; | ||
149 | amb | 110 | |
150 | amb | 285 | WriteFile(segmentsx->fd,&segmentx,sizeof(SegmentX)); |
151 | amb | 281 | |
152 | amb | 285 | segmentsx->xnumber++; |
153 | } | ||
154 | amb | 227 | |
155 | amb | 281 | |
156 | amb | 285 | /*++++++++++++++++++++++++++++++++++++++ |
157 | Sort the segment list. | ||
158 | amb | 232 | |
159 | amb | 285 | SegmentsX* segmentsx The set of segments to process. |
160 | ++++++++++++++++++++++++++++++++++++++*/ | ||
161 | amb | 110 | |
162 | amb | 285 | void SortSegmentList(SegmentsX* segmentsx) |
163 | { | ||
164 | int fd; | ||
165 | amb | 243 | |
166 | amb | 285 | /* Check the start conditions */ |
167 | amb | 243 | |
168 | amb | 285 | assert(!segmentsx->idata); /* Must not have idata filled in => unsorted */ |
169 | amb | 232 | |
170 | amb | 285 | /* Print the start message */ |
171 | amb | 232 | |
172 | amb | 285 | printf("Sorting Segments"); |
173 | fflush(stdout); | ||
174 | amb | 110 | |
175 | amb | 285 | /* Close the files and re-open them (finished appending) */ |
176 | amb | 110 | |
177 | amb | 285 | CloseFile(segmentsx->fd); |
178 | segmentsx->fd=ReOpenFile(segmentsx->filename); | ||
179 | amb | 110 | |
180 | amb | 285 | DeleteFile(segmentsx->filename); |
181 | amb | 110 | |
182 | amb | 285 | fd=OpenFile(segmentsx->filename); |
183 | amb | 110 | |
184 | amb | 285 | /* Sort by node indexes */ |
185 | amb | 132 | |
186 | amb | 311 | filesort_fixed(segmentsx->fd,fd,sizeof(SegmentX),(int (*)(const void*,const void*))sort_by_id,NULL); |
187 | amb | 285 | |
188 | segmentsx->number=segmentsx->xnumber; | ||
189 | |||
190 | /* Close the files and re-open them */ | ||
191 | |||
192 | CloseFile(segmentsx->fd); | ||
193 | amb | 281 | CloseFile(fd); |
194 | |||
195 | amb | 285 | segmentsx->fd=ReOpenFile(segmentsx->filename); |
196 | |||
197 | amb | 281 | /* Print the final message */ |
198 | |||
199 | amb | 285 | printf("\rSorted Segments: Segments=%d\n",segmentsx->xnumber); |
200 | amb | 132 | fflush(stdout); |
201 | amb | 110 | } |
202 | |||
203 | |||
204 | /*++++++++++++++++++++++++++++++++++++++ | ||
205 | amb | 285 | Sort the segments into id order (node1 then node2). |
206 | amb | 110 | |
207 | amb | 285 | int sort_by_id Returns the comparison of the node fields. |
208 | amb | 110 | |
209 | amb | 285 | SegmentX *a The first segment. |
210 | amb | 110 | |
211 | amb | 285 | SegmentX *b The second segment. |
212 | amb | 256 | ++++++++++++++++++++++++++++++++++++++*/ |
213 | |||
214 | amb | 285 | static int sort_by_id(SegmentX *a,SegmentX *b) |
215 | amb | 256 | { |
216 | amb | 285 | node_t a_id1=a->node1; |
217 | node_t b_id1=b->node1; | ||
218 | amb | 256 | |
219 | amb | 285 | if(a_id1<b_id1) |
220 | return(-1); | ||
221 | else if(a_id1>b_id1) | ||
222 | return(1); | ||
223 | else /* if(a_id1==b_id1) */ | ||
224 | amb | 256 | { |
225 | amb | 285 | node_t a_id2=a->node2; |
226 | node_t b_id2=b->node2; | ||
227 | amb | 256 | |
228 | amb | 285 | if(a_id2<b_id2) |
229 | return(-1); | ||
230 | else if(a_id2>b_id2) | ||
231 | return(1); | ||
232 | else | ||
233 | { | ||
234 | distance_t a_distance=a->distance; | ||
235 | distance_t b_distance=b->distance; | ||
236 | amb | 256 | |
237 | amb | 285 | if(a_distance<b_distance) |
238 | return(-1); | ||
239 | else if(a_distance>b_distance) | ||
240 | return(1); | ||
241 | else | ||
242 | return(0); | ||
243 | } | ||
244 | amb | 256 | } |
245 | } | ||
246 | |||
247 | |||
248 | /*++++++++++++++++++++++++++++++++++++++ | ||
249 | amb | 275 | Find the first segment index with a particular starting node. |
250 | amb | 257 | |
251 | amb | 275 | index_t IndexFirstSegmentX Returns a pointer to the index of the first extended segment with the specified id. |
252 | amb | 256 | |
253 | SegmentsX* segmentsx The set of segments to process. | ||
254 | |||
255 | amb | 110 | node_t node The node to look for. |
256 | ++++++++++++++++++++++++++++++++++++++*/ | ||
257 | |||
258 | amb | 275 | index_t IndexFirstSegmentX(SegmentsX* segmentsx,node_t node) |
259 | amb | 110 | { |
260 | int start=0; | ||
261 | int end=segmentsx->number-1; | ||
262 | int mid; | ||
263 | int found; | ||
264 | |||
265 | amb | 280 | /* Check if the first node index exists */ |
266 | |||
267 | amb | 279 | if(segmentsx->firstnode) |
268 | { | ||
269 | index_t index=segmentsx->firstnode[node]; | ||
270 | |||
271 | if(segmentsx->firstnode[node+1]==index) | ||
272 | return(NO_SEGMENT); | ||
273 | |||
274 | return(index); | ||
275 | } | ||
276 | |||
277 | amb | 275 | assert(segmentsx->idata); /* Must have idata filled in => sorted by node 1 */ |
278 | amb | 110 | |
279 | /* Binary search - search key exact match only is required. | ||
280 | * | ||
281 | * # <- start | Check mid and move start or end if it doesn't match | ||
282 | * # | | ||
283 | * # | Since an exact match is wanted we can set end=mid-1 | ||
284 | * # <- mid | or start=mid+1 because we know that mid doesn't match. | ||
285 | * # | | ||
286 | * # | Eventually either end=start or end=start+1 and one of | ||
287 | * # <- end | start or end is the wanted one. | ||
288 | */ | ||
289 | |||
290 | amb | 275 | if(end<start) /* There are no nodes */ |
291 | return(NO_SEGMENT); | ||
292 | else if(node<segmentsx->idata[start]) /* Check key is not before start */ | ||
293 | return(NO_SEGMENT); | ||
294 | else if(node>segmentsx->idata[end]) /* Check key is not after end */ | ||
295 | return(NO_SEGMENT); | ||
296 | amb | 257 | else |
297 | amb | 110 | { |
298 | amb | 257 | do |
299 | { | ||
300 | amb | 275 | mid=(start+end)/2; /* Choose mid point */ |
301 | amb | 110 | |
302 | amb | 275 | if(segmentsx->idata[mid]<node) /* Mid point is too low */ |
303 | amb | 257 | start=mid; |
304 | amb | 275 | else if(segmentsx->idata[mid]>node) /* Mid point is too high */ |
305 | amb | 257 | end=mid; |
306 | amb | 275 | else /* Mid point is correct */ |
307 | amb | 257 | {found=mid; goto found;} |
308 | } | ||
309 | while((end-start)>1); | ||
310 | amb | 110 | |
311 | amb | 275 | if(segmentsx->idata[start]==node) /* Start is correct */ |
312 | amb | 257 | {found=start; goto found;} |
313 | |||
314 | amb | 275 | if(segmentsx->idata[end]==node) /* End is correct */ |
315 | amb | 257 | {found=end; goto found;} |
316 | amb | 110 | } |
317 | |||
318 | amb | 275 | return(NO_SEGMENT); |
319 | amb | 110 | |
320 | found: | ||
321 | |||
322 | amb | 275 | while(found>0 && segmentsx->idata[found-1]==node) |
323 | amb | 110 | found--; |
324 | |||
325 | amb | 275 | return(found); |
326 | amb | 110 | } |
327 | |||
328 | |||
329 | /*++++++++++++++++++++++++++++++++++++++ | ||
330 | amb | 257 | Find the next segment index with a particular starting node. |
331 | amb | 110 | |
332 | amb | 275 | index_t IndexNextSegmentX Returns the index of the next segment with the same id. |
333 | amb | 110 | |
334 | SegmentsX* segmentsx The set of segments to process. | ||
335 | |||
336 | amb | 279 | index_t segindex The current segment index. |
337 | |||
338 | index_t nodeindex The node index. | ||
339 | amb | 110 | ++++++++++++++++++++++++++++++++++++++*/ |
340 | |||
341 | amb | 279 | index_t IndexNextSegmentX(SegmentsX* segmentsx,index_t segindex,index_t nodeindex) |
342 | amb | 110 | { |
343 | amb | 279 | assert(segmentsx->firstnode); /* Must have firstnode filled in => segments updated */ |
344 | |||
345 | if(++segindex==segmentsx->firstnode[nodeindex+1]) | ||
346 | amb | 275 | return(NO_SEGMENT); |
347 | amb | 229 | else |
348 | amb | 279 | return(segindex); |
349 | amb | 110 | } |
350 | |||
351 | |||
352 | /*++++++++++++++++++++++++++++++++++++++ | ||
353 | amb | 285 | Lookup a particular segment. |
354 | amb | 110 | |
355 | amb | 285 | SegmentX *LookupSegmentX Returns a pointer to the extended segment with the specified id. |
356 | amb | 110 | |
357 | amb | 256 | SegmentsX* segmentsx The set of segments to process. |
358 | |||
359 | amb | 285 | index_t index The segment index to look for. |
360 | amb | 256 | |
361 | amb | 285 | int position The position in the cache to use. |
362 | amb | 110 | ++++++++++++++++++++++++++++++++++++++*/ |
363 | |||
364 | amb | 285 | SegmentX *LookupSegmentX(SegmentsX* segmentsx,index_t index,int position) |
365 | amb | 110 | { |
366 | amb | 285 | assert(index!=NO_SEGMENT); /* Must be a valid segment */ |
367 | amb | 275 | |
368 | amb | 285 | if(option_slim) |
369 | amb | 110 | { |
370 | amb | 285 | SeekFile(segmentsx->fd,index*sizeof(SegmentX)); |
371 | amb | 110 | |
372 | amb | 285 | ReadFile(segmentsx->fd,&segmentsx->cached[position-1],sizeof(SegmentX)); |
373 | amb | 110 | |
374 | amb | 285 | return(&segmentsx->cached[position-1]); |
375 | amb | 110 | } |
376 | amb | 285 | else |
377 | { | ||
378 | return(&segmentsx->xdata[index]); | ||
379 | } | ||
380 | amb | 110 | } |
381 | |||
382 | |||
383 | /*++++++++++++++++++++++++++++++++++++++ | ||
384 | amb | 275 | Remove bad segments (duplicated, zero length or missing nodes). |
385 | amb | 110 | |
386 | amb | 195 | NodesX *nodesx The nodes to check. |
387 | |||
388 | amb | 110 | SegmentsX *segmentsx The segments to modify. |
389 | ++++++++++++++++++++++++++++++++++++++*/ | ||
390 | |||
391 | amb | 204 | void RemoveBadSegments(NodesX *nodesx,SegmentsX *segmentsx) |
392 | amb | 110 | { |
393 | amb | 275 | int duplicate=0,loop=0,missing=0,good=0,total=0; |
394 | SegmentX segmentx; | ||
395 | int fd; | ||
396 | node_t prevnode1=NO_NODE,prevnode2=NO_NODE; | ||
397 | amb | 110 | |
398 | amb | 275 | /* Print the start message */ |
399 | |||
400 | amb | 227 | printf("Checking: Segments=0 Duplicate=0 Loop=0 Missing-Node=0"); |
401 | fflush(stdout); | ||
402 | |||
403 | amb | 279 | /* Allocate the array of indexes */ |
404 | |||
405 | segmentsx->idata=(node_t*)malloc(segmentsx->xnumber*sizeof(node_t)); | ||
406 | |||
407 | assert(segmentsx->idata); /* Check malloc() worked */ | ||
408 | |||
409 | amb | 275 | /* Modify the on-disk image */ |
410 | |||
411 | DeleteFile(segmentsx->filename); | ||
412 | |||
413 | fd=OpenFile(segmentsx->filename); | ||
414 | SeekFile(segmentsx->fd,0); | ||
415 | |||
416 | while(!ReadFile(segmentsx->fd,&segmentx,sizeof(SegmentX))) | ||
417 | amb | 110 | { |
418 | amb | 275 | if(prevnode1==segmentx.node1 && prevnode2==segmentx.node2) |
419 | duplicate++; | ||
420 | else if(segmentx.node1==segmentx.node2) | ||
421 | amb | 257 | loop++; |
422 | amb | 275 | else if(IndexNodeX(nodesx,segmentx.node1)==NO_NODE || |
423 | IndexNodeX(nodesx,segmentx.node2)==NO_NODE) | ||
424 | missing++; | ||
425 | else | ||
426 | amb | 257 | { |
427 | amb | 275 | WriteFile(fd,&segmentx,sizeof(SegmentX)); |
428 | |||
429 | amb | 279 | segmentsx->idata[good]=segmentx.node1; |
430 | amb | 275 | good++; |
431 | |||
432 | prevnode1=segmentx.node1; | ||
433 | prevnode2=segmentx.node2; | ||
434 | amb | 110 | } |
435 | |||
436 | amb | 275 | total++; |
437 | amb | 256 | |
438 | amb | 275 | if(!(total%10000)) |
439 | amb | 110 | { |
440 | amb | 275 | printf("\rChecking: Segments=%d Duplicate=%d Loop=%d Missing-Node=%d",total,duplicate,loop,missing); |
441 | amb | 110 | fflush(stdout); |
442 | } | ||
443 | } | ||
444 | |||
445 | amb | 275 | /* Close the files and re-open them */ |
446 | |||
447 | CloseFile(segmentsx->fd); | ||
448 | CloseFile(fd); | ||
449 | |||
450 | segmentsx->fd=ReOpenFile(segmentsx->filename); | ||
451 | |||
452 | segmentsx->number=good; | ||
453 | |||
454 | /* Print the final message */ | ||
455 | |||
456 | printf("\rChecked: Segments=%d Duplicate=%d Loop=%d Missing-Node=%d \n",total,duplicate,loop,missing); | ||
457 | amb | 110 | fflush(stdout); |
458 | } | ||
459 | |||
460 | |||
461 | /*++++++++++++++++++++++++++++++++++++++ | ||
462 | amb | 285 | Measure the segments and replace node/way ids with indexes. |
463 | amb | 110 | |
464 | SegmentsX* segmentsx The set of segments to process. | ||
465 | |||
466 | NodesX *nodesx The list of nodes to use. | ||
467 | amb | 279 | |
468 | WaysX *waysx The list of ways to use. | ||
469 | amb | 110 | ++++++++++++++++++++++++++++++++++++++*/ |
470 | |||
471 | amb | 279 | void UpdateSegments(SegmentsX* segmentsx,NodesX *nodesx,WaysX *waysx) |
472 | amb | 110 | { |
473 | amb | 279 | index_t index=0; |
474 | int i,fd; | ||
475 | amb | 256 | SegmentX segmentx; |
476 | amb | 110 | |
477 | amb | 275 | /* Print the start message */ |
478 | |||
479 | amb | 227 | printf("Measuring Segments: Segments=0"); |
480 | fflush(stdout); | ||
481 | |||
482 | amb | 275 | /* Map into memory */ |
483 | amb | 257 | |
484 | amb | 258 | if(!option_slim) |
485 | amb | 275 | nodesx->xdata=MapFile(nodesx->filename); |
486 | amb | 258 | |
487 | amb | 280 | /* Free the now-unneeded index */ |
488 | |||
489 | free(segmentsx->idata); | ||
490 | segmentsx->idata=NULL; | ||
491 | |||
492 | amb | 279 | /* Allocate the array of indexes */ |
493 | |||
494 | segmentsx->firstnode=(index_t*)malloc((nodesx->number+1)*sizeof(index_t)); | ||
495 | |||
496 | assert(segmentsx->firstnode); /* Check malloc() worked */ | ||
497 | |||
498 | for(i=0;i<nodesx->number;i++) | ||
499 | segmentsx->firstnode[i]=NO_SEGMENT; | ||
500 | |||
501 | segmentsx->firstnode[nodesx->number]=segmentsx->number; | ||
502 | |||
503 | amb | 275 | /* Modify the on-disk image */ |
504 | |||
505 | amb | 256 | DeleteFile(segmentsx->filename); |
506 | |||
507 | fd=OpenFile(segmentsx->filename); | ||
508 | SeekFile(segmentsx->fd,0); | ||
509 | |||
510 | while(!ReadFile(segmentsx->fd,&segmentx,sizeof(SegmentX))) | ||
511 | amb | 110 | { |
512 | amb | 279 | index_t node1=IndexNodeX(nodesx,segmentx.node1); |
513 | index_t node2=IndexNodeX(nodesx,segmentx.node2); | ||
514 | index_t way =IndexWayX (waysx ,segmentx.way); | ||
515 | amb | 110 | |
516 | amb | 279 | NodeX *nodex1=LookupNodeX(nodesx,node1,1); |
517 | NodeX *nodex2=LookupNodeX(nodesx,node2,2); | ||
518 | |||
519 | /* Replace the node and way ids with their indexes */ | ||
520 | |||
521 | segmentx.node1=node1; | ||
522 | segmentx.node2=node2; | ||
523 | segmentx.way =way; | ||
524 | |||
525 | amb | 275 | /* Set the distance but preserve the ONEWAY_* flags */ |
526 | |||
527 | segmentx.distance|=DISTANCE(DistanceX(nodex1,nodex2)); | ||
528 | |||
529 | amb | 279 | /* Set the first segment index in the nodes */ |
530 | |||
531 | if(index<segmentsx->firstnode[node1]) | ||
532 | segmentsx->firstnode[node1]=index; | ||
533 | |||
534 | /* Write the modified segment */ | ||
535 | |||
536 | amb | 275 | WriteFile(fd,&segmentx,sizeof(SegmentX)); |
537 | |||
538 | amb | 279 | index++; |
539 | amb | 275 | |
540 | amb | 279 | if(!(index%10000)) |
541 | amb | 257 | { |
542 | amb | 279 | printf("\rMeasuring Segments: Segments=%d",index); |
543 | amb | 275 | fflush(stdout); |
544 | } | ||
545 | } | ||
546 | amb | 110 | |
547 | amb | 275 | /* Close the files and re-open them */ |
548 | amb | 257 | |
549 | amb | 275 | CloseFile(segmentsx->fd); |
550 | CloseFile(fd); | ||
551 | |||
552 | segmentsx->fd=ReOpenFile(segmentsx->filename); | ||
553 | |||
554 | amb | 280 | /* Free the other now-unneeded indexes */ |
555 | amb | 279 | |
556 | free(nodesx->idata); | ||
557 | nodesx->idata=NULL; | ||
558 | |||
559 | free(waysx->idata); | ||
560 | waysx->idata=NULL; | ||
561 | |||
562 | amb | 275 | /* Unmap from memory */ |
563 | |||
564 | if(!option_slim) | ||
565 | nodesx->xdata=UnmapFile(nodesx->filename); | ||
566 | |||
567 | /* Print the final message */ | ||
568 | |||
569 | printf("\rMeasured Segments: Segments=%d \n",segmentsx->number); | ||
570 | fflush(stdout); | ||
571 | } | ||
572 | |||
573 | |||
574 | /*++++++++++++++++++++++++++++++++++++++ | ||
575 | Make the segments all point the same way (node1<node2). | ||
576 | |||
577 | SegmentsX* segmentsx The set of segments to process. | ||
578 | ++++++++++++++++++++++++++++++++++++++*/ | ||
579 | |||
580 | void RotateSegments(SegmentsX* segmentsx) | ||
581 | { | ||
582 | int index=0,rotated=0; | ||
583 | int fd; | ||
584 | SegmentX segmentx; | ||
585 | |||
586 | /* Check the start conditions */ | ||
587 | |||
588 | assert(!segmentsx->idata); /* Must not have idata filled in => not sorted by node 1 */ | ||
589 | |||
590 | /* Print the start message */ | ||
591 | |||
592 | printf("Rotating Segments: Segments=0 Rotated=0"); | ||
593 | fflush(stdout); | ||
594 | |||
595 | /* Close the files and re-open them (finished appending) */ | ||
596 | |||
597 | CloseFile(segmentsx->fd); | ||
598 | segmentsx->fd=ReOpenFile(segmentsx->filename); | ||
599 | |||
600 | DeleteFile(segmentsx->filename); | ||
601 | |||
602 | fd=OpenFile(segmentsx->filename); | ||
603 | |||
604 | /* Modify the file contents */ | ||
605 | |||
606 | while(!ReadFile(segmentsx->fd,&segmentx,sizeof(SegmentX))) | ||
607 | { | ||
608 | if(segmentx.node1>segmentx.node2) | ||
609 | { | ||
610 | node_t temp; | ||
611 | |||
612 | temp=segmentx.node1; | ||
613 | segmentx.node1=segmentx.node2; | ||
614 | segmentx.node2=temp; | ||
615 | |||
616 | if(segmentx.distance&(ONEWAY_2TO1|ONEWAY_1TO2)) | ||
617 | segmentx.distance^=ONEWAY_2TO1|ONEWAY_1TO2; | ||
618 | |||
619 | rotated++; | ||
620 | amb | 257 | } |
621 | amb | 110 | |
622 | amb | 256 | WriteFile(fd,&segmentx,sizeof(SegmentX)); |
623 | |||
624 | amb | 275 | index++; |
625 | amb | 256 | |
626 | amb | 275 | if(!(index%10000)) |
627 | amb | 110 | { |
628 | amb | 275 | printf("\rRotating Segments: Segments=%d Rotated=%d",index,rotated); |
629 | amb | 110 | fflush(stdout); |
630 | } | ||
631 | } | ||
632 | |||
633 | amb | 275 | /* Close the files and re-open them */ |
634 | |||
635 | amb | 256 | CloseFile(segmentsx->fd); |
636 | CloseFile(fd); | ||
637 | |||
638 | segmentsx->fd=ReOpenFile(segmentsx->filename); | ||
639 | |||
640 | amb | 275 | /* Print the final message */ |
641 | amb | 256 | |
642 | amb | 275 | printf("\rRotated Segments: Segments=%d Rotated=%d \n",index,rotated); |
643 | amb | 110 | fflush(stdout); |
644 | } | ||
645 | |||
646 | |||
647 | /*++++++++++++++++++++++++++++++++++++++ | ||
648 | amb | 275 | Remove the duplicate segments. |
649 | amb | 110 | |
650 | SegmentsX* segmentsx The set of segments to process. | ||
651 | |||
652 | amb | 279 | NodesX *nodesx The list of nodes to use. |
653 | |||
654 | amb | 110 | WaysX *waysx The list of ways to use. |
655 | ++++++++++++++++++++++++++++++++++++++*/ | ||
656 | |||
657 | amb | 279 | void DeduplicateSegments(SegmentsX* segmentsx,NodesX *nodesx,WaysX *waysx) |
658 | amb | 110 | { |
659 | amb | 275 | int duplicate=0,good=0; |
660 | index_t firstindex=0,index=0; | ||
661 | amb | 279 | int i,fd; |
662 | amb | 275 | SegmentX prevsegmentx[16],segmentx; |
663 | amb | 110 | |
664 | amb | 275 | /* Print the start message */ |
665 | |||
666 | amb | 227 | printf("Deduplicating Segments: Segments=0 Duplicate=0"); |
667 | fflush(stdout); | ||
668 | |||
669 | amb | 275 | /* Map into memory */ |
670 | amb | 256 | |
671 | amb | 275 | if(!option_slim) |
672 | waysx->xdata=MapFile(waysx->filename); | ||
673 | |||
674 | amb | 279 | /* Allocate the array of indexes */ |
675 | |||
676 | segmentsx->firstnode=(index_t*)malloc((nodesx->number+1)*sizeof(index_t)); | ||
677 | |||
678 | assert(segmentsx->firstnode); /* Check malloc() worked */ | ||
679 | |||
680 | for(i=0;i<nodesx->number;i++) | ||
681 | segmentsx->firstnode[i]=NO_SEGMENT; | ||
682 | |||
683 | segmentsx->firstnode[nodesx->number]=segmentsx->number; | ||
684 | |||
685 | amb | 275 | /* Modify the on-disk image */ |
686 | |||
687 | DeleteFile(segmentsx->filename); | ||
688 | |||
689 | fd=OpenFile(segmentsx->filename); | ||
690 | SeekFile(segmentsx->fd,0); | ||
691 | |||
692 | while(!ReadFile(segmentsx->fd,&segmentx,sizeof(SegmentX))) | ||
693 | amb | 110 | { |
694 | amb | 275 | int isduplicate=0; |
695 | amb | 256 | |
696 | amb | 275 | if(index && segmentx.node1==prevsegmentx[0].node1 && |
697 | segmentx.node2==prevsegmentx[0].node2) | ||
698 | amb | 110 | { |
699 | amb | 264 | index_t previndex=firstindex; |
700 | amb | 110 | |
701 | amb | 275 | while(previndex<index) |
702 | amb | 110 | { |
703 | amb | 275 | int offset=previndex-firstindex; |
704 | |||
705 | if(DISTFLAG(segmentx.distance)==DISTFLAG(prevsegmentx[offset].distance)) | ||
706 | amb | 264 | { |
707 | amb | 279 | WayX *wayx1=LookupWayX(waysx,prevsegmentx[offset].way,1); |
708 | WayX *wayx2=LookupWayX(waysx, segmentx .way,2); | ||
709 | amb | 110 | |
710 | amb | 275 | if(!WaysCompare(&wayx1->way,&wayx2->way)) |
711 | amb | 264 | { |
712 | amb | 275 | isduplicate=1; |
713 | duplicate++; | ||
714 | break; | ||
715 | amb | 264 | } |
716 | } | ||
717 | |||
718 | previndex++; | ||
719 | amb | 110 | } |
720 | amb | 275 | |
721 | assert((index-firstindex)<(sizeof(prevsegmentx)/sizeof(prevsegmentx[0]))); | ||
722 | |||
723 | prevsegmentx[index-firstindex]=segmentx; | ||
724 | amb | 110 | } |
725 | amb | 264 | else |
726 | { | ||
727 | amb | 275 | firstindex=index; |
728 | prevsegmentx[0]=segmentx; | ||
729 | amb | 264 | } |
730 | amb | 110 | |
731 | amb | 275 | if(!isduplicate) |
732 | amb | 110 | { |
733 | amb | 275 | WriteFile(fd,&segmentx,sizeof(SegmentX)); |
734 | |||
735 | amb | 279 | if(good<segmentsx->firstnode[segmentx.node1]) |
736 | segmentsx->firstnode[segmentx.node1]=good; | ||
737 | |||
738 | amb | 275 | good++; |
739 | } | ||
740 | |||
741 | index++; | ||
742 | |||
743 | if(!(index%10000)) | ||
744 | { | ||
745 | printf("\rDeduplicating Segments: Segments=%d Duplicate=%d",index,duplicate); | ||
746 | amb | 110 | fflush(stdout); |
747 | } | ||
748 | } | ||
749 | |||
750 | amb | 275 | /* Close the files and re-open them */ |
751 | |||
752 | CloseFile(segmentsx->fd); | ||
753 | CloseFile(fd); | ||
754 | |||
755 | segmentsx->fd=ReOpenFile(segmentsx->filename); | ||
756 | |||
757 | amb | 279 | segmentsx->number=good; |
758 | amb | 275 | |
759 | amb | 279 | /* Fix-up the firstnode index for the missing nodes */ |
760 | amb | 275 | |
761 | amb | 279 | for(i=nodesx->number-1;i>=0;i--) |
762 | if(segmentsx->firstnode[i]==NO_SEGMENT) | ||
763 | segmentsx->firstnode[i]=segmentsx->firstnode[i+1]; | ||
764 | amb | 275 | |
765 | /* Unmap from memory */ | ||
766 | |||
767 | if(!option_slim) | ||
768 | waysx->xdata=UnmapFile(waysx->filename); | ||
769 | |||
770 | /* Print the final message */ | ||
771 | |||
772 | printf("\rDeduplicated Segments: Segments=%d Duplicate=%d Unique=%d\n",index,duplicate,index-duplicate); | ||
773 | amb | 110 | fflush(stdout); |
774 | } | ||
775 | |||
776 | |||
777 | /*++++++++++++++++++++++++++++++++++++++ | ||
778 | amb | 209 | Create the real segments data. |
779 | |||
780 | SegmentsX* segmentsx The set of segments to use. | ||
781 | |||
782 | WaysX* waysx The set of ways to use. | ||
783 | ++++++++++++++++++++++++++++++++++++++*/ | ||
784 | |||
785 | void CreateRealSegments(SegmentsX *segmentsx,WaysX *waysx) | ||
786 | { | ||
787 | amb | 214 | index_t i; |
788 | amb | 209 | |
789 | amb | 275 | /* Check the start conditions */ |
790 | |||
791 | amb | 243 | assert(!segmentsx->sdata); /* Must not have sdata filled in => no real segments */ |
792 | amb | 213 | |
793 | amb | 275 | /* Print the start message */ |
794 | |||
795 | amb | 227 | printf("Creating Real Segments: Segments=0"); |
796 | fflush(stdout); | ||
797 | |||
798 | amb | 275 | /* Map into memory */ |
799 | amb | 209 | |
800 | amb | 275 | if(!option_slim) |
801 | { | ||
802 | segmentsx->xdata=MapFile(segmentsx->filename); | ||
803 | waysx->xdata=MapFile(waysx->filename); | ||
804 | } | ||
805 | |||
806 | amb | 280 | /* Free the unneeded memory */ |
807 | |||
808 | free(segmentsx->firstnode); | ||
809 | segmentsx->firstnode=NULL; | ||
810 | |||
811 | amb | 279 | /* Allocate the memory */ |
812 | amb | 275 | |
813 | amb | 209 | segmentsx->sdata=(Segment*)malloc(segmentsx->number*sizeof(Segment)); |
814 | |||
815 | amb | 243 | assert(segmentsx->sdata); /* Check malloc() worked */ |
816 | |||
817 | amb | 275 | /* Loop through and fill */ |
818 | amb | 209 | |
819 | for(i=0;i<segmentsx->number;i++) | ||
820 | { | ||
821 | amb | 275 | SegmentX *segmentx=LookupSegmentX(segmentsx,i,1); |
822 | amb | 279 | WayX *wayx=LookupWayX(waysx,segmentx->way,1); |
823 | amb | 209 | |
824 | segmentsx->sdata[i].node1=0; | ||
825 | segmentsx->sdata[i].node2=0; | ||
826 | segmentsx->sdata[i].next2=NO_NODE; | ||
827 | amb | 310 | segmentsx->sdata[i].way=wayx->prop; |
828 | amb | 256 | segmentsx->sdata[i].distance=segmentx->distance; |
829 | amb | 209 | |
830 | if(!((i+1)%10000)) | ||
831 | { | ||
832 | printf("\rCreating Real Segments: Segments=%d",i+1); | ||
833 | fflush(stdout); | ||
834 | } | ||
835 | } | ||
836 | |||
837 | amb | 275 | /* Unmap from memory */ |
838 | |||
839 | if(!option_slim) | ||
840 | { | ||
841 | segmentsx->xdata=UnmapFile(segmentsx->filename); | ||
842 | waysx->xdata=UnmapFile(waysx->filename); | ||
843 | } | ||
844 | |||
845 | /* Print the final message */ | ||
846 | |||
847 | amb | 209 | printf("\rCreating Real Segments: Segments=%d \n",segmentsx->number); |
848 | fflush(stdout); | ||
849 | } | ||
850 | |||
851 | |||
852 | /*++++++++++++++++++++++++++++++++++++++ | ||
853 | amb | 110 | Assign the nodes indexes to the segments. |
854 | |||
855 | SegmentsX* segmentsx The set of segments to process. | ||
856 | |||
857 | NodesX *nodesx The list of nodes to use. | ||
858 | ++++++++++++++++++++++++++++++++++++++*/ | ||
859 | |||
860 | void IndexSegments(SegmentsX* segmentsx,NodesX *nodesx) | ||
861 | { | ||
862 | amb | 214 | index_t i; |
863 | amb | 110 | |
864 | amb | 275 | /* Check the start conditions */ |
865 | |||
866 | amb | 281 | assert(nodesx->ndata); /* Must have ndata filled in => real nodes exist */ |
867 | assert(segmentsx->sdata); /* Must have sdata filled in => real segments exist */ | ||
868 | amb | 110 | |
869 | amb | 275 | /* Print the start message */ |
870 | |||
871 | amb | 227 | printf("Indexing Nodes: Nodes=0"); |
872 | fflush(stdout); | ||
873 | |||
874 | amb | 275 | /* Map into memory */ |
875 | |||
876 | if(!option_slim) | ||
877 | amb | 281 | { |
878 | nodesx->xdata=MapFile(nodesx->filename); | ||
879 | amb | 275 | segmentsx->xdata=MapFile(segmentsx->filename); |
880 | amb | 281 | } |
881 | amb | 275 | |
882 | amb | 110 | /* Index the segments */ |
883 | |||
884 | for(i=0;i<nodesx->number;i++) | ||
885 | { | ||
886 | amb | 281 | NodeX *nodex=LookupNodeX(nodesx,i,1); |
887 | Node *node =&nodesx->ndata[nodex->id]; | ||
888 | amb | 212 | index_t index=SEGMENT(node->firstseg); |
889 | amb | 110 | |
890 | do | ||
891 | { | ||
892 | amb | 275 | SegmentX *segmentx=LookupSegmentX(segmentsx,index,1); |
893 | amb | 256 | |
894 | amb | 281 | if(segmentx->node1==nodex->id) |
895 | amb | 110 | { |
896 | amb | 209 | segmentsx->sdata[index].node1=i; |
897 | amb | 110 | |
898 | amb | 209 | index++; |
899 | amb | 128 | |
900 | amb | 256 | if(index>=segmentsx->number) |
901 | amb | 209 | break; |
902 | amb | 256 | |
903 | amb | 275 | segmentx=LookupSegmentX(segmentsx,index,1); |
904 | amb | 256 | |
905 | amb | 281 | if(segmentx->node1!=nodex->id) |
906 | amb | 256 | break; |
907 | amb | 110 | } |
908 | else | ||
909 | { | ||
910 | amb | 209 | segmentsx->sdata[index].node2=i; |
911 | amb | 110 | |
912 | amb | 209 | if(segmentsx->sdata[index].next2==NO_NODE) |
913 | break; | ||
914 | amb | 110 | else |
915 | amb | 209 | index=segmentsx->sdata[index].next2; |
916 | amb | 110 | } |
917 | } | ||
918 | amb | 209 | while(1); |
919 | amb | 110 | |
920 | if(!((i+1)%10000)) | ||
921 | { | ||
922 | printf("\rIndexing Nodes: Nodes=%d",i+1); | ||
923 | fflush(stdout); | ||
924 | } | ||
925 | } | ||
926 | |||
927 | amb | 275 | /* Unmap from memory */ |
928 | |||
929 | if(!option_slim) | ||
930 | amb | 281 | { |
931 | nodesx->xdata=UnmapFile(nodesx->filename); | ||
932 | amb | 275 | segmentsx->xdata=UnmapFile(segmentsx->filename); |
933 | amb | 281 | } |
934 | amb | 275 | |
935 | /* Print the final message */ | ||
936 | |||
937 | amb | 110 | printf("\rIndexed Nodes: Nodes=%d \n",nodesx->number); |
938 | fflush(stdout); | ||
939 | } | ||
940 | |||
941 | |||
942 | /*++++++++++++++++++++++++++++++++++++++ | ||
943 | amb | 285 | Save the segment list to a file. |
944 | |||
945 | SegmentsX* segmentsx The set of segments to save. | ||
946 | |||
947 | const char *filename The name of the file to save. | ||
948 | ++++++++++++++++++++++++++++++++++++++*/ | ||
949 | |||
950 | void SaveSegmentList(SegmentsX* segmentsx,const char *filename) | ||
951 | { | ||
952 | index_t i; | ||
953 | int fd; | ||
954 | Segments *segments; | ||
955 | int super_number=0,normal_number=0; | ||
956 | |||
957 | /* Check the start conditions */ | ||
958 | |||
959 | assert(segmentsx->sdata); /* Must have sdata filled in => real segments */ | ||
960 | |||
961 | /* Print the start message */ | ||
962 | |||
963 | printf("Writing Segments: Segments=0"); | ||
964 | fflush(stdout); | ||
965 | |||
966 | /* Count the number of super-segments and normal segments */ | ||
967 | |||
968 | for(i=0;i<segmentsx->number;i++) | ||
969 | { | ||
970 | if(IsSuperSegment(&segmentsx->sdata[i])) | ||
971 | super_number++; | ||
972 | if(IsNormalSegment(&segmentsx->sdata[i])) | ||
973 | normal_number++; | ||
974 | } | ||
975 | |||
976 | /* Fill in a Segments structure with the offset of the real data in the file after | ||
977 | the Segment structure itself. */ | ||
978 | |||
979 | segments=calloc(1,sizeof(Segments)); | ||
980 | |||
981 | assert(segments); /* Check calloc() worked */ | ||
982 | |||
983 | segments->number=segmentsx->number; | ||
984 | segments->snumber=super_number; | ||
985 | segments->nnumber=normal_number; | ||
986 | |||
987 | segments->data=NULL; | ||
988 | |||
989 | segments->segments=(void*)sizeof(Segments); | ||
990 | |||
991 | /* Write out the Segments structure and then the real data. */ | ||
992 | |||
993 | fd=OpenFile(filename); | ||
994 | |||
995 | WriteFile(fd,segments,sizeof(Segments)); | ||
996 | |||
997 | for(i=0;i<segments->number;i++) | ||
998 | { | ||
999 | WriteFile(fd,&segmentsx->sdata[i],sizeof(Segment)); | ||
1000 | |||
1001 | if(!((i+1)%10000)) | ||
1002 | { | ||
1003 | printf("\rWriting Segments: Segments=%d",i+1); | ||
1004 | fflush(stdout); | ||
1005 | } | ||
1006 | } | ||
1007 | |||
1008 | CloseFile(fd); | ||
1009 | |||
1010 | /* Print the final message */ | ||
1011 | |||
1012 | printf("\rWrote Segments: Segments=%d \n",segments->number); | ||
1013 | fflush(stdout); | ||
1014 | |||
1015 | /* Free the fake Segments */ | ||
1016 | |||
1017 | free(segments); | ||
1018 | } | ||
1019 | |||
1020 | |||
1021 | /*++++++++++++++++++++++++++++++++++++++ | ||
1022 | amb | 110 | Calculate the distance between two nodes. |
1023 | |||
1024 | distance_t DistanceX Returns the distance between the extended nodes. | ||
1025 | |||
1026 | NodeX *nodex1 The starting node. | ||
1027 | |||
1028 | NodeX *nodex2 The end node. | ||
1029 | ++++++++++++++++++++++++++++++++++++++*/ | ||
1030 | |||
1031 | amb | 228 | static distance_t DistanceX(NodeX *nodex1,NodeX *nodex2) |
1032 | amb | 110 | { |
1033 | amb | 223 | double dlon = latlong_to_radians(nodex1->longitude) - latlong_to_radians(nodex2->longitude); |
1034 | double dlat = latlong_to_radians(nodex1->latitude) - latlong_to_radians(nodex2->latitude); | ||
1035 | double lat1 = latlong_to_radians(nodex1->latitude); | ||
1036 | double lat2 = latlong_to_radians(nodex2->latitude); | ||
1037 | amb | 110 | |
1038 | amb | 219 | double a1,a2,a,sa,c,d; |
1039 | amb | 110 | |
1040 | if(dlon==0 && dlat==0) | ||
1041 | return 0; | ||
1042 | |||
1043 | amb | 219 | a1 = sin (dlat / 2); |
1044 | a2 = sin (dlon / 2); | ||
1045 | a = (a1 * a1) + cos (lat1) * cos (lat2) * a2 * a2; | ||
1046 | sa = sqrt (a); | ||
1047 | amb | 110 | if (sa <= 1.0) |
1048 | amb | 219 | {c = 2 * asin (sa);} |
1049 | amb | 110 | else |
1050 | amb | 219 | {c = 2 * asin (1.0);} |
1051 | amb | 110 | d = 6378.137 * c; |
1052 | |||
1053 | return km_to_distance(d); | ||
1054 | } |
Properties
Name | Value |
---|---|
cvs:description | Extended segments functions. |