SYSTEMS AND METHODS FOR CROSS-STREET IDENTIFICATION

• US 20100250619A1
• Filed: 03/27/2009
• Published: 09/30/2010
• Est. Priority Date: 03/27/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Hulubei, Tudor
• Granted Patent: US 8,176,045 B2
• Time in Patent Office: Days
• US Class Current: 707/803
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: Y10S 707/92 Navigation

Abstract

Aspects of the invention relate to the use of electronic maps and providing information about intersecting streets. A given region of interest on a map may include any number of features. Features of interest, including road segments and intersections, can be filtered to remove non-street data. The results may be analyzed according to individual street segments. Each segment may be identified by a feature ID, and the relationship each segment has with a given intersection is analyzed. Thus, the direction of a segment into or out of an intersection is determined, along with the physical locations of the beginning and end of the segment. This information is used to provide robust map information that may be displayed to a user. Heuristics can be applied to the map information to provide coherent address or direction information to the user for a given point of interest.

Claims

1. A method, comprising:

identifying a plurality of streets and at least one intersection thereof, the plurality of streets and the at least one intersection being associated with a region of interest of a map, each of the plurality of streets including at least one road segment;

extracting features from a map database for each road segment and the at least one intersection;

creating, for each intersection of interest, a set of road segments connected to that intersection and a relationship of each road segment in the set to that intersection, including whether a given road segment begins or ends at the intersection; and

storing the set of road segments and their relationships to the intersection of interest in a cross-street database.

2. The method of claim 1, further comprising:

keying each feature extracted from the map database with a corresponding ID;

identifying all road segments associated with a particular intersection; and

identifying the relationship between each road segment and the particular intersection.

3. The method of claim 2, further comprising:

generating a skeleton of each road segment keyed by the corresponding ID;

matching individual road segments with respective ones of the skeletons; and

generating a full representation of each road segment.

4. The method of claim 1, further comprising:

retrieving the set of road segments and their relationships to the intersection of interest from the cross-street database;

applying a heuristic to the retrieved set; and

displaying a geographical map on a display to show at least some of the road segments based upon the heuristic.

5. The method of claim 4, wherein the heuristic generates a street identification based upon at least one of how important each road segment is and an angle of impingement of each road segment on a street of interest.

6. The method of claim 1, further comprising:

identifying all cross-streets of the intersection of interest by road segment IDs, each cross street comprising at least one of the road segments;

retrieving original features of interest from the map database;

filtering non-road segments from the original features of interest to obtain a set of filtered road segments;

matching each cross-street of the intersection of interest with the filtered road segments; and

storing the matched cross-streets in the cross-street database.

7. The method of claim 6, wherein retrieving the original features, filtering the non-road segments and matching each cross-street are done by road segment ID.

8. The method of claim 6, further comprising:

retrieving selected matched cross-streets from the cross-street database in response to a user query;

applying a heuristic to the retrieved cross-streets to select a display option; and

displaying a geographical map on a display to identify cross-street information based upon the display option.

9. The method of claim 8, wherein the display option reports the cross-street information in increasing order of street numbers.

10. The method of claim 8, wherein the display option reports the cross-street information without mixing cardinal directions if alternative cross-streets that are on the same cardinal direction exist.

11. The method of claim 8, further comprising determining a distance between a point of interest on the geographical map and endpoints of the cross-street on which the point of interest is located.

12. The method of claim 11, wherein the display option reports a location of the point of interest in relation to the cross-street on which the point of interest is located.

13. A processing system for processing geographical map information, comprising:

at least one processor; and

memory for storing data, the memory being electrically coupled to the at least one processor;

wherein the at least one processor is configured to identify a plurality of streets and at least one intersection thereof, the plurality of streets and the at least one intersection being associated with a region of interest of a map, each of the plurality of streets including at least one road segment, to extract features from a map database for each road segment and the at least one intersection, to create, for each intersection of interest, a set of road segments connected to that intersection and a relationship of each road segment in the set to that intersection, including whether a given road segment begins or ends at the intersection, and to store the set of road segments and their relationships to the intersection of interest in a cross-street database in the memory.

14. The processing system of claim 13, wherein the at least one processor is further configured to retrieve the set of road segments and their relationships to the intersection of interest from the cross-street database, to apply a heuristic to the retrieved set, and to display a geographical map on a display to show at least some of the road segments based upon the heuristic.

15. The processing system of claim 13, wherein the at least one processor is further configured to identify all cross-streets of the intersection of interest by road segment IDs, each cross street comprising at least one of the road segments, to retrieve original features of interest from the map database, to filter non-road segments from the original features of interest to obtain a set of filtered road segments, to match each cross-street of the intersection of interest with the filtered road segments, and to store the matched cross-streets in the cross-street database.

16. The processing system of claim 13 wherein the at least one processor is further configured to retrieve selected matched cross-streets from the cross-street database in response to a user query, to apply a heuristic to the retrieved cross-streets to select a display option, and to display a geographical map on a display to identify cross-street information based upon the display option.

17. A computer-readable recording medium having instructions stored thereon, the instructions, when executed by a processor, cause the processor to perform the operations of:

identifying a plurality of streets and at least one intersection thereof, the plurality of streets and the at least one intersection being associated with a region of interest of a map, each of the plurality of streets including at least one road segment;

extracting features from a map database for each road segment and the at least one intersection;

creating, for each intersection of interest, a set of road segments connected to that intersection and a relationship of each road segment in the set to that intersection, including whether a given road segment begins or ends at the intersection; and

storing the set of road segments and their relationships to the intersection of interest in a cross-street database.