Point of interest search along a route

Abstract

A system includes a GPS module, user interface module, database and routing engine. To find nearby POIs in one embodiment the routing engine identifies POIs in the database located within a threshold distance from the planned route in Euclidean distance. The routing engine filters the results by exploring the road network to determine whether each of the POIs is within the threshold distance of the route in driving distance. The filtering may include exploring outward from the POI, until all roads within the threshold distance are explored or the route is reached; alternatively, distance to the POIs is checked by exploring outward from the route until all roads within the threshold distance of the route have been exposed. For those POIs reached in the exploration, the nearest point on the route and the distance to that point are known. Similar searches are performed based on driving time rather than distance.

What is claimed is: 
     
         1 . A method comprising:
 determining, by one or more processors, a current location of a computing device using GPS signals, the computing device travelling along a route;   for each of a plurality of points of interest:
 determining, by the one or more processors, a route departure point from which to deviate from the route to travel to the point of interest; 
 determining, by the one or more processors, a first distance to travel from the current location to the route departure point and a second distance to travel from the route departure point to the point of interest; 
 determining, by the one or more processors, a total distance by aggregating the first distance and the second distance; and 
   causing the computing device to present, in a user interface, information corresponding to the plurality of points of interest sorted according to the total distances.   
     
     
         2 . The method of  claim 1 , further comprising:
 receiving, by the one or more processors, a request by a user of the computing device via the user interface,   wherein causing the computing device to present the information is responsive to receiving the request.   
     
     
         3 . The method of  claim 2 , wherein the request is associated with a point of interest category, wherein the plurality of points of interest is associated with the point of interest category. 
     
     
         4 . The method of  claim 1 , wherein the user interface includes one or more of an “I need gas” button, an “I need a hotel” button, and an “I need food” button. 
     
     
         5 . The method of  claim 1 , wherein the first distance and the second distance are determined using Euclidean distances. 
     
     
         6 . The method of  claim 1 , wherein the first distance and the second distance are determined using driving distances along roads. 
     
     
         7 . The method of  claim 1 , wherein causing the computing device to present the information comprises:
 causing the computing device to present, in the user interface, the first distance and the second distance of each of the plurality of points of interest.   
     
     
         8 . The method of  claim 1 , wherein causing the computing device to present the information comprises:
 causing the computing device to present, in the user interface, the total distance of each of the plurality of points of interest.   
     
     
         9 . A computer program product comprising a non-transitory computer readable storage medium having instructions encoded thereon that, when executed by one or more processors, cause the one or more processors to:
 determine a current location of a computing device using GPS signals, the computing device travelling along a route;   for each of a plurality of points of interest:
 determine a route departure point from which to deviate from the route to travel to the point of interest; 
 determine a first distance to travel from the current location to the route departure point and a second distance to travel from the route departure point to the point of interest; 
 determine a total distance by aggregating the first distance and the second distance; and 
   cause the computing device to present, in a user interface, information corresponding to the plurality of points of interest sorted according to the total distances.   
     
     
         10 . The non-transitory computer readable storage medium of  claim 9 , comprising further instructions encoded thereon that, when executed by the one or more processors, cause the one or more processors to:
 receive a request by a user of the computing device via the user interface,   wherein causing the computing device to present the information is responsive to receiving the request.   
     
     
         11 . The non-transitory computer readable storage medium of  claim 10 , wherein the request is associated with a point of interest category, wherein the plurality of points of interest is associated with the point of interest category. 
     
     
         12 . The non-transitory computer readable storage medium of  claim 9 , wherein the user interface includes one or more of an “I need gas” button, an “I need a hotel” button, and an “I need food” button. 
     
     
         13 . The non-transitory computer readable storage medium of  claim 9 , wherein the first distance and the second distance are determined using Euclidean distances. 
     
     
         14 . The non-transitory computer readable storage medium of  claim 9 , wherein the first distance and the second distance are determined using driving distances along roads. 
     
     
         15 . The non-transitory computer readable storage medium of  claim 9 , wherein cause the computing device to present the information comprises:
 cause the computing device to present, in the user interface, the first distance and the second distance of each of the plurality of points of interest.   
     
     
         16 . The non-transitory computer readable storage medium of  claim 9 , wherein cause the computing device to present the information comprises:
 cause the computing device to present, in the user interface, the total distance of each of the plurality of points of interest.   
     
     
         17 . A system for providing navigation information, the system comprising:
 one or more processors;   a global navigation satellite system radio, adapted to determine a current location of a computing device travelling along a route;   a routing engine, coupled to the global navigation satellite system and executed by the one or more processors, adapted to:
 for each of a plurality of points of interest:
 determine a route departure point from which to deviate from the route to travel to the point of interest; 
 determine a first distance to travel from the current location to the route departure point and a second distance to travel from the route departure point to the point of interest; 
 determine a total distance by aggregating the first distance and the second distance; and 
 
 cause the computing device to present, in a user interface, information corresponding to the plurality of points of interest sorted according to the total distances. 
   
     
     
         18 . The system of  claim 17 , wherein the routing engine is further adapted to:
 receive a request by a user of the computing device via the user interface,   wherein causing the computing device to present the information is responsive to receiving the request.   
     
     
         19 . The system of  claim 18 , wherein the request is associated with a point of interest category, wherein the plurality of points of interest is associated with the point of interest category. 
     
     
         20 . The system of  claim 17 , wherein the user interface includes one or more of an “I need gas” button, an “I need a hotel” button, and an “I need food” button.