Path finding in a map editor

• US 9,140,573 B2
• Filed: 07/23/2010
• Issued: 09/22/2015
• Est. Priority Date: 07/23/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Pilloff, Mark D.
• Primary Examiner(s): Sheikh, Asfand
• Assistant Examiner(s): Amsdell, Dana
• Application Number:
  US12/842,826
• Publication Number:
  US 20150153193A1
• Time in Patent Office: 1,887 Days
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3667 Display of a road map G01C21/3614 takes precedence; guidance using 3D or perspective road maps G01C21/3635

Abstract

A system and method for automatically finding a path between two selected road segments. A map editor displays road segments in a visual map to a user. The user selects a beginning segment and an ending segment from the displayed segments. The map editor then identifies the best path between these two segments by applying a path-finding algorithm. The path finding algorithm identifies the best path based on the total length of the path and the changes in attributes between adjacent road segments in the path. The path identified by the map editor is then displayed to the user.

Claims

1. A computer-implemented method for map editing in a map editor, comprising:

storing road segments in a computer database, each road segment having a length and attribute data describing features of the segment, a portion of the attribute data being incomplete;

displaying the road segments on a map;

receiving a user input selecting a first road segment from the road segments displayed on the map and receiving a user input selecting a second road segment from the road segments displayed on the map, the first road segment and the second road segment separated by one or more other road segments;

identifying a path comprising a plurality of the road segments connecting the first and second segments by minimizing a cost based upon lengths of the road segments in the path and changes in one or more attributes between adjacent ones of the road segments in the path;

displaying the identified path on the map;

receiving, responsive to displaying the identified path, a user input associating a common attribute with each of the road segments in the identified path, wherein the common attribute is at least one of a road name, speed limit, surface type, road width, one-wayness or address range; and

storing the common attribute in the computer database to modify the incomplete portion of the attribute data.

2. The method of claim 1, wherein minimizing a cost based on lengths of the road segments comprises minimizing a cost based on a total, combined length of the road segments.

3. The method of claim 1, wherein minimizing a cost based on changes in one or more attributes between adjacent ones of the road segments in the path comprises minimizing the cost based on respective changes in road name between the adjacent ones of the road segments.

4. The method of claim 1, wherein minimizing a cost based on changes in one or more attributes between adjacent ones of the road segments in the path comprises minimizing the cost based on respective changes angular direction between the adjacent ones of the road segments.

5. The method of claim 1, wherein minimizing a cost based on changes in one or more attributes comprises minimizing the cost based on respective changes between the adjacent ones of the road segments in at least one of the following attributes:

priority, speed information, surface type, road width, one-wayness, address ranges, and usage.

6. The method of claim 1, wherein the one or more attributes comprise numerical attributes, and a change in a numerical attribute comprises a magnitude of a difference in the numerical values for the attribute between adjacent ones of the segments.

7. The method of claim 1, wherein the one or more attributes comprise categorical attributes, and a change in a categorical attribute comprises a Boolean value indicating the change in the categorical attribute between adjacent ones of the segments.

17. The method of claim 1, wherein the common attribute associated with each of the road segments in the identified path is the road name.

8. The method of 1, wherein minimizing a cost based upon lengths of the road segments in the path and changes in the one or more attributes between adjacent ones of the road segments in the path comprises minimizing a cost function based upon angular changes in direction between adjacent ones of the road segments that have different names, wherein angular changes between adjacent ones of the road segments having a common name do not affect the cost.

9. A non-transitory computer-readable medium storing instructions, the instructions when executed by a processor cause the processor to:

store road segments in a computer database, each road segment having a length and attribute data describing features of the segment, a portion of the attribute data being incomplete;

display the road segments on a map;

receive a user input selecting a first road segment from the road segments displayed on the map and receiving a user input selecting a second road segment from the road segments displayed on the map, the first road segment and the second road segment separated by one or more other road segments;

identify a path comprising a plurality of the road segments connecting the first and second segments by minimizing a cost based upon lengths of the road segments in the path and changes in one or more attributes between adjacent ones of the road segments in the path;

display the identified path on the map;

receive, responsive to displaying the identified path, a user input associating a common attribute with each of the road segments in the identified path, wherein the common attribute is at least one of a road name, speed limit, surface type, road width, one-wayness or address range; and

store the common attribute in the computer database to modify the incomplete portion of the attribute data.

10. A computer system for editing map data, comprising:

a processor; and

a non-transitory computer readable medium storing instructions, the instructions when executed by the processor cause the processor to;

store road segments in a computer database, each road segment having a length and attribute data describing features of the segment, a portion of the attribute data being incomplete;

display the road segments on a map;

receive a user input selecting a first road segment from the road segments displayed on the map and receiving a user input selecting a second road segment from the road segments displayed on the map, the first road segment and the second road segment separated by one or more other road segments;

identify a path comprising a plurality of the road segments connecting the first and second segments by minimizing a cost based upon lengths of the road segments in the path and changes in one or more attributes between adjacent ones of the road segments in the path;

receive, responsive to displaying the identified path, a user input associating a common attribute with each of the road segments in the identified path, wherein the common attribute is at least one of a road name, speed limit, surface type, road width, one-wayness or address range; and

store the common attribute in the computer database to modify the incomplete portion of the attribute data.

11. A computer-implemented method for map editing in a map editor, comprising:

storing nodes and road segments in a computer database, each road segment having a length and attribute data describing features of the segment, a portion of the attribute data being incomplete;

displaying the nodes and road segments on a map;

receiving a user input selecting a first node from the nodes displayed on the map and receiving a user input selecting a second node from the nodes displayed on the map, the first node and the second node separated by one or more of the road segments;

identifying a path comprising a plurality of the road segments connecting the first and second nodes by minimizing a cost based upon lengths of the road segments in the path and changes in one or more attributes between adjacent ones of the road segments in the path;

displaying the identified path on the map;

receiving, responsive to displaying the identified path, a user input associating a common attribute with each of the road segments in the identified path, wherein the common attribute is at least one of a road name, speed limit, surface type, road width, one-wayness or address range; and

storing the common attribute in the computer database to modify the incomplete portion of the attribute data.

12. The method of claim 11, wherein minimizing a cost based on changes in one or more attributes between adjacent ones of the road segments in the path comprises minimizing the cost based on respective changes in road name between the adjacent ones of the road segments.

13. The method of claim 11, wherein minimizing a cost based on changes in one or more attributes between adjacent ones of the road segments in the path comprises minimizing the cost based on respective changes in angular direction between the adjacent ones of the road segments.

18. The method of claim 11, wherein the common attribute associated with each of the road segments in the identified path is the road name.

14. The method of 11, wherein minimizing a cost based upon lengths of the road segments in the path and changes in the one or more attributes between adjacent ones of the road segments in the path comprises minimizing a cost function based upon angular changes in direction between the adjacent ones of the road segments that have different names, wherein angular changes between adjacent ones of the road segments having a common name do not affect the cost.

15. A non-transitory computer-readable medium storing instructions, the instructions when executed by a processor cause the processor to:

store nodes and road segments in a computer database, each road segment having a length and attribute data describing features of the segment, a portion of the attribute data being incomplete;

display the nodes and road segments on a map;

receive a user input selecting a first node from the nodes displayed on the map and receiving a user input selecting a second node from the nodes displayed on the map, the first node and the second node separated by one or more of the road segments;

identify a path comprising a plurality of the road segments connecting the first and second nodes by minimizing a cost based upon lengths of the road segments in the path and changes in one or more attributes between adjacent ones of the road segments in the path;

display the identified path on the map;

receive, responsive to displaying the identified path, a user input associating a common attribute with each of the road segments in the identified path, wherein the common attribute is at least one of a road name, speed limit, surface type, road width, one-wayness or address range; and

store the common attribute in the computer database to modify the incomplete portion of the attribute data.

16. A computer system for editing map data, comprising:

a processor; and

a non-transitory computer readable medium storing instructions, the instructions when executed by the processor cause the processor to;

store nodes and road segments in a computer database, each road segment having a length and attribute data describing features of the segment, a portion of the attribute data being incomplete;

display the nodes and road segments on a map;

receive a user input selecting a first node from the nodes displayed on the map and receiving a user input selecting a second node from the nodes displayed on the map, the first node and the second node separated by one or more of the road segments;

identify a path comprising a plurality of the road segments connecting the first and second nodes by minimizing a cost based upon lengths of the road segments in the path and changes in one or more attributes between adjacent ones of the road segments in the path;

display the identified path on the map;

receive, responsive to displaying the identified path, a user input associating a common attribute with each of the road segments in the identified path, wherein the common attribute is at least one of a road name, speed limit, surface type, road width, one-wayness or address range; and

store the common attribute in the computer database to modify the incomplete portion of the attribute data.