Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino
Contents of /trunk/src/optimiser.c
Parent Directory
|
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)
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. |