Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino
Contents of /trunk/src/optimiser.c
Parent Directory
|
Revision Log
Revision 68 -
(show annotations)
(download)
(as text)
Thu Jan 22 19:39:30 2009 UTC (16 years, 1 month ago) by amb
File MIME type: text/x-csrc
File size: 35790 byte(s)
Thu Jan 22 19:39:30 2009 UTC (16 years, 1 month ago) by amb
File MIME type: text/x-csrc
File size: 35790 byte(s)
Removed the Way_TYPE() macro.
1 | /*************************************** |
2 | $Header: /home/amb/CVS/routino/src/optimiser.c,v 1.26 2009-01-22 19:39:30 amb Exp $ |
3 | |
4 | Routing optimiser. |
5 | ******************/ /****************** |
6 | Written by Andrew M. Bishop |
7 | |
8 | This file Copyright 2008,2009 Andrew M. Bishop |
9 | It may be distributed under the GNU Public License, version 2, or |
10 | any higher version. See section COPYING of the GNU Public license |
11 | for conditions under which this file may be redistributed. |
12 | ***************************************/ |
13 | |
14 | |
15 | #include <assert.h> |
16 | #include <string.h> |
17 | #include <stdlib.h> |
18 | |
19 | #include "nodes.h" |
20 | #include "ways.h" |
21 | #include "segments.h" |
22 | #include "results.h" |
23 | #include "functions.h" |
24 | |
25 | |
26 | /*+ Print the progress? +*/ |
27 | int print_progress=1; |
28 | |
29 | |
30 | /*++++++++++++++++++++++++++++++++++++++ |
31 | Find the optimum route between two nodes. |
32 | |
33 | Results *FindRoute Returns a set of results. |
34 | |
35 | Nodes *nodes The set of nodes to use. |
36 | |
37 | Segments *segments The set of segments to use. |
38 | |
39 | Ways *ways The set of ways to use. |
40 | |
41 | node_t start The start node. |
42 | |
43 | node_t finish The finish node. |
44 | |
45 | wayallow_t transport The mode of transport. |
46 | ++++++++++++++++++++++++++++++++++++++*/ |
47 | |
48 | Results *FindRoute(Nodes *nodes,Segments *segments,Ways *ways,node_t start,node_t finish,wayallow_t transport) |
49 | { |
50 | Results *results; |
51 | node_t node1,node2; |
52 | HalfResult shortest1,quickest1; |
53 | HalfResult shortest2,quickest2; |
54 | HalfResult shortestfinish,quickestfinish; |
55 | Result *result1,*result2; |
56 | Segment *segment; |
57 | Way *way; |
58 | |
59 | /* Set up the finish conditions */ |
60 | |
61 | shortestfinish.distance=INVALID_DISTANCE; |
62 | shortestfinish.duration=INVALID_DURATION; |
63 | quickestfinish.distance=INVALID_DISTANCE; |
64 | quickestfinish.duration=INVALID_DURATION; |
65 | |
66 | /* Insert the first node into the queue */ |
67 | |
68 | results=NewResultsList(); |
69 | |
70 | result1=InsertResult(results,start); |
71 | |
72 | result1->node=start; |
73 | result1->shortest.prev=0; |
74 | result1->shortest.next=0; |
75 | result1->shortest.distance=0; |
76 | result1->shortest.duration=0; |
77 | result1->quickest.prev=0; |
78 | result1->quickest.next=0; |
79 | result1->quickest.distance=0; |
80 | result1->quickest.duration=0; |
81 | |
82 | insert_in_queue(results,result1); |
83 | |
84 | /* Loop across all nodes in the queue */ |
85 | |
86 | while((result1=pop_from_queue(results))) |
87 | { |
88 | node1=result1->node; |
89 | shortest1=result1->shortest; |
90 | quickest1=result1->quickest; |
91 | |
92 | segment=FindFirstSegment(segments,node1); |
93 | |
94 | while(segment) |
95 | { |
96 | duration_t segment_duration; |
97 | |
98 | if(segment->distance==INVALID_DISTANCE) |
99 | goto endloop; |
100 | |
101 | node2=segment->node2; |
102 | |
103 | if(shortest1.prev==node2 && quickest1.prev==node2) |
104 | goto endloop; |
105 | |
106 | way=FindWay(ways,segment->way); |
107 | |
108 | if((way->allow&transport)!=transport) |
109 | goto endloop; |
110 | |
111 | segment_duration=Duration(segment,way,transport); |
112 | |
113 | shortest2.distance=shortest1.distance+segment->distance; |
114 | shortest2.duration=shortest1.duration+segment_duration; |
115 | quickest2.distance=quickest1.distance+segment->distance; |
116 | quickest2.duration=quickest1.duration+segment_duration; |
117 | |
118 | if(shortest2.distance>shortestfinish.distance && quickest2.duration>quickestfinish.duration) |
119 | goto endloop; |
120 | |
121 | result2=FindResult(results,node2); |
122 | |
123 | if(!result2) /* New end node */ |
124 | { |
125 | result2=InsertResult(results,node2); |
126 | result2->node=node2; |
127 | result2->shortest.prev=node1; |
128 | result2->shortest.next=0; |
129 | result2->shortest.distance=shortest2.distance; |
130 | result2->shortest.duration=shortest2.duration; |
131 | result2->quickest.prev=node1; |
132 | result2->quickest.next=0; |
133 | result2->quickest.distance=quickest2.distance; |
134 | result2->quickest.duration=quickest2.duration; |
135 | |
136 | if(node2==finish) |
137 | { |
138 | shortestfinish.distance=shortest2.distance; |
139 | shortestfinish.duration=shortest2.duration; |
140 | quickestfinish.distance=quickest2.distance; |
141 | quickestfinish.duration=quickest2.duration; |
142 | } |
143 | else |
144 | insert_in_queue(results,result2); |
145 | } |
146 | else |
147 | { |
148 | if(shortest2.distance<result2->shortest.distance || |
149 | (shortest2.distance==result2->shortest.distance && |
150 | shortest2.duration<result2->shortest.duration)) /* New end node is shorter */ |
151 | { |
152 | result2->shortest.prev=node1; |
153 | result2->shortest.distance=shortest2.distance; |
154 | result2->shortest.duration=shortest2.duration; |
155 | |
156 | if(node2==finish) |
157 | { |
158 | shortestfinish.distance=shortest2.distance; |
159 | shortestfinish.duration=shortest2.duration; |
160 | } |
161 | else |
162 | insert_in_queue(results,result2); |
163 | } |
164 | |
165 | if(quickest2.duration<result2->quickest.duration || |
166 | (quickest2.duration==result2->quickest.duration && |
167 | quickest2.distance<result2->quickest.distance)) /* New end node is quicker */ |
168 | { |
169 | result2->quickest.prev=node1; |
170 | result2->quickest.distance=quickest2.distance; |
171 | result2->quickest.duration=quickest2.duration; |
172 | |
173 | if(node2==finish) |
174 | { |
175 | quickestfinish.distance=quickest2.distance; |
176 | quickestfinish.duration=quickest2.duration; |
177 | } |
178 | else |
179 | insert_in_queue(results,result2); |
180 | } |
181 | } |
182 | |
183 | endloop: |
184 | |
185 | segment=FindNextSegment(segments,segment); |
186 | } |
187 | |
188 | if(print_progress && !(results->number%10000)) |
189 | { |
190 | printf("\rRouting: End Nodes=%d Shortest=%.1fkm,%.0fmin Quickest=%.1fkm,%.0fmin ",results->number, |
191 | distance_to_km(shortest2.distance),duration_to_minutes(shortest2.duration), |
192 | distance_to_km(quickest2.distance),duration_to_minutes(quickest2.duration)); |
193 | fflush(stdout); |
194 | } |
195 | } |
196 | |
197 | if(print_progress) |
198 | { |
199 | printf("\rRouted: End Nodes=%d Shortest=%.1fkm,%.0fmin Quickest=%.1fkm,%.0fmin\n",results->number, |
200 | distance_to_km(shortestfinish.distance),duration_to_minutes(shortestfinish.duration), |
201 | distance_to_km(quickestfinish.distance),duration_to_minutes(quickestfinish.duration)); |
202 | fflush(stdout); |
203 | } |
204 | |
205 | /* Reverse the results */ |
206 | |
207 | result2=FindResult(results,finish); |
208 | |
209 | do |
210 | { |
211 | if(result2->shortest.prev) |
212 | { |
213 | node_t node1=result2->shortest.prev; |
214 | |
215 | result1=FindResult(results,node1); |
216 | |
217 | result1->shortest.next=result2->node; |
218 | |
219 | result2=result1; |
220 | } |
221 | else |
222 | result2=NULL; |
223 | } |
224 | while(result2); |
225 | |
226 | result2=FindResult(results,finish); |
227 | |
228 | do |
229 | { |
230 | if(result2->quickest.prev) |
231 | { |
232 | node_t node1=result2->quickest.prev; |
233 | |
234 | result1=FindResult(results,node1); |
235 | |
236 | result1->quickest.next=result2->node; |
237 | |
238 | result2=result1; |
239 | } |
240 | else |
241 | result2=NULL; |
242 | } |
243 | while(result2); |
244 | |
245 | return(results); |
246 | } |
247 | |
248 | |
249 | /*++++++++++++++++++++++++++++++++++++++ |
250 | Find the optimum route between two nodes. |
251 | |
252 | Results *FindRoute3 Returns a set of results. |
253 | |
254 | Nodes *supernodes The set of supernodes to use. |
255 | |
256 | Segments *supersegments The set of supersegments to use. |
257 | |
258 | Ways *superways The set of superways to use. |
259 | |
260 | node_t start The start node. |
261 | |
262 | node_t finish The finish node. |
263 | |
264 | Results *begin The initial portion of the route. |
265 | |
266 | Results *end The final portion of the route. |
267 | |
268 | wayallow_t transport The mode of transport. |
269 | ++++++++++++++++++++++++++++++++++++++*/ |
270 | |
271 | Results *FindRoute3(Nodes *supernodes,Segments *supersegments,Ways *superways,node_t start,node_t finish,Results *begin,Results *end,wayallow_t transport) |
272 | { |
273 | Results *results; |
274 | node_t node1,node2; |
275 | HalfResult shortest1,quickest1; |
276 | HalfResult shortest2,quickest2; |
277 | HalfResult shortestfinish,quickestfinish; |
278 | Result *result1,*result2,*result3; |
279 | Segment *segment; |
280 | Way *way; |
281 | int j; |
282 | |
283 | /* Set up the finish conditions */ |
284 | |
285 | shortestfinish.distance=INVALID_DISTANCE; |
286 | shortestfinish.duration=INVALID_DURATION; |
287 | quickestfinish.distance=INVALID_DISTANCE; |
288 | quickestfinish.duration=INVALID_DURATION; |
289 | |
290 | /* Insert the start node */ |
291 | |
292 | results=NewResultsList(); |
293 | |
294 | result1=InsertResult(results,start); |
295 | result2=FindResult(begin,start); |
296 | |
297 | *result1=*result2; |
298 | |
299 | /* Insert the finish points of the beginning part of the path into the queue */ |
300 | |
301 | for(j=0;j<begin->number;j++) |
302 | if(FindNode(supernodes,begin->results[j].node)) |
303 | { |
304 | if(!(result1=FindResult(results,begin->results[j].node))) |
305 | { |
306 | result1=InsertResult(results,begin->results[j].node); |
307 | |
308 | *result1=begin->results[j]; |
309 | |
310 | result1->shortest.prev=start; |
311 | result1->quickest.prev=start; |
312 | } |
313 | |
314 | insert_in_queue(results,result1); |
315 | } |
316 | |
317 | /* Loop across all supernodes in the queue */ |
318 | |
319 | while((result1=pop_from_queue(results))) |
320 | { |
321 | node1=result1->node; |
322 | shortest1=result1->shortest; |
323 | quickest1=result1->quickest; |
324 | |
325 | segment=FindFirstSegment(supersegments,node1); |
326 | |
327 | while(segment) |
328 | { |
329 | duration_t segment_duration; |
330 | |
331 | if(segment->distance==INVALID_DISTANCE) |
332 | goto endloop; |
333 | |
334 | node2=segment->node2; |
335 | |
336 | if(shortest1.prev==node2 && quickest1.prev==node2) |
337 | goto endloop; |
338 | |
339 | way=FindWay(superways,segment->way); |
340 | |
341 | if((way->allow&transport)!=transport) |
342 | goto endloop; |
343 | |
344 | segment_duration=Duration(segment,way,transport); |
345 | |
346 | shortest2.distance=shortest1.distance+segment->distance; |
347 | shortest2.duration=shortest1.duration+segment_duration; |
348 | quickest2.distance=quickest1.distance+segment->distance; |
349 | quickest2.duration=quickest1.duration+segment_duration; |
350 | |
351 | if(shortest2.distance>shortestfinish.distance && quickest2.duration>quickestfinish.duration) |
352 | goto endloop; |
353 | |
354 | result2=FindResult(results,node2); |
355 | result3=NULL; |
356 | |
357 | if(!result2) /* New end node */ |
358 | { |
359 | result2=InsertResult(results,node2); |
360 | result2->node=node2; |
361 | result2->shortest.prev=node1; |
362 | result2->shortest.next=0; |
363 | result2->shortest.distance=shortest2.distance; |
364 | result2->shortest.duration=shortest2.duration; |
365 | result2->quickest.prev=node1; |
366 | result2->quickest.next=0; |
367 | result2->quickest.distance=quickest2.distance; |
368 | result2->quickest.duration=quickest2.duration; |
369 | |
370 | if(!(result3=FindResult(end,node2))) |
371 | insert_in_queue(results,result2); |
372 | } |
373 | else |
374 | { |
375 | if(shortest2.distance<result2->shortest.distance || |
376 | (shortest2.distance==result2->shortest.distance && |
377 | shortest2.duration<result2->shortest.duration)) /* New end node is shorter */ |
378 | { |
379 | result2->shortest.prev=node1; |
380 | result2->shortest.distance=shortest2.distance; |
381 | result2->shortest.duration=shortest2.duration; |
382 | |
383 | if(!(result3=FindResult(end,node2))) |
384 | insert_in_queue(results,result2); |
385 | } |
386 | |
387 | if(quickest2.duration<result2->quickest.duration || |
388 | (quickest2.duration==result2->quickest.duration && |
389 | quickest2.distance<result2->quickest.distance)) /* New end node is quicker */ |
390 | { |
391 | result2->quickest.prev=node1; |
392 | result2->quickest.distance=quickest2.distance; |
393 | result2->quickest.duration=quickest2.duration; |
394 | |
395 | if(!(result3=FindResult(end,node2))) |
396 | insert_in_queue(results,result2); |
397 | } |
398 | } |
399 | |
400 | if(result3) |
401 | { |
402 | if((shortest2.distance+result3->shortest.distance)<shortestfinish.distance || |
403 | ((shortest2.distance+result3->shortest.distance)==shortestfinish.distance && |
404 | (shortest2.duration+result3->shortest.duration)<shortestfinish.duration)) |
405 | { |
406 | shortestfinish.distance=shortest2.distance+result3->shortest.distance; |
407 | shortestfinish.duration=shortest2.duration+result3->shortest.duration; |
408 | } |
409 | if((quickest2.duration+result3->quickest.duration)<quickestfinish.duration || |
410 | ((quickest2.duration+result3->quickest.duration)==quickestfinish.duration && |
411 | (quickest2.distance+result3->quickest.distance)<quickestfinish.distance)) |
412 | { |
413 | quickestfinish.distance=quickest2.distance+result3->quickest.distance; |
414 | quickestfinish.duration=quickest2.duration+result3->quickest.duration; |
415 | } |
416 | } |
417 | |
418 | endloop: |
419 | |
420 | segment=FindNextSegment(supersegments,segment); |
421 | } |
422 | |
423 | if(print_progress && !(results->number%10000)) |
424 | { |
425 | printf("\rRouting: End Nodes=%d Shortest=%.1fkm,%.0fmin Quickest=%.1fkm,%.0fmin ",results->number, |
426 | distance_to_km(shortest2.distance),duration_to_minutes(shortest2.duration), |
427 | distance_to_km(quickest2.distance),duration_to_minutes(quickest2.duration)); |
428 | fflush(stdout); |
429 | } |
430 | } |
431 | |
432 | if(print_progress) |
433 | { |
434 | printf("\rRouted: End Super-Nodes=%d Shortest=%.1fkm,%.0fmin Quickest=%.1fkm,%.0fmin\n",results->number, |
435 | distance_to_km(shortestfinish.distance),duration_to_minutes(shortestfinish.duration), |
436 | distance_to_km(quickestfinish.distance),duration_to_minutes(quickestfinish.duration)); |
437 | fflush(stdout); |
438 | } |
439 | |
440 | /* Finish off the end part of the route. */ |
441 | |
442 | if(!FindResult(results,finish)) |
443 | { |
444 | result2=InsertResult(results,finish); |
445 | result1=FindResult(end,finish); |
446 | |
447 | *result2=*result1; |
448 | |
449 | result2->shortest.distance=INVALID_DISTANCE; |
450 | result2->shortest.duration=INVALID_DURATION; |
451 | result2->quickest.distance=INVALID_DISTANCE; |
452 | result2->quickest.duration=INVALID_DURATION; |
453 | |
454 | for(j=0;j<end->number;j++) |
455 | if(FindNode(supernodes,end->results[j].node)) |
456 | if((result1=FindResult(results,end->results[j].node))) |
457 | { |
458 | if((result1->shortest.distance+end->results[j].shortest.distance)<result2->shortest.distance || |
459 | ((result1->shortest.distance+end->results[j].shortest.distance)==result2->shortest.distance && |
460 | (result1->shortest.duration+end->results[j].shortest.duration)<result2->shortest.duration)) |
461 | { |
462 | result2->shortest.distance=result1->shortest.distance+end->results[j].shortest.distance; |
463 | result2->shortest.duration=result1->shortest.duration+end->results[j].shortest.duration; |
464 | result2->shortest.prev=result1->node; |
465 | } |
466 | if((result1->quickest.duration+end->results[j].quickest.duration)<result2->quickest.duration || |
467 | ((result1->quickest.duration+end->results[j].quickest.duration)==result2->quickest.duration && |
468 | (result1->quickest.distance+end->results[j].quickest.distance)<result2->quickest.distance)) |
469 | { |
470 | result2->quickest.distance=result1->quickest.distance+end->results[j].quickest.distance; |
471 | result2->quickest.duration=result1->quickest.duration+end->results[j].quickest.duration; |
472 | result2->quickest.prev=result1->node; |
473 | } |
474 | } |
475 | } |
476 | |
477 | /* Reverse the results */ |
478 | |
479 | result2=FindResult(results,finish); |
480 | |
481 | do |
482 | { |
483 | if(result2->shortest.prev) |
484 | { |
485 | node_t node1=result2->shortest.prev; |
486 | |
487 | result1=FindResult(results,node1); |
488 | |
489 | result1->shortest.next=result2->node; |
490 | |
491 | result2=result1; |
492 | } |
493 | else |
494 | result2=NULL; |
495 | } |
496 | while(result2); |
497 | |
498 | result2=FindResult(results,finish); |
499 | |
500 | do |
501 | { |
502 | if(result2->quickest.prev) |
503 | { |
504 | node_t node1=result2->quickest.prev; |
505 | |
506 | result1=FindResult(results,node1); |
507 | |
508 | result1->quickest.next=result2->node; |
509 | |
510 | result2=result1; |
511 | } |
512 | else |
513 | result2=NULL; |
514 | } |
515 | while(result2); |
516 | |
517 | return(results); |
518 | } |
519 | |
520 | |
521 | /*++++++++++++++++++++++++++++++++++++++ |
522 | Print the optimum route between two nodes. |
523 | |
524 | Results *Results The set of results to print. |
525 | |
526 | Nodes *nodes The list of nodes. |
527 | |
528 | Segments *segments The set of segments to use. |
529 | |
530 | Ways *ways The list of ways. |
531 | |
532 | Nodes *supernodes The list of super-nodes. |
533 | |
534 | node_t start The start node. |
535 | |
536 | node_t finish The finish node. |
537 | |
538 | wayallow_t transport The mode of transport. |
539 | ++++++++++++++++++++++++++++++++++++++*/ |
540 | |
541 | void PrintRoute(Results *results,Nodes *nodes,Segments *segments,Ways *ways,Nodes *supernodes,node_t start,node_t finish,wayallow_t transport) |
542 | { |
543 | FILE *textfile,*gpxfile; |
544 | Result *result; |
545 | |
546 | /* Print the result for the shortest route */ |
547 | |
548 | textfile=fopen("shortest.txt","w"); |
549 | gpxfile=fopen("shortest.gpx","w"); |
550 | |
551 | fprintf(gpxfile,"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n"); |
552 | fprintf(gpxfile,"<gpx version=\"1.0\" creator=\"Router\" xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\" xmlns=\"http://www.topografix.com/GPX/1/0\" xsi:schemaLocation=\"http://www.topografix.com/GPX/1/0 http://www.topografix.com/GPX/1/0/gpx.xsd\">\n"); |
553 | fprintf(gpxfile,"<trk>\n"); |
554 | fprintf(gpxfile,"<trkseg>\n"); |
555 | |
556 | result=FindResult(results,start); |
557 | |
558 | do |
559 | { |
560 | Node *node=FindNode(nodes,result->node); |
561 | |
562 | fprintf(gpxfile,"<trkpt lat=\"%.6f\" lon=\"%.6f\"></trkpt>\n",node->latitude,node->longitude); |
563 | |
564 | if(result->shortest.prev) |
565 | { |
566 | Segment *segment; |
567 | Way *way; |
568 | |
569 | segment=FindFirstSegment(segments,result->shortest.prev); |
570 | while(segment->node2!=result->node) |
571 | segment=FindNextSegment(segments,segment); |
572 | |
573 | way=FindWay(ways,segment->way); |
574 | |
575 | fprintf(textfile,"%8.4f %9.4f %10d%c %5.3f %5.2f %7.2f %5.1f %3d %s\n",node->latitude,node->longitude, |
576 | node->id,supernodes?(FindNode(supernodes,node->id)?'*':' '):' ', |
577 | distance_to_km(segment->distance),duration_to_minutes(Duration(segment,way,transport)), |
578 | distance_to_km(result->shortest.distance),duration_to_minutes(result->shortest.duration), |
579 | WaySpeed(way),WayName(ways,way)); |
580 | } |
581 | else |
582 | fprintf(textfile,"%8.4f %9.4f %10d%c %5.3f %5.2f %7.2f %5.1f\n",node->latitude,node->longitude, |
583 | node->id,supernodes?(FindNode(supernodes,node->id)?'*':' '):' ', |
584 | 0.0,0.0,0.0,0.0); |
585 | |
586 | if(result->shortest.next) |
587 | result=FindResult(results,result->shortest.next); |
588 | else |
589 | result=NULL; |
590 | } |
591 | while(result); |
592 | |
593 | fprintf(gpxfile,"</trkseg>\n"); |
594 | fprintf(gpxfile,"</trk>\n"); |
595 | fprintf(gpxfile,"</gpx>\n"); |
596 | |
597 | fclose(textfile); |
598 | fclose(gpxfile); |
599 | |
600 | /* Print the result for the quickest route */ |
601 | |
602 | textfile=fopen("quickest.txt","w"); |
603 | gpxfile=fopen("quickest.gpx","w"); |
604 | |
605 | fprintf(gpxfile,"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n"); |
606 | fprintf(gpxfile,"<gpx version=\"1.0\" creator=\"Router\" xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\" xmlns=\"http://www.topografix.com/GPX/1/0\" xsi:schemaLocation=\"http://www.topografix.com/GPX/1/0 http://www.topografix.com/GPX/1/0/gpx.xsd\">\n"); |
607 | fprintf(gpxfile,"<trk>\n"); |
608 | fprintf(gpxfile,"<trkseg>\n"); |
609 | |
610 | result=FindResult(results,start); |
611 | |
612 | do |
613 | { |
614 | Node *node=FindNode(nodes,result->node); |
615 | |
616 | fprintf(gpxfile,"<trkpt lat=\"%.6f\" lon=\"%.6f\"></trkpt>\n",node->latitude,node->longitude); |
617 | |
618 | if(result->quickest.prev) |
619 | { |
620 | Segment *segment; |
621 | Way *way; |
622 | |
623 | segment=FindFirstSegment(segments,result->quickest.prev); |
624 | while(segment->node2!=result->node) |
625 | segment=FindNextSegment(segments,segment); |
626 | |
627 | way=FindWay(ways,segment->way); |
628 | |
629 | fprintf(textfile,"%8.4f %9.4f %10d%c %5.3f %5.2f %7.2f %5.1f %3d %s\n",node->latitude,node->longitude, |
630 | node->id,supernodes?(FindNode(supernodes,node->id)?'*':' '):' ', |
631 | distance_to_km(segment->distance),duration_to_minutes(Duration(segment,way,transport)), |
632 | distance_to_km(result->quickest.distance),duration_to_minutes(result->quickest.duration), |
633 | WaySpeed(way),WayName(ways,way)); |
634 | } |
635 | else |
636 | fprintf(textfile,"%8.4f %9.4f %10d%c %5.3f %5.2f %7.2f %5.1f\n",node->latitude,node->longitude, |
637 | node->id,supernodes?(FindNode(supernodes,node->id)?'*':' '):' ', |
638 | 0.0,0.0,0.0,0.0); |
639 | |
640 | if(result->quickest.next) |
641 | result=FindResult(results,result->quickest.next); |
642 | else |
643 | result=NULL; |
644 | } |
645 | while(result); |
646 | |
647 | fprintf(gpxfile,"</trkseg>\n"); |
648 | fprintf(gpxfile,"</trk>\n"); |
649 | fprintf(gpxfile,"</gpx>\n"); |
650 | |
651 | fclose(textfile); |
652 | fclose(gpxfile); |
653 | } |
654 | |
655 | |
656 | /*++++++++++++++++++++++++++++++++++++++ |
657 | Find all routes from a specified node to any node in the specified list. |
658 | |
659 | Results *FindRoutes Returns a set of results. |
660 | |
661 | Nodes *nodes The set of nodes to use. |
662 | |
663 | Segments *segments The set of segments to use. |
664 | |
665 | Ways *ways The set of ways to use. |
666 | |
667 | node_t start The start node. |
668 | |
669 | Nodes *finish The finishing nodes. |
670 | |
671 | wayallow_t transport The mode of transport. |
672 | ++++++++++++++++++++++++++++++++++++++*/ |
673 | |
674 | Results *FindRoutes(Nodes *nodes,Segments *segments,Ways *ways,node_t start,Nodes *finish,wayallow_t transport) |
675 | { |
676 | Results *results; |
677 | node_t node1,node2; |
678 | HalfResult shortest1,quickest1; |
679 | HalfResult shortest2,quickest2; |
680 | Result *result1,*result2; |
681 | Segment *segment; |
682 | Way *way; |
683 | |
684 | /* Insert the first node into the queue */ |
685 | |
686 | results=NewResultsList(); |
687 | |
688 | result1=InsertResult(results,start); |
689 | |
690 | result1->node=start; |
691 | result1->shortest.prev=0; |
692 | result1->shortest.next=0; |
693 | result1->shortest.distance=0; |
694 | result1->shortest.duration=0; |
695 | result1->quickest.prev=0; |
696 | result1->quickest.next=0; |
697 | result1->quickest.distance=0; |
698 | result1->quickest.duration=0; |
699 | |
700 | insert_in_queue(results,result1); |
701 | |
702 | /* Loop across all nodes in the queue */ |
703 | |
704 | while((result1=pop_from_queue(results))) |
705 | { |
706 | node1=result1->node; |
707 | shortest1=result1->shortest; |
708 | quickest1=result1->quickest; |
709 | |
710 | segment=FindFirstSegment(segments,node1); |
711 | |
712 | while(segment) |
713 | { |
714 | duration_t segment_duration; |
715 | |
716 | if(segment->distance==INVALID_DISTANCE) |
717 | goto endloop; |
718 | |
719 | node2=segment->node2; |
720 | |
721 | if(shortest1.prev==node2 && quickest1.prev==node2) |
722 | goto endloop; |
723 | |
724 | way=FindWay(ways,segment->way); |
725 | |
726 | if((way->allow&transport)!=transport) |
727 | goto endloop; |
728 | |
729 | segment_duration=Duration(segment,way,transport); |
730 | |
731 | shortest2.distance=shortest1.distance+segment->distance; |
732 | shortest2.duration=shortest1.duration+segment_duration; |
733 | quickest2.distance=quickest1.distance+segment->distance; |
734 | quickest2.duration=quickest1.duration+segment_duration; |
735 | |
736 | result2=FindResult(results,node2); |
737 | |
738 | if(!result2) /* New end node */ |
739 | { |
740 | result2=InsertResult(results,node2); |
741 | result2->node=node2; |
742 | result2->shortest.prev=node1; |
743 | result2->shortest.next=0; |
744 | result2->shortest.distance=shortest2.distance; |
745 | result2->shortest.duration=shortest2.duration; |
746 | result2->quickest.prev=node1; |
747 | result2->quickest.next=0; |
748 | result2->quickest.distance=quickest2.distance; |
749 | result2->quickest.duration=quickest2.duration; |
750 | |
751 | if(!FindNode(finish,node2)) |
752 | insert_in_queue(results,result2); |
753 | } |
754 | else |
755 | { |
756 | if(shortest2.distance<result2->shortest.distance || |
757 | (shortest2.distance==result2->shortest.distance && |
758 | shortest2.duration<result2->shortest.duration)) /* New end node is shorter */ |
759 | { |
760 | result2->shortest.prev=node1; |
761 | result2->shortest.distance=shortest2.distance; |
762 | result2->shortest.duration=shortest2.duration; |
763 | |
764 | if(!FindNode(finish,node2)) |
765 | insert_in_queue(results,result2); |
766 | } |
767 | |
768 | if(quickest2.duration<result2->quickest.duration || |
769 | (quickest2.duration==result2->quickest.duration && |
770 | quickest2.distance<result2->quickest.distance)) /* New end node is quicker */ |
771 | { |
772 | result2->quickest.prev=node1; |
773 | result2->quickest.distance=quickest2.distance; |
774 | result2->quickest.duration=quickest2.duration; |
775 | |
776 | if(!FindNode(finish,node2)) |
777 | insert_in_queue(results,result2); |
778 | } |
779 | } |
780 | |
781 | endloop: |
782 | |
783 | segment=FindNextSegment(segments,segment); |
784 | } |
785 | } |
786 | |
787 | return(results); |
788 | } |
789 | |
790 | |
791 | /*++++++++++++++++++++++++++++++++++++++ |
792 | Find all routes from any node in the specified list to a specific node. |
793 | |
794 | Results *FindReverseRoute Returns a set of results. |
795 | |
796 | Nodes *nodes The set of nodes to use. |
797 | |
798 | Segments *segments The set of segments to use. |
799 | |
800 | Ways *ways The set of ways to use. |
801 | |
802 | Nodes *start The starting nodes. |
803 | |
804 | node_t finish The finishing node. |
805 | |
806 | wayallow_t transport The mode of transport. |
807 | ++++++++++++++++++++++++++++++++++++++*/ |
808 | |
809 | Results *FindReverseRoutes(Nodes *nodes,Segments *segments,Ways *ways,Nodes *start,node_t finish,wayallow_t transport) |
810 | { |
811 | Results *results; |
812 | node_t node1,node2; |
813 | HalfResult shortest1,quickest1; |
814 | HalfResult shortest2,quickest2; |
815 | Result *result1,*result2; |
816 | Segment *segment; |
817 | Way *way; |
818 | |
819 | /* Insert the first node into the queue */ |
820 | |
821 | results=NewResultsList(); |
822 | |
823 | result1=InsertResult(results,finish); |
824 | |
825 | result1->node=finish; |
826 | result1->shortest.prev=0; |
827 | result1->shortest.next=0; |
828 | result1->shortest.distance=0; |
829 | result1->shortest.duration=0; |
830 | result1->quickest.prev=0; |
831 | result1->quickest.next=0; |
832 | result1->quickest.distance=0; |
833 | result1->quickest.duration=0; |
834 | |
835 | insert_in_queue(results,result1); |
836 | |
837 | /* Loop across all nodes in the queue */ |
838 | |
839 | while((result1=pop_from_queue(results))) |
840 | { |
841 | node1=result1->node; |
842 | shortest1=result1->shortest; |
843 | quickest1=result1->quickest; |
844 | |
845 | segment=FindFirstSegment(segments,node1); |
846 | |
847 | while(segment) |
848 | { |
849 | duration_t reversesegment_duration; |
850 | |
851 | /* Reverse the segment and check it exists */ |
852 | |
853 | node_t reversenode; |
854 | Segment *reversesegment; |
855 | |
856 | reversenode=segment->node2; |
857 | reversesegment=FindFirstSegment(segments,reversenode); |
858 | |
859 | while(reversesegment && reversesegment->node2!=node1) |
860 | reversesegment=FindNextSegment(segments,reversesegment); |
861 | |
862 | if(!reversesegment) |
863 | goto endloop; |
864 | |
865 | if(reversesegment->distance==INVALID_DISTANCE) |
866 | goto endloop; |
867 | |
868 | node2=reversesegment->node1; |
869 | |
870 | if(shortest1.prev==node2 && quickest1.prev==node2) |
871 | goto endloop; |
872 | |
873 | way=FindWay(ways,reversesegment->way); |
874 | |
875 | if((way->allow&transport)!=transport) |
876 | goto endloop; |
877 | |
878 | reversesegment_duration=Duration(reversesegment,way,transport); |
879 | |
880 | shortest2.distance=shortest1.distance+reversesegment->distance; |
881 | shortest2.duration=shortest1.duration+reversesegment_duration; |
882 | quickest2.distance=quickest1.distance+reversesegment->distance; |
883 | quickest2.duration=quickest1.duration+reversesegment_duration; |
884 | |
885 | result2=FindResult(results,node2); |
886 | |
887 | if(!result2) /* New end node */ |
888 | { |
889 | result2=InsertResult(results,node2); |
890 | result2->node=node2; |
891 | result2->shortest.prev=0; |
892 | result2->shortest.next=node1; |
893 | result2->shortest.distance=shortest2.distance; |
894 | result2->shortest.duration=shortest2.duration; |
895 | result2->quickest.prev=0; |
896 | result2->quickest.next=node1; |
897 | result2->quickest.distance=quickest2.distance; |
898 | result2->quickest.duration=quickest2.duration; |
899 | |
900 | if(!FindNode(start,node2)) |
901 | insert_in_queue(results,result2); |
902 | } |
903 | else |
904 | { |
905 | if(shortest2.distance<result2->shortest.distance || |
906 | (shortest2.distance==result2->shortest.distance && |
907 | shortest2.duration<result2->shortest.duration)) /* New end node is shorter */ |
908 | { |
909 | result2->shortest.next=node1; |
910 | result2->shortest.distance=shortest2.distance; |
911 | result2->shortest.duration=shortest2.duration; |
912 | |
913 | if(!FindNode(start,node2)) |
914 | insert_in_queue(results,result2); |
915 | } |
916 | |
917 | if(quickest2.duration<result2->quickest.duration || |
918 | (quickest2.duration==result2->quickest.duration && |
919 | quickest2.distance<result2->quickest.distance)) /* New end node is quicker */ |
920 | { |
921 | result2->quickest.next=node1; |
922 | result2->quickest.distance=quickest2.distance; |
923 | result2->quickest.duration=quickest2.duration; |
924 | |
925 | if(!FindNode(start,node2)) |
926 | insert_in_queue(results,result2); |
927 | } |
928 | } |
929 | |
930 | endloop: |
931 | |
932 | segment=FindNextSegment(segments,segment); |
933 | } |
934 | } |
935 | |
936 | return(results); |
937 | } |
938 | |
939 | |
940 | /*++++++++++++++++++++++++++++++++++++++ |
941 | Print the optimum route between two nodes. |
942 | |
943 | Results *CombineRoutes Returns the results from joining the super-nodes. |
944 | |
945 | Results *results The set of results from the super-nodes. |
946 | |
947 | Nodes *nodes The list of nodes. |
948 | |
949 | Segments *segments The set of segments to use. |
950 | |
951 | Ways *ways The list of ways. |
952 | |
953 | node_t start The start node. |
954 | |
955 | node_t finish The finish node. |
956 | |
957 | wayallow_t transport The mode of transport. |
958 | ++++++++++++++++++++++++++++++++++++++*/ |
959 | |
960 | Results *CombineRoutes(Results *results,Nodes *nodes,Segments *segments,Ways *ways,node_t start,node_t finish,wayallow_t transport) |
961 | { |
962 | Result *result1,*result2,*result3,*result4; |
963 | Results *combined; |
964 | |
965 | combined=NewResultsList(); |
966 | |
967 | print_progress=0; |
968 | |
969 | /* Sort out the shortest */ |
970 | |
971 | result1=FindResult(results,start); |
972 | |
973 | result3=InsertResult(combined,start); |
974 | |
975 | result3->node=result1->node; |
976 | |
977 | result3->shortest.distance=0; |
978 | result3->shortest.duration=0; |
979 | result3->shortest.next=0; |
980 | result3->shortest.prev=0; |
981 | |
982 | do |
983 | { |
984 | if(result1->shortest.next) |
985 | { |
986 | Results *results2=FindRoute(nodes,segments,ways,result1->node,result1->shortest.next,transport); |
987 | |
988 | result2=FindResult(results2,result1->node); |
989 | |
990 | result3->shortest.next=result2->shortest.next; |
991 | |
992 | result2=FindResult(results2,result2->shortest.next); |
993 | |
994 | do |
995 | { |
996 | result4=InsertResult(combined,result2->node); |
997 | |
998 | result4->node=result2->node; |
999 | |
1000 | result4->shortest=result2->shortest; |
1001 | result4->shortest.distance+=result3->shortest.distance; |
1002 | result4->shortest.duration+=result3->shortest.duration; |
1003 | |
1004 | if(result2->shortest.next) |
1005 | result2=FindResult(results2,result2->shortest.next); |
1006 | else |
1007 | result2=NULL; |
1008 | } |
1009 | while(result2); |
1010 | |
1011 | FreeResultsList(results2); |
1012 | |
1013 | result1=FindResult(results,result1->shortest.next); |
1014 | |
1015 | result3=result4; |
1016 | } |
1017 | else |
1018 | result1=NULL; |
1019 | } |
1020 | while(result1); |
1021 | |
1022 | /* Sort out the quickest */ |
1023 | |
1024 | result1=FindResult(results,start); |
1025 | |
1026 | result3=FindResult(combined,start); |
1027 | |
1028 | result3->quickest.distance=0; |
1029 | result3->quickest.duration=0; |
1030 | result3->quickest.next=0; |
1031 | result3->quickest.prev=0; |
1032 | |
1033 | do |
1034 | { |
1035 | if(result1->quickest.next) |
1036 | { |
1037 | Results *results2=FindRoute(nodes,segments,ways,result1->node,result1->quickest.next,transport); |
1038 | |
1039 | result2=FindResult(results2,result1->node); |
1040 | |
1041 | result3->quickest.next=result2->quickest.next; |
1042 | |
1043 | result2=FindResult(results2,result2->quickest.next); |
1044 | |
1045 | do |
1046 | { |
1047 | result4=FindResult(combined,result2->node); |
1048 | |
1049 | if(!result4) |
1050 | { |
1051 | result4=InsertResult(combined,result2->node); |
1052 | |
1053 | result4->node=result2->node; |
1054 | } |
1055 | |
1056 | result4->quickest=result2->quickest; |
1057 | result4->quickest.distance+=result3->quickest.distance; |
1058 | result4->quickest.duration+=result3->quickest.duration; |
1059 | |
1060 | if(result2->quickest.next) |
1061 | result2=FindResult(results2,result2->quickest.next); |
1062 | else |
1063 | result2=NULL; |
1064 | } |
1065 | while(result2); |
1066 | |
1067 | FreeResultsList(results2); |
1068 | |
1069 | result1=FindResult(results,result1->quickest.next); |
1070 | |
1071 | result3=result4; |
1072 | } |
1073 | else |
1074 | result1=NULL; |
1075 | } |
1076 | while(result1); |
1077 | |
1078 | /* Now print out the result normally */ |
1079 | |
1080 | print_progress=1; |
1081 | |
1082 | return(combined); |
1083 | } |
1084 | |
1085 | |
1086 | /*++++++++++++++++++++++++++++++++++++++ |
1087 | Find all routes from a specified node to any node in the specified list that follows a certain type of way. |
1088 | |
1089 | Results *FindRoutesWay Returns a set of results. |
1090 | |
1091 | Nodes *nodes The set of nodes to use. |
1092 | |
1093 | Segments *segments The set of segments to use. |
1094 | |
1095 | Ways *ways The set of ways to use. |
1096 | |
1097 | node_t start The start node. |
1098 | |
1099 | Nodes *finish The finishing nodes. |
1100 | |
1101 | Way *match The way that the route must match. |
1102 | |
1103 | int iteration The iteration number in Super-Segment generation. |
1104 | ++++++++++++++++++++++++++++++++++++++*/ |
1105 | |
1106 | Results *FindRoutesWay(Nodes *nodes,Segments *segments,Ways *ways,node_t start,Nodes *finish,Way *match,int iteration) |
1107 | { |
1108 | Results *results; |
1109 | node_t node1,node2; |
1110 | HalfResult shortest1,quickest1; |
1111 | HalfResult shortest2,quickest2; |
1112 | Result *result1,*result2; |
1113 | Segment *segment; |
1114 | Way *way; |
1115 | |
1116 | /* Insert the first node into the queue */ |
1117 | |
1118 | results=NewResultsList(); |
1119 | |
1120 | result1=InsertResult(results,start); |
1121 | |
1122 | result1->node=start; |
1123 | result1->shortest.prev=0; |
1124 | result1->shortest.next=0; |
1125 | result1->shortest.distance=0; |
1126 | result1->shortest.duration=0; |
1127 | result1->quickest.prev=0; |
1128 | result1->quickest.next=0; |
1129 | result1->quickest.distance=0; |
1130 | result1->quickest.duration=0; |
1131 | |
1132 | insert_in_queue(results,result1); |
1133 | |
1134 | /* Loop across all nodes in the queue */ |
1135 | |
1136 | while((result1=pop_from_queue(results))) |
1137 | { |
1138 | node1=result1->node; |
1139 | shortest1=result1->shortest; |
1140 | quickest1=result1->quickest; |
1141 | |
1142 | segment=FindFirstSegment(segments,node1); |
1143 | |
1144 | while(segment) |
1145 | { |
1146 | duration_t segment_duration; |
1147 | |
1148 | if(segment->distance==INVALID_DISTANCE) |
1149 | goto endloop; |
1150 | |
1151 | node2=segment->node2; |
1152 | |
1153 | if(shortest1.prev==node2 && quickest1.prev==node2) |
1154 | goto endloop; |
1155 | |
1156 | way=FindWay(ways,segment->way); |
1157 | |
1158 | if(way->type !=match->type || |
1159 | way->allow!=match->allow || |
1160 | way->limit!=match->limit) |
1161 | goto endloop; |
1162 | |
1163 | segment_duration=0; |
1164 | |
1165 | shortest2.distance=shortest1.distance+segment->distance; |
1166 | shortest2.duration=shortest1.duration+segment_duration; |
1167 | quickest2.distance=quickest1.distance+segment->distance; |
1168 | quickest2.duration=quickest1.duration+segment_duration; |
1169 | |
1170 | result2=FindResult(results,node2); |
1171 | |
1172 | if(!result2) /* New end node */ |
1173 | { |
1174 | result2=InsertResult(results,node2); |
1175 | result2->node=node2; |
1176 | result2->shortest.prev=node1; |
1177 | result2->shortest.next=0; |
1178 | result2->shortest.distance=shortest2.distance; |
1179 | result2->shortest.duration=shortest2.duration; |
1180 | result2->quickest.prev=node1; |
1181 | result2->quickest.next=0; |
1182 | result2->quickest.distance=quickest2.distance; |
1183 | result2->quickest.duration=quickest2.duration; |
1184 | |
1185 | if(!FindNode(finish,node2)) |
1186 | insert_in_queue(results,result2); |
1187 | } |
1188 | else |
1189 | { |
1190 | if(shortest2.distance<result2->shortest.distance || |
1191 | (shortest2.distance==result2->shortest.distance && |
1192 | shortest2.duration<result2->shortest.duration)) /* New end node is shorter */ |
1193 | { |
1194 | result2->shortest.prev=node1; |
1195 | result2->shortest.distance=shortest2.distance; |
1196 | result2->shortest.duration=shortest2.duration; |
1197 | |
1198 | if(!FindNode(finish,node2)) |
1199 | insert_in_queue(results,result2); |
1200 | } |
1201 | |
1202 | if(quickest2.duration<result2->quickest.duration || |
1203 | (quickest2.duration==result2->quickest.duration && |
1204 | quickest2.distance<result2->quickest.distance)) /* New end node is quicker */ |
1205 | { |
1206 | result2->quickest.prev=node1; |
1207 | result2->quickest.distance=quickest2.distance; |
1208 | result2->quickest.duration=quickest2.duration; |
1209 | |
1210 | if(!FindNode(finish,node2)) |
1211 | insert_in_queue(results,result2); |
1212 | } |
1213 | } |
1214 | |
1215 | endloop: |
1216 | |
1217 | segment=FindNextSegment(segments,segment); |
1218 | } |
1219 | } |
1220 | |
1221 | return(results); |
1222 | } |
Properties
Name | Value |
---|---|
cvs:description | Route optimiser. |