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