Method and system for generating drive time isocontours using nested graphs

• US 8,688,379 B1
• Filed: 01/10/2012
• Issued: 04/01/2014
• Est. Priority Date: 01/10/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: McGill, James Brian
• Primary Examiner(s): CHEUNG, CALVIN K
• Application Number:
  US13/347,636
• Time in Patent Office: 812 Days
• Field of Search: 701410-416, 701/426, 701/527, 701/533
• US Class Current: 701/533
• CPC Class Codes: G01C 21/3679 Retrieval, searching and output of POI information, e.g. hotels, restaurants, shops, filling stations, parking facilities G01C21/3611 takes precedence

Abstract

Systems, methods, and machine-readable media for determining one or more possible destinations that may be reached using a hierarchy of maps. The system may be configured to receive search parameters indicating a starting point and an allotted cost and identify a set of nodes on a first level map that may be reached given the allotted cost. If further level maps in the hierarchy of maps are to be searched, the system may identify nodes in other level maps in the hierarchy of maps that may be reached given the remaining allotted cost and add the identified nodes to the set of nodes. Based on the set of nodes, the system may calculate the area that may be reached from the starting point given the allotted cost.

Claims

1. A method for determining one or more destinations that may be reached using a hierarchy of maps, the hierarchy of maps comprising a plurality of level maps, the method comprising:

receiving search parameters indicating a starting point of a trip and an allotted cost to one or more destinations, wherein the allotted cost is in a unit of measure;

selecting a starting node that corresponds to the starting point on a first level map;

identifying, using a processor, a set of nodes on the first level map wherein each node in the set of nodes has a travel cost from the starting node that is less than the allotted cost;

for each node in the set of nodes;

calculating a remaining cost for the node in the set of nodes, the remaining cost being a difference between the allotted cost and the travel cost for the node, and wherein the remaining cost is in the same unit of measure as the allotted cost,

identifying second level nodes on a second level map wherein each second level node has a travel cost from the node in the set of nodes that is less than the remaining cost, and

adding the identified second level nodes in the second level map to the set of nodes;

determining whether further levels of maps in the hierarchy of maps are to be searched;

searching, if further levels of maps are to be searched, the levels of maps for nodes that may be reached from the starting node given the allotted cost; and

determining, based on the set of nodes, a geographic area that may be reached from the starting point given the allotted cost.

2. The method of claim 1, further comprising generating the hierarchy of maps based on mapping data comprising path segments and nodes, the hierarchy of maps comprising at least two levels of maps wherein each level of map contains a different level of detail.

3. The method of claim 2, wherein the hierarchy of maps are generated based on popularity levels for the path segments in the mapping data.

4. The method of claim 2, wherein the hierarchy of maps are generated based on the types of path segments in the mapping data.

5. The method of claim 1, wherein determining the one or more destinations that may be reached from the starting point given the allotted cost comprises generating an isocontour based on the set of nodes.

6. The method of claim 5, wherein the isocontour is generated using a Delaunay tessellation.

7. The method of claim 1, wherein the first level map is not the highest level map in the hierarchy of maps.

8. The method of claim 1, wherein the second level map contains a greater level of detail than the first level map.

9. The method of claim 1, wherein the first level map is not the highest level map in the hierarchy of maps, and

wherein the first level map contains a greater level of detail than the second level map.

10. A system for determining one or more destinations that may be reached using a hierarchy of maps, the hierarchy of maps comprising plurality of levels of maps, the system comprising:

one or more processors; and

a machine-readable medium encoded with instructions executable by the one or more processors, the instructions comprising;

an interface module configured to receive search parameters indicating a starting point and an allotted cost, wherein the allotted cost is in a unit of measure;

a search module configured to;

select a starting node that corresponds to the starting point;

select a first level map in the hierarchy of maps that is includes the starting node;

identify a set of nodes on the first level map wherein each node in the set of nodes has a travel cost from the starting node that is less than the allotted cost;

determine if further level maps in the hierarchy of maps are to be searched;

a cost module configured to calculate a remaining cost for each node in the set of nodes, the remaining cost being a difference between the allotted cost and the travel cost for the node, and wherein the remaining cost is in the same unit of measure as the allotted cost; and

wherein, if further level maps are to be searched, the search module is further configured to;

identify second level nodes in a second level map wherein each second level node has a travel cost from one of the nodes in the set of nodes that is less than the remaining cost, and

add the identified second level nodes in the second level map to the set of nodes; and

an isocontour module configured to determine, based on the set of nodes, a geographic area that may be reached from the starting point given the allotted cost.

11. The system of claim 10, further comprising a map module configured to generate the hierarchy of maps based on mapping data comprising path segments and nodes, the hierarchy of maps comprising at least two levels of maps wherein each level of map contains a different level of detail.

12. The system of claim 11, wherein the hierarchy of maps are generated based on popularity levels for the path segments in the mapping data.

13. The system of claim 10, wherein the isocontour module is configured to determine the one or more destinations that may be reached from the starting point given the allotted cost by generating an isocontour based on the set of nodes.

14. The system of claim 13, wherein the isocontour is generated using a Delaunay tessellation.

15. The system of claim 10, wherein the first level map is not the highest level map in the hierarchy of maps.

16. The system of claim 10, wherein the second level map contains a greater level of detail than the first level map.

17. The system of claim 10, wherein the first level map is not the highest level map in the hierarchy of maps, and

wherein the first level map contains a greater level of detail than the second level map.

18. A non-transitory machine-readable medium comprising instructions stored therein, which when executed by a machine, cause the machine to perform operations comprising:

receiving a request to determine one or more destinations that may be reached from a starting location, the request indicating the starting location and an allotted cost, wherein the allotted cost is in a unit of measure;

selecting a starting node and a first level map in a hierarchy of maps, wherein the starting node corresponds to the starting location;

identifying a set of nodes on the first level map wherein each node in the set of nodes has a travel cost from the starting node that is less than the allotted cost;

determining if further level maps in the hierarchy of maps are to be searched;

if further level maps are to be searched;

calculating a remaining cost for each node in the set of nodes, the remaining cost being a difference between the allotted cost and the travel cost for the node, and wherein the remaining cost is in the same unit of measure as the allotted cost,

selecting a second level map in the hierarchy of maps,

identifying second level nodes on the second level map wherein each second level node has a travel cost from the starting node that is less than the remaining cost, and

adding the identified second level nodes in the second level map to the set of nodes; and

determining, based on the set of nodes, a geographic area that may be reached from the starting point given the allotted cost.

19. The non-transitory machine-readable medium of claim 18, further comprising generating the hierarchy of maps based on mapping data comprising path segments and nodes, the hierarchy of maps comprising at least two levels of maps wherein each level of map contains a different level of detail.

20. The non-transitory machine-readable medium of claim 19, wherein the hierarchy of maps are generated based on popularity levels for the path segments in the mapping data.

21. The non-transitory machine-readable medium of claim 18, wherein determining the one or more destinations that may be reached from the starting point given the allotted cost comprises generating an isocontour based on the set of nodes.

22. The non-transitory machine-readable medium of claim 18, wherein the second level map contains a greater level of detail than the first level map.