Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino
Contents of /trunk/src/segmentsx.c
Parent Directory
|
Revision Log
Revision 1173 -
(show annotations)
(download)
(as text)
Tue Nov 27 19:51:08 2012 UTC (12 years, 3 months ago) by amb
File MIME type: text/x-csrc
File size: 31645 byte(s)
Tue Nov 27 19:51:08 2012 UTC (12 years, 3 months ago) by amb
File MIME type: text/x-csrc
File size: 31645 byte(s)
Log an error about duplicated segments within a way while parsing the OSM instead of later (will have been removed by de-duplication code before tested later in most cases).
1 | /*************************************** |
2 | Extended Segment data type functions. |
3 | |
4 | Part of the Routino routing software. |
5 | ******************/ /****************** |
6 | This file Copyright 2008-2012 Andrew M. Bishop |
7 | |
8 | This program is free software: you can redistribute it and/or modify |
9 | it under the terms of the GNU Affero General Public License as published by |
10 | the Free Software Foundation, either version 3 of the License, or |
11 | (at your option) any later version. |
12 | |
13 | This program is distributed in the hope that it will be useful, |
14 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
16 | GNU Affero General Public License for more details. |
17 | |
18 | You should have received a copy of the GNU Affero General Public License |
19 | along with this program. If not, see <http://www.gnu.org/licenses/>. |
20 | ***************************************/ |
21 | |
22 | |
23 | #include <math.h> |
24 | #include <stdlib.h> |
25 | #include <string.h> |
26 | |
27 | #include "types.h" |
28 | #include "segments.h" |
29 | #include "ways.h" |
30 | |
31 | #include "typesx.h" |
32 | #include "nodesx.h" |
33 | #include "segmentsx.h" |
34 | #include "waysx.h" |
35 | |
36 | #include "files.h" |
37 | #include "logging.h" |
38 | #include "sorting.h" |
39 | |
40 | |
41 | /* Global variables */ |
42 | |
43 | /*+ The command line '--tmpdir' option or its default value. +*/ |
44 | extern char *option_tmpdirname; |
45 | |
46 | /* Local variables */ |
47 | |
48 | /*+ Temporary file-local variables for use by the sort functions. +*/ |
49 | static NodesX *sortnodesx; |
50 | static SegmentsX *sortsegmentsx; |
51 | static WaysX *sortwaysx; |
52 | |
53 | /* Local functions */ |
54 | |
55 | static int sort_by_way_id(SegmentX *a,SegmentX *b); |
56 | static int apply_changes(SegmentX *segmentx,index_t index); |
57 | |
58 | static int sort_by_id(SegmentX *a,SegmentX *b); |
59 | static int deduplicate(SegmentX *segmentx,index_t index); |
60 | |
61 | static int delete_pruned(SegmentX *segmentx,index_t index); |
62 | |
63 | static int deduplicate_super(SegmentX *segmentx,index_t index); |
64 | |
65 | static int geographically_index(SegmentX *segmentx,index_t index); |
66 | |
67 | static distance_t DistanceX(NodeX *nodex1,NodeX *nodex2); |
68 | |
69 | |
70 | /*++++++++++++++++++++++++++++++++++++++ |
71 | Allocate a new segment list (create a new file or open an existing one). |
72 | |
73 | SegmentsX *NewSegmentList Returns the segment list. |
74 | |
75 | int append Set to 1 if the file is to be opened for appending. |
76 | |
77 | int readonly Set to 1 if the file is to be opened for reading. |
78 | ++++++++++++++++++++++++++++++++++++++*/ |
79 | |
80 | SegmentsX *NewSegmentList(int append,int readonly) |
81 | { |
82 | SegmentsX *segmentsx; |
83 | |
84 | segmentsx=(SegmentsX*)calloc(1,sizeof(SegmentsX)); |
85 | |
86 | logassert(segmentsx,"Failed to allocate memory (try using slim mode?)"); /* Check calloc() worked */ |
87 | |
88 | segmentsx->filename =(char*)malloc(strlen(option_tmpdirname)+32); |
89 | segmentsx->filename_tmp=(char*)malloc(strlen(option_tmpdirname)+32); |
90 | |
91 | sprintf(segmentsx->filename ,"%s/segmentsx.parsed.mem",option_tmpdirname); |
92 | sprintf(segmentsx->filename_tmp,"%s/segmentsx.%p.tmp" ,option_tmpdirname,(void*)segmentsx); |
93 | |
94 | if(append || readonly) |
95 | if(ExistsFile(segmentsx->filename)) |
96 | { |
97 | off_t size; |
98 | |
99 | size=SizeFile(segmentsx->filename); |
100 | |
101 | segmentsx->number=size/sizeof(SegmentX); |
102 | |
103 | RenameFile(segmentsx->filename,segmentsx->filename_tmp); |
104 | } |
105 | |
106 | if(append) |
107 | segmentsx->fd=OpenFileAppend(segmentsx->filename_tmp); |
108 | else if(!readonly) |
109 | segmentsx->fd=OpenFileNew(segmentsx->filename_tmp); |
110 | else |
111 | segmentsx->fd=-1; |
112 | |
113 | return(segmentsx); |
114 | } |
115 | |
116 | |
117 | /*++++++++++++++++++++++++++++++++++++++ |
118 | Free a segment list. |
119 | |
120 | SegmentsX *segmentsx The set of segments to be freed. |
121 | |
122 | int keep If set then the results file is to be kept. |
123 | ++++++++++++++++++++++++++++++++++++++*/ |
124 | |
125 | void FreeSegmentList(SegmentsX *segmentsx,int keep) |
126 | { |
127 | if(keep) |
128 | RenameFile(segmentsx->filename_tmp,segmentsx->filename); |
129 | else |
130 | DeleteFile(segmentsx->filename_tmp); |
131 | |
132 | free(segmentsx->filename); |
133 | free(segmentsx->filename_tmp); |
134 | |
135 | if(segmentsx->firstnode) |
136 | free(segmentsx->firstnode); |
137 | |
138 | if(segmentsx->next1) |
139 | free(segmentsx->next1); |
140 | |
141 | if(segmentsx->usednode) |
142 | free(segmentsx->usednode); |
143 | |
144 | free(segmentsx); |
145 | } |
146 | |
147 | |
148 | /*++++++++++++++++++++++++++++++++++++++ |
149 | Append a single segment to an unsorted segment list. |
150 | |
151 | SegmentsX *segmentsx The set of segments to modify. |
152 | |
153 | way_t way The way that the segment belongs to. |
154 | |
155 | node_t node1 The first node in the segment. |
156 | |
157 | node_t node2 The second node in the segment. |
158 | |
159 | distance_t distance The distance between the nodes (or just the flags). |
160 | ++++++++++++++++++++++++++++++++++++++*/ |
161 | |
162 | void AppendSegmentList(SegmentsX *segmentsx,way_t way,node_t node1,node_t node2,distance_t distance) |
163 | { |
164 | SegmentX segmentx; |
165 | |
166 | if(node1>node2) |
167 | { |
168 | node_t temp; |
169 | |
170 | temp=node1; |
171 | node1=node2; |
172 | node2=temp; |
173 | |
174 | if(distance&(ONEWAY_2TO1|ONEWAY_1TO2)) |
175 | distance^=ONEWAY_2TO1|ONEWAY_1TO2; |
176 | } |
177 | |
178 | segmentx.node1=node1; |
179 | segmentx.node2=node2; |
180 | segmentx.next2=NO_SEGMENT; |
181 | segmentx.way=way; |
182 | segmentx.distance=distance; |
183 | |
184 | WriteFile(segmentsx->fd,&segmentx,sizeof(SegmentX)); |
185 | |
186 | segmentsx->number++; |
187 | |
188 | logassert(segmentsx->number<SEGMENT_FAKE,"Too many segments (change index_t to 64-bits?)"); /* SEGMENT_FAKE marks the high-water mark for real segments. */ |
189 | } |
190 | |
191 | |
192 | /*++++++++++++++++++++++++++++++++++++++ |
193 | Finish appending segments and change the filename over. |
194 | |
195 | SegmentsX *segmentsx The segments that have been appended. |
196 | ++++++++++++++++++++++++++++++++++++++*/ |
197 | |
198 | void FinishSegmentList(SegmentsX *segmentsx) |
199 | { |
200 | if(segmentsx->fd!=-1) |
201 | segmentsx->fd=CloseFile(segmentsx->fd); |
202 | } |
203 | |
204 | |
205 | /*++++++++++++++++++++++++++++++++++++++ |
206 | Find the first extended segment with a particular starting node index. |
207 | |
208 | SegmentX *FirstSegmentX Returns a pointer to the first extended segment with the specified id. |
209 | |
210 | SegmentsX *segmentsx The set of segments to use. |
211 | |
212 | index_t nodeindex The node index to look for. |
213 | |
214 | int position A flag to pass through. |
215 | ++++++++++++++++++++++++++++++++++++++*/ |
216 | |
217 | SegmentX *FirstSegmentX(SegmentsX *segmentsx,index_t nodeindex,int position) |
218 | { |
219 | index_t index=segmentsx->firstnode[nodeindex]; |
220 | SegmentX *segmentx; |
221 | |
222 | if(index==NO_SEGMENT) |
223 | return(NULL); |
224 | |
225 | segmentx=LookupSegmentX(segmentsx,index,position); |
226 | |
227 | return(segmentx); |
228 | } |
229 | |
230 | |
231 | /*++++++++++++++++++++++++++++++++++++++ |
232 | Find the next segment with a particular starting node index. |
233 | |
234 | SegmentX *NextSegmentX Returns a pointer to the next segment with the same id. |
235 | |
236 | SegmentsX *segmentsx The set of segments to use. |
237 | |
238 | SegmentX *segmentx The current segment. |
239 | |
240 | index_t nodeindex The node index. |
241 | ++++++++++++++++++++++++++++++++++++++*/ |
242 | |
243 | SegmentX *NextSegmentX(SegmentsX *segmentsx,SegmentX *segmentx,index_t nodeindex) |
244 | { |
245 | #if SLIM |
246 | int position=1+(segmentx-&segmentsx->cached[0]); |
247 | #endif |
248 | |
249 | if(segmentx->node1==nodeindex) |
250 | { |
251 | if(segmentsx->next1) |
252 | { |
253 | index_t index=IndexSegmentX(segmentsx,segmentx); |
254 | |
255 | if(segmentsx->next1[index]==NO_SEGMENT) |
256 | return(NULL); |
257 | |
258 | segmentx=LookupSegmentX(segmentsx,segmentsx->next1[index],position); |
259 | |
260 | return(segmentx); |
261 | } |
262 | else |
263 | { |
264 | #if SLIM |
265 | index_t index=IndexSegmentX(segmentsx,segmentx); |
266 | index++; |
267 | |
268 | if(index>=segmentsx->number) |
269 | return(NULL); |
270 | |
271 | segmentx=LookupSegmentX(segmentsx,index,position); |
272 | #else |
273 | segmentx++; |
274 | |
275 | if(IndexSegmentX(segmentsx,segmentx)>=segmentsx->number) |
276 | return(NULL); |
277 | #endif |
278 | |
279 | if(segmentx->node1!=nodeindex) |
280 | return(NULL); |
281 | |
282 | return(segmentx); |
283 | } |
284 | } |
285 | else |
286 | { |
287 | if(segmentx->next2==NO_SEGMENT) |
288 | return(NULL); |
289 | |
290 | return(LookupSegmentX(segmentsx,segmentx->next2,position)); |
291 | } |
292 | } |
293 | |
294 | |
295 | /*++++++++++++++++++++++++++++++++++++++ |
296 | Apply the changes to the segments (no unique id to use). |
297 | |
298 | SegmentsX *segmentsx The set of segments to sort and modify. |
299 | ++++++++++++++++++++++++++++++++++++++*/ |
300 | |
301 | void ApplySegmentChanges(SegmentsX *segmentsx) |
302 | { |
303 | int fd; |
304 | index_t xnumber; |
305 | |
306 | /* Print the start message */ |
307 | |
308 | printf_first("Applying Segment Changes"); |
309 | |
310 | /* Re-open the file read-only and a new file writeable */ |
311 | |
312 | segmentsx->fd=ReOpenFile(segmentsx->filename_tmp); |
313 | |
314 | DeleteFile(segmentsx->filename_tmp); |
315 | |
316 | fd=OpenFileNew(segmentsx->filename_tmp); |
317 | |
318 | /* Sort by node indexes */ |
319 | |
320 | xnumber=segmentsx->number; |
321 | |
322 | segmentsx->number=filesort_fixed(segmentsx->fd,fd,sizeof(SegmentX),NULL, |
323 | (int (*)(const void*,const void*))sort_by_way_id, |
324 | (int (*)(void*,index_t))apply_changes); |
325 | |
326 | /* Close the files */ |
327 | |
328 | segmentsx->fd=CloseFile(segmentsx->fd); |
329 | CloseFile(fd); |
330 | |
331 | /* Print the final message */ |
332 | |
333 | printf_last("Applying Segment Changes: Segments=%"Pindex_t" Changed=%"Pindex_t,xnumber,xnumber-segmentsx->number); |
334 | } |
335 | |
336 | |
337 | /*++++++++++++++++++++++++++++++++++++++ |
338 | Sort the segments into way id order. |
339 | |
340 | int sort_by_way_id Returns the comparison of the way fields. |
341 | |
342 | SegmentX *a The first segment. |
343 | |
344 | SegmentX *b The second segment. |
345 | ++++++++++++++++++++++++++++++++++++++*/ |
346 | |
347 | static int sort_by_way_id(SegmentX *a,SegmentX *b) |
348 | { |
349 | way_t a_id=a->way; |
350 | way_t b_id=b->way; |
351 | |
352 | if(a_id<b_id) |
353 | return(-1); |
354 | else if(a_id>b_id) |
355 | return(1); |
356 | else /* if(a_id==b_id) */ |
357 | return(-FILESORT_PRESERVE_ORDER(a,b)); /* latest version first */ |
358 | } |
359 | |
360 | |
361 | /*++++++++++++++++++++++++++++++++++++++ |
362 | Apply the changes to the segments. |
363 | |
364 | int apply_changes Return 1 if the value is to be kept, otherwise 0. |
365 | |
366 | SegmentX *segmentx The extended segment. |
367 | |
368 | index_t index The number of sorted segments that have already been written to the output file. |
369 | ++++++++++++++++++++++++++++++++++++++*/ |
370 | |
371 | static int apply_changes(SegmentX *segmentx,index_t index) |
372 | { |
373 | static way_t prevway=NO_WAY_ID; |
374 | static int deleted=0; |
375 | |
376 | if(prevway!=segmentx->way) |
377 | { |
378 | prevway=segmentx->way; |
379 | deleted=0; |
380 | } |
381 | |
382 | if(!deleted) |
383 | if(segmentx->node1==NO_NODE_ID) |
384 | deleted=1; |
385 | |
386 | if(deleted) |
387 | return(0); |
388 | else |
389 | return(1); |
390 | } |
391 | |
392 | |
393 | /*++++++++++++++++++++++++++++++++++++++ |
394 | Sort the segment list and deduplicate it. |
395 | |
396 | SegmentsX *segmentsx The set of segments to sort and modify. |
397 | ++++++++++++++++++++++++++++++++++++++*/ |
398 | |
399 | void SortSegmentList(SegmentsX *segmentsx) |
400 | { |
401 | int fd; |
402 | index_t xnumber; |
403 | |
404 | /* Print the start message */ |
405 | |
406 | printf_first("Sorting Segments"); |
407 | |
408 | /* Re-open the file read-only and a new file writeable */ |
409 | |
410 | segmentsx->fd=ReOpenFile(segmentsx->filename_tmp); |
411 | |
412 | DeleteFile(segmentsx->filename_tmp); |
413 | |
414 | fd=OpenFileNew(segmentsx->filename_tmp); |
415 | |
416 | /* Sort by node indexes */ |
417 | |
418 | xnumber=segmentsx->number; |
419 | |
420 | segmentsx->number=filesort_fixed(segmentsx->fd,fd,sizeof(SegmentX),NULL, |
421 | (int (*)(const void*,const void*))sort_by_id, |
422 | (int (*)(void*,index_t))deduplicate); |
423 | |
424 | /* Close the files */ |
425 | |
426 | segmentsx->fd=CloseFile(segmentsx->fd); |
427 | CloseFile(fd); |
428 | |
429 | /* Print the final message */ |
430 | |
431 | printf_last("Sorted Segments: Segments=%"Pindex_t" Duplicates=%"Pindex_t,xnumber,xnumber-segmentsx->number); |
432 | } |
433 | |
434 | |
435 | /*++++++++++++++++++++++++++++++++++++++ |
436 | Sort the segments into id order, first by node1 then by node2, finally by distance. |
437 | |
438 | int sort_by_id Returns the comparison of the node fields. |
439 | |
440 | SegmentX *a The first segment. |
441 | |
442 | SegmentX *b The second segment. |
443 | ++++++++++++++++++++++++++++++++++++++*/ |
444 | |
445 | static int sort_by_id(SegmentX *a,SegmentX *b) |
446 | { |
447 | node_t a_id1=a->node1; |
448 | node_t b_id1=b->node1; |
449 | |
450 | if(a_id1<b_id1) |
451 | return(-1); |
452 | else if(a_id1>b_id1) |
453 | return(1); |
454 | else /* if(a_id1==b_id1) */ |
455 | { |
456 | node_t a_id2=a->node2; |
457 | node_t b_id2=b->node2; |
458 | |
459 | if(a_id2<b_id2) |
460 | return(-1); |
461 | else if(a_id2>b_id2) |
462 | return(1); |
463 | else |
464 | { |
465 | distance_t a_distance=DISTANCE(a->distance); |
466 | distance_t b_distance=DISTANCE(b->distance); |
467 | |
468 | if(a_distance<b_distance) |
469 | return(-1); |
470 | else if(a_distance>b_distance) |
471 | return(1); |
472 | else |
473 | { |
474 | distance_t a_distflag=DISTFLAG(a->distance); |
475 | distance_t b_distflag=DISTFLAG(b->distance); |
476 | |
477 | if(a_distflag<b_distflag) |
478 | return(-1); |
479 | else if(a_distflag>b_distflag) |
480 | return(1); |
481 | else |
482 | return(FILESORT_PRESERVE_ORDER(a,b)); /* preserve order */ |
483 | } |
484 | } |
485 | } |
486 | } |
487 | |
488 | |
489 | /*++++++++++++++++++++++++++++++++++++++ |
490 | Discard duplicate segments. |
491 | |
492 | int deduplicate Return 1 if the value is to be kept, otherwise 0. |
493 | |
494 | SegmentX *segmentx The extended segment. |
495 | |
496 | index_t index The number of sorted segments that have already been written to the output file. |
497 | ++++++++++++++++++++++++++++++++++++++*/ |
498 | |
499 | static int deduplicate(SegmentX *segmentx,index_t index) |
500 | { |
501 | static node_t prevnode1=NO_NODE_ID,prevnode2=NO_NODE_ID; |
502 | static way_t prevway=NO_WAY_ID; |
503 | static distance_t prevdist=0; |
504 | |
505 | if(prevnode1!=segmentx->node1 || prevnode2!=segmentx->node2 || prevway!=segmentx->way || prevdist!=segmentx->distance) |
506 | { |
507 | prevnode1=segmentx->node1; |
508 | prevnode2=segmentx->node2; |
509 | prevway=segmentx->way; |
510 | prevdist=segmentx->distance; |
511 | |
512 | return(1); |
513 | } |
514 | else |
515 | return(0); |
516 | } |
517 | |
518 | |
519 | /*++++++++++++++++++++++++++++++++++++++ |
520 | Remove bad segments (duplicated, zero length or with missing nodes). |
521 | |
522 | SegmentsX *segmentsx The set of segments to modify. |
523 | |
524 | NodesX *nodesx The set of nodes to use. |
525 | |
526 | WaysX *waysx The set of ways to use. |
527 | |
528 | int keep If set to 1 then keep the old data file otherwise delete it. |
529 | ++++++++++++++++++++++++++++++++++++++*/ |
530 | |
531 | void RemoveBadSegments(SegmentsX *segmentsx,NodesX *nodesx,WaysX *waysx,int keep) |
532 | { |
533 | index_t noway=0,loop=0,nonode=0,duplicate=0,good=0,total=0; |
534 | node_t prevnode1=NO_NODE_ID,prevnode2=NO_NODE_ID; |
535 | way_t prevway=NO_WAY_ID; |
536 | distance_t prevdist=0; |
537 | SegmentX segmentx; |
538 | int fd; |
539 | |
540 | /* Print the start message */ |
541 | |
542 | printf_first("Checking Segments: Segments=0 Loop=0 No-Way=0 No-Node=0 Duplicate=0"); |
543 | |
544 | /* Allocate the node usage bitmask */ |
545 | |
546 | segmentsx->usednode=AllocBitMask(nodesx->number); |
547 | |
548 | logassert(segmentsx->usednode,"Failed to allocate memory (try using slim mode?)"); /* Check AllocBitMask() worked */ |
549 | |
550 | /* Re-open the file read-only and a new file writeable */ |
551 | |
552 | segmentsx->fd=ReOpenFile(segmentsx->filename_tmp); |
553 | |
554 | if(keep) |
555 | RenameFile(segmentsx->filename_tmp,segmentsx->filename); |
556 | else |
557 | DeleteFile(segmentsx->filename_tmp); |
558 | |
559 | fd=OpenFileNew(segmentsx->filename_tmp); |
560 | |
561 | /* Modify the on-disk image */ |
562 | |
563 | while(!ReadFile(segmentsx->fd,&segmentx,sizeof(SegmentX))) |
564 | { |
565 | index_t index1=IndexNodeX(nodesx,segmentx.node1); |
566 | index_t index2=IndexNodeX(nodesx,segmentx.node2); |
567 | index_t indexw=IndexWayX(waysx,segmentx.way); |
568 | |
569 | if(indexw==NO_WAY) |
570 | { |
571 | logerror("Segment belongs to way %"Pway_t" but it doesn't exist.\n",segmentx.way); |
572 | |
573 | noway++; |
574 | } |
575 | else if(segmentx.node1==segmentx.node2) |
576 | { |
577 | logerror("Segment connects node %"Pnode_t" to itself.\n",segmentx.node1); |
578 | |
579 | loop++; |
580 | } |
581 | else if(index1==NO_NODE || index2==NO_NODE) |
582 | { |
583 | if(index1==NO_NODE && index2==NO_NODE) |
584 | logerror("Segment connects nodes %"Pnode_t" and %"Pnode_t" but neither exist.\n",segmentx.node1,segmentx.node2); |
585 | |
586 | if(index1==NO_NODE && index2!=NO_NODE) |
587 | logerror("Segment connects nodes %"Pnode_t" and %"Pnode_t" but the first one does not exist.\n",segmentx.node1,segmentx.node2); |
588 | |
589 | if(index1!=NO_NODE && index2==NO_NODE) |
590 | logerror("Segment connects nodes %"Pnode_t" and %"Pnode_t" but the second one does not exist.\n",segmentx.node1,segmentx.node2); |
591 | |
592 | nonode++; |
593 | } |
594 | else if(prevnode1==segmentx.node1 && prevnode2==segmentx.node2) |
595 | { |
596 | if(prevway==segmentx.way) |
597 | ; /* already logged an error - only possible to get here for oneway opposite direction segments */ |
598 | else |
599 | { |
600 | if(!(prevdist&SEGMENT_AREA) && !(segmentx.distance&SEGMENT_AREA)) |
601 | logerror("Segment connecting nodes %"Pnode_t" and %"Pnode_t" is duplicated.\n",segmentx.node1,segmentx.node2); |
602 | |
603 | if(!(prevdist&SEGMENT_AREA) && (segmentx.distance&SEGMENT_AREA)) |
604 | logerror("Segment connecting nodes %"Pnode_t" and %"Pnode_t" is duplicated (discarded the area).\n",segmentx.node1,segmentx.node2); |
605 | |
606 | if((prevdist&SEGMENT_AREA) && !(segmentx.distance&SEGMENT_AREA)) |
607 | logerror("Segment connecting nodes %"Pnode_t" and %"Pnode_t" is duplicated (discarded the non-area).\n",segmentx.node1,segmentx.node2); |
608 | |
609 | if((prevdist&SEGMENT_AREA) && (segmentx.distance&SEGMENT_AREA)) |
610 | logerror("Segment connecting nodes %"Pnode_t" and %"Pnode_t" is duplicated (both are areas).\n",segmentx.node1,segmentx.node2); |
611 | } |
612 | |
613 | duplicate++; |
614 | } |
615 | else |
616 | { |
617 | WriteFile(fd,&segmentx,sizeof(SegmentX)); |
618 | |
619 | SetBit(segmentsx->usednode,index1); |
620 | SetBit(segmentsx->usednode,index2); |
621 | |
622 | prevnode1=segmentx.node1; |
623 | prevnode2=segmentx.node2; |
624 | prevway=segmentx.way; |
625 | prevdist=DISTANCE(segmentx.distance); |
626 | |
627 | good++; |
628 | } |
629 | |
630 | total++; |
631 | |
632 | if(!(total%10000)) |
633 | printf_middle("Checking Segments: Segments=%"Pindex_t" Loop=%"Pindex_t" No-Way=%"Pindex_t" No-Node=%"Pindex_t" Duplicate=%"Pindex_t,total,loop,noway,nonode,duplicate); |
634 | } |
635 | |
636 | segmentsx->number=good; |
637 | |
638 | /* Close the files */ |
639 | |
640 | segmentsx->fd=CloseFile(segmentsx->fd); |
641 | CloseFile(fd); |
642 | |
643 | /* Print the final message */ |
644 | |
645 | printf_last("Checked Segments: Segments=%"Pindex_t" Loop=%"Pindex_t" No-Way=%"Pindex_t" No-Node=%"Pindex_t" Duplicate=%"Pindex_t,total,loop,noway,nonode,duplicate); |
646 | } |
647 | |
648 | |
649 | /*++++++++++++++++++++++++++++++++++++++ |
650 | Measure the segments and replace node/way ids with indexes. |
651 | |
652 | SegmentsX *segmentsx The set of segments to process. |
653 | |
654 | NodesX *nodesx The set of nodes to use. |
655 | |
656 | WaysX *waysx The set of ways to use. |
657 | ++++++++++++++++++++++++++++++++++++++*/ |
658 | |
659 | void MeasureSegments(SegmentsX *segmentsx,NodesX *nodesx,WaysX *waysx) |
660 | { |
661 | index_t index=0; |
662 | int fd; |
663 | SegmentX segmentx; |
664 | |
665 | /* Print the start message */ |
666 | |
667 | printf_first("Measuring Segments: Segments=0"); |
668 | |
669 | /* Map into memory / open the file */ |
670 | |
671 | #if !SLIM |
672 | nodesx->data=MapFile(nodesx->filename_tmp); |
673 | #else |
674 | nodesx->fd=ReOpenFile(nodesx->filename_tmp); |
675 | #endif |
676 | |
677 | /* Allocate the way usage bitmask */ |
678 | |
679 | segmentsx->usedway=AllocBitMask(waysx->number); |
680 | |
681 | logassert(segmentsx->usedway,"Failed to allocate memory (try using slim mode?)"); /* Check AllocBitMask() worked */ |
682 | |
683 | /* Re-open the file read-only and a new file writeable */ |
684 | |
685 | segmentsx->fd=ReOpenFile(segmentsx->filename_tmp); |
686 | |
687 | DeleteFile(segmentsx->filename_tmp); |
688 | |
689 | fd=OpenFileNew(segmentsx->filename_tmp); |
690 | |
691 | /* Modify the on-disk image */ |
692 | |
693 | while(!ReadFile(segmentsx->fd,&segmentx,sizeof(SegmentX))) |
694 | { |
695 | index_t node1=IndexNodeX(nodesx,segmentx.node1); |
696 | index_t node2=IndexNodeX(nodesx,segmentx.node2); |
697 | index_t way =IndexWayX (waysx ,segmentx.way); |
698 | |
699 | NodeX *nodex1=LookupNodeX(nodesx,node1,1); |
700 | NodeX *nodex2=LookupNodeX(nodesx,node2,2); |
701 | |
702 | /* Replace the node and way ids with their indexes */ |
703 | |
704 | segmentx.node1=node1; |
705 | segmentx.node2=node2; |
706 | segmentx.way =way; |
707 | |
708 | SetBit(segmentsx->usedway,segmentx.way); |
709 | |
710 | /* Set the distance but keep the other flags except for area */ |
711 | |
712 | segmentx.distance=DISTANCE(DistanceX(nodex1,nodex2))|DISTFLAG(segmentx.distance); |
713 | segmentx.distance&=~SEGMENT_AREA; |
714 | |
715 | /* Write the modified segment */ |
716 | |
717 | WriteFile(fd,&segmentx,sizeof(SegmentX)); |
718 | |
719 | index++; |
720 | |
721 | if(!(index%10000)) |
722 | printf_middle("Measuring Segments: Segments=%"Pindex_t,index); |
723 | } |
724 | |
725 | /* Close the files */ |
726 | |
727 | segmentsx->fd=CloseFile(segmentsx->fd); |
728 | CloseFile(fd); |
729 | |
730 | /* Free the other now-unneeded indexes */ |
731 | |
732 | free(nodesx->idata); |
733 | nodesx->idata=NULL; |
734 | |
735 | free(waysx->idata); |
736 | waysx->idata=NULL; |
737 | |
738 | /* Unmap from memory / close the file */ |
739 | |
740 | #if !SLIM |
741 | nodesx->data=UnmapFile(nodesx->data); |
742 | #else |
743 | nodesx->fd=CloseFile(nodesx->fd); |
744 | #endif |
745 | |
746 | /* Print the final message */ |
747 | |
748 | printf_last("Measured Segments: Segments=%"Pindex_t,segmentsx->number); |
749 | } |
750 | |
751 | |
752 | /*++++++++++++++++++++++++++++++++++++++ |
753 | Index the segments by creating the firstnode index and filling in the segment next2 parameter. |
754 | |
755 | SegmentsX *segmentsx The set of segments to modify. |
756 | |
757 | NodesX *nodesx The set of nodes to use. |
758 | |
759 | WaysX *waysx The set of ways to use. |
760 | ++++++++++++++++++++++++++++++++++++++*/ |
761 | |
762 | void IndexSegments(SegmentsX *segmentsx,NodesX *nodesx,WaysX *waysx) |
763 | { |
764 | index_t index,i; |
765 | |
766 | if(segmentsx->number==0) |
767 | return; |
768 | |
769 | /* Print the start message */ |
770 | |
771 | printf_first("Indexing Segments: Segments=0"); |
772 | |
773 | /* Allocate the array of indexes */ |
774 | |
775 | if(segmentsx->firstnode) |
776 | free(segmentsx->firstnode); |
777 | |
778 | segmentsx->firstnode=(index_t*)malloc(nodesx->number*sizeof(index_t)); |
779 | |
780 | logassert(segmentsx->firstnode,"Failed to allocate memory (try using slim mode?)"); /* Check malloc() worked */ |
781 | |
782 | for(i=0;i<nodesx->number;i++) |
783 | segmentsx->firstnode[i]=NO_SEGMENT; |
784 | |
785 | /* Map into memory / open the files */ |
786 | |
787 | #if !SLIM |
788 | segmentsx->data=MapFileWriteable(segmentsx->filename_tmp); |
789 | #else |
790 | segmentsx->fd=ReOpenFileWriteable(segmentsx->filename_tmp); |
791 | #endif |
792 | |
793 | /* Read through the segments in reverse order */ |
794 | |
795 | for(index=segmentsx->number-1;index!=NO_SEGMENT;index--) |
796 | { |
797 | SegmentX *segmentx=LookupSegmentX(segmentsx,index,1); |
798 | |
799 | if(nodesx->pdata) |
800 | { |
801 | segmentx->node1=nodesx->pdata[segmentx->node1]; |
802 | segmentx->node2=nodesx->pdata[segmentx->node2]; |
803 | } |
804 | |
805 | if(waysx->cdata) |
806 | segmentx->way=waysx->cdata[segmentx->way]; |
807 | |
808 | segmentx->next2=segmentsx->firstnode[segmentx->node2]; |
809 | |
810 | PutBackSegmentX(segmentsx,segmentx); |
811 | |
812 | segmentsx->firstnode[segmentx->node1]=index; |
813 | segmentsx->firstnode[segmentx->node2]=index; |
814 | |
815 | if(!(index%10000)) |
816 | printf_middle("Indexing Segments: Segments=%"Pindex_t,segmentsx->number-index); |
817 | } |
818 | |
819 | /* Unmap from memory / close the files */ |
820 | |
821 | #if !SLIM |
822 | segmentsx->data=UnmapFile(segmentsx->data); |
823 | #else |
824 | segmentsx->fd=CloseFile(segmentsx->fd); |
825 | #endif |
826 | |
827 | /* Free the memory */ |
828 | |
829 | if(nodesx->pdata) |
830 | { |
831 | free(nodesx->pdata); |
832 | nodesx->pdata=NULL; |
833 | } |
834 | |
835 | if(waysx->cdata) |
836 | { |
837 | free(waysx->cdata); |
838 | waysx->cdata=NULL; |
839 | } |
840 | |
841 | /* Print the final message */ |
842 | |
843 | printf_last("Indexed Segments: Segments=%"Pindex_t,segmentsx->number); |
844 | } |
845 | |
846 | |
847 | /*++++++++++++++++++++++++++++++++++++++ |
848 | Prune the deleted segments while resorting the list. |
849 | |
850 | SegmentsX *segmentsx The set of segments to sort and modify. |
851 | |
852 | WaysX *waysx The set of ways to check. |
853 | ++++++++++++++++++++++++++++++++++++++*/ |
854 | |
855 | void RemovePrunedSegments(SegmentsX *segmentsx,WaysX *waysx) |
856 | { |
857 | int fd; |
858 | index_t xnumber; |
859 | |
860 | /* Print the start message */ |
861 | |
862 | printf_first("Sorting and Pruning Segments"); |
863 | |
864 | /* Allocate the way usage bitmask */ |
865 | |
866 | segmentsx->usedway=AllocBitMask(waysx->number); |
867 | |
868 | logassert(segmentsx->usedway,"Failed to allocate memory (try using slim mode?)"); /* Check AllocBitMask() worked */ |
869 | |
870 | /* Re-open the file read-only and a new file writeable */ |
871 | |
872 | segmentsx->fd=ReOpenFile(segmentsx->filename_tmp); |
873 | |
874 | DeleteFile(segmentsx->filename_tmp); |
875 | |
876 | fd=OpenFileNew(segmentsx->filename_tmp); |
877 | |
878 | /* Sort by node indexes */ |
879 | |
880 | xnumber=segmentsx->number; |
881 | |
882 | sortsegmentsx=segmentsx; |
883 | |
884 | segmentsx->number=filesort_fixed(segmentsx->fd,fd,sizeof(SegmentX),(int (*)(void*,index_t))delete_pruned, |
885 | (int (*)(const void*,const void*))sort_by_id, |
886 | NULL); |
887 | |
888 | /* Close the files */ |
889 | |
890 | segmentsx->fd=CloseFile(segmentsx->fd); |
891 | CloseFile(fd); |
892 | |
893 | /* Print the final message */ |
894 | |
895 | printf_last("Sorted and Pruned Segments: Segments=%"Pindex_t" Deleted=%"Pindex_t,xnumber,xnumber-segmentsx->number); |
896 | } |
897 | |
898 | |
899 | /*++++++++++++++++++++++++++++++++++++++ |
900 | Delete the pruned segments. |
901 | |
902 | int delete_pruned Return 1 if the value is to be kept, otherwise 0. |
903 | |
904 | SegmentX *segmentx The extended segment. |
905 | |
906 | index_t index The number of unsorted segments that have been read from the input file. |
907 | ++++++++++++++++++++++++++++++++++++++*/ |
908 | |
909 | static int delete_pruned(SegmentX *segmentx,index_t index) |
910 | { |
911 | if(IsPrunedSegmentX(segmentx)) |
912 | return(0); |
913 | |
914 | SetBit(sortsegmentsx->usedway,segmentx->way); |
915 | |
916 | return(1); |
917 | } |
918 | |
919 | |
920 | /*++++++++++++++++++++++++++++++++++++++ |
921 | Remove the duplicate super-segments. |
922 | |
923 | SegmentsX *segmentsx The set of super-segments to modify. |
924 | |
925 | WaysX *waysx The set of ways to use. |
926 | ++++++++++++++++++++++++++++++++++++++*/ |
927 | |
928 | void DeduplicateSuperSegments(SegmentsX *segmentsx,WaysX *waysx) |
929 | { |
930 | int fd; |
931 | index_t xnumber; |
932 | |
933 | /* Print the start message */ |
934 | |
935 | printf_first("Sorting and Deduplicating Super-Segments"); |
936 | |
937 | /* Map into memory / open the file */ |
938 | |
939 | #if !SLIM |
940 | waysx->data=MapFile(waysx->filename_tmp); |
941 | #else |
942 | waysx->fd=ReOpenFile(waysx->filename_tmp); |
943 | #endif |
944 | |
945 | /* Re-open the file read-only and a new file writeable */ |
946 | |
947 | segmentsx->fd=ReOpenFile(segmentsx->filename_tmp); |
948 | |
949 | DeleteFile(segmentsx->filename_tmp); |
950 | |
951 | fd=OpenFileNew(segmentsx->filename_tmp); |
952 | |
953 | /* Sort by node indexes */ |
954 | |
955 | xnumber=segmentsx->number; |
956 | |
957 | sortsegmentsx=segmentsx; |
958 | sortwaysx=waysx; |
959 | |
960 | segmentsx->number=filesort_fixed(segmentsx->fd,fd,sizeof(SegmentX),NULL, |
961 | (int (*)(const void*,const void*))sort_by_id, |
962 | (int (*)(void*,index_t))deduplicate_super); |
963 | |
964 | /* Close the files */ |
965 | |
966 | segmentsx->fd=CloseFile(segmentsx->fd); |
967 | CloseFile(fd); |
968 | |
969 | /* Unmap from memory / close the file */ |
970 | |
971 | #if !SLIM |
972 | waysx->data=UnmapFile(waysx->data); |
973 | #else |
974 | waysx->fd=CloseFile(waysx->fd); |
975 | #endif |
976 | |
977 | /* Print the final message */ |
978 | |
979 | printf_last("Sorted and Deduplicated Super-Segments: Super-Segments=%"Pindex_t" Duplicate=%"Pindex_t,xnumber,xnumber-segmentsx->number); |
980 | } |
981 | |
982 | |
983 | /*++++++++++++++++++++++++++++++++++++++ |
984 | De-duplicate super-segments. |
985 | |
986 | int deduplicate_super Return 1 if the value is to be kept, otherwise 0. |
987 | |
988 | SegmentX *segmentx The extended super-segment. |
989 | |
990 | index_t index The number of sorted super-segments that have already been written to the output file. |
991 | ++++++++++++++++++++++++++++++++++++++*/ |
992 | |
993 | static int deduplicate_super(SegmentX *segmentx,index_t index) |
994 | { |
995 | static int nprev=0; |
996 | static index_t prevnode1=NO_NODE,prevnode2=NO_NODE; |
997 | static SegmentX prevsegx[MAX_SEG_PER_NODE]; |
998 | static Way prevway[MAX_SEG_PER_NODE]; |
999 | |
1000 | WayX *wayx=LookupWayX(sortwaysx,segmentx->way,1); |
1001 | int isduplicate=0; |
1002 | |
1003 | if(index==0 || segmentx->node1!=prevnode1 || segmentx->node2!=prevnode2) |
1004 | { |
1005 | nprev=1; |
1006 | prevnode1=segmentx->node1; |
1007 | prevnode2=segmentx->node2; |
1008 | prevsegx[0]=*segmentx; |
1009 | prevway[0] =wayx->way; |
1010 | } |
1011 | else |
1012 | { |
1013 | int offset; |
1014 | |
1015 | for(offset=0;offset<nprev;offset++) |
1016 | { |
1017 | if(DISTFLAG(segmentx->distance)==DISTFLAG(prevsegx[offset].distance)) |
1018 | if(!WaysCompare(&prevway[offset],&wayx->way)) |
1019 | { |
1020 | isduplicate=1; |
1021 | break; |
1022 | } |
1023 | } |
1024 | |
1025 | if(isduplicate) |
1026 | { |
1027 | nprev--; |
1028 | |
1029 | for(;offset<nprev;offset++) |
1030 | { |
1031 | prevsegx[offset]=prevsegx[offset+1]; |
1032 | prevway[offset] =prevway[offset+1]; |
1033 | } |
1034 | } |
1035 | else |
1036 | { |
1037 | logassert(nprev<MAX_SEG_PER_NODE,"Too many segments for one node (increase MAX_SEG_PER_NODE?)"); /* Only a limited amount of information stored. */ |
1038 | |
1039 | prevsegx[nprev]=*segmentx; |
1040 | prevway[nprev] =wayx->way; |
1041 | |
1042 | nprev++; |
1043 | } |
1044 | } |
1045 | |
1046 | return(!isduplicate); |
1047 | } |
1048 | |
1049 | |
1050 | /*++++++++++++++++++++++++++++++++++++++ |
1051 | Sort the segments geographically after updating the node indexes. |
1052 | |
1053 | SegmentsX *segmentsx The set of segments to modify. |
1054 | |
1055 | NodesX *nodesx The set of nodes to use. |
1056 | ++++++++++++++++++++++++++++++++++++++*/ |
1057 | |
1058 | void SortSegmentListGeographically(SegmentsX *segmentsx,NodesX *nodesx) |
1059 | { |
1060 | int fd; |
1061 | |
1062 | /* Print the start message */ |
1063 | |
1064 | printf_first("Sorting Segments Geographically"); |
1065 | |
1066 | /* Re-open the file read-only and a new file writeable */ |
1067 | |
1068 | segmentsx->fd=ReOpenFile(segmentsx->filename_tmp); |
1069 | |
1070 | DeleteFile(segmentsx->filename_tmp); |
1071 | |
1072 | fd=OpenFileNew(segmentsx->filename_tmp); |
1073 | |
1074 | /* Update the segments with geographically sorted node indexes and sort them */ |
1075 | |
1076 | sortnodesx=nodesx; |
1077 | |
1078 | filesort_fixed(segmentsx->fd,fd,sizeof(SegmentX),(int (*)(void*,index_t))geographically_index, |
1079 | (int (*)(const void*,const void*))sort_by_id, |
1080 | NULL); |
1081 | /* Close the files */ |
1082 | |
1083 | segmentsx->fd=CloseFile(segmentsx->fd); |
1084 | CloseFile(fd); |
1085 | |
1086 | /* Print the final message */ |
1087 | |
1088 | printf_last("Sorted Segments Geographically: Segments=%"Pindex_t,segmentsx->number); |
1089 | } |
1090 | |
1091 | |
1092 | /*++++++++++++++++++++++++++++++++++++++ |
1093 | Update the segment indexes. |
1094 | |
1095 | int geographically_index Return 1 if the value is to be kept, otherwise 0. |
1096 | |
1097 | SegmentX *segmentx The extended segment. |
1098 | |
1099 | index_t index The number of unsorted segments that have been read from the input file. |
1100 | ++++++++++++++++++++++++++++++++++++++*/ |
1101 | |
1102 | static int geographically_index(SegmentX *segmentx,index_t index) |
1103 | { |
1104 | segmentx->node1=sortnodesx->gdata[segmentx->node1]; |
1105 | segmentx->node2=sortnodesx->gdata[segmentx->node2]; |
1106 | |
1107 | if(segmentx->node1>segmentx->node2) |
1108 | { |
1109 | index_t temp; |
1110 | |
1111 | temp=segmentx->node1; |
1112 | segmentx->node1=segmentx->node2; |
1113 | segmentx->node2=temp; |
1114 | |
1115 | if(segmentx->distance&(ONEWAY_2TO1|ONEWAY_1TO2)) |
1116 | segmentx->distance^=ONEWAY_2TO1|ONEWAY_1TO2; |
1117 | } |
1118 | |
1119 | return(1); |
1120 | } |
1121 | |
1122 | |
1123 | /*++++++++++++++++++++++++++++++++++++++ |
1124 | Save the segment list to a file. |
1125 | |
1126 | SegmentsX *segmentsx The set of segments to save. |
1127 | |
1128 | const char *filename The name of the file to save. |
1129 | ++++++++++++++++++++++++++++++++++++++*/ |
1130 | |
1131 | void SaveSegmentList(SegmentsX *segmentsx,const char *filename) |
1132 | { |
1133 | index_t i; |
1134 | int fd; |
1135 | SegmentsFile segmentsfile={0}; |
1136 | index_t super_number=0,normal_number=0; |
1137 | |
1138 | /* Print the start message */ |
1139 | |
1140 | printf_first("Writing Segments: Segments=0"); |
1141 | |
1142 | /* Re-open the file */ |
1143 | |
1144 | segmentsx->fd=ReOpenFile(segmentsx->filename_tmp); |
1145 | |
1146 | /* Write out the segments data */ |
1147 | |
1148 | fd=OpenFileNew(filename); |
1149 | |
1150 | SeekFile(fd,sizeof(SegmentsFile)); |
1151 | |
1152 | for(i=0;i<segmentsx->number;i++) |
1153 | { |
1154 | SegmentX segmentx; |
1155 | Segment segment={0}; |
1156 | |
1157 | ReadFile(segmentsx->fd,&segmentx,sizeof(SegmentX)); |
1158 | |
1159 | segment.node1 =segmentx.node1; |
1160 | segment.node2 =segmentx.node2; |
1161 | segment.next2 =segmentx.next2; |
1162 | segment.way =segmentx.way; |
1163 | segment.distance=segmentx.distance; |
1164 | |
1165 | if(IsSuperSegment(&segment)) |
1166 | super_number++; |
1167 | if(IsNormalSegment(&segment)) |
1168 | normal_number++; |
1169 | |
1170 | WriteFile(fd,&segment,sizeof(Segment)); |
1171 | |
1172 | if(!((i+1)%10000)) |
1173 | printf_middle("Writing Segments: Segments=%"Pindex_t,i+1); |
1174 | } |
1175 | |
1176 | /* Write out the header structure */ |
1177 | |
1178 | segmentsfile.number=segmentsx->number; |
1179 | segmentsfile.snumber=super_number; |
1180 | segmentsfile.nnumber=normal_number; |
1181 | |
1182 | SeekFile(fd,0); |
1183 | WriteFile(fd,&segmentsfile,sizeof(SegmentsFile)); |
1184 | |
1185 | CloseFile(fd); |
1186 | |
1187 | /* Close the file */ |
1188 | |
1189 | segmentsx->fd=CloseFile(segmentsx->fd); |
1190 | |
1191 | /* Print the final message */ |
1192 | |
1193 | printf_last("Wrote Segments: Segments=%"Pindex_t,segmentsx->number); |
1194 | } |
1195 | |
1196 | |
1197 | /*++++++++++++++++++++++++++++++++++++++ |
1198 | Calculate the distance between two nodes. |
1199 | |
1200 | distance_t DistanceX Returns the distance between the extended nodes. |
1201 | |
1202 | NodeX *nodex1 The starting node. |
1203 | |
1204 | NodeX *nodex2 The end node. |
1205 | ++++++++++++++++++++++++++++++++++++++*/ |
1206 | |
1207 | static distance_t DistanceX(NodeX *nodex1,NodeX *nodex2) |
1208 | { |
1209 | double dlon = latlong_to_radians(nodex1->longitude) - latlong_to_radians(nodex2->longitude); |
1210 | double dlat = latlong_to_radians(nodex1->latitude) - latlong_to_radians(nodex2->latitude); |
1211 | double lat1 = latlong_to_radians(nodex1->latitude); |
1212 | double lat2 = latlong_to_radians(nodex2->latitude); |
1213 | |
1214 | double a1,a2,a,sa,c,d; |
1215 | |
1216 | if(dlon==0 && dlat==0) |
1217 | return 0; |
1218 | |
1219 | a1 = sin (dlat / 2); |
1220 | a2 = sin (dlon / 2); |
1221 | a = (a1 * a1) + cos (lat1) * cos (lat2) * a2 * a2; |
1222 | sa = sqrt (a); |
1223 | if (sa <= 1.0) |
1224 | {c = 2 * asin (sa);} |
1225 | else |
1226 | {c = 2 * asin (1.0);} |
1227 | d = 6378.137 * c; |
1228 | |
1229 | return km_to_distance(d); |
1230 | } |
Properties
Name | Value |
---|---|
cvs:description | Extended segments functions. |