Routino SVN Repository Browser

Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino

ViewVC logotype

Contents of /trunk/src/prunex.c

Parent Directory Parent Directory | Revision Log 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)
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 }