PATH FINDING IN A MAP EDITOR

• US 20150153193A1
• Filed: 07/23/2010
• Published: 06/04/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.
• Granted Patent: US 9,140,573 B2
• Time in Patent Office: 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 identifying a path between road segments in a map editor, comprising:

storing in a database a plurality of road segments, each road segment having a length and a plurality of attributes describing features of the segment;

displaying the plurality of road segments on a map;

receiving a selection of first and second road segments from the road segments displayed on the map;

identifying a path comprising a set of the road segments that connect the first and second segments by minimizing a cost based upon lengths of the road segments in the path and changes in the attributes between adjacent ones of the road segments in the path;

displaying the identified path on a map;

receiving a user input associating a common attribute with each of the road segments in the identified path, the common attribute describing a common feature of the road segments in the identified path; and

storing, into the database, the common attribute associated with each of the road segments in the identified path.

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

3. The method of claim 1, wherein the changes in attributes comprise a change in road name between adjacent road segments.

4. The method of claim 1, wherein the changes in attributes comprise a change in angular direction between adjacent road segments.

5. The method of claim 1, wherein the changes in attributes comprise a change 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 attributes comprise categorical attributes and numerical attributes, and a change in a numerical attribute comprises a magnitude of a difference in the numerical values for the attribute between adjacent segments.

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

8. The method of claim 1, further comprising:

receiving a user input associating a common attribute with each of the road segments in the identified path, and;

storing the attribute in the database.

18. The method of claim 1, wherein the common attribute describes a road name that is common to the road segments in the identified path.

19. The method of claim 1, wherein the common attribute describes a speed limit that is common to the road segments in the identified path.

20. The method of claim 1, wherein the common attribute describes a road priority that is common to the road segments in the identified path.

9. The method of 1, wherein minimizing a cost based upon lengths of the connected road segments in the path and changes in the attributes between adjacent road segments in the path comprises minimizing a cost function based upon angular changes in direction between adjacent road segments that have different names for the adjacent road segments.

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

store in a database a plurality of road segments, each road segment having a length and a plurality of attributes describing features of the segment;

display the plurality of road segments on a map;

receive a selection of a first and second road segments displayed on the map;

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

display the identified path on a map.

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

a database interface module configured to store in a database a plurality of road segments, each road segment having a length and a plurality of attributes describing features of the segment;

a segment selection module configured to;

display the plurality of road segments on a map; and

receive a selection of a first and second road segments displayed on the map;

a path identification module configured to identify a path comprising a plurality of connected road segments between the first and second segments by minimizing a cost based upon lengths of the connected road segments in the path and changes in the attributes between adjacent road segments in the path; and

a path display module configured to display the identified path on a map.

12. A computer-implemented method for identifying a path between nodes in a map editor, comprising:

storing in a database a plurality of nodes and road segments, each road segment having a length and a plurality of attributes describing features of the segment;

displaying the plurality of nodes and road segments on a map;

receiving a selection of a first and second nodes displayed on the map;

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

displaying the identified path on a map.

13. The method of claim 12, wherein the changes in attributes comprise a change in road name between adjacent road segments.

14. The method of claim 12, wherein the changes in attributes comprise a change in angular direction between adjacent road segments.

15. The method of 12, wherein minimizing a cost based upon lengths of the connected road segments in the path and changes in the attributes between adjacent road segments in the path comprises minimizing a cost function based upon angular changes in direction between adjacent road segments that have different names for the adjacent road segments.

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

store in a database a plurality of nodes and road segments, each road segment having a length and a plurality of attributes describing features of the segment;

display the plurality of nodes and road segments on a map;

receive a selection of a first and second road nodes displayed on the map;

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

display the identified path on a map.

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

a database interface module configured to store in a database a plurality of nodes and road segments, each road segment having a length and a plurality of attributes describing features of the segment;

a selection module configured to;

display the plurality of nodes and road segments on a map; and

receive a selection of a first and second nodes displayed on the map;

a path identification module configured to identify a path comprising a plurality of connected road segments between the first and second nodes by minimizing a cost based upon lengths of the connected road segments in the path and changes in the attributes between adjacent road segments in the path; and

a path display module configured to display the identified path on a map.