1 /***************************************
2 $Header: /home/amb/routino/src/RCS/router.c,v 1.83 2010/06/28 17:56:26 amb Exp $
6 Part of the Routino routing software.
7 ******************/ /******************
8 This file Copyright 2008-2010 Andrew M. Bishop
10 This program is free software: you can redistribute it and/or modify
11 it under the terms of the GNU Affero General Public License as published by
12 the Free Software Foundation, either version 3 of the License, or
13 (at your option) any later version.
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU Affero General Public License for more details.
20 You should have received a copy of the GNU Affero General Public License
21 along with this program. If not, see <http://www.gnu.org/licenses/>.
22 ***************************************/
31 #include "functions.h"
32 #include "translations.h"
39 /*+ The number of waypoints allowed to be specified. +*/
42 /*+ The maximum distance from the specified point to search for a node or segment (in km). +*/
45 /*+ The minimum distance along a segment from a node to insert a fake node. (in km). +*/
46 #define MINSEGMENT 0.005
49 /*+ A set of fake segments to allow start/finish in the middle of a segment. +*/
50 static Segment fake_segments[2*NWAYPOINTS];
52 /*+ A set of fake node latitudes and longitudes. +*/
53 static double point_lon[NWAYPOINTS+1],point_lat[NWAYPOINTS+1];
55 /*+ The option not to print any progress information. +*/
58 /*+ The options to select the format of the output. +*/
59 int option_html=0,option_gpx_track=0,option_gpx_route=0,option_text=0,option_text_all=0,option_none=0;
61 /*+ The option to calculate the quickest route insted of the shortest. +*/
62 int option_quickest=0;
67 static void print_usage(int detail);
70 /*++++++++++++++++++++++++++++++++++++++
71 The main program for the router.
72 ++++++++++++++++++++++++++++++++++++++*/
74 int main(int argc,char** argv)
77 Segments *OSMSegments;
79 Results *results[NWAYPOINTS+1]={NULL};
80 int point_used[NWAYPOINTS+1]={0};
81 int help_profile=0,help_profile_xml=0,help_profile_json=0,help_profile_pl=0;
82 char *dirname=NULL,*prefix=NULL;
83 char *profiles=NULL,*profilename=NULL;
84 char *translations=NULL,*language=NULL;
86 Transport transport=Transport_None;
87 Profile *profile=NULL;
88 index_t start=NO_NODE,finish=NO_NODE;
91 /* Parse the command line arguments */
96 /* Get the non-routing, general program options */
98 for(arg=1;arg<argc;arg++)
100 if(!strcmp(argv[arg],"--help"))
102 else if(!strcmp(argv[arg],"--help-profile"))
104 else if(!strcmp(argv[arg],"--help-profile-xml"))
106 else if(!strcmp(argv[arg],"--help-profile-json"))
108 else if(!strcmp(argv[arg],"--help-profile-perl"))
110 else if(!strncmp(argv[arg],"--dir=",6))
111 dirname=&argv[arg][6];
112 else if(!strncmp(argv[arg],"--prefix=",9))
113 prefix=&argv[arg][9];
114 else if(!strncmp(argv[arg],"--profiles=",11))
115 profiles=&argv[arg][11];
116 else if(!strncmp(argv[arg],"--translations=",15))
117 translations=&argv[arg][15];
118 else if(!strcmp(argv[arg],"--exact-nodes-only"))
120 else if(!strcmp(argv[arg],"--quiet"))
122 else if(!strcmp(argv[arg],"--output-html"))
124 else if(!strcmp(argv[arg],"--output-gpx-track"))
126 else if(!strcmp(argv[arg],"--output-gpx-route"))
128 else if(!strcmp(argv[arg],"--output-text"))
130 else if(!strcmp(argv[arg],"--output-text-all"))
132 else if(!strcmp(argv[arg],"--output-none"))
134 else if(!strncmp(argv[arg],"--profile=",10))
135 profilename=&argv[arg][10];
136 else if(!strncmp(argv[arg],"--language=",11))
137 language=&argv[arg][11];
138 else if(!strncmp(argv[arg],"--transport=",12))
140 transport=TransportType(&argv[arg][12]);
142 if(transport==Transport_None)
151 /* Load in the profiles */
153 if(transport==Transport_None)
154 transport=Transport_Motorcar;
158 if(!ExistsFile(profiles))
160 fprintf(stderr,"Error: The '--profiles' option specifies a file that does not exist.\n");
166 if(ExistsFile(FileName(dirname,prefix,"profiles.xml")))
167 profiles=FileName(dirname,prefix,"profiles.xml");
170 fprintf(stderr,"Error: The '--profiles' option was not used and the default 'profiles.xml' does not exist.\n");
175 if(profiles && ParseXMLProfiles(profiles))
177 fprintf(stderr,"Error: Cannot read the profiles in the file '%s'.\n",profiles);
183 profile=GetProfile(profilename);
187 fprintf(stderr,"Error: Cannot find a profile called '%s' in '%s'.\n",profilename,profiles);
192 profile=GetProfile(TransportName(transport));
196 profile=(Profile*)calloc(1,sizeof(Profile));
197 profile->transport=transport;
200 /* Parse the other command line arguments */
202 for(arg=1;arg<argc;arg++)
206 else if(!strcmp(argv[arg],"--shortest"))
208 else if(!strcmp(argv[arg],"--quickest"))
210 else if(isdigit(argv[arg][0]) ||
211 ((argv[arg][0]=='-' || argv[arg][0]=='+') && isdigit(argv[arg][1])))
213 for(point=1;point<=NWAYPOINTS;point++)
214 if(point_used[point]!=3)
216 if(point_used[point]==0)
218 point_lon[point]=degrees_to_radians(atof(argv[arg]));
221 else /* if(point_used[point]==1) */
223 point_lat[point]=degrees_to_radians(atof(argv[arg]));
229 else if(!strncmp(argv[arg],"--lon",5) && isdigit(argv[arg][5]))
231 char *p=&argv[arg][6];
232 while(isdigit(*p)) p++;
236 point=atoi(&argv[arg][5]);
237 if(point>NWAYPOINTS || point_used[point]&1)
240 point_lon[point]=degrees_to_radians(atof(p));
241 point_used[point]+=1;
243 else if(!strncmp(argv[arg],"--lat",5) && isdigit(argv[arg][5]))
245 char *p=&argv[arg][6];
246 while(isdigit(*p)) p++;
250 point=atoi(&argv[arg][5]);
251 if(point>NWAYPOINTS || point_used[point]&2)
254 point_lat[point]=degrees_to_radians(atof(p));
255 point_used[point]+=2;
257 else if(!strncmp(argv[arg],"--transport=",12))
258 ; /* Done this already */
259 else if(!strncmp(argv[arg],"--highway-",10))
262 char *equal=strchr(argv[arg],'=');
268 string=strcpy((char*)malloc(strlen(argv[arg])),argv[arg]+10);
269 string[equal-argv[arg]-10]=0;
271 highway=HighwayType(string);
273 if(highway==Way_Count)
276 profile->highway[highway]=atof(equal+1);
280 else if(!strncmp(argv[arg],"--speed-",8))
283 char *equal=strchr(argv[arg],'=');
289 string=strcpy((char*)malloc(strlen(argv[arg])),argv[arg]+8);
290 string[equal-argv[arg]-8]=0;
292 highway=HighwayType(string);
294 if(highway==Way_Count)
297 profile->speed[highway]=kph_to_speed(atof(equal+1));
301 else if(!strncmp(argv[arg],"--property-",11))
304 char *equal=strchr(argv[arg],'=');
310 string=strcpy((char*)malloc(strlen(argv[arg])),argv[arg]+11);
311 string[equal-argv[arg]-11]=0;
313 property=PropertyType(string);
315 if(property==Way_Count)
318 profile->props_yes[property]=atof(equal+1);
322 else if(!strncmp(argv[arg],"--oneway=",9))
323 profile->oneway=!!atoi(&argv[arg][9]);
324 else if(!strncmp(argv[arg],"--weight=",9))
325 profile->weight=tonnes_to_weight(atof(&argv[arg][9]));
326 else if(!strncmp(argv[arg],"--height=",9))
327 profile->height=metres_to_height(atof(&argv[arg][9]));
328 else if(!strncmp(argv[arg],"--width=",8))
329 profile->width=metres_to_width(atof(&argv[arg][8]));
330 else if(!strncmp(argv[arg],"--length=",9))
331 profile->length=metres_to_length(atof(&argv[arg][9]));
336 for(point=1;point<=NWAYPOINTS;point++)
337 if(point_used[point]==1 || point_used[point]==2)
342 PrintProfile(profile);
346 else if(help_profile_xml)
352 else if(help_profile_json)
358 else if(help_profile_pl)
365 /* Load in the translations */
367 if(option_html==0 && option_gpx_track==0 && option_gpx_route==0 && option_text==0 && option_text_all==0 && option_none==0)
368 option_html=option_gpx_track=option_gpx_route=option_text=option_text_all=1;
370 if(option_html || option_gpx_route || option_gpx_track)
372 if(translations && ExistsFile(translations))
374 else if(!translations && ExistsFile(FileName(dirname,prefix,"translations.xml")))
375 translations=FileName(dirname,prefix,"translations.xml");
377 if(!translations && language)
379 fprintf(stderr,"Error: Cannot use '--language' option without reading some translations.\n");
383 if(translations && ParseXMLTranslations(translations,language))
385 fprintf(stderr,"Error: Cannot read the translations in the file '%s'.\n",translations);
390 /* Load in the data - Note: No error checking because Load*List() will call exit() in case of an error. */
392 OSMNodes=LoadNodeList(FileName(dirname,prefix,"nodes.mem"));
394 OSMSegments=LoadSegmentList(FileName(dirname,prefix,"segments.mem"));
396 OSMWays=LoadWayList(FileName(dirname,prefix,"ways.mem"));
398 if(UpdateProfile(profile,OSMWays))
400 fprintf(stderr,"Error: Profile is invalid or not compatible with database.\n");
404 /* Loop through all pairs of points */
406 for(point=1;point<=NWAYPOINTS;point++)
409 distance_t distmax=km_to_distance(MAXSEARCH);
411 Segment *segment=NULL;
414 if(point_used[point]!=3)
417 /* Find the closest point */
423 finish=FindClosestNode(OSMNodes,OSMSegments,OSMWays,point_lat[point],point_lon[point],distmax,profile,&distmin);
427 distance_t dist1,dist2;
429 if((segment=FindClosestSegment(OSMNodes,OSMSegments,OSMWays,point_lat[point],point_lon[point],distmax,profile,&distmin,&node1,&node2,&dist1,&dist2)))
430 finish=CreateFakes(OSMNodes,point,segment,node1,node2,dist1,dist2);
437 fprintf(stderr,"Error: Cannot find node close to specified point %d.\n",point);
445 if(IsFakeNode(finish))
446 GetFakeLatLong(finish,&lat,&lon);
448 GetLatLong(OSMNodes,finish,&lat,&lon);
450 if(IsFakeNode(finish))
451 printf("Point %d is segment %d (node %d -> %d): %3.6f %4.6f = %2.3f km\n",point,IndexSegment(OSMSegments,segment),node1,node2,
452 radians_to_degrees(lon),radians_to_degrees(lat),distance_to_km(distmin));
454 printf("Point %d is node %d: %3.6f %4.6f = %2.3f km\n",point,finish,
455 radians_to_degrees(lon),radians_to_degrees(lat),distance_to_km(distmin));
464 /* Calculate the beginning of the route */
466 if(!IsFakeNode(start) && IsSuperNode(OSMNodes,start))
470 begin=NewResultsList(1);
474 result=InsertResult(begin,start);
480 begin=FindStartRoutes(OSMNodes,OSMSegments,OSMWays,start,profile);
484 fprintf(stderr,"Error: Cannot find initial section of route compatible with profile.\n");
489 if(FindResult(begin,finish))
491 FixForwardRoute(begin,finish);
493 results[point]=begin;
497 printf("\rRouted: Super-Nodes Checked = %d\n",begin->number);
503 Results *superresults;
505 /* Calculate the end of the route */
507 if(!IsFakeNode(finish) && IsSuperNode(OSMNodes,finish))
511 end=NewResultsList(1);
515 result=InsertResult(end,finish);
521 end=FindFinishRoutes(OSMNodes,OSMSegments,OSMWays,finish,profile);
525 fprintf(stderr,"Error: Cannot find final section of route compatible with profile.\n");
530 /* Calculate the middle of the route */
532 superresults=FindMiddleRoute(OSMNodes,OSMSegments,OSMWays,begin,end,profile);
534 FreeResultsList(begin);
535 FreeResultsList(end);
539 fprintf(stderr,"Error: Cannot find route compatible with profile.\n");
543 results[point]=CombineRoutes(superresults,OSMNodes,OSMSegments,OSMWays,profile);
545 FreeResultsList(superresults);
549 /* Print out the combined route */
552 PrintRoute(results,NWAYPOINTS,OSMNodes,OSMSegments,OSMWays,profile);
558 /*++++++++++++++++++++++++++++++++++++++
559 Create a pair of fake segments corresponding to the given segment split in two.
561 index_t CreateFakes Returns the fake node index (or a real one in special cases).
563 Nodes *nodes The set of nodes to use.
565 int point Which of the waypoints is this.
567 Segment *segment The segment to split.
569 index_t node1 The first node at the end of this segment.
571 index_t node2 The second node at the end of this segment.
573 distance_t dist1 The distance to the first node.
575 distance_t dist2 The distance to the second node.
576 ++++++++++++++++++++++++++++++++++++++*/
578 index_t CreateFakes(Nodes *nodes,int point,Segment *segment,index_t node1,index_t node2,distance_t dist1,distance_t dist2)
581 double lat1,lon1,lat2,lon2;
583 /* Check if we are actually close enough to an existing node */
585 if(dist1<km_to_distance(MINSEGMENT) && dist2>km_to_distance(MINSEGMENT))
588 if(dist2<km_to_distance(MINSEGMENT) && dist1>km_to_distance(MINSEGMENT))
591 if(dist1<km_to_distance(MINSEGMENT) && dist2<km_to_distance(MINSEGMENT))
599 /* Create the fake node */
601 fakenode=point|NODE_SUPER;
603 GetLatLong(nodes,node1,&lat1,&lon1);
604 GetLatLong(nodes,node2,&lat2,&lon2);
606 if(lat1>3 && lat2<-3)
608 else if(lat1<-3 && lat2>3)
611 point_lat[point]=lat1+(lat2-lat1)*(double)dist1/(double)(dist1+dist2);
612 point_lon[point]=lon1+(lon2-lon1)*(double)dist1/(double)(dist1+dist2);
614 if(point_lat[point]>M_PI) point_lat[point]-=2*M_PI;
616 /* Create the first fake segment */
618 fake_segments[2*point-2]=*segment;
620 if(segment->node1==node1)
621 fake_segments[2*point-2].node1=fakenode;
623 fake_segments[2*point-2].node2=fakenode;
625 fake_segments[2*point-2].distance=DISTANCE(dist1)|DISTFLAG(segment->distance);
627 /* Create the second fake segment */
629 fake_segments[2*point-1]=*segment;
631 if(segment->node1==node2)
632 fake_segments[2*point-1].node1=fakenode;
634 fake_segments[2*point-1].node2=fakenode;
636 fake_segments[2*point-1].distance=DISTANCE(dist2)|DISTFLAG(segment->distance);
642 /*++++++++++++++++++++++++++++++++++++++
643 Lookup the latitude and longitude of a fake node.
645 index_t fakenode The node to lookup.
647 double *latitude Returns the latitude
649 double *longitude Returns the longitude.
650 ++++++++++++++++++++++++++++++++++++++*/
652 void GetFakeLatLong(index_t fakenode, double *latitude,double *longitude)
654 index_t realnode=fakenode&(~NODE_SUPER);
656 *latitude =point_lat[realnode];
657 *longitude=point_lon[realnode];
661 /*++++++++++++++++++++++++++++++++++++++
662 Finds the first fake segment associated to a fake node.
664 Segment *FirstFakeSegment Returns the first fake segment.
666 index_t fakenode The node to lookup.
667 ++++++++++++++++++++++++++++++++++++++*/
669 Segment *FirstFakeSegment(index_t fakenode)
671 index_t realnode=fakenode&(~NODE_SUPER);
673 return(&fake_segments[2*realnode-2]);
677 /*++++++++++++++++++++++++++++++++++++++
678 Finds the next (there can only be two) fake segment associated to a fake node.
680 Segment *NextFakeSegment Returns the second fake segment.
682 Segment *segment The first fake segment.
684 index_t fakenode The node to lookup.
685 ++++++++++++++++++++++++++++++++++++++*/
687 Segment *NextFakeSegment(Segment *segment,index_t fakenode)
689 index_t realnode=fakenode&(~NODE_SUPER);
691 if(segment==&fake_segments[2*realnode-2])
692 return(&fake_segments[2*realnode-1]);
698 /*++++++++++++++++++++++++++++++++++++++
699 Finds the next (there can only be two) fake segment associated to a fake node.
701 Segment *ExtraFakeSegment Returns a segment between the two specified nodes if it exists.
703 index_t node The real node.
705 index_t fakenode The fake node to lookup.
706 ++++++++++++++++++++++++++++++++++++++*/
708 Segment *ExtraFakeSegment(index_t node,index_t fakenode)
710 index_t realnode=fakenode&(~NODE_SUPER);
712 if(fake_segments[2*realnode-2].node1==node || fake_segments[2*realnode-2].node2==node)
713 return(&fake_segments[2*realnode-2]);
715 if(fake_segments[2*realnode-1].node1==node || fake_segments[2*realnode-1].node2==node)
716 return(&fake_segments[2*realnode-1]);
722 /*++++++++++++++++++++++++++++++++++++++
723 Print out the usage information.
725 int detail The level of detail to use - 0 = low, 1 = high.
726 ++++++++++++++++++++++++++++++++++++++*/
728 static void print_usage(int detail)
731 "Usage: router [--help | --help-profile | --help-profile-xml |\n"
732 " --help-profile-json | --help-profile-perl ]\n"
733 " [--dir=<dirname>] [--prefix=<name>]\n"
734 " [--profiles=<filename>] [--translations=<filename>]\n"
735 " [--exact-nodes-only]\n"
737 " [--language=<lang>]\n"
739 " [--output-gpx-track] [--output-gpx-route]\n"
740 " [--output-text] [--output-text-all]\n"
742 " [--profile=<name>]\n"
743 " [--transport=<transport>]\n"
744 " [--shortest | --quickest]\n"
745 " --lon1=<longitude> --lat1=<latitude>\n"
746 " --lon2=<longitude> --lon2=<latitude>\n"
747 " [ ... --lon99=<longitude> --lon99=<latitude>]\n"
748 " [--highway-<highway>=<preference> ...]\n"
749 " [--speed-<highway>=<speed> ...]\n"
750 " [--property-<property>=<preference> ...]\n"
751 " [--oneway=(0|1)]\n"
752 " [--weight=<weight>]\n"
753 " [--height=<height>] [--width=<width>] [--length=<length>]\n");
758 "--help Prints this information.\n"
759 "--help-profile Prints the information about the selected profile.\n"
760 "--help-profile-xml Prints all loaded profiles in XML format.\n"
761 "--help-profile-json Prints all loaded profiles in JSON format.\n"
762 "--help-profile-perl Prints all loaded profiles in Perl format.\n"
764 "--dir=<dirname> The directory containing the routing database.\n"
765 "--prefix=<name> The filename prefix for the routing database.\n"
766 "--profiles=<filename> The name of the profiles (defaults to 'profiles.xml'\n"
767 " with '--dirname' and '--prefix' options).\n"
768 "--translations=<fname> The filename of the translations (defaults to\n"
769 " 'translations.xml' with '--dirname' and '--prefix').\n"
771 "--exact-nodes-only Only route between nodes (don't find closest segment).\n"
773 "--quiet Don't print any screen output when running.\n"
774 "--language=<lang> Use the translations for specified language.\n"
775 "--output-html Write an HTML description of the route.\n"
776 "--output-gpx-track Write a GPX track file with all route points.\n"
777 "--output-gpx-route Write a GPX route file with interesting junctions.\n"
778 "--output-text Write a plain text file with interesting junctions.\n"
779 "--output-text-all Write a plain test file with all route points.\n"
780 "--output-none Don't write any output files or read any translations.\n"
781 " (If no output option is given then all are written.)\n"
783 "--profile=<name> Select the loaded profile with this name.\n"
784 "--transport=<transport> Select the transport to use (selects the profile\n"
785 " named after the transport if '--profile' is not used.)\n"
787 "--shortest Find the shortest route between the waypoints.\n"
788 "--quickest Find the quickest route between the waypoints.\n"
790 "--lon<n>=<longitude> Specify the longitude of the n'th waypoint.\n"
791 "--lat<n>=<latitude> Specify the latitude of the n'th waypoint.\n"
793 " Routing preference options\n"
794 "--highway-<highway>=<preference> * preference for highway type (%%).\n"
795 "--speed-<highway>=<speed> * speed for highway type (km/h).\n"
796 "--property-<property>=<preference> * preference for proprty type (%%).\n"
797 "--oneway=(0|1) * oneway streets are to be obeyed.\n"
798 "--weight=<weight> * maximum weight limit (tonnes).\n"
799 "--height=<height> * maximum height limit (metres).\n"
800 "--width=<width> * maximum width limit (metres).\n"
801 "--length=<length> * maximum length limit (metres).\n"
803 "<transport> defaults to motorcar but can be set to:\n"
806 "<highway> can be selected from:\n"
809 "<property> can be selected from:\n"
811 TransportList(),HighwayList(),PropertyList());