Using a corridor search to identify locations of interest along a route

1. A method for determining locations of interest for a route, the method comprising:

accessing shape points that correspond to a route from an origin to a destination;

accessing grid information that delineates a region of geography independently of the route, wherein the grid information includes portions;

identifying a particular portion of a grid that corresponds to a shape point, wherein the particular shape point is one of the shape points that correspond to the route;

identifying locations of interest that are associated with the identified portion of the grid; and

identifying at least some of the identified locations of interest as locations of interest for the route.

2. The method of claim 1 wherein the locations of interest for the route are identified by at least identifying portions of the grid that have been redundantly identified and eliminating the redundantly identified portions of the grid such that only non-redundantly identified portions of the grid are identified as locations of interest for the route.

3. The method of claim 1 wherein identifying at least some of the identified locations of interest as locations of interest for the route comprises:

determining distances of identified locations of interest to points on the route, wherein a distance of a particular identified location to a point on the route is determined;

comparing more than one of the determined distances to a threshold distance; and

eliminating identified locations of interest when the determined distance for an identified location of interest is not within the threshold distance.

4. The method of claim 1 wherein identifying at least some of the identified locations of interest as locations of interest for the route comprises:

determining driving distances of identified locations of interest to points on the route, wherein a driving distance of a particular identified location to a point on the route is determined;

comparing more than one of the determined driving distances to a threshold driving distance; and

eliminating identified locations of interest when the determined driving distance for an identified location of interest is not within the threshold driving distance.

5. The method of claim 1 wherein:

the grid is a multiple-level grid hierarchy, and

identifying the particular portion of a grid that corresponds to a shape point comprises associating, with an accessed shape point, a spatial identifier of a portion of the multiple-level grid hierarchy, and

identifying locations of interest that are associated with the identified portion of the grid comprises identifying locations of interest that are associated with a spatial identifier of a portion of the multiple-level grid hierarchy.

6. The method of claim 5 wherein each level of the multiple-level grid hierarchy includes four quadrants.

7. The method of claim 1 wherein locations of interest are determined by an on-board vehicle navigation system.

8. The method of claim 1 further comprising displaying the identified locations of interest using a personal digital assistant.

9. The method of claim 1 further comprising displaying the identified locations of interest using an on-board navigation system.

10. The method of claim 1 wherein a location of interest is identified based on an indirect association between a location of interest and a shape point.

11. The method of claim 1 wherein a portion of the route corresponds to a longitude and latitude coordinate of a point included in the route.

12. The method of claim 1 wherein a portion of the route comprises an endpoint of a vector having a quantity and direction representing a shape of a portion of the route.

13. A computer-readable medium or propagated signal having embodied thereon a computer program configured to determine locations of interest for a route, the medium or signal comprising one or more code segments configured to:

access shape points that correspond to a route from an origin to a destination;

access grid information that delineates a region of geography independently of the route, wherein the grid information includes portions;

identify a particular portion of a grid that corresponds to a shape point, wherein the particular shape point is one of the shape points that correspond to the route;

identify locations of interest that are associated with the identified portion of the grid; and

identify at least some of the identified locations of interest as locations of interest for the route.

14. The medium of claim 13 wherein the one or more code segments are configured to identify locations of interest for the route by at least identifying portions of the grid that have been redundantly identified and eliminating the redundantly identified portions of the grid such that only non-redundantly identified portions of the grid are identified as locations of interest for the route.

15. The medium of claim 13 wherein the one or more code segments configured to identify at least some of the identified locations of interest as locations of interest for the route comprise one or more code segments configured to:

determine distances of identified locations of interest to points on the route, wherein a distance of a particular identified location to a point on the route is determined;

compare more than one of the determined distances to a threshold distance; and

eliminate identified locations of interest when the determined distance for an identified location of interest is not within the threshold distance.

16. The medium of claim 13 wherein the one or more code segments configured to identify at least some of the identified locations of interest as locations of interest for the route comprise one or more code segments configured to:

determine a driving distances of identified locations of interest to points on the route, wherein a driving distance of a particular identified location to a point on the route is determined;

compare more than one driving determined distance to a threshold driving distance; and

eliminate identified locations of interest when the determined driving distance for an identified location of interest is not within the threshold driving distance.

17. The medium of claim 13 wherein:

the grid is a multiple-level grid hierarchy, and

the one or more code segments configured to identify the particular portion of a grid that corresponds to a shape point comprise one or more code segments configured to associate, with an accessed shape point, a spatial identifier of a portion of the multiple-level grid hierarchy, and

the one or more code segments configured to identify locations of interest that are associated with the identified portion of the grid comprise one or more code segments configured to identify locations of interest that are associated with a spatial identifier of a portion of the multiple-level grid hierarchy.

18. The medium of claim 17 wherein each level of the multiple-level grid hierarchy includes four quadrants.

19. The medium of claim 13 wherein the one or more code segments are configured to identify a location of interest based on an indirect association between a location of interest and a shape point.

20. A system for determining locations of interest for a route, the system comprising a processor connected to a storage device and one or more input/output devices, wherein the processor is configured to:

access shape points that correspond to a route from an origin to a destination;

access grid information that delineates a region of geography independently of the route, wherein the grid information includes portions;

identify a particular portion of a grid that corresponds to a shape point, wherein the particular shape point is one of the shape points that correspond to the route;

identify locations of interest that are associated with the identified portion of the grid; and

identify at least some of the identified locations of interest as locations of interest for the route.

21. The system of claim 20 wherein the processor is configured to identify locations of interest for the route by at least identifying portions of the grid that have been redundantly identified and eliminating the redundantly identified portions of the grid such that only non-redundantly identified portions of the grid are identified as locations of interest for the route.

22. The system of claim 20 wherein the processor configured to identify at least some of the identified locations of interest as locations of interest for the route comprises a processor configured to:

determine distances of identified locations of interest to points on the route, wherein a distance of a particular identified location to a point on the route is determined;

compare more than one of the determined distances to a threshold distance; and

eliminate identified locations of interest when the determined distance for an identified location of interest is not within the threshold distance.

23. The system of claim 20 wherein the processor configured to identify at least some of the identified locations of interest as locations of interest for the route comprises a processor configured to:

determine driving distances of identified locations of interest to points on the route, wherein a driving distance of a particular identified location to a point on the route is determined;

compare more than one of the determined driving distances to a threshold distance; and

eliminate identified locations of interest when the determined driving distance for an identified location of interest is not within the threshold driving distance.

24. The system of claim 20 wherein:

the grid is a multiple-level grid hierarchy, and

the processor configured to identify the particular portion of a grid that corresponds to a shape point comprises a processor configured to associate, with an accessed shape point, a spatial identifier of a portion of the multiple-level grid hierarchy, and

the processor configured to identify locations of interest that are associated with a portion of the grid comprises a processor configured to identify locations of interest that are associated with a spatial identifier of a portion of the multiple-level grid hierarchy.

25. The system of claim 24 wherein each level of the multiple-level grid hierarchy includes four quadrants.

26. The system of claim 20 wherein the processor is configured to identify a location of interest is based on an indirect association between a location of interest and a shape point.

27. A method for determining locations of interest for a route, the method comprising:

accessing shape points that correspond to the route from an origin to a destination;

associating, with an accessed shape point, a spatial identifier of a portion of a multiple-level grid hierarchy that corresponds to the accessed shape point;

identifying locations of interest that are associated with the spatial identifier of the portion of the multiple-level grid hierarchy; and

identifying at least some of the identified locations of interest as locations of interest for the route.

28. The method of claim 27 wherein each level of the multiple-level grid hierarchy includes four quadrants.

29. The method of claim 27 wherein the accessed shape point comprises a longitude and latitude coordinate of a point included in the route.

30. The method of claim 27 wherein the accessed shape point comprises an endpoint of a vector having a quantity and direction representing a shape of a portion of the route.

31. The method of claim 27 wherein the locations of interest for the route are identified by at least identifying portions of the multiple-level grid hierarchy that have been redundantly identified and eliminating the redundantly identified portions of the multiple-level grid hierarchy such that only non-redundantly identified portions of the multiple-level grid hierarchy are identified as locations of interest for the route.

32. The method of claim 27 wherein identifying at least some of the identified locations of interest as locations of interest for the route comprises:

determining distances of identified locations of interest to points on the route, wherein a distance of a particular identified location to a point on the route is determined;

comparing more than one of the determined distances to a threshold distance; and

eliminating identified locations of interest when the determined distance for an identified location of interest is not within the threshold distance.

33. The method of claim 27 wherein identifying at least some of the identified locations of interest as locations of interest for the route comprises:

determining driving distances of identified locations of interest to points on the route, wherein a driving distance of a particular identified location to a point on the route is determined;

comparing more than one of the determined driving distances to a threshold driving distance; and

eliminating identified locations of interest when the determined driving distance for an identified location of interest is not within the threshold driving distance.

34. An apparatus for determining locations of interest for a route, the apparatus being configured to:

access shape points that correspond to the route from an origin to a destination;

associate, with an accessed shape point, a spatial identifier of a portion of a multiple-level grid hierarchy that corresponds to the accessed shape point;

identify locations of interest that are associated with the spatial identifier of the portion of the multiple-level grid hierarchy; and

identify at least some of the identified locations of interest as locations of interest for the route.

35. The apparatus of claim 34 wherein each level of the multiple-level grid hierarchy includes four quadrants.

36. The apparatus of claim 34 wherein the accessed shape point comprises a longitude and latitude coordinate of a point included in the route.

37. The apparatus of claim 34 wherein the accessed shape point comprises an endpoint of a vector having a quantity and direction representing a shape of a portion of the route.

38. The apparatus of claim 34 wherein the locations of interest for the route are identified by at least identifying portions of the multiple-level grid hierarchy that have been redundantly identified and eliminating the redundantly identified portions of the multiple-level grid hierarchy such that only non-redundantly identified portions of the multiple-level grid hierarchy are identified as locations of interest for the route.

39. The apparatus of claim 34 wherein the apparatus is further configured to:

determine distances of identified locations of interest to points on the route, wherein a distance of a particular identified location to a point on the route is determined;

compare more than one of the determined distances to a threshold distance; and

eliminate identified locations of interest when the determined distance for an identified location of interest is not within the threshold distance.

40. The apparatus of claim 34 wherein the apparatus is further configured to:

determine driving distances of identified locations of interest to points on the route, wherein a driving distance of a particular identified location to a point on the route is determined;

compare more than one of the driving determined distances to a threshold driving distance; and

eliminate identified locations of interest when the determined driving distance for an identified location of interest is not within the threshold driving distance.

41. A method for determining locations of interest for a route, the method comprising:

accessing grid information that delineates a region of geography independently of a route from an origin to a destination, wherein the grid information includes portions;

identifying a particular portion of a grid that corresponds to a particular portion of a route from an origin to a destination;

identifying locations of interest that are associated with the identified portion of the grid; and

identifying at least some of the identified locations of interest as locations of interest for the route.

42. The method of claim 41 wherein the particular portion of the route corresponds to a longitude and latitude coordinate of a point included in the route.

43. The method of claim 41 wherein the particular portion of the route comprises an endpoint of a vector having a quantity and direction representing a shape of a portion of the route.

44. The method of claim 41 wherein identifying locations of interest that are associated with the identified portion of the grid comprises:

identifying portions of the grid that have been redundantly identified, and

eliminating the redundantly identified portions of the grid such that locations of interest for the route are identified for only non-redundantly identified portions of the grid.

45. The method of claim 41 wherein identifying at least some of the identified locations of interest as locations of interest for the route comprises:

determining distances of identified locations of interest to a point along the route;

comparing more than one of the determined distances to a threshold distance; and

eliminating identified locations of interest when the determined distance for an identified location of interest is not within the threshold distance.

46. The method of claim 41 wherein identifying at least some of the identified locations of interest as locations of interest for the route comprises:

determining driving distances of identified locations of interest to a point along the route;

comparing more than one of the determined driving distances to a threshold driving distance; and

eliminating identified locations of interest when the determined driving distance for an identified location of interest is not within the threshold driving distance.

47. The method of claim 41 wherein:

the grid is a multiple-level grid hierarchy, and

identifying the particular portion of a grid that corresponds to a particular portion of a route comprises associating, with a particular portion of the route, a spatial identifier of a portion of the multiple-level grid hierarchy, and

identifying locations of interest that are associated with the identified portion of the grid comprises identifying locations of interest that are associated with a spatial identifier of a portion of the multiple-level grid hierarchy.

48. The method of claim 47 wherein each level of the multiple-level grid hierarchy includes four quadrants.