Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino
Contents of /trunk/src/prunex.c
Parent Directory
|
Revision Log
Revision 1121 -
(show annotations)
(download)
(as text)
Fri Nov 2 19:51:17 2012 UTC (12 years, 4 months ago) by amb
File MIME type: text/x-csrc
File size: 40180 byte(s)
Fri Nov 2 19:51:17 2012 UTC (12 years, 4 months ago) by amb
File MIME type: text/x-csrc
File size: 40180 byte(s)
Fix a bug which gave different results for slim mode and normal mode when pruning short segments.
1 | /*************************************** |
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 | #include "types.h" |
27 | #include "segments.h" |
28 | |
29 | #include "typesx.h" |
30 | #include "nodesx.h" |
31 | #include "segmentsx.h" |
32 | #include "waysx.h" |
33 | |
34 | #include "prunex.h" |
35 | |
36 | #include "files.h" |
37 | #include "logging.h" |
38 | |
39 | |
40 | /* Global variables */ |
41 | |
42 | /*+ The command line '--tmpdir' option or its default value. +*/ |
43 | extern char *option_tmpdirname; |
44 | |
45 | /* Local functions */ |
46 | |
47 | static void prune_segment(SegmentsX *segmentsx,SegmentX *segmentx); |
48 | static void modify_segment(SegmentsX *segmentsx,SegmentX *segmentx,index_t newnode1,index_t newnode2); |
49 | |
50 | static void unlink_segment_node1_refs(SegmentsX *segmentsx,SegmentX *segmentx); |
51 | static void unlink_segment_node2_refs(SegmentsX *segmentsx,SegmentX *segmentx); |
52 | |
53 | static double distance(double lat1,double lon1,double lat2,double lon2); |
54 | |
55 | |
56 | /*++++++++++++++++++++++++++++++++++++++ |
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 | segmentsx->fd=ReOpenFile(segmentsx->filename_tmp); |
84 | |
85 | /* Read the on-disk image */ |
86 | |
87 | while(!ReadFile(segmentsx->fd,&segmentx,sizeof(SegmentX))) |
88 | { |
89 | index_t node1=segmentx.node1; |
90 | |
91 | if(index==0) |
92 | ; |
93 | else if(lastnode1==node1) |
94 | segmentsx->next1[index-1]=index; |
95 | else |
96 | segmentsx->next1[index-1]=NO_SEGMENT; |
97 | |
98 | lastnode1=node1; |
99 | index++; |
100 | |
101 | if(!(index%10000)) |
102 | printf_middle("Added Extra Segment Indexes: Segments=%"Pindex_t,index); |
103 | } |
104 | |
105 | segmentsx->next1[index-1]=NO_SEGMENT; |
106 | |
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 | 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 | WaysX *waysx The set of ways to use. |
143 | |
144 | distance_t minimum The minimum distance to keep. |
145 | ++++++++++++++++++++++++++++++++++++++*/ |
146 | |
147 | void PruneIsolatedRegions(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,distance_t minimum) |
148 | { |
149 | transport_t transport; |
150 | BitMask *connected,*region; |
151 | index_t *regionsegments,*othersegments; |
152 | int nallocregionsegments,nallocothersegments; |
153 | char *newwayfilename; |
154 | index_t nnewways=0; |
155 | int fd; |
156 | |
157 | if(nodesx->number==0 || segmentsx->number==0) |
158 | return; |
159 | |
160 | /* Map into memory / open the files */ |
161 | |
162 | #if !SLIM |
163 | nodesx->data=MapFile(nodesx->filename_tmp); |
164 | segmentsx->data=MapFileWriteable(segmentsx->filename_tmp); |
165 | waysx->data=MapFile(waysx->filename_tmp); |
166 | #else |
167 | nodesx->fd=ReOpenFile(nodesx->filename_tmp); |
168 | segmentsx->fd=ReOpenFileWriteable(segmentsx->filename_tmp); |
169 | waysx->fd=ReOpenFile(waysx->filename_tmp); |
170 | #endif |
171 | |
172 | 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 | 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 | /* Loop through the transport types */ |
191 | |
192 | for(transport=Transport_None+1;transport<Transport_Count;transport++) |
193 | { |
194 | 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 | |
199 | /* Print the start message */ |
200 | |
201 | printf_first("Pruning Isolated Regions (%s): Segments=0 Adjusted=0 Pruned=0",transport_str); |
202 | |
203 | /* Loop through the segments and find the disconnected ones */ |
204 | |
205 | ClearAllBits(connected,segmentsx->number); |
206 | ClearAllBits(region ,segmentsx->number); |
207 | |
208 | for(i=0;i<segmentsx->number;i++) |
209 | { |
210 | int nregionsegments=0,nothersegments=0; |
211 | distance_t total=0; |
212 | SegmentX *segmentx; |
213 | WayX *wayx,tmpwayx; |
214 | |
215 | segmentx=LookupSegmentX(segmentsx,i,1); |
216 | |
217 | if(IsPrunedSegmentX(segmentx)) |
218 | goto endloop; |
219 | |
220 | if(IsBitSet(connected,i)) |
221 | goto endloop; |
222 | |
223 | 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 | |
228 | if(!(wayx->way.allow&transports)) |
229 | goto endloop; |
230 | |
231 | othersegments[nothersegments++]=i; |
232 | SetBit(region,i); |
233 | |
234 | do |
235 | { |
236 | index_t thissegment,nodes[2]; |
237 | |
238 | thissegment=othersegments[--nothersegments]; |
239 | |
240 | if(nregionsegments==nallocregionsegments) |
241 | regionsegments=(index_t*)realloc(regionsegments,(nallocregionsegments+=1024)*sizeof(index_t)); |
242 | |
243 | 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 | { |
253 | NodeX *nodex=LookupNodeX(nodesx,nodes[j],1); |
254 | |
255 | if(!(nodex->allow&transports)) |
256 | continue; |
257 | |
258 | segmentx=FirstSegmentX(segmentsx,nodes[j],1); |
259 | |
260 | while(segmentx) |
261 | { |
262 | index_t segment=IndexSegmentX(segmentsx,segmentx); |
263 | |
264 | if(segment!=thissegment) |
265 | { |
266 | 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 | |
271 | if(wayx->way.allow&transports) |
272 | { |
273 | /* Already connected - finish */ |
274 | |
275 | if(IsBitSet(connected,segment)) |
276 | { |
277 | total=minimum; |
278 | goto foundconnection; |
279 | } |
280 | |
281 | /* Not in region - add to list */ |
282 | |
283 | 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 | } |
292 | } |
293 | |
294 | segmentx=NextSegmentX(segmentsx,segmentx,nodes[j]); |
295 | } |
296 | } |
297 | } |
298 | while(nothersegments>0 && total<minimum); |
299 | |
300 | foundconnection: |
301 | |
302 | /* Prune the segments or mark them as connected */ |
303 | |
304 | if(total<minimum) /* not connected - delete them */ |
305 | { |
306 | nregions++; |
307 | |
308 | for(j=0;j<nregionsegments;j++) |
309 | { |
310 | SegmentX *segmentx; |
311 | WayX *wayx,tmpwayx; |
312 | |
313 | SetBit(connected,regionsegments[j]); /* not really connected, but don't need to check again */ |
314 | ClearBit(region,regionsegments[j]); |
315 | |
316 | 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 | } |
356 | else /* connected - mark as part of the main region */ |
357 | { |
358 | 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 | } |
370 | |
371 | 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 | } |
376 | |
377 | /* Print the final message */ |
378 | |
379 | 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 | } |
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 | nodesx->data=UnmapFile(nodesx->filename_tmp); |
392 | segmentsx->data=UnmapFile(segmentsx->filename_tmp); |
393 | waysx->data=UnmapFile(waysx->filename_tmp); |
394 | #else |
395 | nodesx->fd=CloseFile(nodesx->fd); |
396 | segmentsx->fd=CloseFile(segmentsx->fd); |
397 | waysx->fd=CloseFile(waysx->fd); |
398 | #endif |
399 | |
400 | /* Append the new ways to the end of the existing ones */ |
401 | |
402 | SeekFile(fd,0); |
403 | |
404 | waysx->fd=OpenFileAppend(waysx->filename_tmp); |
405 | |
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 | } |
422 | |
423 | |
424 | /*++++++++++++++++++++++++++++++++++++++ |
425 | 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 | distance_t minimum The maximum length to remove or one less than the minimum length to keep. |
434 | ++++++++++++++++++++++++++++++++++++++*/ |
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 | nodesx->data=MapFileWriteable(nodesx->filename_tmp); |
452 | segmentsx->data=MapFileWriteable(segmentsx->filename_tmp); |
453 | waysx->data=MapFile(waysx->filename_tmp); |
454 | #else |
455 | nodesx->fd=ReOpenFileWriteable(nodesx->filename_tmp); |
456 | segmentsx->fd=ReOpenFileWriteable(segmentsx->filename_tmp); |
457 | waysx->fd=ReOpenFile(waysx->filename_tmp); |
458 | #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 | goto endloop; |
468 | |
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 | index_t node1=NO_NODE,node2,node3,node4=NO_NODE; |
515 | 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 | else |
679 | PutBackSegmentX(segmentsx,segmentx1); |
680 | } |
681 | else /* if(segmentx1->node2==node1) */ |
682 | { |
683 | if(segmentx1->node1!=newnode) |
684 | modify_segment(segmentsx,segmentx1,newnode,node1); |
685 | else |
686 | PutBackSegmentX(segmentsx,segmentx1); |
687 | } |
688 | |
689 | if(segmentx3->node1==node4) |
690 | { |
691 | if(segmentx3->node2!=newnode) |
692 | modify_segment(segmentsx,segmentx3,node4,newnode); |
693 | else |
694 | PutBackSegmentX(segmentsx,segmentx3); |
695 | } |
696 | else /* if(segmentx3->node2==node4) */ |
697 | { |
698 | if(segmentx3->node1!=newnode) |
699 | modify_segment(segmentsx,segmentx3,newnode,node4); |
700 | else |
701 | PutBackSegmentX(segmentsx,segmentx3); |
702 | } |
703 | |
704 | ReLookupSegmentX(segmentsx,segmentx2); |
705 | |
706 | prune_segment(segmentsx,segmentx2); |
707 | } |
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 | /* 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 | /* 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 | |
780 | ReLookupSegmentX(segmentsx,segmentx2); |
781 | |
782 | prune_segment(segmentsx,segmentx2); |
783 | } |
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 | nodesx->data=UnmapFile(nodesx->filename_tmp); |
798 | segmentsx->data=UnmapFile(segmentsx->filename_tmp); |
799 | waysx->data=UnmapFile(waysx->filename_tmp); |
800 | #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 | 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 | int nalloc; |
830 | index_t *nodes,*segments; |
831 | double *lats,*lons; |
832 | 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 | nodesx->data=MapFile(nodesx->filename_tmp); |
847 | segmentsx->data=MapFileWriteable(segmentsx->filename_tmp); |
848 | waysx->data=MapFile(waysx->filename_tmp); |
849 | #else |
850 | nodesx->fd=ReOpenFile(nodesx->filename_tmp); |
851 | segmentsx->fd=ReOpenFileWriteable(segmentsx->filename_tmp); |
852 | waysx->fd=ReOpenFile(waysx->filename_tmp); |
853 | #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 | 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 | /* Loop through the nodes and find stretchs of simple highway for possible modification */ |
872 | |
873 | for(i=0;i<nodesx->number;i++) |
874 | { |
875 | int lowerbounded=0,upperbounded=0; |
876 | index_t lower=nalloc/2,current=nalloc/2,upper=nalloc/2; |
877 | |
878 | if(IsBitSet(checked,i)) |
879 | goto endloop; |
880 | |
881 | if(segmentsx->firstnode[i]==NO_SEGMENT) |
882 | 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 | index_t segment1=NO_SEGMENT,segment2=NO_SEGMENT; |
892 | index_t way1=NO_WAY,way2=NO_WAY; |
893 | int segcount=0; |
894 | NodeX *nodex; |
895 | |
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 | 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 | 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 | /* Check if allowed due to highway properties and node restrictions */ |
964 | |
965 | 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 | if(wayx1->way.name!=wayx2->way.name) |
976 | segcount=0; |
977 | |
978 | 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 | if(upper==(nalloc-1)) |
990 | { |
991 | nodes =(index_t*)realloc(nodes ,(nalloc+=1024)*sizeof(index_t)); |
992 | segments=(index_t*)realloc(segments, nalloc *sizeof(index_t)); |
993 | |
994 | lats=(double*)realloc(lats,nalloc*sizeof(double)); |
995 | lons=(double*)realloc(lons,nalloc*sizeof(double)); |
996 | } |
997 | |
998 | if(lower==0) /* move everything up by one */ |
999 | { |
1000 | memmove(nodes+1 ,nodes ,(1+upper-lower)*sizeof(index_t)); |
1001 | memmove(segments+1,segments,(1+upper-lower)*sizeof(index_t)); |
1002 | |
1003 | memmove(lats+1,lats,(1+upper-lower)*sizeof(double)); |
1004 | memmove(lons+1,lons,(1+upper-lower)*sizeof(double)); |
1005 | |
1006 | 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 | /* Mark the nodes */ |
1081 | |
1082 | for(current=lower;current<=upper;current++) |
1083 | SetBit(checked,nodes[current]); |
1084 | |
1085 | /* Check for straight highway */ |
1086 | |
1087 | while((upper-lower)>=2) |
1088 | { |
1089 | index_t bestc=lower; |
1090 | |
1091 | for(current=lower+2;current<=upper;current++) |
1092 | { |
1093 | double dist1,dist2,dist3,dist3a,dist3b,distp; |
1094 | index_t c; |
1095 | |
1096 | dist3=distance(lats[lower],lons[lower],lats[current],lons[current]); |
1097 | |
1098 | for(c=lower+1;c<current;c++) |
1099 | { |
1100 | dist1=distance(lats[lower] ,lons[lower] ,lats[c],lons[c]); |
1101 | dist2=distance(lats[current],lons[current],lats[c],lons[c]); |
1102 | |
1103 | /* Use law of cosines (assume flat Earth) */ |
1104 | |
1105 | dist3a=(dist1*dist1-dist2*dist2+dist3*dist3)/(2.0*dist3); |
1106 | dist3b=dist3-dist3a; |
1107 | |
1108 | 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 | |
1117 | if(distp>maximumf) /* gone too far */ |
1118 | break; |
1119 | } |
1120 | |
1121 | if(c>bestc) |
1122 | bestc=c; |
1123 | |
1124 | if(bestc>c) |
1125 | c=bestc; |
1126 | |
1127 | if(c==current && current!=upper) /* Can replace at least this far (not finished yet) */ |
1128 | continue; |
1129 | |
1130 | 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 | |
1140 | current=c; |
1141 | |
1142 | for(c=lower+1;c<current;c++) |
1143 | { |
1144 | segmentx=LookupSegmentX(segmentsx,segments[c],1); |
1145 | |
1146 | distance+=DISTANCE(segmentx->distance); |
1147 | |
1148 | prune_segment(segmentsx,segmentx); |
1149 | |
1150 | npruned++; |
1151 | } |
1152 | |
1153 | segmentx=LookupSegmentX(segmentsx,segments[lower],1); |
1154 | |
1155 | if(nodes[lower]==nodes[current]) /* loop; all within maximum distance */ |
1156 | { |
1157 | prune_segment(segmentsx,segmentx); |
1158 | |
1159 | npruned++; |
1160 | } |
1161 | else |
1162 | { |
1163 | segmentx->distance+=distance; |
1164 | |
1165 | 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 | lower=current; |
1172 | break; |
1173 | } |
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 | free(lats); |
1191 | free(lons); |
1192 | |
1193 | #if !SLIM |
1194 | nodesx->data=UnmapFile(nodesx->filename_tmp); |
1195 | segmentsx->data=UnmapFile(segmentsx->filename_tmp); |
1196 | waysx->data=UnmapFile(waysx->filename_tmp); |
1197 | #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 | Prune a segment; unused nodes and ways will get marked for pruning later. |
1211 | |
1212 | SegmentsX *segmentsx The set of segments to use. |
1213 | |
1214 | SegmentX *segmentx The segment to be pruned. |
1215 | ++++++++++++++++++++++++++++++++++++++*/ |
1216 | |
1217 | static void prune_segment(SegmentsX *segmentsx,SegmentX *segmentx) |
1218 | { |
1219 | unlink_segment_node1_refs(segmentsx,segmentx); |
1220 | |
1221 | unlink_segment_node2_refs(segmentsx,segmentx); |
1222 | |
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 | Modify a segment's nodes; unused nodes will get marked for pruning later. |
1233 | |
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 | if(newnode1>newnode2) /* rotate the segment around */ |
1248 | { |
1249 | 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 | } |
1258 | |
1259 | if(newnode1!=segmentx->node1) |
1260 | unlink_segment_node1_refs(segmentsx,segmentx); |
1261 | |
1262 | if(newnode2!=segmentx->node2) |
1263 | unlink_segment_node2_refs(segmentsx,segmentx); |
1264 | |
1265 | if(newnode1!=segmentx->node1) /* only modify it if the node has changed */ |
1266 | { |
1267 | segmentx->node1=newnode1; |
1268 | |
1269 | segmentsx->next1[thissegment]=segmentsx->firstnode[newnode1]; |
1270 | segmentsx->firstnode[newnode1]=thissegment; |
1271 | } |
1272 | |
1273 | if(newnode2!=segmentx->node2) /* only modify it if the node has changed */ |
1274 | { |
1275 | segmentx->node2=newnode2; |
1276 | |
1277 | segmentx->next2=segmentsx->firstnode[newnode2]; |
1278 | segmentsx->firstnode[newnode2]=thissegment; |
1279 | } |
1280 | |
1281 | PutBackSegmentX(segmentsx,segmentx); |
1282 | } |
1283 | |
1284 | |
1285 | /*++++++++++++++++++++++++++++++++++++++ |
1286 | Unlink a node1 from a segment by modifying the linked list type arrangement of node references. |
1287 | |
1288 | SegmentsX *segmentsx The set of segments to use. |
1289 | |
1290 | SegmentX *segmentx The segment to be modified. |
1291 | ++++++++++++++++++++++++++++++++++++++*/ |
1292 | |
1293 | static void unlink_segment_node1_refs(SegmentsX *segmentsx,SegmentX *segmentx) |
1294 | { |
1295 | index_t segment,thissegment; |
1296 | |
1297 | thissegment=IndexSegmentX(segmentsx,segmentx); |
1298 | |
1299 | segment=segmentsx->firstnode[segmentx->node1]; |
1300 | |
1301 | if(segment==thissegment) |
1302 | segmentsx->firstnode[segmentx->node1]=segmentsx->next1[thissegment]; |
1303 | else |
1304 | { |
1305 | do |
1306 | { |
1307 | index_t nextsegment; |
1308 | SegmentX *segx=LookupSegmentX(segmentsx,segment,4); |
1309 | |
1310 | if(segx->node1==segmentx->node1) |
1311 | { |
1312 | nextsegment=segmentsx->next1[segment]; |
1313 | |
1314 | 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 | { |
1323 | segx->next2=segmentsx->next1[thissegment]; |
1324 | |
1325 | PutBackSegmentX(segmentsx,segx); |
1326 | } |
1327 | } |
1328 | |
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 | { |
1363 | 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 | nextsegment=segx->next2; |
1371 | |
1372 | if(nextsegment==thissegment) |
1373 | { |
1374 | segx->next2=segmentx->next2; |
1375 | |
1376 | PutBackSegmentX(segmentsx,segx); |
1377 | } |
1378 | } |
1379 | |
1380 | segment=nextsegment; |
1381 | } |
1382 | while(segment!=thissegment && segment!=NO_SEGMENT); |
1383 | } |
1384 | } |
1385 | |
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 | } |