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