Point of interest search along a route with return
View Patent ↗A routing module identifies POIs that can be reached from a route with a cost less than distance m. A routing engine performs a reverse exploration on nodes in the planned route to locate POIs from which the route can be reached with a cost of less than a second cost n. POIs identified as being reachable from the route with a cost of less than m, and from which the route is reachable with a cost less than n are then further filtered to identify a subset of the POIs for which the sum of the time or distance from the route to the POI and the time or distance from the POI back to the route is less than a threshold time or distance, t.
1. A method for providing routing to a point of interest, the method comprising:
identifying a first set of points of interest, each point of interest in the first set reachable from a planned navigation route with a cost less than a first threshold cost;
identifying a second set of points of interest, the planned navigation route reachable from each point of interest in the second set with a cost less than a second threshold cost;
determining a third set of points of interest, the third set including only the points of interest in both the first and second set;
determining a fourth set of points of interest, the fourth set including only the points of interest in the third set wherein a cost to reach the point of interest from the route plus a cost to return to the route from the point of interest is less than a third threshold cost; and
displaying the fourth set of points of interest in a user interface of a navigation device.
2. The method of claim 1 wherein the third threshold cost is a driving distance.
3. The method of claim 1 wherein the third threshold cost is an estimated driving time.
4. A system for providing routing to a point of interest, comprising:
a database storing point of interest data;
a global navigation satellite system radio, adapted to determine a current location of a user;
a routing engine, coupled to the global navigation satellite system radio and the database, adapted to:
identify a first set of points of interest, each point of interest in the first set reachable from a planned navigation route inferred from the direction of travel of the user with a cost less than a first threshold cost;
identify a second set of points of interest, the planned navigation route reachable from each point of interest in the second set with a cost less than a second threshold cost;
determine a third set of points of interest, the third set including only the points of interest in both the first and second set;
determine a fourth set of points of interest, the fourth set including only the points of interest in the third set wherein a cost to reach the point of interest from the route plus a cost to return to the route from the point of interest is less than a third threshold cost; and
a user interface module, coupled to the routing engine, adapted to display one or more indicia of the distance to the point of interest.
5. The method of claim 4 wherein the global navigation satellite system radio is a GPS radio.
6. A computer program product for providing routing to a point of interest, the computer program product stored on a non-transitory computer-readable medium and including instructions adapted to cause a computer to execute steps comprising:
identifying a first set of points of interest, each point of interest in the first set reachable from a planned navigation route inferred from a direction of travel of a user with a cost less than a first threshold cost;
identifying a second set of points of interest, the planned navigation route reachable from each point of interest in the second set with a cost less than a second threshold cost;
determining a third set of points of interest, the third set including only the points of interest in both the first and second set;
determining a fourth set of points of interest, the fourth set including only the points of interest in the third set wherein a cost to reach the point of interest from the route plus a cost to return to the route from the point of interest is less than a third threshold cost; and
displaying the fourth set of points of interest in a user interface of a navigation device.
7. A computer-implemented method for providing routing to a point of interest, the method comprising:
identifying, for each point of interest in a first set of points of interest, a cost to reach the point of interest from a navigation route inferred from a direction of travel of the user without a user input destination and a cost to return to the navigation route from the point of interest;
determining, for each point of interest in the first set of points of interest, a detour cost for the point of interest by combining the cost to reach the point of interest from the navigation route and the cost to return to the navigation route from the point of interest;
identifying a second set of points of interest from points of interest in the first set of points of interest that have a detour cost less than a maximum detour cost;
displaying the second set of points of interest in a user interface of a navigation device.
8. The method of claim 7 , wherein the inferred navigation route is based in part on a prediction score determined by tracked user behavior.
9. The method of claim 7 , wherein the detour cost is measured in estimated driving time.
10. The method of claim 7 , wherein the maximum detour cost is selected by the user, and further comprising
providing a user interface to the user for selecting the maximum detour cost;
receiving, from the user on the user interface, a selection of a maximum detour cost; and
setting the maximum detour cost based on to the selection.
11. The method of claim 10 , wherein the user selection of a maximum detour cost is a relative measurement, and setting the maximum detour cost converts the relative measurement to a numerical value.
12. The method of claim 11 , wherein the relative measurement is urgency.
13. The method of claim 7 , further comprising
receiving a selection from the user of eligible points of interest, and
wherein each point of interest in the set of identified second set of points of interest matches the user selection of eligible points of interest.
14. The method of claim 13 , wherein the selection designates eligible categories of points of interest.
15. The system of claim 4 , wherein the inferred navigation route is based in part on a prediction score determined by tracked user behavior.
16. The system of claim 4 , wherein the costs are measured in estimated driving time.
17. The system of claim 4 , wherein the third threshold cost is based on a user-selectable measurement of urgency.
18. The system of claim 4 , wherein the user interface module is further adapted to receive a user selection of eligible points of interest, and the routing engine is further adapted to exclude points of interest from the fourth set of points of interest that do not match the user selection of eligible points of interest.