Intersection clustering in a map editor

• US 8,849,867 B1
• Filed: 07/23/2010
• Issued: 09/30/2014
• 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): Uddin, Mohammed R
• Application Number:
  US12/842,830
• Time in Patent Office: 1,530 Days
• Field of Search: 707/802, 707/694, 707/812
• US Class Current: 707/802
• CPC Class Codes: G01C 21/3632 Guidance using simplified or iconic instructions, e.g. using arrows G01C21/365 takes precedence

Abstract

A system, method, and user interface for locating intersections and adding turn restrictions to the intersections in a map editor. A map editor displays nodes and road segments in a visual map to a user. The user selects a group of nodes that represent a single physical intersection. The map editor identifies the entrance and exits to the intersection and associates each entrance with one or more of the exits. The user then selects an entrance to the intersection. The map editor displays an indicator for each exit associated with the entrance. The appearance of each indicator is based whether it is legally permitted for a vehicle to drive from the entrance, through the intersection, to the exit that corresponds to the exit indicator. The user then enters restriction information for each of the exits, which updates the appearance of the indicators.

Claims

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

storing nodes and road segments associated with the nodes in a database;

displaying, by the map editor, a map of the nodes and road segments;

receiving, by the map editor, a selection of a single physical intersection displayed in the map, wherein the single physical intersection is represented collectively by a plurality of the nodes;

automatically identifying, by the map editor, an entrance segment from the road segments displayed in the map that are connected to the plurality of the nodes, the entrance segment corresponding to an entrance to the single physical intersection represented collectively by the plurality of the nodes;

automatically identifying, by the map editor, one or more exit segments from the road segments displayed in the map that are connected to the plurality of the nodes, the one or more exit segments corresponding to exits from the single physical intersection represented collectively by the plurality of the nodes;

automatically identifying, by the map editor, a set of the exit segments that are potentially reachable from the entrance segment via the single physical intersection represented collectively by the plurality of the nodes;

storing associations between the entrance segment and the set of the exit segments into the database, wherein storing comprises instantiating data fields for storing information about whether it is legally permitted for a vehicle to drive from the entrance segment, through the intersection, to the set of the exit segments; and

displaying an exit indicator corresponding to an exit segment from the set of the exit segments, an appearance of the exit indicator based on the information stored in the data fields and indicating whether it is legally permitted for a vehicle to drive from the entrance segment, through the physical intersection, to the exit segment.

2. The method of claim 1, wherein identifying a set of the exit segments that are potentially reachable comprises applying a path-finding algorithm to determine if a path exists between the entrance segment and the exit segments.

3. The method of claim 1, wherein the entrance segment is identified from the road segments based on directions of travel of the road segments.

4. The method of claim 1, wherein the one or more exit segment are identified from the road segments based on directions of travel of the road segments.

5. The method of claim 1, further comprising:

receiving a selection of an entrance to the intersection;

displaying an entrance indicator corresponding to the entrance; and

displaying a plurality of exit indicators, each exit indicator corresponding to an exit that is associated with the entrance.

6. The method of claim 5, wherein each exit indicator from the plurality of exit indicators has an appearance based on whether it is legally permitted for a vehicle to drive from the selected entrance, through the intersection, to the exit that corresponds to the exit indicator.

7. The method of claim 5, further comprising:

receiving information indicating whether it is legally permitted for a vehicle to drive from the selected entrance, through the intersection, to one of the exits from the intersection; and

storing the information into the database.

8. A system for editing map data, comprising:

a non-transitory computer-readable storage medium storing computer code for;

storing nodes and road segments associated with the nodes in a database;

displaying, by a map editor, a map of the nodes and road segments;

receiving, by the map editor, a selection of a single physical intersection displayed in the map, wherein the single physical intersection is represented collectively by a plurality of the nodes;

automatically identifying, by the map editor, an entrance segment from the road segments displayed in the map that are connected to the plurality of the nodes, the entrance segment corresponding to an entrance to the single physical intersection represented collectively by the plurality of the nodes;

automatically identifying, by the map editor, one or more exit segments from the road segments displayed in the map that are connected to the plurality of the nodes, the one or more exit segments corresponding to exits from the single physical intersection represented collectively by the plurality of the nodes;

automatically identifying, by the map editor, a set of the exit segments that are potentially reachable from the entrance segment via the single physical intersection represented collectively by the plurality of the nodes;

storing associations between the entrance segment and the set of the exit segments into the database, wherein storing comprises instantiating data fields for storing information about whether it is legally permitted for a vehicle to drive from the entrance segment, through the intersection, to the set of the exit segments; and

displaying an exit indicator corresponding to an exit segment from the set of the exit segments, an appearance of the exit indicator based on the information stored in the data fields and indicating whether it is legally permitted for a vehicle to drive from the entrance segment, through the physical intersection, to the exit segment; and

a processor for executing the computer code.

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

store nodes and road segments associated with the nodes in a database;

display, by a map editor, a map of the nodes and road segments;

receive, by the map editor, a selection of a single physical intersection displayed in the map, wherein the single physical intersection is represented collectively by a plurality of the nodes;

automatically identify, by the map editor, an entrance segment from the road segments displayed in the map that are connected to the plurality of the nodes, the entrance segment corresponding to an entrance to the single physical intersection represented collectively by the plurality of the nodes;

automatically identify, by the map editor, one or more exit segments from the road segments displayed in the map that are connected to the plurality of the nodes, the one or more exit segments corresponding to exits from the single physical intersection represented collectively by the plurality of the nodes;

automatically identify, by the map editor, a set of the exit segments that are potentially reachable from the entrance segment via the single physical intersection represented collectively by the plurality of the nodes; and

store associations between the entrance segment and the set of the exit segments into the database, wherein storing comprises instantiating data fields for storing information about whether it is legally permitted for a vehicle to drive from the entrance segment, through the intersection, to the set of the exit segments; and

display an exit indicator corresponding to an exit segment from the set of the exit segments, an appearance of the exit indicator based on the information stored in the data fields and indicating whether it is legally permitted for a vehicle to drive from the entrance segment, through the physical intersection, to the exit segment.

10. A computer implemented method for editing turn restrictions in a map editor, comprising:

storing nodes and road segments associated with the nodes in a database, wherein a plurality of the nodes collectively represents a single physical intersection;

displaying, by the map editor, a map of the nodes and road segments;

receiving, by the map editor, a selection of an entrance to the single physical intersection represented collectively by the plurality of the nodes;

displaying, by the map editor, one or more exit indicators on the map of the nodes and road segments, the exit indicators displayed at locations on the map corresponding to exits from the single physical intersection represented collectively by the plurality of the nodes;

receiving, by the map editor, turn restriction information indicating whether it is legally permitted for a vehicle to drive from the selected entrance, through the single physical intersection represented collectively by the plurality of the nodes, to an exit from the single physical intersection represented collectively by the plurality of the nodes;

updating, by the map editor, an appearance of an exit indicator of the one or more exit indicators that corresponds to the exit responsive to the turn restriction information, the appearance of the exit indicator updated to indicate whether it is legally permitted for a vehicle to drive from the selected entrance, through the intersection, to the exit from the single physical intersection represented collectively by the plurality of the nodes; and

storing the turn restriction information into the database.

11. The method of claim 10, further comprising displaying an entrance indicator corresponding to the selected entrance.

12. The method of claim 11, wherein the entrance indicator has an appearance based on whether it is legally permitted for a vehicle to drive from the entrance, through the intersection, to each exit associated with the entrance, is known.

13. A system for editing map data, comprising:

a non-transitory computer-readable storage medium storing computer code for;

storing nodes and road segments associated with the nodes in a database, wherein a plurality of the nodes collectively represents a single physical intersection;

displaying, by a map editor, a map of the nodes and road segments;

receiving, by the map editor, a selection of an entrance to the single physical intersection represented collectively by the plurality of the nodes;

displaying, by the map editor, one or more exit indicators on the map of the nodes and road segments, the exit indicators displayed at locations on the map corresponding to exits from the single physical intersection represented collectively by the plurality of the nodes;

receiving, by the map editor, turn restriction information indicating whether it is legally permitted for a vehicle to drive from the selected entrance, through the single physical intersection represented collectively by the plurality of the nodes, to an exit from the single physical intersection represented collectively by the plurality of the nodes;

updating, by the map editor, an appearance of an exit indicator of the one or more exit indicators that corresponds to the exit responsive to the turn restriction information, the appearance of the exit indicator updated to indicate whether it is legally permitted for a vehicle to drive from the selected entrance, through the intersection, to the exit from the single physical intersection represented collectively by the plurality of the nodes; and

storing the turn restriction information into the database; and

a processor for executing the computer code.

14. A non-transitory computer-readable storage medium storing computer code, that when executed by a processor, cause the processor to:

store nodes and road segments associated with the nodes in a database, wherein a plurality of the nodes collectively represents a single physical intersection;

display, by a map editor, a map of the nodes and road segments;

receive, by the map editor, a selection of an entrance to the single physical intersection represented collectively by the plurality of the nodes;

display, by the map editor, one or more exit indicators on the map of the nodes and road segments, the exit indicators displayed at locations on the map corresponding to exits from the single physical intersection represented collectively by the plurality of the nodes;

receive, by the map editor, turn restriction information indicating whether it is legally permitted for a vehicle to drive from the selected entrance, through the single physical intersection represented collectively by the plurality of the nodes, to an exit from the single physical intersection represented collectively by the plurality of the nodes;

update, by the map editor, an appearance of an exit indicator of the one or more exit indicators that corresponds to the exit responsive to the turn restriction information, the appearance of the exit indicator updated to indicate whether it is legally permitted for a vehicle to drive from the selected entrance, through the intersection, to the exit from the single physical intersection represented collectively by the plurality of the nodes; and

store the turn restriction information into the database.

15. A non-transitory computer-readable storage medium storing a computer program executable by a processor, for producing a user interface of a map editor, the user interface comprising:

a map that includes nodes and road segments, wherein a plurality of the nodes collectively represent a single physical intersection, the road segments including both entrances and exits of the single physical intersection represented collectively by the plurality of the nodes;

an entrance indicator at a location on the map corresponding to one of the entrances to the single physical intersection represented collectively by the plurality of nodes; and

one or more exit indicators at locations on the map corresponding to the exits from the single physical intersection represented collectively by the plurality of the nodes, each exit indicator having an appearance based on whether it is legally permitted for a vehicle to drive from the entrance that corresponds to the entrance indicator, through the single physical intersection represented collectively by the plurality of the nodes, to the exit that corresponds to the exit indicator,

wherein the appearance of each exit indicator is further based on whether a vehicle is unable to reach the exit that corresponds to the exit indicator, from the entrance that corresponds to the entrance indicator, without driving through the intersection against the flow of traffic,

wherein the entrance indicator has an appearance based on whether it is legally permitted for a vehicle to drive from the entrance that corresponds to the entrance indicator, through the intersection, to each exit associated with the entrance, is known.

16. The storage medium of claim 15, wherein each exit indicator comprises an arrow that points away from the intersection.

17. The storage medium of claim 15, wherein the entrance indicator comprises an arrow that points towards the intersection.