Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino
Annotation of /trunk/src/prunex.c
Parent Directory
|
Revision Log
Revision 1122 -
(hide annotations)
(download)
(as text)
Sat Nov 3 08:58:47 2012 UTC (12 years, 4 months ago) by amb
File MIME type: text/x-csrc
File size: 40108 byte(s)
Sat Nov 3 08:58:47 2012 UTC (12 years, 4 months ago) by amb
File MIME type: text/x-csrc
File size: 40108 byte(s)
Change the UnmapFile() function to take a pointer to the data instead of the filename (like the CloseFile() function takes the file descriptor).
1 | amb | 949 | /*************************************** |
2 | Data pruning functions. | ||
3 | |||
4 | Part of the Routino routing software. | ||
5 | ******************/ /****************** | ||
6 | This file Copyright 2011-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 <stdlib.h> | ||
24 | #include <assert.h> | ||
25 | |||
26 | amb | 964 | #include "types.h" |
27 | #include "segments.h" | ||
28 | |||
29 | amb | 955 | #include "typesx.h" |
30 | amb | 949 | #include "nodesx.h" |
31 | #include "segmentsx.h" | ||
32 | #include "waysx.h" | ||
33 | amb | 955 | |
34 | amb | 949 | #include "prunex.h" |
35 | |||
36 | #include "files.h" | ||
37 | #include "logging.h" | ||
38 | |||
39 | |||
40 | amb | 1117 | /* Global variables */ |
41 | |||
42 | /*+ The command line '--tmpdir' option or its default value. +*/ | ||
43 | extern char *option_tmpdirname; | ||
44 | |||
45 | amb | 949 | /* Local functions */ |
46 | |||
47 | amb | 960 | static void prune_segment(SegmentsX *segmentsx,SegmentX *segmentx); |
48 | amb | 949 | static void modify_segment(SegmentsX *segmentsx,SegmentX *segmentx,index_t newnode1,index_t newnode2); |
49 | |||
50 | amb | 970 | static void unlink_segment_node1_refs(SegmentsX *segmentsx,SegmentX *segmentx); |
51 | static void unlink_segment_node2_refs(SegmentsX *segmentsx,SegmentX *segmentx); | ||
52 | amb | 949 | |
53 | amb | 966 | static double distance(double lat1,double lon1,double lat2,double lon2); |
54 | amb | 949 | |
55 | amb | 966 | |
56 | amb | 949 | /*++++++++++++++++++++++++++++++++++++++ |
57 | Initialise the data structures needed for pruning. | ||
58 | |||
59 | NodesX *nodesx The set of nodes to use. | ||
60 | |||
61 | SegmentsX *segmentsx The set of segments to use. | ||
62 | |||
63 | WaysX *waysx The set of ways to use. | ||
64 | ++++++++++++++++++++++++++++++++++++++*/ | ||
65 | |||
66 | void StartPruning(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx) | ||
67 | { | ||
68 | SegmentX segmentx; | ||
69 | index_t index=0,lastnode1=NO_NODE; | ||
70 | |||
71 | /* Print the start message */ | ||
72 | |||
73 | printf_first("Adding Extra Segment Indexes: Segments=0"); | ||
74 | |||
75 | /* Allocate the array of next segment */ | ||
76 | |||
77 | segmentsx->next1=(index_t*)calloc(segmentsx->number,sizeof(index_t)); | ||
78 | |||
79 | assert(segmentsx->next1); /* Check malloc() worked */ | ||
80 | |||
81 | /* Open the file read-only */ | ||
82 | |||
83 | amb | 1120 | segmentsx->fd=ReOpenFile(segmentsx->filename_tmp); |
84 | amb | 949 | |
85 | /* Read the on-disk image */ | ||
86 | |||
87 | while(!ReadFile(segmentsx->fd,&segmentx,sizeof(SegmentX))) | ||
88 | { | ||
89 | index_t node1=segmentx.node1; | ||
90 | |||
91 | amb | 953 | if(index==0) |
92 | ; | ||
93 | else if(lastnode1==node1) | ||
94 | segmentsx->next1[index-1]=index; | ||
95 | amb | 949 | else |
96 | amb | 953 | segmentsx->next1[index-1]=NO_SEGMENT; |
97 | amb | 949 | |
98 | lastnode1=node1; | ||
99 | index++; | ||
100 | |||
101 | if(!(index%10000)) | ||
102 | printf_middle("Added Extra Segment Indexes: Segments=%"Pindex_t,index); | ||
103 | } | ||
104 | |||
105 | amb | 953 | segmentsx->next1[index-1]=NO_SEGMENT; |
106 | amb | 949 | |
107 | /* Close the file */ | ||
108 | |||
109 | segmentsx->fd=CloseFile(segmentsx->fd); | ||
110 | |||
111 | /* Print the final message */ | ||
112 | |||
113 | printf_last("Added Extra Segment Indexes: Segments=%"Pindex_t,segmentsx->number); | ||
114 | } | ||
115 | |||
116 | |||
117 | /*++++++++++++++++++++++++++++++++++++++ | ||
118 | Delete the data structures needed for pruning. | ||
119 | |||
120 | NodesX *nodesx The set of nodes to use. | ||
121 | |||
122 | SegmentsX *segmentsx The set of segments to use. | ||
123 | |||
124 | WaysX *waysx The set of ways to use. | ||
125 | ++++++++++++++++++++++++++++++++++++++*/ | ||
126 | |||
127 | void FinishPruning(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx) | ||
128 | { | ||
129 | free(segmentsx->next1); | ||
130 | segmentsx->next1=NULL; | ||
131 | } | ||
132 | |||
133 | |||
134 | /*++++++++++++++++++++++++++++++++++++++ | ||
135 | amb | 953 | Prune out any groups of nodes and segments whose total length is less than a |
136 | specified minimum. | ||
137 | |||
138 | NodesX *nodesx The set of nodes to use. | ||
139 | |||
140 | SegmentsX *segmentsx The set of segments to use. | ||
141 | |||
142 | amb | 963 | WaysX *waysx The set of ways to use. |
143 | |||
144 | amb | 953 | distance_t minimum The minimum distance to keep. |
145 | ++++++++++++++++++++++++++++++++++++++*/ | ||
146 | |||
147 | amb | 963 | void PruneIsolatedRegions(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,distance_t minimum) |
148 | amb | 953 | { |
149 | amb | 1117 | transport_t transport; |
150 | amb | 953 | BitMask *connected,*region; |
151 | index_t *regionsegments,*othersegments; | ||
152 | int nallocregionsegments,nallocothersegments; | ||
153 | amb | 1117 | char *newwayfilename; |
154 | index_t nnewways=0; | ||
155 | int fd; | ||
156 | amb | 953 | |
157 | if(nodesx->number==0 || segmentsx->number==0) | ||
158 | return; | ||
159 | |||
160 | /* Map into memory / open the files */ | ||
161 | |||
162 | #if !SLIM | ||
163 | amb | 1120 | nodesx->data=MapFile(nodesx->filename_tmp); |
164 | segmentsx->data=MapFileWriteable(segmentsx->filename_tmp); | ||
165 | waysx->data=MapFile(waysx->filename_tmp); | ||
166 | amb | 953 | #else |
167 | amb | 1120 | nodesx->fd=ReOpenFile(nodesx->filename_tmp); |
168 | segmentsx->fd=ReOpenFileWriteable(segmentsx->filename_tmp); | ||
169 | waysx->fd=ReOpenFile(waysx->filename_tmp); | ||
170 | amb | 953 | #endif |
171 | |||
172 | amb | 1117 | newwayfilename=(char*)malloc(strlen(option_tmpdirname)+36); |
173 | |||
174 | sprintf(newwayfilename,"%s/waysx.%p.new.tmp",option_tmpdirname,(void*)waysx); | ||
175 | |||
176 | fd=OpenFileNew(newwayfilename); | ||
177 | |||
178 | amb | 953 | connected=AllocBitMask(segmentsx->number); |
179 | region =AllocBitMask(segmentsx->number); | ||
180 | |||
181 | assert(connected); /* Check AllocBitMask() worked */ | ||
182 | assert(region); /* Check AllocBitMask() worked */ | ||
183 | |||
184 | regionsegments=(index_t*)malloc((nallocregionsegments=1024)*sizeof(index_t)); | ||
185 | othersegments =(index_t*)malloc((nallocothersegments =1024)*sizeof(index_t)); | ||
186 | |||
187 | assert(regionsegments); /* Check malloc() worked */ | ||
188 | assert(othersegments); /* Check malloc() worked */ | ||
189 | |||
190 | amb | 1117 | /* Loop through the transport types */ |
191 | amb | 953 | |
192 | amb | 1117 | for(transport=Transport_None+1;transport<Transport_Count;transport++) |
193 | amb | 953 | { |
194 | amb | 1117 | index_t i,j; |
195 | index_t nregions=0,npruned=0,nadjusted=0; | ||
196 | const char *transport_str=TransportName(transport); | ||
197 | transports_t transports=TRANSPORTS(transport); | ||
198 | amb | 972 | |
199 | amb | 1117 | /* Print the start message */ |
200 | amb | 972 | |
201 | amb | 1117 | printf_first("Pruning Isolated Regions (%s): Segments=0 Adjusted=0 Pruned=0",transport_str); |
202 | amb | 972 | |
203 | amb | 1117 | /* Loop through the segments and find the disconnected ones */ |
204 | amb | 977 | |
205 | amb | 1117 | ClearAllBits(connected,segmentsx->number); |
206 | ClearAllBits(region ,segmentsx->number); | ||
207 | amb | 977 | |
208 | amb | 1117 | for(i=0;i<segmentsx->number;i++) |
209 | amb | 953 | { |
210 | amb | 1117 | int nregionsegments=0,nothersegments=0; |
211 | distance_t total=0; | ||
212 | SegmentX *segmentx; | ||
213 | WayX *wayx,tmpwayx; | ||
214 | amb | 953 | |
215 | amb | 1117 | segmentx=LookupSegmentX(segmentsx,i,1); |
216 | amb | 953 | |
217 | amb | 1117 | if(IsPrunedSegmentX(segmentx)) |
218 | goto endloop; | ||
219 | amb | 953 | |
220 | amb | 1117 | if(IsBitSet(connected,i)) |
221 | goto endloop; | ||
222 | amb | 953 | |
223 | amb | 1117 | if(segmentx->way<waysx->number) |
224 | wayx=LookupWayX(waysx,segmentx->way,1); | ||
225 | else | ||
226 | SeekReadFile(fd,(wayx=&tmpwayx),sizeof(WayX),(segmentx->way-waysx->number)*sizeof(WayX)); | ||
227 | amb | 953 | |
228 | amb | 1117 | if(!(wayx->way.allow&transports)) |
229 | goto endloop; | ||
230 | amb | 953 | |
231 | amb | 1117 | othersegments[nothersegments++]=i; |
232 | SetBit(region,i); | ||
233 | amb | 953 | |
234 | amb | 1117 | do |
235 | amb | 977 | { |
236 | amb | 1117 | index_t thissegment,nodes[2]; |
237 | amb | 953 | |
238 | amb | 1117 | thissegment=othersegments[--nothersegments]; |
239 | amb | 963 | |
240 | amb | 1117 | if(nregionsegments==nallocregionsegments) |
241 | regionsegments=(index_t*)realloc(regionsegments,(nallocregionsegments+=1024)*sizeof(index_t)); | ||
242 | amb | 977 | |
243 | amb | 1117 | regionsegments[nregionsegments++]=thissegment; |
244 | |||
245 | segmentx=LookupSegmentX(segmentsx,thissegment,1); | ||
246 | |||
247 | nodes[0]=segmentx->node1; | ||
248 | nodes[1]=segmentx->node2; | ||
249 | total+=DISTANCE(segmentx->distance); | ||
250 | |||
251 | for(j=0;j<2;j++) | ||
252 | amb | 953 | { |
253 | amb | 1117 | NodeX *nodex=LookupNodeX(nodesx,nodes[j],1); |
254 | amb | 963 | |
255 | amb | 1117 | if(!(nodex->allow&transports)) |
256 | continue; | ||
257 | |||
258 | segmentx=FirstSegmentX(segmentsx,nodes[j],1); | ||
259 | |||
260 | while(segmentx) | ||
261 | amb | 953 | { |
262 | amb | 1117 | index_t segment=IndexSegmentX(segmentsx,segmentx); |
263 | amb | 953 | |
264 | amb | 1117 | if(segment!=thissegment) |
265 | amb | 953 | { |
266 | amb | 1117 | if(segmentx->way<waysx->number) |
267 | wayx=LookupWayX(waysx,segmentx->way,1); | ||
268 | else | ||
269 | SeekReadFile(fd,(wayx=&tmpwayx),sizeof(WayX),(segmentx->way-waysx->number)*sizeof(WayX)); | ||
270 | amb | 953 | |
271 | amb | 1117 | if(wayx->way.allow&transports) |
272 | amb | 953 | { |
273 | amb | 1117 | /* Already connected - finish */ |
274 | amb | 953 | |
275 | amb | 1117 | if(IsBitSet(connected,segment)) |
276 | { | ||
277 | total=minimum; | ||
278 | goto foundconnection; | ||
279 | } | ||
280 | amb | 963 | |
281 | amb | 1117 | /* Not in region - add to list */ |
282 | amb | 963 | |
283 | amb | 1117 | if(!IsBitSet(region,segment)) |
284 | { | ||
285 | if(nothersegments==nallocothersegments) | ||
286 | othersegments=(index_t*)realloc(othersegments,(nallocothersegments+=1024)*sizeof(index_t)); | ||
287 | |||
288 | othersegments[nothersegments++]=segment; | ||
289 | SetBit(region,segment); | ||
290 | } | ||
291 | amb | 953 | } |
292 | } | ||
293 | amb | 1117 | |
294 | segmentx=NextSegmentX(segmentsx,segmentx,nodes[j]); | ||
295 | amb | 977 | } |
296 | amb | 953 | } |
297 | } | ||
298 | amb | 1117 | while(nothersegments>0 && total<minimum); |
299 | amb | 953 | |
300 | amb | 1117 | foundconnection: |
301 | amb | 953 | |
302 | amb | 1117 | /* Prune the segments or mark them as connected */ |
303 | amb | 953 | |
304 | amb | 1117 | if(total<minimum) /* not connected - delete them */ |
305 | amb | 953 | { |
306 | amb | 1117 | nregions++; |
307 | amb | 953 | |
308 | amb | 1117 | for(j=0;j<nregionsegments;j++) |
309 | { | ||
310 | SegmentX *segmentx; | ||
311 | WayX *wayx,tmpwayx; | ||
312 | amb | 953 | |
313 | amb | 1117 | SetBit(connected,regionsegments[j]); /* not really connected, but don't need to check again */ |
314 | ClearBit(region,regionsegments[j]); | ||
315 | amb | 953 | |
316 | amb | 1117 | segmentx=LookupSegmentX(segmentsx,regionsegments[j],1); |
317 | |||
318 | if(segmentx->way<waysx->number) | ||
319 | wayx=LookupWayX(waysx,segmentx->way,1); | ||
320 | else | ||
321 | SeekReadFile(fd,(wayx=&tmpwayx),sizeof(WayX),(segmentx->way-waysx->number)*sizeof(WayX)); | ||
322 | |||
323 | if(wayx->way.allow==transports) | ||
324 | { | ||
325 | prune_segment(segmentsx,segmentx); | ||
326 | |||
327 | npruned++; | ||
328 | } | ||
329 | else | ||
330 | { | ||
331 | if(segmentx->way<waysx->number) /* create a new way */ | ||
332 | { | ||
333 | tmpwayx=*wayx; | ||
334 | |||
335 | tmpwayx.way.allow&=~transports; | ||
336 | |||
337 | SeekWriteFile(fd,&tmpwayx,sizeof(WayX),nnewways*sizeof(WayX)); | ||
338 | |||
339 | segmentx->way=waysx->number+nnewways; | ||
340 | |||
341 | nnewways++; | ||
342 | |||
343 | PutBackSegmentX(segmentsx,segmentx); | ||
344 | } | ||
345 | else /* modify the existing one */ | ||
346 | { | ||
347 | tmpwayx.way.allow&=~transports; | ||
348 | |||
349 | SeekWriteFile(fd,&tmpwayx,sizeof(WayX),(segmentx->way-waysx->number)*sizeof(WayX)); | ||
350 | } | ||
351 | |||
352 | nadjusted++; | ||
353 | } | ||
354 | } | ||
355 | amb | 953 | } |
356 | amb | 1117 | else /* connected - mark as part of the main region */ |
357 | amb | 953 | { |
358 | amb | 1117 | for(j=0;j<nregionsegments;j++) |
359 | { | ||
360 | SetBit(connected,regionsegments[j]); | ||
361 | ClearBit(region,regionsegments[j]); | ||
362 | } | ||
363 | |||
364 | for(j=0;j<nothersegments;j++) | ||
365 | { | ||
366 | SetBit(connected,othersegments[j]); | ||
367 | ClearBit(region,othersegments[j]); | ||
368 | } | ||
369 | amb | 977 | } |
370 | amb | 953 | |
371 | amb | 1117 | endloop: |
372 | |||
373 | if(!((i+1)%10000)) | ||
374 | printf_middle("Pruning Isolated Regions (%s): Segments=%"Pindex_t" Adjusted=%"Pindex_t" Pruned=%"Pindex_t" (%"Pindex_t" Regions)",transport_str,i+1,nadjusted,npruned,nregions); | ||
375 | amb | 953 | } |
376 | |||
377 | amb | 1117 | /* Print the final message */ |
378 | amb | 977 | |
379 | amb | 1117 | printf_last("Pruned Isolated Regions (%s): Segments=%"Pindex_t" Adjusted=%"Pindex_t" Pruned=%"Pindex_t" (%"Pindex_t" Regions)",transport_str,segmentsx->number,nadjusted,npruned,nregions); |
380 | amb | 953 | } |
381 | |||
382 | /* Unmap from memory / close the files */ | ||
383 | |||
384 | free(region); | ||
385 | free(connected); | ||
386 | |||
387 | free(regionsegments); | ||
388 | free(othersegments); | ||
389 | |||
390 | #if !SLIM | ||
391 | amb | 1122 | nodesx->data=UnmapFile(nodesx->data); |
392 | segmentsx->data=UnmapFile(segmentsx->data); | ||
393 | waysx->data=UnmapFile(waysx->data); | ||
394 | amb | 953 | #else |
395 | nodesx->fd=CloseFile(nodesx->fd); | ||
396 | segmentsx->fd=CloseFile(segmentsx->fd); | ||
397 | amb | 963 | waysx->fd=CloseFile(waysx->fd); |
398 | amb | 953 | #endif |
399 | |||
400 | amb | 1117 | /* Append the new ways to the end of the existing ones */ |
401 | amb | 953 | |
402 | amb | 1117 | SeekFile(fd,0); |
403 | |||
404 | amb | 1120 | waysx->fd=OpenFileAppend(waysx->filename_tmp); |
405 | amb | 1117 | |
406 | for(;nnewways>0;nnewways--) | ||
407 | { | ||
408 | WayX wayx; | ||
409 | |||
410 | ReadFile(fd,&wayx,sizeof(WayX)); | ||
411 | WriteFile(waysx->fd,&wayx,sizeof(WayX)); | ||
412 | |||
413 | waysx->number++; | ||
414 | } | ||
415 | |||
416 | waysx->fd=CloseFile(waysx->fd); | ||
417 | |||
418 | CloseFile(fd); | ||
419 | |||
420 | DeleteFile(newwayfilename); | ||
421 | amb | 953 | } |
422 | |||
423 | |||
424 | /*++++++++++++++++++++++++++++++++++++++ | ||
425 | amb | 964 | Prune out any segments that are shorter than a specified minimum. |
426 | |||
427 | NodesX *nodesx The set of nodes to use. | ||
428 | |||
429 | SegmentsX *segmentsx The set of segments to use. | ||
430 | |||
431 | WaysX *waysx The set of ways to use. | ||
432 | |||
433 | amb | 966 | distance_t minimum The maximum length to remove or one less than the minimum length to keep. |
434 | amb | 964 | ++++++++++++++++++++++++++++++++++++++*/ |
435 | |||
436 | void PruneShortSegments(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,distance_t minimum) | ||
437 | { | ||
438 | index_t i; | ||
439 | index_t nshort=0,npruned=0; | ||
440 | |||
441 | if(nodesx->number==0 || segmentsx->number==0 || waysx->number==0) | ||
442 | return; | ||
443 | |||
444 | /* Print the start message */ | ||
445 | |||
446 | printf_first("Pruning Short Segments: Segments=0 Short=0 Pruned=0"); | ||
447 | |||
448 | /* Map into memory / open the files */ | ||
449 | |||
450 | #if !SLIM | ||
451 | amb | 1120 | nodesx->data=MapFileWriteable(nodesx->filename_tmp); |
452 | segmentsx->data=MapFileWriteable(segmentsx->filename_tmp); | ||
453 | waysx->data=MapFile(waysx->filename_tmp); | ||
454 | amb | 964 | #else |
455 | amb | 1120 | nodesx->fd=ReOpenFileWriteable(nodesx->filename_tmp); |
456 | segmentsx->fd=ReOpenFileWriteable(segmentsx->filename_tmp); | ||
457 | waysx->fd=ReOpenFile(waysx->filename_tmp); | ||
458 | amb | 964 | #endif |
459 | |||
460 | /* Loop through the segments and find the short ones for possible modification */ | ||
461 | |||
462 | for(i=0;i<segmentsx->number;i++) | ||
463 | { | ||
464 | SegmentX *segmentx2=LookupSegmentX(segmentsx,i,2); | ||
465 | |||
466 | if(IsPrunedSegmentX(segmentx2)) | ||
467 | amb | 966 | goto endloop; |
468 | amb | 964 | |
469 | /* | ||
470 | : | ||
471 | Initial state: ..N3 -------- N2 | ||
472 | : S2 | ||
473 | |||
474 | : | ||
475 | Final state: ..N3 N2 -- | ||
476 | : S2 | ||
477 | |||
478 | = OR = | ||
479 | |||
480 | : : | ||
481 | Initial state: ..N1 -------- N2 ---- N3 -------- N4.. | ||
482 | : S1 S2 S3 : | ||
483 | |||
484 | : : | ||
485 | Final state: ..N1 ------------ N3 ------------ N4.. N2 -- | ||
486 | : S1 S3 : S2 | ||
487 | |||
488 | Not if N1 is the same as N4. | ||
489 | Not if S2 has different one-way properties from S1 and S3. | ||
490 | Must combine N2, S2 and N3 disallowed transports into new N3. | ||
491 | Must not delete N2 or N3 if they are mini-roundabouts. | ||
492 | Must not delete N2 or N3 if they are part of turn relations. | ||
493 | |||
494 | = OR = | ||
495 | |||
496 | : : | ||
497 | Initial state: ..N1 -------- N2 ---- N3.. | ||
498 | : S1 S2 : | ||
499 | |||
500 | : : | ||
501 | Final state: ..N1 ------------ N3.. N2 -- | ||
502 | : S1 : S2 | ||
503 | |||
504 | Not if N1 is the same as N3. | ||
505 | Not if S1 has different one-way properties from S2. | ||
506 | Not if S1 has different highway properties from S2. | ||
507 | Not if N2 disallows transports allowed on S1 and S2. | ||
508 | Not if N2 is a mini-roundabouts. | ||
509 | Not if N2 is involved in a turn restriction. | ||
510 | */ | ||
511 | |||
512 | if(DISTANCE(segmentx2->distance)<=minimum) | ||
513 | { | ||
514 | amb | 973 | index_t node1=NO_NODE,node2,node3,node4=NO_NODE; |
515 | amb | 964 | index_t segment1=NO_SEGMENT,segment2=i,segment3=NO_SEGMENT; |
516 | SegmentX *segmentx; | ||
517 | int segcount2=0,segcount3=0; | ||
518 | |||
519 | nshort++; | ||
520 | |||
521 | node2=segmentx2->node1; | ||
522 | node3=segmentx2->node2; | ||
523 | |||
524 | /* Count the segments connected to N2 and N3 */ | ||
525 | |||
526 | segmentx=FirstSegmentX(segmentsx,node2,4); | ||
527 | |||
528 | while(segmentx) | ||
529 | { | ||
530 | segcount2++; | ||
531 | |||
532 | if(segment1==NO_SEGMENT) | ||
533 | { | ||
534 | index_t segment=IndexSegmentX(segmentsx,segmentx); | ||
535 | |||
536 | if(segment!=segment2) | ||
537 | { | ||
538 | segment1=segment; | ||
539 | node1=OtherNode(segmentx,node2); | ||
540 | } | ||
541 | } | ||
542 | |||
543 | segmentx=NextSegmentX(segmentsx,segmentx,node2); | ||
544 | } | ||
545 | |||
546 | segmentx=FirstSegmentX(segmentsx,node3,4); | ||
547 | |||
548 | while(segmentx) | ||
549 | { | ||
550 | segcount3++; | ||
551 | |||
552 | if(segment3==NO_SEGMENT) | ||
553 | { | ||
554 | index_t segment=IndexSegmentX(segmentsx,segmentx); | ||
555 | |||
556 | if(segment!=segment2) | ||
557 | { | ||
558 | segment3=segment; | ||
559 | node4=OtherNode(segmentx,node3); | ||
560 | } | ||
561 | } | ||
562 | |||
563 | segmentx=NextSegmentX(segmentsx,segmentx,node3); | ||
564 | } | ||
565 | |||
566 | /* Check which case we are handling (and canonicalise) */ | ||
567 | |||
568 | if(segcount2>2 && segcount3>2) /* none of the cases in diagram - too complicated */ | ||
569 | { | ||
570 | goto endloop; | ||
571 | } | ||
572 | else if(segcount2==1 || segcount3==1) /* first case in diagram - prune segment */ | ||
573 | { | ||
574 | prune_segment(segmentsx,segmentx2); | ||
575 | } | ||
576 | else if(segcount2==2 && segcount3==2) /* second case in diagram - modify one segment and prune segment */ | ||
577 | { | ||
578 | SegmentX *segmentx1,*segmentx3; | ||
579 | WayX *wayx1,*wayx2,*wayx3; | ||
580 | NodeX *nodex2,*nodex3,*newnodex; | ||
581 | index_t newnode; | ||
582 | int join12=1,join23=1; | ||
583 | |||
584 | /* Check if pruning would collapse a loop */ | ||
585 | |||
586 | if(node1==node4) | ||
587 | goto endloop; | ||
588 | |||
589 | /* Check if allowed due to one-way properties */ | ||
590 | |||
591 | segmentx1=LookupSegmentX(segmentsx,segment1,1); | ||
592 | segmentx3=LookupSegmentX(segmentsx,segment3,3); | ||
593 | |||
594 | if(!IsOneway(segmentx1) && !IsOneway(segmentx2)) | ||
595 | ; | ||
596 | else if(IsOneway(segmentx1) && IsOneway(segmentx2)) | ||
597 | { | ||
598 | if(IsOnewayTo(segmentx1,node2) && !IsOnewayFrom(segmentx2,node2)) /* S1 is one-way but S2 doesn't continue */ | ||
599 | join12=0; | ||
600 | |||
601 | if(IsOnewayFrom(segmentx1,node2) && !IsOnewayTo(segmentx2,node2)) /* S1 is one-way but S2 doesn't continue */ | ||
602 | join12=0; | ||
603 | } | ||
604 | else | ||
605 | join12=0; | ||
606 | |||
607 | if(!IsOneway(segmentx3) && !IsOneway(segmentx2)) | ||
608 | ; | ||
609 | else if(IsOneway(segmentx3) && IsOneway(segmentx2)) | ||
610 | { | ||
611 | if(IsOnewayTo(segmentx3,node3) && !IsOnewayFrom(segmentx2,node3)) /* S3 is one-way but S2 doesn't continue */ | ||
612 | join23=0; | ||
613 | |||
614 | if(IsOnewayFrom(segmentx3,node3) && !IsOnewayTo(segmentx2,node3)) /* S3 is one-way but S2 doesn't continue */ | ||
615 | join23=0; | ||
616 | } | ||
617 | else | ||
618 | join23=0; | ||
619 | |||
620 | if(!join12 && !join23) | ||
621 | goto endloop; | ||
622 | |||
623 | /* Check if allowed due to mini-roundabout and turn restriction */ | ||
624 | |||
625 | nodex2=LookupNodeX(nodesx,node2,2); | ||
626 | nodex3=LookupNodeX(nodesx,node3,3); | ||
627 | |||
628 | if(nodex2->flags&NODE_MINIRNDBT) | ||
629 | join12=0; | ||
630 | |||
631 | if(nodex3->flags&NODE_MINIRNDBT) | ||
632 | join23=0; | ||
633 | |||
634 | if(nodex2->flags&NODE_TURNRSTRCT2 || nodex2->flags&NODE_TURNRSTRCT) | ||
635 | join12=0; | ||
636 | |||
637 | if(nodex3->flags&NODE_TURNRSTRCT2 || nodex3->flags&NODE_TURNRSTRCT) | ||
638 | join23=0; | ||
639 | |||
640 | if(!join12 && !join23) | ||
641 | goto endloop; | ||
642 | |||
643 | /* New node properties */ | ||
644 | |||
645 | if(join12) | ||
646 | { | ||
647 | newnode=node3; | ||
648 | newnodex=nodex3; | ||
649 | } | ||
650 | else /* if(join23) */ | ||
651 | { | ||
652 | newnode=node2; | ||
653 | newnodex=nodex2; | ||
654 | } | ||
655 | |||
656 | wayx1=LookupWayX(waysx,segmentx1->way,1); | ||
657 | wayx2=LookupWayX(waysx,segmentx2->way,2); | ||
658 | wayx3=LookupWayX(waysx,segmentx3->way,3); | ||
659 | |||
660 | newnodex->allow=nodex2->allow&nodex3->allow; /* combine the restrictions of the two nodes */ | ||
661 | newnodex->allow&=~((~wayx2->way.allow)&wayx3->way.allow); /* disallow anything blocked by segment2 */ | ||
662 | newnodex->allow&=~((~wayx2->way.allow)&wayx1->way.allow); /* disallow anything blocked by segment2 */ | ||
663 | |||
664 | newnodex->latitude =(nodex2->latitude +nodex3->latitude )/2; | ||
665 | newnodex->longitude=(nodex2->longitude+nodex3->longitude)/2; | ||
666 | |||
667 | PutBackNodeX(nodesx,newnodex); | ||
668 | |||
669 | /* Modify segments */ | ||
670 | |||
671 | segmentx1->distance+=DISTANCE(segmentx2->distance)/2; | ||
672 | segmentx3->distance+=DISTANCE(segmentx2->distance)-DISTANCE(segmentx2->distance)/2; | ||
673 | |||
674 | if(segmentx1->node1==node1) | ||
675 | { | ||
676 | if(segmentx1->node2!=newnode) | ||
677 | modify_segment(segmentsx,segmentx1,node1,newnode); | ||
678 | amb | 1121 | else |
679 | PutBackSegmentX(segmentsx,segmentx1); | ||
680 | amb | 964 | } |
681 | else /* if(segmentx1->node2==node1) */ | ||
682 | { | ||
683 | if(segmentx1->node1!=newnode) | ||
684 | modify_segment(segmentsx,segmentx1,newnode,node1); | ||
685 | amb | 1121 | else |
686 | PutBackSegmentX(segmentsx,segmentx1); | ||
687 | amb | 964 | } |
688 | |||
689 | if(segmentx3->node1==node4) | ||
690 | { | ||
691 | if(segmentx3->node2!=newnode) | ||
692 | modify_segment(segmentsx,segmentx3,node4,newnode); | ||
693 | amb | 1121 | else |
694 | PutBackSegmentX(segmentsx,segmentx3); | ||
695 | amb | 964 | } |
696 | else /* if(segmentx3->node2==node4) */ | ||
697 | { | ||
698 | if(segmentx3->node1!=newnode) | ||
699 | modify_segment(segmentsx,segmentx3,newnode,node4); | ||
700 | amb | 1121 | else |
701 | PutBackSegmentX(segmentsx,segmentx3); | ||
702 | amb | 964 | } |
703 | amb | 1121 | |
704 | ReLookupSegmentX(segmentsx,segmentx2); | ||
705 | |||
706 | prune_segment(segmentsx,segmentx2); | ||
707 | amb | 964 | } |
708 | else /* third case in diagram - prune one segment */ | ||
709 | { | ||
710 | SegmentX *segmentx1; | ||
711 | WayX *wayx1,*wayx2; | ||
712 | NodeX *nodex2; | ||
713 | |||
714 | if(segcount3==2) /* not as in diagram, shuffle things round */ | ||
715 | { | ||
716 | index_t temp; | ||
717 | |||
718 | temp=segment1; segment1=segment3; segment3=temp; | ||
719 | temp=node1; node1=node4; node4=temp; | ||
720 | temp=node2; node2=node3; node3=temp; | ||
721 | } | ||
722 | |||
723 | /* Check if pruning would collapse a loop */ | ||
724 | |||
725 | if(node1==node3) | ||
726 | goto endloop; | ||
727 | |||
728 | /* Check if allowed due to one-way properties */ | ||
729 | |||
730 | segmentx1=LookupSegmentX(segmentsx,segment1,1); | ||
731 | |||
732 | if(!IsOneway(segmentx1) && !IsOneway(segmentx2)) | ||
733 | ; | ||
734 | else if(IsOneway(segmentx1) && IsOneway(segmentx2)) | ||
735 | { | ||
736 | if(IsOnewayTo(segmentx1,node2) && !IsOnewayFrom(segmentx2,node2)) /* S1 is one-way but S2 doesn't continue */ | ||
737 | goto endloop; | ||
738 | |||
739 | if(IsOnewayFrom(segmentx1,node2) && !IsOnewayTo(segmentx2,node2)) /* S1 is one-way but S2 doesn't continue */ | ||
740 | goto endloop; | ||
741 | } | ||
742 | else | ||
743 | goto endloop; | ||
744 | |||
745 | amb | 976 | /* Check if allowed due to highway properties */ |
746 | |||
747 | wayx1=LookupWayX(waysx,segmentx1->way,1); | ||
748 | wayx2=LookupWayX(waysx,segmentx2->way,2); | ||
749 | |||
750 | if(WaysCompare(&wayx1->way,&wayx2->way)) | ||
751 | goto endloop; | ||
752 | |||
753 | amb | 964 | /* Check if allowed due to mini-roundabout and turn restriction */ |
754 | |||
755 | nodex2=LookupNodeX(nodesx,node2,2); | ||
756 | |||
757 | if(nodex2->flags&NODE_MINIRNDBT) | ||
758 | goto endloop; | ||
759 | |||
760 | if(nodex2->flags&NODE_TURNRSTRCT2 || nodex2->flags&NODE_TURNRSTRCT) | ||
761 | goto endloop; | ||
762 | |||
763 | /* Check if allowed due to node restrictions */ | ||
764 | |||
765 | if((nodex2->allow&wayx1->way.allow)!=wayx1->way.allow) | ||
766 | goto endloop; | ||
767 | |||
768 | if((nodex2->allow&wayx2->way.allow)!=wayx2->way.allow) | ||
769 | goto endloop; | ||
770 | |||
771 | /* Modify segments */ | ||
772 | |||
773 | segmentx1->distance+=DISTANCE(segmentx2->distance); | ||
774 | |||
775 | if(segmentx1->node1==node1) | ||
776 | modify_segment(segmentsx,segmentx1,node1,node3); | ||
777 | else /* if(segmentx1->node2==node1) */ | ||
778 | modify_segment(segmentsx,segmentx1,node3,node1); | ||
779 | amb | 1121 | |
780 | ReLookupSegmentX(segmentsx,segmentx2); | ||
781 | |||
782 | prune_segment(segmentsx,segmentx2); | ||
783 | amb | 964 | } |
784 | |||
785 | npruned++; | ||
786 | } | ||
787 | |||
788 | endloop: | ||
789 | |||
790 | if(!((i+1)%10000)) | ||
791 | printf_middle("Pruning Short Segments: Segments=%"Pindex_t" Short=%"Pindex_t" Pruned=%"Pindex_t,i+1,nshort,npruned); | ||
792 | } | ||
793 | |||
794 | /* Unmap from memory / close the files */ | ||
795 | |||
796 | #if !SLIM | ||
797 | amb | 1122 | nodesx->data=UnmapFile(nodesx->data); |
798 | segmentsx->data=UnmapFile(segmentsx->data); | ||
799 | waysx->data=UnmapFile(waysx->data); | ||
800 | amb | 964 | #else |
801 | nodesx->fd=CloseFile(nodesx->fd); | ||
802 | segmentsx->fd=CloseFile(segmentsx->fd); | ||
803 | waysx->fd=CloseFile(waysx->fd); | ||
804 | #endif | ||
805 | |||
806 | /* Print the final message */ | ||
807 | |||
808 | printf_last("Pruned Short Segments: Segments=%"Pindex_t" Short=%"Pindex_t" Pruned=%"Pindex_t,segmentsx->number,nshort,npruned); | ||
809 | } | ||
810 | |||
811 | |||
812 | /*++++++++++++++++++++++++++++++++++++++ | ||
813 | amb | 966 | Prune out any nodes from straight highways where the introduced error is smaller than a specified maximum. |
814 | |||
815 | NodesX *nodesx The set of nodes to use. | ||
816 | |||
817 | SegmentsX *segmentsx The set of segments to use. | ||
818 | |||
819 | WaysX *waysx The set of ways to use. | ||
820 | |||
821 | distance_t maximum The maximum error to introduce. | ||
822 | ++++++++++++++++++++++++++++++++++++++*/ | ||
823 | |||
824 | void PruneStraightHighwayNodes(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,distance_t maximum) | ||
825 | { | ||
826 | index_t i; | ||
827 | index_t npruned=0; | ||
828 | BitMask *checked; | ||
829 | amb | 967 | int nalloc; |
830 | amb | 966 | index_t *nodes,*segments; |
831 | amb | 967 | double *lats,*lons; |
832 | amb | 966 | double maximumf; |
833 | |||
834 | if(nodesx->number==0 || segmentsx->number==0 || waysx->number==0) | ||
835 | return; | ||
836 | |||
837 | maximumf=distance_to_km(maximum); | ||
838 | |||
839 | /* Print the start message */ | ||
840 | |||
841 | printf_first("Pruning Straight Highway Nodes: Nodes=0 Pruned=0"); | ||
842 | |||
843 | /* Map into memory / open the files */ | ||
844 | |||
845 | #if !SLIM | ||
846 | amb | 1120 | nodesx->data=MapFile(nodesx->filename_tmp); |
847 | segmentsx->data=MapFileWriteable(segmentsx->filename_tmp); | ||
848 | waysx->data=MapFile(waysx->filename_tmp); | ||
849 | amb | 966 | #else |
850 | amb | 1120 | nodesx->fd=ReOpenFile(nodesx->filename_tmp); |
851 | segmentsx->fd=ReOpenFileWriteable(segmentsx->filename_tmp); | ||
852 | waysx->fd=ReOpenFile(waysx->filename_tmp); | ||
853 | amb | 966 | #endif |
854 | |||
855 | checked=AllocBitMask(nodesx->number); | ||
856 | |||
857 | assert(checked); /* Check AllocBitMask() worked */ | ||
858 | |||
859 | nodes =(index_t*)malloc((nalloc=1024)*sizeof(index_t)); | ||
860 | segments=(index_t*)malloc( nalloc *sizeof(index_t)); | ||
861 | |||
862 | assert(nodes); /* Check malloc() worked */ | ||
863 | assert(segments); /* Check malloc() worked */ | ||
864 | |||
865 | amb | 967 | lats=(double*)malloc(nalloc*sizeof(double)); |
866 | lons=(double*)malloc(nalloc*sizeof(double)); | ||
867 | |||
868 | assert(lats); /* Check malloc() worked */ | ||
869 | assert(lons); /* Check malloc() worked */ | ||
870 | |||
871 | amb | 966 | /* Loop through the nodes and find stretchs of simple highway for possible modification */ |
872 | |||
873 | for(i=0;i<nodesx->number;i++) | ||
874 | { | ||
875 | amb | 976 | int lowerbounded=0,upperbounded=0; |
876 | amb | 966 | index_t lower=nalloc/2,current=nalloc/2,upper=nalloc/2; |
877 | |||
878 | amb | 976 | if(IsBitSet(checked,i)) |
879 | amb | 966 | goto endloop; |
880 | |||
881 | amb | 976 | if(segmentsx->firstnode[i]==NO_SEGMENT) |
882 | amb | 966 | goto endloop; |
883 | |||
884 | /* Find all connected nodes */ | ||
885 | |||
886 | nodes[current]=i; | ||
887 | |||
888 | do | ||
889 | { | ||
890 | index_t node1=NO_NODE,node2=NO_NODE; | ||
891 | amb | 973 | index_t segment1=NO_SEGMENT,segment2=NO_SEGMENT; |
892 | index_t way1=NO_WAY,way2=NO_WAY; | ||
893 | amb | 966 | int segcount=0; |
894 | amb | 967 | NodeX *nodex; |
895 | amb | 966 | |
896 | if(!IsBitSet(checked,nodes[current])) | ||
897 | { | ||
898 | SegmentX *segmentx; | ||
899 | |||
900 | /* Count the segments connected to the node */ | ||
901 | |||
902 | segmentx=FirstSegmentX(segmentsx,nodes[current],1); | ||
903 | |||
904 | while(segmentx) | ||
905 | { | ||
906 | segcount++; | ||
907 | |||
908 | if(node1==NO_NODE) | ||
909 | { | ||
910 | segment1=IndexSegmentX(segmentsx,segmentx); | ||
911 | node1=OtherNode(segmentx,nodes[current]); | ||
912 | way1=segmentx->way; | ||
913 | } | ||
914 | else if(node2==NO_NODE) | ||
915 | { | ||
916 | segment2=IndexSegmentX(segmentsx,segmentx); | ||
917 | node2=OtherNode(segmentx,nodes[current]); | ||
918 | way2=segmentx->way; | ||
919 | } | ||
920 | |||
921 | segmentx=NextSegmentX(segmentsx,segmentx,nodes[current]); | ||
922 | } | ||
923 | } | ||
924 | |||
925 | /* Perform more checks */ | ||
926 | |||
927 | amb | 967 | nodex=LookupNodeX(nodesx,nodes[current],1); |
928 | |||
929 | lats[current]=latlong_to_radians(nodex->latitude); | ||
930 | lons[current]=latlong_to_radians(nodex->longitude); | ||
931 | |||
932 | /* Check if allowed due to mini-roundabout and turn restriction */ | ||
933 | |||
934 | if(nodex->flags&NODE_MINIRNDBT) | ||
935 | segcount=0; | ||
936 | |||
937 | if(nodex->flags&NODE_TURNRSTRCT2 || nodex->flags&NODE_TURNRSTRCT) | ||
938 | segcount=0; | ||
939 | |||
940 | /* Check if allowed due to one-way properties */ | ||
941 | |||
942 | amb | 966 | if(segcount==2) |
943 | { | ||
944 | SegmentX *segmentx1,*segmentx2; | ||
945 | |||
946 | segmentx1=LookupSegmentX(segmentsx,segment1,1); | ||
947 | segmentx2=LookupSegmentX(segmentsx,segment2,2); | ||
948 | |||
949 | if(!IsOneway(segmentx1) && !IsOneway(segmentx2)) | ||
950 | ; | ||
951 | else if(IsOneway(segmentx1) && IsOneway(segmentx2)) | ||
952 | { | ||
953 | if(IsOnewayTo(segmentx1,nodes[current]) && !IsOnewayFrom(segmentx2,nodes[current])) /* S1 is one-way but S2 doesn't continue */ | ||
954 | segcount=0; | ||
955 | |||
956 | if(IsOnewayFrom(segmentx1,nodes[current]) && !IsOnewayTo(segmentx2,nodes[current])) /* S1 is one-way but S2 doesn't continue */ | ||
957 | segcount=0; | ||
958 | } | ||
959 | else | ||
960 | segcount=0; | ||
961 | } | ||
962 | |||
963 | amb | 967 | /* Check if allowed due to highway properties and node restrictions */ |
964 | |||
965 | amb | 966 | if(segcount==2) |
966 | { | ||
967 | WayX *wayx1,*wayx2; | ||
968 | |||
969 | wayx1=LookupWayX(waysx,way1,1); | ||
970 | wayx2=LookupWayX(waysx,way2,2); | ||
971 | |||
972 | if(WaysCompare(&wayx1->way,&wayx2->way)) | ||
973 | segcount=0; | ||
974 | |||
975 | amb | 971 | if(wayx1->way.name!=wayx2->way.name) |
976 | segcount=0; | ||
977 | |||
978 | amb | 966 | if((nodex->allow&wayx1->way.allow)!=wayx1->way.allow) |
979 | segcount=0; | ||
980 | |||
981 | if((nodex->allow&wayx2->way.allow)!=wayx2->way.allow) | ||
982 | segcount=0; | ||
983 | } | ||
984 | |||
985 | /* Update the lists */ | ||
986 | |||
987 | if(segcount==2) | ||
988 | { | ||
989 | amb | 970 | if(upper==(nalloc-1)) |
990 | amb | 966 | { |
991 | nodes =(index_t*)realloc(nodes ,(nalloc+=1024)*sizeof(index_t)); | ||
992 | segments=(index_t*)realloc(segments, nalloc *sizeof(index_t)); | ||
993 | amb | 967 | |
994 | lats=(double*)realloc(lats,nalloc*sizeof(double)); | ||
995 | lons=(double*)realloc(lons,nalloc*sizeof(double)); | ||
996 | amb | 966 | } |
997 | |||
998 | if(lower==0) /* move everything up by one */ | ||
999 | { | ||
1000 | amb | 1017 | memmove(nodes+1 ,nodes ,(1+upper-lower)*sizeof(index_t)); |
1001 | memmove(segments+1,segments,(1+upper-lower)*sizeof(index_t)); | ||
1002 | amb | 966 | |
1003 | amb | 1017 | memmove(lats+1,lats,(1+upper-lower)*sizeof(double)); |
1004 | memmove(lons+1,lons,(1+upper-lower)*sizeof(double)); | ||
1005 | amb | 967 | |
1006 | amb | 966 | current++; |
1007 | lower++; | ||
1008 | upper++; | ||
1009 | } | ||
1010 | |||
1011 | if(lower==upper) /* first */ | ||
1012 | { | ||
1013 | lower--; | ||
1014 | |||
1015 | nodes[lower]=node1; | ||
1016 | segments[lower]=segment1; | ||
1017 | |||
1018 | upper++; | ||
1019 | |||
1020 | nodes[upper]=node2; | ||
1021 | segments[upper-1]=segment2; | ||
1022 | |||
1023 | current--; | ||
1024 | } | ||
1025 | else if(current==lower) | ||
1026 | { | ||
1027 | lower--; | ||
1028 | |||
1029 | if(nodes[current+1]==node2) | ||
1030 | { | ||
1031 | nodes[lower]=node1; | ||
1032 | segments[lower]=segment1; | ||
1033 | } | ||
1034 | else /* if(nodes[current+1]==node1) */ | ||
1035 | { | ||
1036 | nodes[lower]=node2; | ||
1037 | segments[lower]=segment2; | ||
1038 | } | ||
1039 | |||
1040 | current--; | ||
1041 | } | ||
1042 | else /* if(current==upper) */ | ||
1043 | { | ||
1044 | upper++; | ||
1045 | |||
1046 | if(nodes[current-1]==node2) | ||
1047 | { | ||
1048 | nodes[upper]=node1; | ||
1049 | segments[upper-1]=segment1; | ||
1050 | } | ||
1051 | else /* if(nodes[current-1]==node1) */ | ||
1052 | { | ||
1053 | nodes[upper]=node2; | ||
1054 | segments[upper-1]=segment2; | ||
1055 | } | ||
1056 | |||
1057 | current++; | ||
1058 | } | ||
1059 | |||
1060 | if(nodes[upper]==nodes[lower]) | ||
1061 | { | ||
1062 | lowerbounded=1; | ||
1063 | upperbounded=1; | ||
1064 | } | ||
1065 | } | ||
1066 | else | ||
1067 | { | ||
1068 | if(current==upper) | ||
1069 | upperbounded=1; | ||
1070 | |||
1071 | if(current==lower) | ||
1072 | { | ||
1073 | lowerbounded=1; | ||
1074 | current=upper; | ||
1075 | } | ||
1076 | } | ||
1077 | } | ||
1078 | while(!(lowerbounded && upperbounded)); | ||
1079 | |||
1080 | amb | 967 | /* Mark the nodes */ |
1081 | |||
1082 | for(current=lower;current<=upper;current++) | ||
1083 | SetBit(checked,nodes[current]); | ||
1084 | |||
1085 | amb | 966 | /* Check for straight highway */ |
1086 | |||
1087 | while((upper-lower)>=2) | ||
1088 | { | ||
1089 | amb | 967 | index_t bestc=lower; |
1090 | amb | 966 | |
1091 | amb | 967 | for(current=lower+2;current<=upper;current++) |
1092 | amb | 966 | { |
1093 | amb | 967 | double dist1,dist2,dist3,dist3a,dist3b,distp; |
1094 | index_t c; | ||
1095 | amb | 966 | |
1096 | amb | 967 | dist3=distance(lats[lower],lons[lower],lats[current],lons[current]); |
1097 | amb | 966 | |
1098 | amb | 967 | for(c=lower+1;c<current;c++) |
1099 | amb | 966 | { |
1100 | amb | 967 | dist1=distance(lats[lower] ,lons[lower] ,lats[c],lons[c]); |
1101 | dist2=distance(lats[current],lons[current],lats[c],lons[c]); | ||
1102 | amb | 966 | |
1103 | amb | 967 | /* Use law of cosines (assume flat Earth) */ |
1104 | amb | 966 | |
1105 | amb | 967 | dist3a=(dist1*dist1-dist2*dist2+dist3*dist3)/(2.0*dist3); |
1106 | dist3b=dist3-dist3a; | ||
1107 | amb | 966 | |
1108 | amb | 967 | if((dist1+dist2)<dist3) |
1109 | distp=0; | ||
1110 | else if(dist3a>=0 && dist3b>=0) | ||
1111 | distp=sqrt(dist1*dist1-dist3a*dist3a); | ||
1112 | else if(dist3a>0) | ||
1113 | distp=dist2; | ||
1114 | else /* if(dist3b>0) */ | ||
1115 | distp=dist1; | ||
1116 | amb | 966 | |
1117 | amb | 967 | if(distp>maximumf) /* gone too far */ |
1118 | break; | ||
1119 | } | ||
1120 | amb | 966 | |
1121 | amb | 967 | if(c>bestc) |
1122 | bestc=c; | ||
1123 | amb | 966 | |
1124 | amb | 967 | if(bestc>c) |
1125 | c=bestc; | ||
1126 | amb | 966 | |
1127 | amb | 967 | if(c==current && current!=upper) /* Can replace at least this far (not finished yet) */ |
1128 | continue; | ||
1129 | amb | 966 | |
1130 | amb | 967 | if((c-lower)<2) /* first three points are not straight */ |
1131 | { | ||
1132 | lower=c; | ||
1133 | break; | ||
1134 | } | ||
1135 | else /* delete some segments and shift along */ | ||
1136 | { | ||
1137 | SegmentX *segmentx; | ||
1138 | distance_t distance=0; | ||
1139 | amb | 966 | |
1140 | amb | 967 | current=c; |
1141 | amb | 966 | |
1142 | amb | 967 | for(c=lower+1;c<current;c++) |
1143 | { | ||
1144 | segmentx=LookupSegmentX(segmentsx,segments[c],1); | ||
1145 | amb | 966 | |
1146 | amb | 967 | distance+=DISTANCE(segmentx->distance); |
1147 | amb | 966 | |
1148 | amb | 967 | prune_segment(segmentsx,segmentx); |
1149 | amb | 966 | |
1150 | amb | 967 | npruned++; |
1151 | } | ||
1152 | amb | 966 | |
1153 | amb | 967 | segmentx=LookupSegmentX(segmentsx,segments[lower],1); |
1154 | amb | 966 | |
1155 | amb | 970 | if(nodes[lower]==nodes[current]) /* loop; all within maximum distance */ |
1156 | { | ||
1157 | prune_segment(segmentsx,segmentx); | ||
1158 | amb | 966 | |
1159 | amb | 970 | npruned++; |
1160 | } | ||
1161 | else | ||
1162 | { | ||
1163 | segmentx->distance+=distance; | ||
1164 | amb | 966 | |
1165 | amb | 970 | if(segmentx->node1==nodes[lower]) |
1166 | modify_segment(segmentsx,segmentx,nodes[lower],nodes[current]); | ||
1167 | else /* if(segmentx->node2==nodes[lower]) */ | ||
1168 | modify_segment(segmentsx,segmentx,nodes[current],nodes[lower]); | ||
1169 | } | ||
1170 | |||
1171 | amb | 967 | lower=current; |
1172 | break; | ||
1173 | amb | 966 | } |
1174 | } | ||
1175 | } | ||
1176 | |||
1177 | endloop: | ||
1178 | |||
1179 | if(!((i+1)%10000)) | ||
1180 | printf_middle("Pruning Straight Highway Nodes: Nodes=%"Pindex_t" Pruned=%"Pindex_t,i+1,npruned); | ||
1181 | } | ||
1182 | |||
1183 | /* Unmap from memory / close the files */ | ||
1184 | |||
1185 | free(checked); | ||
1186 | |||
1187 | free(nodes); | ||
1188 | free(segments); | ||
1189 | |||
1190 | amb | 967 | free(lats); |
1191 | free(lons); | ||
1192 | |||
1193 | amb | 966 | #if !SLIM |
1194 | amb | 1122 | nodesx->data=UnmapFile(nodesx->data); |
1195 | segmentsx->data=UnmapFile(segmentsx->data); | ||
1196 | waysx->data=UnmapFile(waysx->data); | ||
1197 | amb | 966 | #else |
1198 | nodesx->fd=CloseFile(nodesx->fd); | ||
1199 | segmentsx->fd=CloseFile(segmentsx->fd); | ||
1200 | waysx->fd=CloseFile(waysx->fd); | ||
1201 | #endif | ||
1202 | |||
1203 | /* Print the final message */ | ||
1204 | |||
1205 | printf_last("Pruned Straight Highway Nodes: Nodes=%"Pindex_t" Pruned=%"Pindex_t,nodesx->number,npruned); | ||
1206 | } | ||
1207 | |||
1208 | |||
1209 | /*++++++++++++++++++++++++++++++++++++++ | ||
1210 | amb | 960 | Prune a segment; unused nodes and ways will get marked for pruning later. |
1211 | amb | 953 | |
1212 | SegmentsX *segmentsx The set of segments to use. | ||
1213 | |||
1214 | SegmentX *segmentx The segment to be pruned. | ||
1215 | ++++++++++++++++++++++++++++++++++++++*/ | ||
1216 | |||
1217 | amb | 960 | static void prune_segment(SegmentsX *segmentsx,SegmentX *segmentx) |
1218 | amb | 953 | { |
1219 | amb | 970 | unlink_segment_node1_refs(segmentsx,segmentx); |
1220 | amb | 1121 | |
1221 | amb | 970 | unlink_segment_node2_refs(segmentsx,segmentx); |
1222 | amb | 953 | |
1223 | segmentx->node1=NO_NODE; | ||
1224 | segmentx->node2=NO_NODE; | ||
1225 | segmentx->next2=NO_SEGMENT; | ||
1226 | |||
1227 | PutBackSegmentX(segmentsx,segmentx); | ||
1228 | } | ||
1229 | |||
1230 | |||
1231 | /*++++++++++++++++++++++++++++++++++++++ | ||
1232 | amb | 960 | Modify a segment's nodes; unused nodes will get marked for pruning later. |
1233 | amb | 949 | |
1234 | SegmentsX *segmentsx The set of segments to use. | ||
1235 | |||
1236 | SegmentX *segmentx The segment to be modified. | ||
1237 | |||
1238 | index_t newnode1 The new value of node1. | ||
1239 | |||
1240 | index_t newnode2 The new value of node2. | ||
1241 | ++++++++++++++++++++++++++++++++++++++*/ | ||
1242 | |||
1243 | static void modify_segment(SegmentsX *segmentsx,SegmentX *segmentx,index_t newnode1,index_t newnode2) | ||
1244 | { | ||
1245 | index_t thissegment=IndexSegmentX(segmentsx,segmentx); | ||
1246 | |||
1247 | amb | 970 | if(newnode1>newnode2) /* rotate the segment around */ |
1248 | amb | 949 | { |
1249 | amb | 968 | index_t temp; |
1250 | |||
1251 | if(segmentx->distance&(ONEWAY_2TO1|ONEWAY_1TO2)) | ||
1252 | segmentx->distance^=ONEWAY_2TO1|ONEWAY_1TO2; | ||
1253 | |||
1254 | temp=newnode1; | ||
1255 | newnode1=newnode2; | ||
1256 | newnode2=temp; | ||
1257 | amb | 970 | } |
1258 | amb | 968 | |
1259 | amb | 970 | if(newnode1!=segmentx->node1) |
1260 | unlink_segment_node1_refs(segmentsx,segmentx); | ||
1261 | amb | 968 | |
1262 | amb | 970 | if(newnode2!=segmentx->node2) |
1263 | unlink_segment_node2_refs(segmentsx,segmentx); | ||
1264 | amb | 949 | |
1265 | amb | 968 | if(newnode1!=segmentx->node1) /* only modify it if the node has changed */ |
1266 | { | ||
1267 | amb | 949 | segmentx->node1=newnode1; |
1268 | |||
1269 | segmentsx->next1[thissegment]=segmentsx->firstnode[newnode1]; | ||
1270 | segmentsx->firstnode[newnode1]=thissegment; | ||
1271 | } | ||
1272 | |||
1273 | amb | 968 | if(newnode2!=segmentx->node2) /* only modify it if the node has changed */ |
1274 | amb | 949 | { |
1275 | segmentx->node2=newnode2; | ||
1276 | |||
1277 | segmentx->next2=segmentsx->firstnode[newnode2]; | ||
1278 | segmentsx->firstnode[newnode2]=thissegment; | ||
1279 | amb | 1121 | } |
1280 | amb | 970 | |
1281 | amb | 1121 | PutBackSegmentX(segmentsx,segmentx); |
1282 | amb | 949 | } |
1283 | |||
1284 | |||
1285 | /*++++++++++++++++++++++++++++++++++++++ | ||
1286 | amb | 970 | Unlink a node1 from a segment by modifying the linked list type arrangement of node references. |
1287 | amb | 949 | |
1288 | SegmentsX *segmentsx The set of segments to use. | ||
1289 | |||
1290 | amb | 970 | SegmentX *segmentx The segment to be modified. |
1291 | amb | 949 | ++++++++++++++++++++++++++++++++++++++*/ |
1292 | |||
1293 | amb | 970 | static void unlink_segment_node1_refs(SegmentsX *segmentsx,SegmentX *segmentx) |
1294 | amb | 949 | { |
1295 | amb | 970 | index_t segment,thissegment; |
1296 | amb | 949 | |
1297 | amb | 970 | thissegment=IndexSegmentX(segmentsx,segmentx); |
1298 | amb | 953 | |
1299 | amb | 970 | segment=segmentsx->firstnode[segmentx->node1]; |
1300 | |||
1301 | amb | 949 | if(segment==thissegment) |
1302 | amb | 970 | segmentsx->firstnode[segmentx->node1]=segmentsx->next1[thissegment]; |
1303 | amb | 949 | else |
1304 | { | ||
1305 | do | ||
1306 | { | ||
1307 | amb | 970 | index_t nextsegment; |
1308 | amb | 964 | SegmentX *segx=LookupSegmentX(segmentsx,segment,4); |
1309 | amb | 949 | |
1310 | amb | 970 | if(segx->node1==segmentx->node1) |
1311 | amb | 949 | { |
1312 | nextsegment=segmentsx->next1[segment]; | ||
1313 | |||
1314 | amb | 970 | if(nextsegment==thissegment) |
1315 | segmentsx->next1[segment]=segmentsx->next1[thissegment]; | ||
1316 | } | ||
1317 | else /* if(segx->node2==segmentx->node1) */ | ||
1318 | { | ||
1319 | nextsegment=segx->next2; | ||
1320 | |||
1321 | if(nextsegment==thissegment) | ||
1322 | amb | 949 | { |
1323 | amb | 970 | segx->next2=segmentsx->next1[thissegment]; |
1324 | |||
1325 | PutBackSegmentX(segmentsx,segx); | ||
1326 | amb | 949 | } |
1327 | } | ||
1328 | amb | 970 | |
1329 | segment=nextsegment; | ||
1330 | } | ||
1331 | while(segment!=thissegment && segment!=NO_SEGMENT); | ||
1332 | } | ||
1333 | } | ||
1334 | |||
1335 | |||
1336 | /*++++++++++++++++++++++++++++++++++++++ | ||
1337 | Unlink a node2 from a segment by modifying the linked list type arrangement of node references. | ||
1338 | |||
1339 | SegmentsX *segmentsx The set of segments to use. | ||
1340 | |||
1341 | SegmentX *segmentx The segment to be modified. | ||
1342 | ++++++++++++++++++++++++++++++++++++++*/ | ||
1343 | |||
1344 | static void unlink_segment_node2_refs(SegmentsX *segmentsx,SegmentX *segmentx) | ||
1345 | { | ||
1346 | index_t segment,thissegment; | ||
1347 | |||
1348 | thissegment=IndexSegmentX(segmentsx,segmentx); | ||
1349 | |||
1350 | segment=segmentsx->firstnode[segmentx->node2]; | ||
1351 | |||
1352 | if(segment==thissegment) | ||
1353 | segmentsx->firstnode[segmentx->node2]=segmentx->next2; | ||
1354 | else | ||
1355 | { | ||
1356 | do | ||
1357 | { | ||
1358 | index_t nextsegment; | ||
1359 | SegmentX *segx=LookupSegmentX(segmentsx,segment,4); | ||
1360 | |||
1361 | if(segx->node1==segmentx->node2) | ||
1362 | amb | 949 | { |
1363 | amb | 970 | nextsegment=segmentsx->next1[segment]; |
1364 | |||
1365 | if(nextsegment==thissegment) | ||
1366 | segmentsx->next1[segment]=segmentx->next2; | ||
1367 | } | ||
1368 | else /* if(segx->node2==segmentx->node2) */ | ||
1369 | { | ||
1370 | amb | 949 | nextsegment=segx->next2; |
1371 | |||
1372 | amb | 970 | if(nextsegment==thissegment) |
1373 | amb | 949 | { |
1374 | amb | 970 | segx->next2=segmentx->next2; |
1375 | amb | 949 | |
1376 | PutBackSegmentX(segmentsx,segx); | ||
1377 | } | ||
1378 | } | ||
1379 | |||
1380 | segment=nextsegment; | ||
1381 | } | ||
1382 | amb | 953 | while(segment!=thissegment && segment!=NO_SEGMENT); |
1383 | amb | 949 | } |
1384 | } | ||
1385 | amb | 966 | |
1386 | |||
1387 | /*++++++++++++++++++++++++++++++++++++++ | ||
1388 | Calculate the distance between two locations. | ||
1389 | |||
1390 | double distance Returns the distance between the locations. | ||
1391 | |||
1392 | double lat1 The latitude of the first location. | ||
1393 | |||
1394 | double lon1 The longitude of the first location. | ||
1395 | |||
1396 | double lat2 The latitude of the second location. | ||
1397 | |||
1398 | double lon2 The longitude of the second location. | ||
1399 | ++++++++++++++++++++++++++++++++++++++*/ | ||
1400 | |||
1401 | static double distance(double lat1,double lon1,double lat2,double lon2) | ||
1402 | { | ||
1403 | double dlon = lon1 - lon2; | ||
1404 | double dlat = lat1 - lat2; | ||
1405 | |||
1406 | double a1,a2,a,sa,c,d; | ||
1407 | |||
1408 | if(dlon==0 && dlat==0) | ||
1409 | return 0; | ||
1410 | |||
1411 | a1 = sin (dlat / 2); | ||
1412 | a2 = sin (dlon / 2); | ||
1413 | a = (a1 * a1) + cos (lat1) * cos (lat2) * a2 * a2; | ||
1414 | sa = sqrt (a); | ||
1415 | if (sa <= 1.0) | ||
1416 | {c = 2 * asin (sa);} | ||
1417 | else | ||
1418 | {c = 2 * asin (1.0);} | ||
1419 | d = 6378.137 * c; | ||
1420 | |||
1421 | return(d); | ||
1422 | } |