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