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 1117 -
(show annotations)
(download)
(as text)
Wed Oct 24 08:35:00 2012 UTC (12 years, 4 months ago) by amb
File MIME type: text/x-csrc
File size: 40008 byte(s)
Wed Oct 24 08:35:00 2012 UTC (12 years, 4 months ago) by amb
File MIME type: text/x-csrc
File size: 40008 byte(s)
Perform the pruning for isolated regions in terms of each transport type individually.
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); |
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); |
164 | segmentsx->data=MapFileWriteable(segmentsx->filename); |
165 | waysx->data=MapFile(waysx->filename); |
166 | #else |
167 | nodesx->fd=ReOpenFile(nodesx->filename); |
168 | segmentsx->fd=ReOpenFileWriteable(segmentsx->filename); |
169 | waysx->fd=ReOpenFile(waysx->filename); |
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 | printf("waysx->number=%d\n",waysx->number); |
193 | |
194 | for(transport=Transport_None+1;transport<Transport_Count;transport++) |
195 | { |
196 | index_t i,j; |
197 | index_t nregions=0,npruned=0,nadjusted=0; |
198 | const char *transport_str=TransportName(transport); |
199 | transports_t transports=TRANSPORTS(transport); |
200 | |
201 | /* Print the start message */ |
202 | |
203 | printf_first("Pruning Isolated Regions (%s): Segments=0 Adjusted=0 Pruned=0",transport_str); |
204 | |
205 | /* Loop through the segments and find the disconnected ones */ |
206 | |
207 | ClearAllBits(connected,segmentsx->number); |
208 | ClearAllBits(region ,segmentsx->number); |
209 | |
210 | for(i=0;i<segmentsx->number;i++) |
211 | { |
212 | int nregionsegments=0,nothersegments=0; |
213 | distance_t total=0; |
214 | SegmentX *segmentx; |
215 | WayX *wayx,tmpwayx; |
216 | |
217 | segmentx=LookupSegmentX(segmentsx,i,1); |
218 | |
219 | if(IsPrunedSegmentX(segmentx)) |
220 | goto endloop; |
221 | |
222 | if(IsBitSet(connected,i)) |
223 | goto endloop; |
224 | |
225 | if(segmentx->way<waysx->number) |
226 | wayx=LookupWayX(waysx,segmentx->way,1); |
227 | else |
228 | SeekReadFile(fd,(wayx=&tmpwayx),sizeof(WayX),(segmentx->way-waysx->number)*sizeof(WayX)); |
229 | |
230 | if(!(wayx->way.allow&transports)) |
231 | goto endloop; |
232 | |
233 | othersegments[nothersegments++]=i; |
234 | SetBit(region,i); |
235 | |
236 | do |
237 | { |
238 | index_t thissegment,nodes[2]; |
239 | |
240 | thissegment=othersegments[--nothersegments]; |
241 | |
242 | if(nregionsegments==nallocregionsegments) |
243 | regionsegments=(index_t*)realloc(regionsegments,(nallocregionsegments+=1024)*sizeof(index_t)); |
244 | |
245 | regionsegments[nregionsegments++]=thissegment; |
246 | |
247 | segmentx=LookupSegmentX(segmentsx,thissegment,1); |
248 | |
249 | nodes[0]=segmentx->node1; |
250 | nodes[1]=segmentx->node2; |
251 | total+=DISTANCE(segmentx->distance); |
252 | |
253 | for(j=0;j<2;j++) |
254 | { |
255 | NodeX *nodex=LookupNodeX(nodesx,nodes[j],1); |
256 | |
257 | if(!(nodex->allow&transports)) |
258 | continue; |
259 | |
260 | segmentx=FirstSegmentX(segmentsx,nodes[j],1); |
261 | |
262 | while(segmentx) |
263 | { |
264 | index_t segment=IndexSegmentX(segmentsx,segmentx); |
265 | |
266 | if(segment!=thissegment) |
267 | { |
268 | if(segmentx->way<waysx->number) |
269 | wayx=LookupWayX(waysx,segmentx->way,1); |
270 | else |
271 | SeekReadFile(fd,(wayx=&tmpwayx),sizeof(WayX),(segmentx->way-waysx->number)*sizeof(WayX)); |
272 | |
273 | if(wayx->way.allow&transports) |
274 | { |
275 | /* Already connected - finish */ |
276 | |
277 | if(IsBitSet(connected,segment)) |
278 | { |
279 | total=minimum; |
280 | goto foundconnection; |
281 | } |
282 | |
283 | /* Not in region - add to list */ |
284 | |
285 | if(!IsBitSet(region,segment)) |
286 | { |
287 | if(nothersegments==nallocothersegments) |
288 | othersegments=(index_t*)realloc(othersegments,(nallocothersegments+=1024)*sizeof(index_t)); |
289 | |
290 | othersegments[nothersegments++]=segment; |
291 | SetBit(region,segment); |
292 | } |
293 | } |
294 | } |
295 | |
296 | segmentx=NextSegmentX(segmentsx,segmentx,nodes[j]); |
297 | } |
298 | } |
299 | } |
300 | while(nothersegments>0 && total<minimum); |
301 | |
302 | foundconnection: |
303 | |
304 | /* Prune the segments or mark them as connected */ |
305 | |
306 | if(total<minimum) /* not connected - delete them */ |
307 | { |
308 | nregions++; |
309 | |
310 | for(j=0;j<nregionsegments;j++) |
311 | { |
312 | SegmentX *segmentx; |
313 | WayX *wayx,tmpwayx; |
314 | |
315 | SetBit(connected,regionsegments[j]); /* not really connected, but don't need to check again */ |
316 | ClearBit(region,regionsegments[j]); |
317 | |
318 | segmentx=LookupSegmentX(segmentsx,regionsegments[j],1); |
319 | |
320 | if(segmentx->way<waysx->number) |
321 | wayx=LookupWayX(waysx,segmentx->way,1); |
322 | else |
323 | SeekReadFile(fd,(wayx=&tmpwayx),sizeof(WayX),(segmentx->way-waysx->number)*sizeof(WayX)); |
324 | |
325 | if(wayx->way.allow==transports) |
326 | { |
327 | prune_segment(segmentsx,segmentx); |
328 | |
329 | npruned++; |
330 | } |
331 | else |
332 | { |
333 | if(segmentx->way<waysx->number) /* create a new way */ |
334 | { |
335 | tmpwayx=*wayx; |
336 | |
337 | tmpwayx.way.allow&=~transports; |
338 | |
339 | SeekWriteFile(fd,&tmpwayx,sizeof(WayX),nnewways*sizeof(WayX)); |
340 | |
341 | segmentx->way=waysx->number+nnewways; |
342 | |
343 | nnewways++; |
344 | |
345 | PutBackSegmentX(segmentsx,segmentx); |
346 | } |
347 | else /* modify the existing one */ |
348 | { |
349 | tmpwayx.way.allow&=~transports; |
350 | |
351 | SeekWriteFile(fd,&tmpwayx,sizeof(WayX),(segmentx->way-waysx->number)*sizeof(WayX)); |
352 | } |
353 | |
354 | nadjusted++; |
355 | } |
356 | } |
357 | } |
358 | else /* connected - mark as part of the main region */ |
359 | { |
360 | for(j=0;j<nregionsegments;j++) |
361 | { |
362 | SetBit(connected,regionsegments[j]); |
363 | ClearBit(region,regionsegments[j]); |
364 | } |
365 | |
366 | for(j=0;j<nothersegments;j++) |
367 | { |
368 | SetBit(connected,othersegments[j]); |
369 | ClearBit(region,othersegments[j]); |
370 | } |
371 | } |
372 | |
373 | endloop: |
374 | |
375 | if(!((i+1)%10000)) |
376 | 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); |
377 | } |
378 | |
379 | /* Print the final message */ |
380 | |
381 | 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); |
382 | } |
383 | |
384 | /* Unmap from memory / close the files */ |
385 | |
386 | free(region); |
387 | free(connected); |
388 | |
389 | free(regionsegments); |
390 | free(othersegments); |
391 | |
392 | #if !SLIM |
393 | nodesx->data=UnmapFile(nodesx->filename); |
394 | segmentsx->data=UnmapFile(segmentsx->filename); |
395 | waysx->data=UnmapFile(waysx->filename); |
396 | #else |
397 | nodesx->fd=CloseFile(nodesx->fd); |
398 | segmentsx->fd=CloseFile(segmentsx->fd); |
399 | waysx->fd=CloseFile(waysx->fd); |
400 | #endif |
401 | |
402 | /* Append the new ways to the end of the existing ones */ |
403 | |
404 | SeekFile(fd,0); |
405 | |
406 | waysx->fd=OpenFileAppend(waysx->filename); |
407 | |
408 | for(;nnewways>0;nnewways--) |
409 | { |
410 | WayX wayx; |
411 | |
412 | ReadFile(fd,&wayx,sizeof(WayX)); |
413 | WriteFile(waysx->fd,&wayx,sizeof(WayX)); |
414 | |
415 | waysx->number++; |
416 | } |
417 | |
418 | waysx->fd=CloseFile(waysx->fd); |
419 | |
420 | CloseFile(fd); |
421 | |
422 | DeleteFile(newwayfilename); |
423 | } |
424 | |
425 | |
426 | /*++++++++++++++++++++++++++++++++++++++ |
427 | Prune out any segments that are shorter than a specified minimum. |
428 | |
429 | NodesX *nodesx The set of nodes to use. |
430 | |
431 | SegmentsX *segmentsx The set of segments to use. |
432 | |
433 | WaysX *waysx The set of ways to use. |
434 | |
435 | distance_t minimum The maximum length to remove or one less than the minimum length to keep. |
436 | ++++++++++++++++++++++++++++++++++++++*/ |
437 | |
438 | void PruneShortSegments(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,distance_t minimum) |
439 | { |
440 | index_t i; |
441 | index_t nshort=0,npruned=0; |
442 | |
443 | if(nodesx->number==0 || segmentsx->number==0 || waysx->number==0) |
444 | return; |
445 | |
446 | /* Print the start message */ |
447 | |
448 | printf_first("Pruning Short Segments: Segments=0 Short=0 Pruned=0"); |
449 | |
450 | /* Map into memory / open the files */ |
451 | |
452 | #if !SLIM |
453 | nodesx->data=MapFileWriteable(nodesx->filename); |
454 | segmentsx->data=MapFileWriteable(segmentsx->filename); |
455 | waysx->data=MapFile(waysx->filename); |
456 | #else |
457 | nodesx->fd=ReOpenFileWriteable(nodesx->filename); |
458 | segmentsx->fd=ReOpenFileWriteable(segmentsx->filename); |
459 | waysx->fd=ReOpenFile(waysx->filename); |
460 | #endif |
461 | |
462 | /* Loop through the segments and find the short ones for possible modification */ |
463 | |
464 | for(i=0;i<segmentsx->number;i++) |
465 | { |
466 | SegmentX *segmentx2=LookupSegmentX(segmentsx,i,2); |
467 | |
468 | if(IsPrunedSegmentX(segmentx2)) |
469 | goto endloop; |
470 | |
471 | /* |
472 | : |
473 | Initial state: ..N3 -------- N2 |
474 | : S2 |
475 | |
476 | : |
477 | Final state: ..N3 N2 -- |
478 | : S2 |
479 | |
480 | = OR = |
481 | |
482 | : : |
483 | Initial state: ..N1 -------- N2 ---- N3 -------- N4.. |
484 | : S1 S2 S3 : |
485 | |
486 | : : |
487 | Final state: ..N1 ------------ N3 ------------ N4.. N2 -- |
488 | : S1 S3 : S2 |
489 | |
490 | Not if N1 is the same as N4. |
491 | Not if S2 has different one-way properties from S1 and S3. |
492 | Must combine N2, S2 and N3 disallowed transports into new N3. |
493 | Must not delete N2 or N3 if they are mini-roundabouts. |
494 | Must not delete N2 or N3 if they are part of turn relations. |
495 | |
496 | = OR = |
497 | |
498 | : : |
499 | Initial state: ..N1 -------- N2 ---- N3.. |
500 | : S1 S2 : |
501 | |
502 | : : |
503 | Final state: ..N1 ------------ N3.. N2 -- |
504 | : S1 : S2 |
505 | |
506 | Not if N1 is the same as N3. |
507 | Not if S1 has different one-way properties from S2. |
508 | Not if S1 has different highway properties from S2. |
509 | Not if N2 disallows transports allowed on S1 and S2. |
510 | Not if N2 is a mini-roundabouts. |
511 | Not if N2 is involved in a turn restriction. |
512 | */ |
513 | |
514 | if(DISTANCE(segmentx2->distance)<=minimum) |
515 | { |
516 | index_t node1=NO_NODE,node2,node3,node4=NO_NODE; |
517 | index_t segment1=NO_SEGMENT,segment2=i,segment3=NO_SEGMENT; |
518 | SegmentX *segmentx; |
519 | int segcount2=0,segcount3=0; |
520 | |
521 | nshort++; |
522 | |
523 | node2=segmentx2->node1; |
524 | node3=segmentx2->node2; |
525 | |
526 | /* Count the segments connected to N2 and N3 */ |
527 | |
528 | segmentx=FirstSegmentX(segmentsx,node2,4); |
529 | |
530 | while(segmentx) |
531 | { |
532 | segcount2++; |
533 | |
534 | if(segment1==NO_SEGMENT) |
535 | { |
536 | index_t segment=IndexSegmentX(segmentsx,segmentx); |
537 | |
538 | if(segment!=segment2) |
539 | { |
540 | segment1=segment; |
541 | node1=OtherNode(segmentx,node2); |
542 | } |
543 | } |
544 | |
545 | segmentx=NextSegmentX(segmentsx,segmentx,node2); |
546 | } |
547 | |
548 | segmentx=FirstSegmentX(segmentsx,node3,4); |
549 | |
550 | while(segmentx) |
551 | { |
552 | segcount3++; |
553 | |
554 | if(segment3==NO_SEGMENT) |
555 | { |
556 | index_t segment=IndexSegmentX(segmentsx,segmentx); |
557 | |
558 | if(segment!=segment2) |
559 | { |
560 | segment3=segment; |
561 | node4=OtherNode(segmentx,node3); |
562 | } |
563 | } |
564 | |
565 | segmentx=NextSegmentX(segmentsx,segmentx,node3); |
566 | } |
567 | |
568 | /* Check which case we are handling (and canonicalise) */ |
569 | |
570 | if(segcount2>2 && segcount3>2) /* none of the cases in diagram - too complicated */ |
571 | { |
572 | goto endloop; |
573 | } |
574 | else if(segcount2==1 || segcount3==1) /* first case in diagram - prune segment */ |
575 | { |
576 | prune_segment(segmentsx,segmentx2); |
577 | } |
578 | else if(segcount2==2 && segcount3==2) /* second case in diagram - modify one segment and prune segment */ |
579 | { |
580 | SegmentX *segmentx1,*segmentx3; |
581 | WayX *wayx1,*wayx2,*wayx3; |
582 | NodeX *nodex2,*nodex3,*newnodex; |
583 | index_t newnode; |
584 | int join12=1,join23=1; |
585 | |
586 | /* Check if pruning would collapse a loop */ |
587 | |
588 | if(node1==node4) |
589 | goto endloop; |
590 | |
591 | /* Check if allowed due to one-way properties */ |
592 | |
593 | segmentx1=LookupSegmentX(segmentsx,segment1,1); |
594 | segmentx3=LookupSegmentX(segmentsx,segment3,3); |
595 | |
596 | if(!IsOneway(segmentx1) && !IsOneway(segmentx2)) |
597 | ; |
598 | else if(IsOneway(segmentx1) && IsOneway(segmentx2)) |
599 | { |
600 | if(IsOnewayTo(segmentx1,node2) && !IsOnewayFrom(segmentx2,node2)) /* S1 is one-way but S2 doesn't continue */ |
601 | join12=0; |
602 | |
603 | if(IsOnewayFrom(segmentx1,node2) && !IsOnewayTo(segmentx2,node2)) /* S1 is one-way but S2 doesn't continue */ |
604 | join12=0; |
605 | } |
606 | else |
607 | join12=0; |
608 | |
609 | if(!IsOneway(segmentx3) && !IsOneway(segmentx2)) |
610 | ; |
611 | else if(IsOneway(segmentx3) && IsOneway(segmentx2)) |
612 | { |
613 | if(IsOnewayTo(segmentx3,node3) && !IsOnewayFrom(segmentx2,node3)) /* S3 is one-way but S2 doesn't continue */ |
614 | join23=0; |
615 | |
616 | if(IsOnewayFrom(segmentx3,node3) && !IsOnewayTo(segmentx2,node3)) /* S3 is one-way but S2 doesn't continue */ |
617 | join23=0; |
618 | } |
619 | else |
620 | join23=0; |
621 | |
622 | if(!join12 && !join23) |
623 | goto endloop; |
624 | |
625 | /* Check if allowed due to mini-roundabout and turn restriction */ |
626 | |
627 | nodex2=LookupNodeX(nodesx,node2,2); |
628 | nodex3=LookupNodeX(nodesx,node3,3); |
629 | |
630 | if(nodex2->flags&NODE_MINIRNDBT) |
631 | join12=0; |
632 | |
633 | if(nodex3->flags&NODE_MINIRNDBT) |
634 | join23=0; |
635 | |
636 | if(nodex2->flags&NODE_TURNRSTRCT2 || nodex2->flags&NODE_TURNRSTRCT) |
637 | join12=0; |
638 | |
639 | if(nodex3->flags&NODE_TURNRSTRCT2 || nodex3->flags&NODE_TURNRSTRCT) |
640 | join23=0; |
641 | |
642 | if(!join12 && !join23) |
643 | goto endloop; |
644 | |
645 | /* New node properties */ |
646 | |
647 | if(join12) |
648 | { |
649 | newnode=node3; |
650 | newnodex=nodex3; |
651 | } |
652 | else /* if(join23) */ |
653 | { |
654 | newnode=node2; |
655 | newnodex=nodex2; |
656 | } |
657 | |
658 | wayx1=LookupWayX(waysx,segmentx1->way,1); |
659 | wayx2=LookupWayX(waysx,segmentx2->way,2); |
660 | wayx3=LookupWayX(waysx,segmentx3->way,3); |
661 | |
662 | newnodex->allow=nodex2->allow&nodex3->allow; /* combine the restrictions of the two nodes */ |
663 | newnodex->allow&=~((~wayx2->way.allow)&wayx3->way.allow); /* disallow anything blocked by segment2 */ |
664 | newnodex->allow&=~((~wayx2->way.allow)&wayx1->way.allow); /* disallow anything blocked by segment2 */ |
665 | |
666 | newnodex->latitude =(nodex2->latitude +nodex3->latitude )/2; |
667 | newnodex->longitude=(nodex2->longitude+nodex3->longitude)/2; |
668 | |
669 | PutBackNodeX(nodesx,newnodex); |
670 | |
671 | /* Modify segments */ |
672 | |
673 | segmentx1->distance+=DISTANCE(segmentx2->distance)/2; |
674 | segmentx3->distance+=DISTANCE(segmentx2->distance)-DISTANCE(segmentx2->distance)/2; |
675 | |
676 | PutBackSegmentX(segmentsx,segmentx1); |
677 | PutBackSegmentX(segmentsx,segmentx3); |
678 | |
679 | prune_segment(segmentsx,segmentx2); |
680 | |
681 | if(segmentx1->node1==node1) |
682 | { |
683 | if(segmentx1->node2!=newnode) |
684 | modify_segment(segmentsx,segmentx1,node1,newnode); |
685 | } |
686 | else /* if(segmentx1->node2==node1) */ |
687 | { |
688 | if(segmentx1->node1!=newnode) |
689 | modify_segment(segmentsx,segmentx1,newnode,node1); |
690 | } |
691 | |
692 | if(segmentx3->node1==node4) |
693 | { |
694 | if(segmentx3->node2!=newnode) |
695 | modify_segment(segmentsx,segmentx3,node4,newnode); |
696 | } |
697 | else /* if(segmentx3->node2==node4) */ |
698 | { |
699 | if(segmentx3->node1!=newnode) |
700 | modify_segment(segmentsx,segmentx3,newnode,node4); |
701 | } |
702 | } |
703 | else /* third case in diagram - prune one segment */ |
704 | { |
705 | SegmentX *segmentx1; |
706 | WayX *wayx1,*wayx2; |
707 | NodeX *nodex2; |
708 | |
709 | if(segcount3==2) /* not as in diagram, shuffle things round */ |
710 | { |
711 | index_t temp; |
712 | |
713 | temp=segment1; segment1=segment3; segment3=temp; |
714 | temp=node1; node1=node4; node4=temp; |
715 | temp=node2; node2=node3; node3=temp; |
716 | } |
717 | |
718 | /* Check if pruning would collapse a loop */ |
719 | |
720 | if(node1==node3) |
721 | goto endloop; |
722 | |
723 | /* Check if allowed due to one-way properties */ |
724 | |
725 | segmentx1=LookupSegmentX(segmentsx,segment1,1); |
726 | |
727 | if(!IsOneway(segmentx1) && !IsOneway(segmentx2)) |
728 | ; |
729 | else if(IsOneway(segmentx1) && IsOneway(segmentx2)) |
730 | { |
731 | if(IsOnewayTo(segmentx1,node2) && !IsOnewayFrom(segmentx2,node2)) /* S1 is one-way but S2 doesn't continue */ |
732 | goto endloop; |
733 | |
734 | if(IsOnewayFrom(segmentx1,node2) && !IsOnewayTo(segmentx2,node2)) /* S1 is one-way but S2 doesn't continue */ |
735 | goto endloop; |
736 | } |
737 | else |
738 | goto endloop; |
739 | |
740 | /* Check if allowed due to highway properties */ |
741 | |
742 | wayx1=LookupWayX(waysx,segmentx1->way,1); |
743 | wayx2=LookupWayX(waysx,segmentx2->way,2); |
744 | |
745 | if(WaysCompare(&wayx1->way,&wayx2->way)) |
746 | goto endloop; |
747 | |
748 | /* Check if allowed due to mini-roundabout and turn restriction */ |
749 | |
750 | nodex2=LookupNodeX(nodesx,node2,2); |
751 | |
752 | if(nodex2->flags&NODE_MINIRNDBT) |
753 | goto endloop; |
754 | |
755 | if(nodex2->flags&NODE_TURNRSTRCT2 || nodex2->flags&NODE_TURNRSTRCT) |
756 | goto endloop; |
757 | |
758 | /* Check if allowed due to node restrictions */ |
759 | |
760 | if((nodex2->allow&wayx1->way.allow)!=wayx1->way.allow) |
761 | goto endloop; |
762 | |
763 | if((nodex2->allow&wayx2->way.allow)!=wayx2->way.allow) |
764 | goto endloop; |
765 | |
766 | /* Modify segments */ |
767 | |
768 | segmentx1->distance+=DISTANCE(segmentx2->distance); |
769 | |
770 | PutBackSegmentX(segmentsx,segmentx1); |
771 | |
772 | prune_segment(segmentsx,segmentx2); |
773 | |
774 | if(segmentx1->node1==node1) |
775 | modify_segment(segmentsx,segmentx1,node1,node3); |
776 | else /* if(segmentx1->node2==node1) */ |
777 | modify_segment(segmentsx,segmentx1,node3,node1); |
778 | } |
779 | |
780 | npruned++; |
781 | } |
782 | |
783 | endloop: |
784 | |
785 | if(!((i+1)%10000)) |
786 | printf_middle("Pruning Short Segments: Segments=%"Pindex_t" Short=%"Pindex_t" Pruned=%"Pindex_t,i+1,nshort,npruned); |
787 | } |
788 | |
789 | /* Unmap from memory / close the files */ |
790 | |
791 | #if !SLIM |
792 | nodesx->data=UnmapFile(nodesx->filename); |
793 | segmentsx->data=UnmapFile(segmentsx->filename); |
794 | waysx->data=UnmapFile(waysx->filename); |
795 | #else |
796 | nodesx->fd=CloseFile(nodesx->fd); |
797 | segmentsx->fd=CloseFile(segmentsx->fd); |
798 | waysx->fd=CloseFile(waysx->fd); |
799 | #endif |
800 | |
801 | /* Print the final message */ |
802 | |
803 | printf_last("Pruned Short Segments: Segments=%"Pindex_t" Short=%"Pindex_t" Pruned=%"Pindex_t,segmentsx->number,nshort,npruned); |
804 | } |
805 | |
806 | |
807 | /*++++++++++++++++++++++++++++++++++++++ |
808 | Prune out any nodes from straight highways where the introduced error is smaller than a specified maximum. |
809 | |
810 | NodesX *nodesx The set of nodes to use. |
811 | |
812 | SegmentsX *segmentsx The set of segments to use. |
813 | |
814 | WaysX *waysx The set of ways to use. |
815 | |
816 | distance_t maximum The maximum error to introduce. |
817 | ++++++++++++++++++++++++++++++++++++++*/ |
818 | |
819 | void PruneStraightHighwayNodes(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,distance_t maximum) |
820 | { |
821 | index_t i; |
822 | index_t npruned=0; |
823 | BitMask *checked; |
824 | int nalloc; |
825 | index_t *nodes,*segments; |
826 | double *lats,*lons; |
827 | double maximumf; |
828 | |
829 | if(nodesx->number==0 || segmentsx->number==0 || waysx->number==0) |
830 | return; |
831 | |
832 | maximumf=distance_to_km(maximum); |
833 | |
834 | /* Print the start message */ |
835 | |
836 | printf_first("Pruning Straight Highway Nodes: Nodes=0 Pruned=0"); |
837 | |
838 | /* Map into memory / open the files */ |
839 | |
840 | #if !SLIM |
841 | nodesx->data=MapFile(nodesx->filename); |
842 | segmentsx->data=MapFileWriteable(segmentsx->filename); |
843 | waysx->data=MapFile(waysx->filename); |
844 | #else |
845 | nodesx->fd=ReOpenFile(nodesx->filename); |
846 | segmentsx->fd=ReOpenFileWriteable(segmentsx->filename); |
847 | waysx->fd=ReOpenFile(waysx->filename); |
848 | #endif |
849 | |
850 | checked=AllocBitMask(nodesx->number); |
851 | |
852 | assert(checked); /* Check AllocBitMask() worked */ |
853 | |
854 | nodes =(index_t*)malloc((nalloc=1024)*sizeof(index_t)); |
855 | segments=(index_t*)malloc( nalloc *sizeof(index_t)); |
856 | |
857 | assert(nodes); /* Check malloc() worked */ |
858 | assert(segments); /* Check malloc() worked */ |
859 | |
860 | lats=(double*)malloc(nalloc*sizeof(double)); |
861 | lons=(double*)malloc(nalloc*sizeof(double)); |
862 | |
863 | assert(lats); /* Check malloc() worked */ |
864 | assert(lons); /* Check malloc() worked */ |
865 | |
866 | /* Loop through the nodes and find stretchs of simple highway for possible modification */ |
867 | |
868 | for(i=0;i<nodesx->number;i++) |
869 | { |
870 | int lowerbounded=0,upperbounded=0; |
871 | index_t lower=nalloc/2,current=nalloc/2,upper=nalloc/2; |
872 | |
873 | if(IsBitSet(checked,i)) |
874 | goto endloop; |
875 | |
876 | if(segmentsx->firstnode[i]==NO_SEGMENT) |
877 | goto endloop; |
878 | |
879 | /* Find all connected nodes */ |
880 | |
881 | nodes[current]=i; |
882 | |
883 | do |
884 | { |
885 | index_t node1=NO_NODE,node2=NO_NODE; |
886 | index_t segment1=NO_SEGMENT,segment2=NO_SEGMENT; |
887 | index_t way1=NO_WAY,way2=NO_WAY; |
888 | int segcount=0; |
889 | NodeX *nodex; |
890 | |
891 | if(!IsBitSet(checked,nodes[current])) |
892 | { |
893 | SegmentX *segmentx; |
894 | |
895 | /* Count the segments connected to the node */ |
896 | |
897 | segmentx=FirstSegmentX(segmentsx,nodes[current],1); |
898 | |
899 | while(segmentx) |
900 | { |
901 | segcount++; |
902 | |
903 | if(node1==NO_NODE) |
904 | { |
905 | segment1=IndexSegmentX(segmentsx,segmentx); |
906 | node1=OtherNode(segmentx,nodes[current]); |
907 | way1=segmentx->way; |
908 | } |
909 | else if(node2==NO_NODE) |
910 | { |
911 | segment2=IndexSegmentX(segmentsx,segmentx); |
912 | node2=OtherNode(segmentx,nodes[current]); |
913 | way2=segmentx->way; |
914 | } |
915 | |
916 | segmentx=NextSegmentX(segmentsx,segmentx,nodes[current]); |
917 | } |
918 | } |
919 | |
920 | /* Perform more checks */ |
921 | |
922 | nodex=LookupNodeX(nodesx,nodes[current],1); |
923 | |
924 | lats[current]=latlong_to_radians(nodex->latitude); |
925 | lons[current]=latlong_to_radians(nodex->longitude); |
926 | |
927 | /* Check if allowed due to mini-roundabout and turn restriction */ |
928 | |
929 | if(nodex->flags&NODE_MINIRNDBT) |
930 | segcount=0; |
931 | |
932 | if(nodex->flags&NODE_TURNRSTRCT2 || nodex->flags&NODE_TURNRSTRCT) |
933 | segcount=0; |
934 | |
935 | /* Check if allowed due to one-way properties */ |
936 | |
937 | if(segcount==2) |
938 | { |
939 | SegmentX *segmentx1,*segmentx2; |
940 | |
941 | segmentx1=LookupSegmentX(segmentsx,segment1,1); |
942 | segmentx2=LookupSegmentX(segmentsx,segment2,2); |
943 | |
944 | if(!IsOneway(segmentx1) && !IsOneway(segmentx2)) |
945 | ; |
946 | else if(IsOneway(segmentx1) && IsOneway(segmentx2)) |
947 | { |
948 | if(IsOnewayTo(segmentx1,nodes[current]) && !IsOnewayFrom(segmentx2,nodes[current])) /* S1 is one-way but S2 doesn't continue */ |
949 | segcount=0; |
950 | |
951 | if(IsOnewayFrom(segmentx1,nodes[current]) && !IsOnewayTo(segmentx2,nodes[current])) /* S1 is one-way but S2 doesn't continue */ |
952 | segcount=0; |
953 | } |
954 | else |
955 | segcount=0; |
956 | } |
957 | |
958 | /* Check if allowed due to highway properties and node restrictions */ |
959 | |
960 | if(segcount==2) |
961 | { |
962 | WayX *wayx1,*wayx2; |
963 | |
964 | wayx1=LookupWayX(waysx,way1,1); |
965 | wayx2=LookupWayX(waysx,way2,2); |
966 | |
967 | if(WaysCompare(&wayx1->way,&wayx2->way)) |
968 | segcount=0; |
969 | |
970 | if(wayx1->way.name!=wayx2->way.name) |
971 | segcount=0; |
972 | |
973 | if((nodex->allow&wayx1->way.allow)!=wayx1->way.allow) |
974 | segcount=0; |
975 | |
976 | if((nodex->allow&wayx2->way.allow)!=wayx2->way.allow) |
977 | segcount=0; |
978 | } |
979 | |
980 | /* Update the lists */ |
981 | |
982 | if(segcount==2) |
983 | { |
984 | if(upper==(nalloc-1)) |
985 | { |
986 | nodes =(index_t*)realloc(nodes ,(nalloc+=1024)*sizeof(index_t)); |
987 | segments=(index_t*)realloc(segments, nalloc *sizeof(index_t)); |
988 | |
989 | lats=(double*)realloc(lats,nalloc*sizeof(double)); |
990 | lons=(double*)realloc(lons,nalloc*sizeof(double)); |
991 | } |
992 | |
993 | if(lower==0) /* move everything up by one */ |
994 | { |
995 | memmove(nodes+1 ,nodes ,(1+upper-lower)*sizeof(index_t)); |
996 | memmove(segments+1,segments,(1+upper-lower)*sizeof(index_t)); |
997 | |
998 | memmove(lats+1,lats,(1+upper-lower)*sizeof(double)); |
999 | memmove(lons+1,lons,(1+upper-lower)*sizeof(double)); |
1000 | |
1001 | current++; |
1002 | lower++; |
1003 | upper++; |
1004 | } |
1005 | |
1006 | if(lower==upper) /* first */ |
1007 | { |
1008 | lower--; |
1009 | |
1010 | nodes[lower]=node1; |
1011 | segments[lower]=segment1; |
1012 | |
1013 | upper++; |
1014 | |
1015 | nodes[upper]=node2; |
1016 | segments[upper-1]=segment2; |
1017 | |
1018 | current--; |
1019 | } |
1020 | else if(current==lower) |
1021 | { |
1022 | lower--; |
1023 | |
1024 | if(nodes[current+1]==node2) |
1025 | { |
1026 | nodes[lower]=node1; |
1027 | segments[lower]=segment1; |
1028 | } |
1029 | else /* if(nodes[current+1]==node1) */ |
1030 | { |
1031 | nodes[lower]=node2; |
1032 | segments[lower]=segment2; |
1033 | } |
1034 | |
1035 | current--; |
1036 | } |
1037 | else /* if(current==upper) */ |
1038 | { |
1039 | upper++; |
1040 | |
1041 | if(nodes[current-1]==node2) |
1042 | { |
1043 | nodes[upper]=node1; |
1044 | segments[upper-1]=segment1; |
1045 | } |
1046 | else /* if(nodes[current-1]==node1) */ |
1047 | { |
1048 | nodes[upper]=node2; |
1049 | segments[upper-1]=segment2; |
1050 | } |
1051 | |
1052 | current++; |
1053 | } |
1054 | |
1055 | if(nodes[upper]==nodes[lower]) |
1056 | { |
1057 | lowerbounded=1; |
1058 | upperbounded=1; |
1059 | } |
1060 | } |
1061 | else |
1062 | { |
1063 | if(current==upper) |
1064 | upperbounded=1; |
1065 | |
1066 | if(current==lower) |
1067 | { |
1068 | lowerbounded=1; |
1069 | current=upper; |
1070 | } |
1071 | } |
1072 | } |
1073 | while(!(lowerbounded && upperbounded)); |
1074 | |
1075 | /* Mark the nodes */ |
1076 | |
1077 | for(current=lower;current<=upper;current++) |
1078 | SetBit(checked,nodes[current]); |
1079 | |
1080 | /* Check for straight highway */ |
1081 | |
1082 | while((upper-lower)>=2) |
1083 | { |
1084 | index_t bestc=lower; |
1085 | |
1086 | for(current=lower+2;current<=upper;current++) |
1087 | { |
1088 | double dist1,dist2,dist3,dist3a,dist3b,distp; |
1089 | index_t c; |
1090 | |
1091 | dist3=distance(lats[lower],lons[lower],lats[current],lons[current]); |
1092 | |
1093 | for(c=lower+1;c<current;c++) |
1094 | { |
1095 | dist1=distance(lats[lower] ,lons[lower] ,lats[c],lons[c]); |
1096 | dist2=distance(lats[current],lons[current],lats[c],lons[c]); |
1097 | |
1098 | /* Use law of cosines (assume flat Earth) */ |
1099 | |
1100 | dist3a=(dist1*dist1-dist2*dist2+dist3*dist3)/(2.0*dist3); |
1101 | dist3b=dist3-dist3a; |
1102 | |
1103 | if((dist1+dist2)<dist3) |
1104 | distp=0; |
1105 | else if(dist3a>=0 && dist3b>=0) |
1106 | distp=sqrt(dist1*dist1-dist3a*dist3a); |
1107 | else if(dist3a>0) |
1108 | distp=dist2; |
1109 | else /* if(dist3b>0) */ |
1110 | distp=dist1; |
1111 | |
1112 | if(distp>maximumf) /* gone too far */ |
1113 | break; |
1114 | } |
1115 | |
1116 | if(c>bestc) |
1117 | bestc=c; |
1118 | |
1119 | if(bestc>c) |
1120 | c=bestc; |
1121 | |
1122 | if(c==current && current!=upper) /* Can replace at least this far (not finished yet) */ |
1123 | continue; |
1124 | |
1125 | if((c-lower)<2) /* first three points are not straight */ |
1126 | { |
1127 | lower=c; |
1128 | break; |
1129 | } |
1130 | else /* delete some segments and shift along */ |
1131 | { |
1132 | SegmentX *segmentx; |
1133 | distance_t distance=0; |
1134 | |
1135 | current=c; |
1136 | |
1137 | for(c=lower+1;c<current;c++) |
1138 | { |
1139 | segmentx=LookupSegmentX(segmentsx,segments[c],1); |
1140 | |
1141 | distance+=DISTANCE(segmentx->distance); |
1142 | |
1143 | prune_segment(segmentsx,segmentx); |
1144 | |
1145 | npruned++; |
1146 | } |
1147 | |
1148 | segmentx=LookupSegmentX(segmentsx,segments[lower],1); |
1149 | |
1150 | if(nodes[lower]==nodes[current]) /* loop; all within maximum distance */ |
1151 | { |
1152 | prune_segment(segmentsx,segmentx); |
1153 | |
1154 | npruned++; |
1155 | } |
1156 | else |
1157 | { |
1158 | segmentx->distance+=distance; |
1159 | |
1160 | PutBackSegmentX(segmentsx,segmentx); |
1161 | |
1162 | if(segmentx->node1==nodes[lower]) |
1163 | modify_segment(segmentsx,segmentx,nodes[lower],nodes[current]); |
1164 | else /* if(segmentx->node2==nodes[lower]) */ |
1165 | modify_segment(segmentsx,segmentx,nodes[current],nodes[lower]); |
1166 | } |
1167 | |
1168 | lower=current; |
1169 | break; |
1170 | } |
1171 | } |
1172 | } |
1173 | |
1174 | endloop: |
1175 | |
1176 | if(!((i+1)%10000)) |
1177 | printf_middle("Pruning Straight Highway Nodes: Nodes=%"Pindex_t" Pruned=%"Pindex_t,i+1,npruned); |
1178 | } |
1179 | |
1180 | /* Unmap from memory / close the files */ |
1181 | |
1182 | free(checked); |
1183 | |
1184 | free(nodes); |
1185 | free(segments); |
1186 | |
1187 | free(lats); |
1188 | free(lons); |
1189 | |
1190 | #if !SLIM |
1191 | nodesx->data=UnmapFile(nodesx->filename); |
1192 | segmentsx->data=UnmapFile(segmentsx->filename); |
1193 | waysx->data=UnmapFile(waysx->filename); |
1194 | #else |
1195 | nodesx->fd=CloseFile(nodesx->fd); |
1196 | segmentsx->fd=CloseFile(segmentsx->fd); |
1197 | waysx->fd=CloseFile(waysx->fd); |
1198 | #endif |
1199 | |
1200 | /* Print the final message */ |
1201 | |
1202 | printf_last("Pruned Straight Highway Nodes: Nodes=%"Pindex_t" Pruned=%"Pindex_t,nodesx->number,npruned); |
1203 | } |
1204 | |
1205 | |
1206 | /*++++++++++++++++++++++++++++++++++++++ |
1207 | Prune a segment; unused nodes and ways will get marked for pruning later. |
1208 | |
1209 | SegmentsX *segmentsx The set of segments to use. |
1210 | |
1211 | SegmentX *segmentx The segment to be pruned. |
1212 | ++++++++++++++++++++++++++++++++++++++*/ |
1213 | |
1214 | static void prune_segment(SegmentsX *segmentsx,SegmentX *segmentx) |
1215 | { |
1216 | unlink_segment_node1_refs(segmentsx,segmentx); |
1217 | unlink_segment_node2_refs(segmentsx,segmentx); |
1218 | |
1219 | segmentx->node1=NO_NODE; |
1220 | segmentx->node2=NO_NODE; |
1221 | segmentx->next2=NO_SEGMENT; |
1222 | |
1223 | PutBackSegmentX(segmentsx,segmentx); |
1224 | } |
1225 | |
1226 | |
1227 | /*++++++++++++++++++++++++++++++++++++++ |
1228 | Modify a segment's nodes; unused nodes will get marked for pruning later. |
1229 | |
1230 | SegmentsX *segmentsx The set of segments to use. |
1231 | |
1232 | SegmentX *segmentx The segment to be modified. |
1233 | |
1234 | index_t newnode1 The new value of node1. |
1235 | |
1236 | index_t newnode2 The new value of node2. |
1237 | ++++++++++++++++++++++++++++++++++++++*/ |
1238 | |
1239 | static void modify_segment(SegmentsX *segmentsx,SegmentX *segmentx,index_t newnode1,index_t newnode2) |
1240 | { |
1241 | index_t thissegment=IndexSegmentX(segmentsx,segmentx); |
1242 | |
1243 | if(newnode1>newnode2) /* rotate the segment around */ |
1244 | { |
1245 | index_t temp; |
1246 | |
1247 | if(segmentx->distance&(ONEWAY_2TO1|ONEWAY_1TO2)) |
1248 | segmentx->distance^=ONEWAY_2TO1|ONEWAY_1TO2; |
1249 | |
1250 | PutBackSegmentX(segmentsx,segmentx); |
1251 | |
1252 | temp=newnode1; |
1253 | newnode1=newnode2; |
1254 | newnode2=temp; |
1255 | } |
1256 | |
1257 | if(newnode1!=segmentx->node1) |
1258 | unlink_segment_node1_refs(segmentsx,segmentx); |
1259 | |
1260 | if(newnode2!=segmentx->node2) |
1261 | unlink_segment_node2_refs(segmentsx,segmentx); |
1262 | |
1263 | if(newnode1!=segmentx->node1) /* only modify it if the node has changed */ |
1264 | { |
1265 | segmentx->node1=newnode1; |
1266 | |
1267 | segmentsx->next1[thissegment]=segmentsx->firstnode[newnode1]; |
1268 | segmentsx->firstnode[newnode1]=thissegment; |
1269 | |
1270 | PutBackSegmentX(segmentsx,segmentx); |
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 | PutBackSegmentX(segmentsx,segmentx); |
1281 | } |
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 | } |