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/optimiser.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 688 - (show annotations) (download) (as text)
Wed Apr 27 18:42:07 2011 UTC (13 years, 10 months ago) by amb
File MIME type: text/x-csrc
File size: 35486 byte(s)
Force going straight on if a waypoint is a super-node.

1 /***************************************
2 Routing optimiser.
3
4 Part of the Routino routing software.
5 ******************/ /******************
6 This file Copyright 2008-2011 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 <stdio.h>
24
25 #include "types.h"
26 #include "nodes.h"
27 #include "segments.h"
28 #include "ways.h"
29 #include "relations.h"
30
31 #include "logging.h"
32 #include "functions.h"
33 #include "fakes.h"
34 #include "results.h"
35
36
37 /* Global variables */
38
39 /*+ The option not to print any progress information. +*/
40 extern int option_quiet;
41
42 /*+ The option to calculate the quickest route insted of the shortest. +*/
43 extern int option_quickest;
44
45
46 /* Local functions */
47
48 static index_t FindSuperSegment(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,index_t endnode,index_t endsegment,Profile *profile);
49
50
51 /*++++++++++++++++++++++++++++++++++++++
52 Find the optimum route between two nodes not passing through a super-node (except in case of an override).
53
54 Results *FindNormalRoute Returns a set of results.
55
56 Nodes *nodes The set of nodes to use.
57
58 Segments *segments The set of segments to use.
59
60 Ways *ways The set of ways to use.
61
62 Relations *relations The set of relations to use.
63
64 index_t start_node The start node.
65
66 index_t prev_segment The previous segment before the start node.
67
68 index_t finish_node The finish node.
69
70 Profile *profile The profile containing the transport type, speeds and allowed highways.
71
72 int override A flag to indicate if U-turns and passing over super-nodes are allowed (to get out of dead-ends).
73 ++++++++++++++++++++++++++++++++++++++*/
74
75 Results *FindNormalRoute(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,index_t start_node,index_t prev_segment,index_t finish_node,Profile *profile,int override)
76 {
77 Results *results;
78 Queue *queue;
79 score_t finish_score;
80 double finish_lat,finish_lon;
81 Result *finish_result;
82 Result *result1,*result2;
83
84 /* Set up the finish conditions */
85
86 finish_score=INF_SCORE;
87 finish_result=NULL;
88
89 if(IsFakeNode(finish_node))
90 GetFakeLatLong(finish_node,&finish_lat,&finish_lon);
91 else
92 GetLatLong(nodes,finish_node,&finish_lat,&finish_lon);
93
94 /* Create the list of results and insert the first node into the queue */
95
96 results=NewResultsList(8);
97
98 results->start_node=start_node;
99 results->prev_segment=prev_segment;
100
101 result1=InsertResult(results,start_node,prev_segment);
102
103 queue=NewQueueList();
104
105 InsertInQueue(queue,result1);
106
107 /* Loop across all nodes in the queue */
108
109 while((result1=PopFromQueue(queue)))
110 {
111 Segment *segment;
112 index_t node1,seg1,seg1r;
113 index_t turnrelation=NO_RELATION;
114 int routes_out=0;
115 Segment *uturn_segment=NULL;
116
117 /* score must be better than current best score */
118 if(result1->score>finish_score)
119 continue;
120
121 node1=result1->node;
122 seg1=result1->segment;
123
124 if(IsFakeSegment(seg1))
125 seg1r=IndexRealSegment(seg1);
126 else
127 seg1r=seg1;
128
129 /* lookup if a turn restriction applies */
130 if(profile->turns && IsTurnRestrictedNode(LookupNode(nodes,node1,1)))
131 turnrelation=FindFirstTurnRelation2(relations,node1,seg1r);
132
133 /* Loop across all segments */
134
135 if(IsFakeNode(node1))
136 segment=FirstFakeSegment(node1);
137 else
138 segment=FirstSegment(segments,nodes,node1);
139
140 while(segment)
141 {
142 Way *way;
143 index_t node2,seg2,seg2r;
144 score_t segment_pref,segment_score,cumulative_score;
145 int i;
146
147 node2=OtherNode(segment,node1); /* need this here because we use node2 at the end of the loop */
148
149 /* must be a normal segment */
150 if(!IsNormalSegment(segment))
151 goto endloop;
152
153 /* must obey one-way restrictions (unless profile allows) */
154 if(profile->oneway && IsOnewayTo(segment,node1))
155 goto endloop;
156
157 if(IsFakeNode(node1) || IsFakeNode(node2))
158 {
159 seg2 =IndexFakeSegment(segment);
160 seg2r=IndexRealSegment(seg2);
161 }
162 else
163 {
164 seg2 =IndexSegment(segments,segment);
165 seg2r=seg2;
166 }
167
168 /* must not perform u-turn (unless profile allows) */
169 if(profile->turns && (seg1==seg2 || seg1==seg2r || seg1r==seg2) && segment!=uturn_segment)
170 {
171 if(override)
172 uturn_segment=segment;
173 goto endloop;
174 }
175
176 /* must obey turn relations */
177 if(turnrelation!=NO_RELATION && !IsTurnAllowed(relations,turnrelation,node1,seg1r,seg2r,profile->allow))
178 goto endloop;
179
180 /* must not pass over super-node (unless override is active) */
181 if(node2!=finish_node && !IsFakeNode(node2) && IsSuperNode(LookupNode(nodes,node2,2)) && !override)
182 goto endloop;
183
184 way=LookupWay(ways,segment->way,1);
185
186 /* mode of transport must be allowed on the highway */
187 if(!(way->allow&profile->allow))
188 goto endloop;
189
190 /* must obey weight restriction (if exists) */
191 if(way->weight && way->weight<profile->weight)
192 goto endloop;
193
194 /* must obey height/width/length restriction (if exists) */
195 if((way->height && way->height<profile->height) ||
196 (way->width && way->width <profile->width ) ||
197 (way->length && way->length<profile->length))
198 goto endloop;
199
200 segment_pref=profile->highway[HIGHWAY(way->type)];
201
202 for(i=1;i<Property_Count;i++)
203 if(ways->file.props & PROPERTIES(i))
204 {
205 if(way->props & PROPERTIES(i))
206 segment_pref*=profile->props_yes[i];
207 else
208 segment_pref*=profile->props_no[i];
209 }
210
211 /* profile preferences must allow this highway */
212 if(segment_pref==0)
213 goto endloop;
214
215 /* mode of transport must be allowed through node2 */
216 if(!IsFakeNode(node2))
217 {
218 Node *node=LookupNode(nodes,node2,2);
219
220 if(!(node->allow&profile->allow))
221 goto endloop;
222 }
223
224 routes_out++;
225
226 if(option_quickest==0)
227 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
228 else
229 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
230
231 cumulative_score=result1->score+segment_score;
232
233 /* score must be better than current best score */
234 if(cumulative_score>finish_score)
235 goto endloop;
236
237 result2=FindResult(results,node2,seg2);
238
239 if(!result2) /* New end node/segment combination */
240 {
241 result2=InsertResult(results,node2,seg2);
242 result2->prev=result1;
243 result2->score=cumulative_score;
244
245 if(node2==finish_node)
246 {
247 if(cumulative_score<finish_score)
248 {
249 finish_score=cumulative_score;
250 finish_result=result2;
251 }
252 }
253 else
254 {
255 result2->sortby=result2->score;
256
257 InsertInQueue(queue,result2);
258 }
259 }
260 else if(cumulative_score<result2->score) /* New score for end node/segment combination is better */
261 {
262 result2->prev=result1;
263 result2->score=cumulative_score;
264 result2->segment=seg2;
265
266 if(node2==finish_node)
267 {
268 if(cumulative_score<finish_score)
269 {
270 finish_score=cumulative_score;
271 finish_result=result2;
272 }
273 }
274 else
275 {
276 result2->sortby=result2->score;
277
278 if(result2->score<finish_score)
279 InsertInQueue(queue,result2);
280 }
281 }
282
283 endloop:
284
285 if(IsFakeNode(node1))
286 segment=NextFakeSegment(segment,node1);
287 else if(IsFakeNode(node2))
288 segment=NULL; /* cannot call NextSegment() with a fake segment */
289 else
290 {
291 segment=NextSegment(segments,segment,node1);
292
293 if(!segment && IsFakeNode(finish_node))
294 segment=ExtraFakeSegment(node1,finish_node);
295 }
296
297 /* allow u-turn at dead-ends if override is enabled */
298 if(!segment && routes_out==0 && uturn_segment)
299 segment=uturn_segment;
300 }
301 }
302
303 FreeQueueList(queue);
304
305 /* Check it worked */
306
307 if(!finish_result)
308 {
309 FreeResultsList(results);
310 return(NULL);
311 }
312
313 FixForwardRoute(results,finish_result);
314
315 return(results);
316 }
317
318
319 /*++++++++++++++++++++++++++++++++++++++
320 Find the optimum route between two nodes where the start and end are a set of pre/post-routed super-nodes.
321
322 Results *FindMiddleRoute Returns a set of results.
323
324 Nodes *nodes The set of nodes to use.
325
326 Segments *segments The set of segments to use.
327
328 Ways *ways The set of ways to use.
329
330 Relations *relations The set of relations to use.
331
332 Results *begin The initial portion of the route.
333
334 Results *end The final portion of the route.
335
336 Profile *profile The profile containing the transport type, speeds and allowed highways.
337 ++++++++++++++++++++++++++++++++++++++*/
338
339 Results *FindMiddleRoute(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,Results *begin,Results *end,Profile *profile)
340 {
341 Results *results;
342 Queue *queue;
343 Result *finish_result;
344 score_t finish_score;
345 double finish_lat,finish_lon;
346 Result *result1,*result2,*result3,*result4;
347
348 if(!option_quiet)
349 printf_first("Routing: Super-Nodes checked = 0");
350
351 /* Set up the finish conditions */
352
353 finish_score=INF_DISTANCE;
354 finish_result=NULL;
355
356 if(IsFakeNode(end->finish_node))
357 GetFakeLatLong(end->finish_node,&finish_lat,&finish_lon);
358 else
359 GetLatLong(nodes,end->finish_node,&finish_lat,&finish_lon);
360
361 /* Create the list of results and insert the first node into the queue */
362
363 results=NewResultsList(2048);
364
365 results->start_node=begin->start_node;
366 results->prev_segment=begin->prev_segment;
367
368 if(begin->number==1)
369 {
370 index_t superseg=FindSuperSegment(nodes,segments,ways,relations,begin->start_node,begin->prev_segment,profile);
371
372 results->prev_segment=superseg;
373 }
374
375 result1=InsertResult(results,results->start_node,results->prev_segment);
376
377 queue=NewQueueList();
378
379 /* Insert the finish points of the beginning part of the path into the queue,
380 translating the segments into super-segments. */
381
382 result3=FirstResult(begin);
383
384 while(result3)
385 {
386 if(result3->node!=begin->start_node && !IsFakeNode(result3->node) && IsSuperNode(LookupNode(nodes,result3->node,1)))
387 {
388 index_t superseg=FindSuperSegment(nodes,segments,ways,relations,result3->node,result3->segment,profile);
389
390 result2=InsertResult(results,result3->node,superseg);
391
392 result2->prev=result1;
393
394 result2->score=result3->score;
395 result2->sortby=result3->score;
396
397 InsertInQueue(queue,result2);
398
399 if((result4=FindResult(end,result2->node,result2->segment)))
400 {
401 if((result2->score+result4->score)<finish_score)
402 {
403 finish_score=result2->score+result4->score;
404 finish_result=result2;
405 }
406 }
407 }
408
409 result3=NextResult(begin,result3);
410 }
411
412 if(begin->number==1)
413 InsertInQueue(queue,result1);
414
415 /* Loop across all nodes in the queue */
416
417 while((result1=PopFromQueue(queue)))
418 {
419 index_t node1,seg1;
420 Segment *segment;
421 index_t turnrelation=NO_RELATION;
422
423 /* score must be better than current best score */
424 if(result1->score>finish_score)
425 continue;
426
427 node1=result1->node;
428 seg1=result1->segment;
429
430 /* lookup if a turn restriction applies */
431 if(profile->turns && IsTurnRestrictedNode(LookupNode(nodes,node1,1)))
432 turnrelation=FindFirstTurnRelation2(relations,node1,seg1);
433
434 /* Loop across all segments */
435
436 segment=FirstSegment(segments,nodes,node1); /* node1 cannot be a fake node (must be a super-node) */
437
438 while(segment)
439 {
440 Way *way;
441 Node *node;
442 index_t node2,seg2;
443 score_t segment_pref,segment_score,cumulative_score;
444 int i;
445
446 /* must be a super segment */
447 if(!IsSuperSegment(segment))
448 goto endloop;
449
450 /* must obey one-way restrictions (unless profile allows) */
451 if(profile->oneway && IsOnewayTo(segment,node1))
452 goto endloop;
453
454 node2=OtherNode(segment,node1);
455
456 seg2=IndexSegment(segments,segment); /* node2 cannot be a fake node (must be a super-node) */
457
458 /* must not perform u-turn */
459 if(seg1==seg2) /* No fake segments, applies to all profiles */
460 goto endloop;
461
462 /* must obey turn relations */
463 if(turnrelation!=NO_RELATION && !IsTurnAllowed(relations,turnrelation,node1,seg1,seg2,profile->allow))
464 goto endloop;
465
466 way=LookupWay(ways,segment->way,1);
467
468 /* transport must be allowed on the highway */
469 if(!(way->allow&profile->allow))
470 goto endloop;
471
472 /* must obey weight restriction (if exists) */
473 if(way->weight && way->weight<profile->weight)
474 goto endloop;
475
476 /* must obey height/width/length restriction (if exists) */
477 if((way->height && way->height<profile->height) ||
478 (way->width && way->width <profile->width ) ||
479 (way->length && way->length<profile->length))
480 goto endloop;
481
482 segment_pref=profile->highway[HIGHWAY(way->type)];
483
484 for(i=1;i<Property_Count;i++)
485 if(ways->file.props & PROPERTIES(i))
486 {
487 if(way->props & PROPERTIES(i))
488 segment_pref*=profile->props_yes[i];
489 else
490 segment_pref*=profile->props_no[i];
491 }
492
493 /* profile preferences must allow this highway */
494 if(segment_pref==0)
495 goto endloop;
496
497 node=LookupNode(nodes,node2,2); /* node2 cannot be a fake node (must be a super-node) */
498
499 /* mode of transport must be allowed through node2 */
500 if(!(node->allow&profile->allow))
501 goto endloop;
502
503 if(option_quickest==0)
504 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
505 else
506 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
507
508 cumulative_score=result1->score+segment_score;
509
510 /* score must be better than current best score */
511 if(cumulative_score>finish_score)
512 goto endloop;
513
514 result2=FindResult(results,node2,seg2);
515
516 if(!result2) /* New end node/segment pair */
517 {
518 result2=InsertResult(results,node2,seg2);
519 result2->prev=result1;
520 result2->score=cumulative_score;
521
522 if((result3=FindResult(end,node2,seg2)))
523 {
524 if((result2->score+result3->score)<finish_score)
525 {
526 finish_score=result2->score+result3->score;
527 finish_result=result2;
528 }
529 }
530 else
531 {
532 double lat,lon;
533 distance_t direct;
534
535 GetLatLong(nodes,node2,&lat,&lon); /* node2 cannot be a fake node (must be a super-node) */
536
537 direct=Distance(lat,lon,finish_lat,finish_lon);
538
539 if(option_quickest==0)
540 result2->sortby=result2->score+(score_t)direct/profile->max_pref;
541 else
542 result2->sortby=result2->score+(score_t)distance_speed_to_duration(direct,profile->max_speed)/profile->max_pref;
543
544 InsertInQueue(queue,result2);
545 }
546 }
547 else if(cumulative_score<result2->score) /* New end node/segment pair is better */
548 {
549 result2->prev=result1;
550 result2->score=cumulative_score;
551
552 if((result3=FindResult(end,node2,seg2)))
553 {
554 if((result2->score+result3->score)<finish_score)
555 {
556 finish_score=result2->score+result3->score;
557 finish_result=result2;
558 }
559 }
560 else if(result2->score<finish_score)
561 {
562 double lat,lon;
563 distance_t direct;
564
565 GetLatLong(nodes,node2,&lat,&lon); /* node2 cannot be a fake node (must be a super-node) */
566
567 direct=Distance(lat,lon,finish_lat,finish_lon);
568
569 if(option_quickest==0)
570 result2->sortby=result2->score+(score_t)direct/profile->max_pref;
571 else
572 result2->sortby=result2->score+(score_t)distance_speed_to_duration(direct,profile->max_speed)/profile->max_pref;
573
574 InsertInQueue(queue,result2);
575 }
576 }
577
578 if(!option_quiet && !(results->number%10000))
579 printf_middle("Routing: Super-Nodes checked = %d",results->number);
580
581 endloop:
582
583 segment=NextSegment(segments,segment,node1); /* node1 cannot be a fake node (must be a super-node) */
584 }
585 }
586
587 if(!option_quiet)
588 printf_last("Routing: Super-Nodes checked = %d",results->number);
589
590 FreeQueueList(queue);
591
592 /* Check it worked */
593
594 if(!finish_result)
595 {
596 FreeResultsList(results);
597 return(NULL);
598 }
599
600 /* Finish off the end part of the route */
601
602 if(finish_result->node!=end->finish_node)
603 {
604 result3=InsertResult(results,end->finish_node,NO_SEGMENT);
605
606 result3->prev=finish_result;
607 result3->score=finish_score;
608
609 finish_result=result3;
610 }
611
612 FixForwardRoute(results,finish_result);
613
614 return(results);
615 }
616
617
618 /*++++++++++++++++++++++++++++++++++++++
619 Find the super-segment that represents the route that contains a particular segment.
620
621 index_t FindSuperSegment Returns the index of the super-segment.
622
623 Nodes *nodes The set of nodes to use.
624
625 Segments *segments The set of segments to use.
626
627 Ways *ways The set of ways to use.
628
629 Relations *relations The set of relations to use.
630
631 index_t endnode The super-node that the route ends at.
632
633 index_t endsegment The segment that the route ends with.
634
635 Profile *profile The profile containing the transport type, speeds and allowed highways.
636 ++++++++++++++++++++++++++++++++++++++*/
637
638 static index_t FindSuperSegment(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,index_t endnode,index_t endsegment,Profile *profile)
639 {
640 Segment *segment;
641
642 segment=LookupSegment(segments,endsegment,1);
643
644 if(IsSuperSegment(segment))
645 return(endsegment);
646
647 /* Loop across all segments */
648
649 segment=FirstSegment(segments,nodes,endnode); /* endnode cannot be a fake node (must be a super-node) */
650
651 while(segment)
652 {
653 if(IsSuperSegment(segment))
654 {
655 Results *results;
656 index_t startnode;
657
658 startnode=OtherNode(segment,endnode);
659
660 results=FindNormalRoute(nodes,segments,ways,relations,startnode,NO_SEGMENT,endnode,profile,0);
661
662 if(results && results->last_segment==endsegment)
663 return(IndexSegment(segments,segment));
664 }
665
666 segment=NextSegment(segments,segment,endnode); /* endnode cannot be a fake node (must be a super-node) */
667 }
668
669 return(endsegment);
670 }
671
672
673 /*++++++++++++++++++++++++++++++++++++++
674 Find all routes from a specified node to any super-node.
675
676 Results *FindStartRoutes Returns a set of results.
677
678 Nodes *nodes The set of nodes to use.
679
680 Segments *segments The set of segments to use.
681
682 Ways *ways The set of ways to use.
683
684 Relations *relations The set of relations to use.
685
686 index_t start_node The start node.
687
688 index_t prev_segment The previous segment before the start node.
689
690 Profile *profile The profile containing the transport type, speeds and allowed highways.
691
692 int override A flag to indicate if U-turns and passing over super-nodes are allowed (to get out of dead-ends).
693 ++++++++++++++++++++++++++++++++++++++*/
694
695 Results *FindStartRoutes(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,index_t start_node,index_t prev_segment,Profile *profile,int override)
696 {
697 Results *results;
698 Queue *queue;
699 Result *result1,*result2;
700
701 /* Create the results and insert the start node */
702
703 results=NewResultsList(8);
704
705 results->start_node=start_node;
706 results->prev_segment=prev_segment;
707
708 result1=InsertResult(results,start_node,prev_segment);
709
710 /* Take a shortcut if the first node is a super-node. */
711
712 if(!IsFakeNode(start_node) && IsSuperNode(LookupNode(nodes,start_node,1)))
713 return(results);
714
715 /* Insert the first node into the queue */
716
717 queue=NewQueueList();
718
719 InsertInQueue(queue,result1);
720
721 /* Loop across all nodes in the queue */
722
723 while((result1=PopFromQueue(queue)))
724 {
725 index_t node1,seg1,seg1r;
726 Segment *segment;
727 int routes_out=0;
728 Segment *uturn_segment=NULL;
729
730 node1=result1->node;
731 seg1=result1->segment;
732
733 if(IsFakeSegment(seg1))
734 seg1r=IndexRealSegment(seg1);
735 else
736 seg1r=seg1;
737
738 /* node1 cannot have a turn restriction because it is not a super-node */
739
740 /* Loop across all segments */
741
742 if(IsFakeNode(node1))
743 segment=FirstFakeSegment(node1);
744 else
745 segment=FirstSegment(segments,nodes,node1);
746
747 while(segment)
748 {
749 Way *way;
750 index_t node2,seg2,seg2r;
751 score_t segment_pref,segment_score,cumulative_score;
752 int i;
753
754 /* must be a normal segment */
755 if(!IsNormalSegment(segment))
756 goto endloop;
757
758 /* must obey one-way restrictions (unless profile allows) */
759 if(profile->oneway && IsOnewayTo(segment,node1))
760 goto endloop;
761
762 node2=OtherNode(segment,node1);
763
764 if(IsFakeNode(node1) || IsFakeNode(node2))
765 {
766 seg2 =IndexFakeSegment(segment);
767 seg2r=IndexRealSegment(seg2);
768 }
769 else
770 {
771 seg2 =IndexSegment(segments,segment);
772 seg2r=seg2;
773 }
774
775 /* must not perform u-turn (unless profile allows) */
776 if(profile->turns && (seg1==seg2 || seg1==seg2r || seg1r==seg2) && segment!=uturn_segment)
777 {
778 if(override)
779 uturn_segment=segment;
780 goto endloop;
781 }
782
783 /* node1 cannot have a turn restriction because it is not a super-node */
784
785 way=LookupWay(ways,segment->way,1);
786
787 /* mode of transport must be allowed on the highway */
788 if(!(way->allow&profile->allow))
789 goto endloop;
790
791 /* must obey weight restriction (if exists) */
792 if(way->weight && way->weight<profile->weight)
793 goto endloop;
794
795 /* must obey height/width/length restriction (if exists) */
796 if((way->height && way->height<profile->height) ||
797 (way->width && way->width <profile->width ) ||
798 (way->length && way->length<profile->length))
799 goto endloop;
800
801 segment_pref=profile->highway[HIGHWAY(way->type)];
802
803 for(i=1;i<Property_Count;i++)
804 if(ways->file.props & PROPERTIES(i))
805 {
806 if(way->props & PROPERTIES(i))
807 segment_pref*=profile->props_yes[i];
808 else
809 segment_pref*=profile->props_no[i];
810 }
811
812 /* profile preferences must allow this highway */
813 if(segment_pref==0)
814 goto endloop;
815
816 /* mode of transport must be allowed through node2 */
817 if(!IsFakeNode(node2))
818 {
819 Node *node=LookupNode(nodes,node2,2);
820
821 if(!(node->allow&profile->allow))
822 goto endloop;
823 }
824
825 routes_out++;
826
827 if(option_quickest==0)
828 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
829 else
830 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
831
832 cumulative_score=result1->score+segment_score;
833
834 result2=FindResult(results,node2,seg2);
835
836 if(!result2) /* New end node/segment combination */
837 {
838 result2=InsertResult(results,node2,seg2);
839 result2->prev=result1;
840 result2->score=cumulative_score;
841
842 if(!IsFakeNode(node2) && !IsSuperNode(LookupNode(nodes,node2,2)))
843 {
844 result2->sortby=result2->score;
845 InsertInQueue(queue,result2);
846 }
847 }
848 else if(cumulative_score<result2->score) /* New end node/segment combination is better */
849 {
850 result2->prev=result1;
851 result2->score=cumulative_score;
852
853 if(!IsFakeNode(node2) && !IsSuperNode(LookupNode(nodes,node2,2)))
854 {
855 result2->sortby=result2->score;
856 InsertInQueue(queue,result2);
857 }
858 }
859
860 endloop:
861
862 if(IsFakeNode(node1))
863 segment=NextFakeSegment(segment,node1);
864 else
865 segment=NextSegment(segments,segment,node1);
866
867 /* allow u-turn at dead-ends if override is enabled */
868 if(!segment && routes_out==0 && uturn_segment)
869 segment=uturn_segment;
870 }
871 }
872
873 FreeQueueList(queue);
874
875 /* Check it worked */
876
877 if(results->number==1)
878 {
879 FreeResultsList(results);
880 return(NULL);
881 }
882
883 return(results);
884 }
885
886
887 /*++++++++++++++++++++++++++++++++++++++
888 Find all routes from any super-node to a specific node (by working backwards from the specific node to all super-nodes).
889
890 Results *FindFinishRoutes Returns a set of results.
891
892 Nodes *nodes The set of nodes to use.
893
894 Segments *segments The set of segments to use.
895
896 Ways *ways The set of ways to use.
897
898 Relations *relations The set of relations to use.
899
900 index_t finish_node The finishing node.
901
902 Profile *profile The profile containing the transport type, speeds and allowed highways.
903 ++++++++++++++++++++++++++++++++++++++*/
904
905 Results *FindFinishRoutes(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,index_t finish_node,Profile *profile)
906 {
907 Results *results,*results2;
908 Queue *queue;
909 Result *result1,*result2,*result3;
910
911 /* Create the results and insert the finish node */
912
913 results=NewResultsList(8);
914
915 results->finish_node=finish_node;
916
917 result1=InsertResult(results,finish_node,NO_SEGMENT);
918
919 /* Insert the first node into the queue */
920
921 queue=NewQueueList();
922
923 InsertInQueue(queue,result1);
924
925 /* Loop across all nodes in the queue */
926
927 while((result1=PopFromQueue(queue)))
928 {
929 index_t node1,seg1,seg1r;
930 Segment *segment;
931 index_t turnrelation=NO_RELATION;
932
933 node1=result1->node;
934 seg1=result1->segment;
935
936 if(IsFakeSegment(seg1))
937 seg1r=IndexRealSegment(seg1);
938 else
939 seg1r=seg1;
940
941 /* lookup if a turn restriction applies */
942 if(profile->turns && IsTurnRestrictedNode(LookupNode(nodes,node1,1)))
943 turnrelation=FindFirstTurnRelation1(relations,node1); /* working backwards => turn relation sort order doesn't help */
944
945 /* Loop across all segments */
946
947 if(IsFakeNode(node1))
948 segment=FirstFakeSegment(node1);
949 else
950 segment=FirstSegment(segments,nodes,node1);
951
952 while(segment)
953 {
954 Way *way;
955 index_t node2,seg2,seg2r;
956 score_t segment_pref,segment_score,cumulative_score;
957 int i;
958
959 /* must be a normal segment */
960 if((IsFakeNode(node1) || !IsSuperNode(LookupNode(nodes,node1,1))) && !IsNormalSegment(segment))
961 goto endloop;
962
963 /* must obey one-way restrictions (unless profile allows) */
964 if(profile->oneway && IsOnewayFrom(segment,node1)) /* Disallow oneway from node2 *to* node1 */
965 goto endloop;
966
967 node2=OtherNode(segment,node1);
968
969 if(IsFakeNode(node1) || IsFakeNode(node2))
970 {
971 seg2 =IndexFakeSegment(segment);
972 seg2r=IndexRealSegment(seg2);
973 }
974 else
975 {
976 seg2 =IndexSegment(segments,segment);
977 seg2r=seg2;
978 }
979
980 /* must not perform u-turn (unless profile allows) */
981 if(profile->turns && (seg1==seg2 || seg1==seg2r || seg1r==seg2))
982 goto endloop;
983
984 /* must obey turn relations */
985 if(turnrelation!=NO_RELATION)
986 {
987 index_t turnrelation2=FindFirstTurnRelation2(relations,node1,seg2r); /* node2 -> node1 -> result1->next->node */
988
989 if(turnrelation2!=NO_RELATION && !IsTurnAllowed(relations,turnrelation2,node1,seg2r,seg1r,profile->allow))
990 goto endloop;
991 }
992
993 way=LookupWay(ways,segment->way,1);
994
995 /* mode of transport must be allowed on the highway */
996 if(!(way->allow&profile->allow))
997 goto endloop;
998
999 /* must obey weight restriction (if exists) */
1000 if(way->weight && way->weight<profile->weight)
1001 goto endloop;
1002
1003 /* must obey height/width/length restriction (if exists) */
1004 if((way->height && way->height<profile->height) ||
1005 (way->width && way->width <profile->width ) ||
1006 (way->length && way->length<profile->length))
1007 goto endloop;
1008
1009 segment_pref=profile->highway[HIGHWAY(way->type)];
1010
1011 for(i=1;i<Property_Count;i++)
1012 if(ways->file.props & PROPERTIES(i))
1013 {
1014 if(way->props & PROPERTIES(i))
1015 segment_pref*=profile->props_yes[i];
1016 else
1017 segment_pref*=profile->props_no[i];
1018 }
1019
1020 /* profile preferences must allow this highway */
1021 if(segment_pref==0)
1022 goto endloop;
1023
1024 /* mode of transport must be allowed through node2 */
1025 if(!IsFakeNode(node2))
1026 {
1027 Node *node=LookupNode(nodes,node2,2);
1028
1029 if(!(node->allow&profile->allow))
1030 goto endloop;
1031 }
1032
1033 if(option_quickest==0)
1034 segment_score=(score_t)DISTANCE(segment->distance)/segment_pref;
1035 else
1036 segment_score=(score_t)Duration(segment,way,profile)/segment_pref;
1037
1038 cumulative_score=result1->score+segment_score;
1039
1040 result2=FindResult(results,node2,seg2);
1041
1042 if(!result2) /* New end node */
1043 {
1044 result2=InsertResult(results,node2,seg2);
1045 result2->next=result1; /* working backwards */
1046 result2->score=cumulative_score;
1047
1048 if(IsFakeNode(node1) || (!IsFakeNode(node1) && !IsSuperNode(LookupNode(nodes,node1,1)))) /* Overshoot by one segment */
1049 {
1050 result2->sortby=result2->score;
1051 InsertInQueue(queue,result2);
1052 }
1053 }
1054 else if(cumulative_score<result2->score) /* New end node is better */
1055 {
1056 result2->next=result1; /* working backwards */
1057 result2->score=cumulative_score;
1058
1059 if(IsFakeNode(node1) || (!IsFakeNode(node1) && !IsSuperNode(LookupNode(nodes,node1,1)))) /* Overshoot by one segment */
1060 {
1061 result2->sortby=result2->score;
1062 InsertInQueue(queue,result2);
1063 }
1064 }
1065
1066 endloop:
1067
1068 if(IsFakeNode(node1))
1069 segment=NextFakeSegment(segment,node1);
1070 else
1071 segment=NextSegment(segments,segment,node1);
1072 }
1073 }
1074
1075 FreeQueueList(queue);
1076
1077 /* Check it worked */
1078
1079 if(results->number==1)
1080 {
1081 FreeResultsList(results);
1082 return(NULL);
1083 }
1084
1085 /* Create a results structure with the node at the end of the segment opposite the start */
1086
1087 results2=NewResultsList(8);
1088
1089 results2->finish_node=results->finish_node;
1090
1091 result3=FirstResult(results);
1092
1093 while(result3)
1094 {
1095 if(result3->next)
1096 {
1097 result2=InsertResult(results2,result3->next->node,result3->segment);
1098
1099 result2->score=result3->next->score;
1100 }
1101
1102 result3=NextResult(results,result3);
1103 }
1104
1105 /* Fix up the result->next pointers */
1106
1107 result3=FirstResult(results);
1108
1109 while(result3)
1110 {
1111 if(result3->next && result3->next->next)
1112 {
1113 result1=FindResult(results2,result3->next->node,result3->segment);
1114 result2=FindResult(results2,result3->next->next->node,result3->next->segment);
1115
1116 result1->next=result2;
1117 }
1118
1119 result3=NextResult(results,result3);
1120 }
1121
1122 FreeResultsList(results);
1123
1124 return(results2);
1125 }
1126
1127
1128 /*++++++++++++++++++++++++++++++++++++++
1129 Create an optimum route given the set of super-nodes to follow.
1130
1131 Results *CombineRoutes Returns the results from joining the super-nodes.
1132
1133 Nodes *nodes The set of nodes to use.
1134
1135 Segments *segments The set of segments to use.
1136
1137 Ways *ways The set of ways to use.
1138
1139 Relations *relations The set of relations to use.
1140
1141 Results *middle The set of results from the super-node route.
1142
1143 Profile *profile The profile containing the transport type, speeds and allowed highways.
1144 ++++++++++++++++++++++++++++++++++++++*/
1145
1146 Results *CombineRoutes(Nodes *nodes,Segments *segments,Ways *ways,Relations *relations,Results *middle,Profile *profile)
1147 {
1148 Result *midres,*comres1;
1149 Results *combined;
1150
1151 combined=NewResultsList(64);
1152
1153 combined->start_node=middle->start_node;
1154 combined->prev_segment=middle->prev_segment;
1155
1156 /* Sort out the combined route */
1157
1158 midres=FindResult(middle,middle->start_node,middle->prev_segment);
1159
1160 comres1=InsertResult(combined,middle->start_node,middle->prev_segment);
1161
1162 do
1163 {
1164 Result *result;
1165
1166 if(midres->next)
1167 {
1168 Results *results=FindNormalRoute(nodes,segments,ways,relations,comres1->node,comres1->segment,midres->next->node,profile,0);
1169
1170 if(!results)
1171 {
1172 /* Try again but override the turn restriction and U-turn constraints */
1173
1174 results=FindNormalRoute(nodes,segments,ways,relations,comres1->node,comres1->segment,midres->next->node,profile,1);
1175 }
1176
1177 if(!results)
1178 return(NULL);
1179
1180 result=FindResult(results,midres->node,comres1->segment);
1181
1182 result=result->next;
1183
1184 /*
1185 * midres midres->next
1186 * = =
1187 * ---*----------------------------------* = middle
1188 *
1189 * ---*----.----.----.----.----.----.----* = results
1190 * =
1191 * result
1192 *
1193 * ---*----.----.----.----.----.----.----* = combined
1194 * = =
1195 * comres1 comres2
1196 */
1197
1198 do
1199 {
1200 Result *comres2;
1201
1202 comres2=InsertResult(combined,result->node,result->segment);
1203
1204 comres2->score=result->score+comres1->score;
1205 comres2->prev=comres1;
1206
1207 result=result->next;
1208
1209 comres1=comres2;
1210 }
1211 while(result);
1212
1213 FreeResultsList(results);
1214 }
1215
1216 midres=midres->next;
1217 }
1218 while(midres);
1219
1220 FixForwardRoute(combined,comres1);
1221
1222 return(combined);
1223 }
1224
1225
1226 /*++++++++++++++++++++++++++++++++++++++
1227 Fix the forward route (i.e. setup next pointers for forward path from prev nodes on reverse path).
1228
1229 Results *results The set of results to update.
1230
1231 Result *finish_result The result for the finish point.
1232 ++++++++++++++++++++++++++++++++++++++*/
1233
1234 void FixForwardRoute(Results *results,Result *finish_result)
1235 {
1236 Result *result2=finish_result;
1237
1238 /* Create the forward links for the optimum path */
1239
1240 do
1241 {
1242 Result *result1;
1243
1244 if(result2->prev)
1245 {
1246 index_t node1=result2->prev->node;
1247 index_t seg1=result2->prev->segment;
1248
1249 result1=FindResult(results,node1,seg1);
1250
1251 result1->next=result2;
1252
1253 result2=result1;
1254 }
1255 else
1256 result2=NULL;
1257 }
1258 while(result2);
1259
1260 results->finish_node=finish_result->node;
1261 results->last_segment=finish_result->segment;
1262 }

Properties

Name Value
cvs:description Route optimiser.