Using a corridor search to identify locations of interest along a travel route
View Patent ↗A corridor search process is used to identify locations of interest along a travel route. The corridor search process identifies locations of interest along a travel route by using a grid search process that first identifies shape points that correspond to the travel route. Each shape point is associated with a portion of a grid system used to delineate a region of geography through which the route traverses. The portions of the grid system correspond to a corridor along the travel route. References to redundant portions of the grid system are removed, and locations of interest are identified based on an association between a location of interest with a particular portion of the grid system.
1. A method for determining a location of interest, the method comprising:
accessing data describing a hierarchy of subsections that cover a region, including:
accessing a first level in the hierarchy that is divided into one or more first subsections that cover the region,
accessing a second level in the hierarchy that is divided into two or more second subsections that also cover the region, wherein the number of second subsections used to cover the region exceed the number of first subsections used to cover the region, and
accessing at least one of the first subsections on the first level and at least one of the second subsections on the second level that cover at least partially overlapping portions of the region;
selecting one or more subsections in the hierarchy of subsections for which locations of interest are to be identified; and
identifying one or more locations of interest associated with the selected one or more subsections.
2. The method of claim 1 wherein identifying one or more locations of interest associated with the selected one or more subsections comprises 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.
3. The method of claim 1 wherein identifying one or more locations of interest associated with the selected one or more subsections comprises:
determining distances of identified locations of interest to points within the selected one or more subsections;
comparing 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 3 wherein the threshold distance is user-configurable.
5. The method of claim 3 wherein the threshold distance is program-configurable and differs based on context.
6. The method of claim 1 wherein identifying one or more locations of interest associated with the selected one or more subsections comprises:
determining driving distances of identified locations of interest to points within the selected one or more subsections;
comparing 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.
7. The method of claim 6 wherein the threshold distance is user-configurable.
8. The method of claim 6 wherein the threshold distance is program-configurable and differs based on context.
9. The method of claim 1 further comprising:
associating, with the selected one or more subsections, a spatial identifier of a portion of the hierarchy of subsections, and wherein
identifying one or more locations of interest associated with the selected one or more subsections comprises identifying locations of interest that are associated with the spatial identifier of the portion of the hierarchy of subsections.
10. The method of claim 9 wherein each level of the hierarchy of subsections includes four quadrants.
11. The method of claim 1 wherein locations of interest are determined by an on-board vehicle navigation system.
12. The method of claim 1 further comprising displaying the identified locations of interest using a personal digital assistant.
13. The method of claim 1 further comprising displaying the identified locations of interest using an on-board navigation system.
14. The method of claim 1 wherein a location of interest is identified based on an indirect association between a location of interest and a subsection.
15. An apparatus for determining a location of interest, the apparatus being configured to:
access data describing a hierarchy of subsections that cover a region, the accessed data describing:
a first level in the hierarchy that is divided into one or more first subsections that cover the region,
a second level in the hierarchy that is divided into two or more second subsections that also cover the region, wherein the number of second subsections used to cover the region exceed the number of first subsections used to cover the region, and
wherein at least one of the first subsections on the first level and at least one of the second subsections on the second level cover at least partially overlapping portions of the region;
select one or more subsections in the hierarchy of subsections for which locations of interest are to be identified; and
identify one or more locations of interest associated with the selected one or more subsections.
16. The apparatus of claim 15 wherein the apparatus is further configured to identify portions of the grid that have been redundantly identified and eliminate the redundantly identified portions of the grid such that only non-redundantly identified portions of the grid are identified as locations of interest.
17. The apparatus of claim 15 wherein the apparatus is further configured to:
determine distances of identified locations of interest to points within the selected one or more subsections;
compare 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.
18. The apparatus of claim 17 wherein the threshold distance is user-configurable.
19. The apparatus of claim 17 wherein the threshold distance is program-configurable and differs based on context.
20. The apparatus of claim 15 wherein the apparatus is further configured to:
identify one or more locations of interest associated with the selected one or more subsections comprises:
determine driving distances of identified locations of interest to points within the selected one or more subsections;
compare the determined driving 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.
21. The apparatus of claim 20 wherein the threshold distance is user-configurable.
22. The apparatus of claim 20 wherein the threshold distance is program-configurable and differs based on context.
23. The apparatus of claim 15 wherein the apparatus is further configured to:
associate, with the selected one or more subsections, a spatial identifier of a portion of the hierarchy of subsections, and wherein
identify locations of interest that are associated with the spatial identifier of the portion of the hierarchy of subsections.
24. The apparatus of claim 23 wherein each level of the hierarchy of subsections includes four quadrants.
25. The apparatus of claim 15 wherein locations of interest are determined by an on-board vehicle navigation system.
26. The method of claim 15 wherein the apparatus is further configured to display the identified locations of interest using a personal digital assistant.
27. The method of claim 15 wherein the apparatus is further configured to display the identified locations of interest using an on-board navigation system.
28. The apparatus of claim 15 wherein a location of interest is identified based on an indirect association between a location of interest and a subsection.
29. An apparatus for determining a location of interest, the apparatus comprising:
means for accessing data describing a hierarchy of subsections that cover a region, including:
means for accessing a first level in the hierarchy that is divided into one or more first subsections that cover the region,
means for accessing a second level in the hierarchy that is divided into two or more second subsections that also cover the region, wherein the number of second subsections used to cover the region exceed the number of first subsections used to cover the region, and
means for accessing at least one of the first subsections on the first level and at least one of the second subsections on the second level that cover at least partially overlapping portions of the region;
means for selecting one or more subsections in the hierarchy of subsections for which locations of interest are to be identified; and
means for identifying one or more locations of interest associated with the selected one or more subsections.