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 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)
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 }