Systems and methods for improved generation of textual directions based on positional information

• US 8,406,997 B2
• Filed: 07/15/2009
• Issued: 03/26/2013
• Est. Priority Date: 07/15/2009
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: MapQuest, Inc. (Apollo Global Management, Inc.)
• Inventors: Nesbitt, David W.
• Primary Examiner(s): Nguyen, Kim T
• Application Number:
  US12/458,545
• Publication Number:
  US 20110015860A1
• Time in Patent Office: 1,350 Days
• Field of Search: 701/400, 701/408, 701/410, 701/418, 701/421
• US Class Current: 701/410
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01C 21/3626 Details of the output of route guidance instructions traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968

Abstract

Systems and methods are provided for providing improved generation of textual directions based on positional information. In an implementation, textual directions for traversing a path are generated based on positional information associated with the path. According to a method, positional information that specifies a longitude and latitude at a plurality of times is received and processed to generate a routing graph. The generated routing graph includes nodes and route links that connect the plurality of nodes. Textual directions are generated for traversing a path associated with the positional data, based in part on link information associated with the links of the generated routing graph.

Claims

1. A computer-implemented method for generating textual directions based on positional data, the method comprising the following steps, performed by one or more processors:

receiving positional information comprising a plurality of positional data elements, the plurality of positional data elements specifying corresponding longitudes and latitudes at corresponding ones of a plurality of times;

processing the received information to generate a routing graph, the routing graph comprising a plurality of nodes and one or more route links that connect the nodes, the one or more route links being associated with corresponding link information, wherein the processing comprises;

identifying, from the received information, a first data element and a second data element, the time specified by the first data element being subsequent to the time specified by the second data element;

selecting a first road corresponding to the longitude and latitude specified by the first data element, and a second road corresponding to the longitude and latitude specified by the second data element;

determining whether the first and second roads correspond to a common route link, based on at least a portion of the link information; and

constructing a portion of the routing graph that includes the common route link, when the first and second roads correspond to the common route link; and

generating, based on the corresponding link information, textual directions for traversing a path representative of the routing graph.

2. The method of claim 1, wherein the processing further comprises:

correlating the first and second roads with stored information to identify first and second route links associated with corresponding ones of the first and second roads;

determining whether the first road intersects the second road; and

constructing a portion of the routing graph that includes the identified route links when the first and second roads intersect, the identified route links being connected within the routing graph by a corresponding one of the nodes.

3. The method of claim 2, wherein the correlating comprises:

accessing the link information associated with the identified route links, the link information comprising connectivity information.

4. The method of claim 3, wherein the determining comprises:

processing the connectivity information associated with the identified route links to determine whether the first and second roads intersect.

5. The method of claim 2, wherein the determining comprises:

determining that the first and second roads are directly connected when the first and second roads are associated with the same route link.

6. The method of claim 2, wherein correlating comprises:

identifying the route link associated with the second road based on a travel direction associated with the second position.

7. The method of claim 2, further comprising:

discarding the second data element when the first and second roads are not directly connected;

identifying an additional data element from the received positional information; and

selecting a second road associated with the additional data element.

8. The method of claim 2, wherein one or more of the first data element and the second data element are representative of a subset of the plurality of positional data elements.

9. The method of claim 8, further comprising:

reducing a size of the subset represented by the second data element when the first and second roads are not directly connected;

identifying an additional data element that represents the reduced subset; and

selecting a second road associated with the additional data element representative of the reduced subset.

10. The method of claim 1, further comprising:

identifying, from the received positional information, a plurality of first positional data elements and a first road corresponding to positions associated with the plurality of first data elements;

selecting a set of candidate roads that could intersect the first road along a travel direction of the first road;

determining whether a shape of a candidate road of the selected set is proximate to a position associated with a second data element in the received positional information; and

constructing a portion of the routing graph that includes route links associated with first road and the candidate road when the shape of the candidate road is proximate to the position associated with the second positional data element.

11. An apparatus, comprising:

a storage device; and

a processor coupled to the storage device, wherein the storage device stores a program for controlling the processor, and wherein the processor, being operative with the program, is configured to;

receive positional information comprising a plurality of positional data elements, the plurality of positional data elements specifying corresponding longitudes and latitudes at corresponding ones of a plurality of times;

process the received information to generate a routing graph, the routing graph comprising a plurality of nodes and one or more route links that connect the nodes, the one or more route links being associated with corresponding link information, the processor being further configured to;

identify, from the received information, a first data element and a second data element, the time specified by the first data element being subsequent to the time specified by the second data element;

select a first road corresponding to the longitude and latitude specified by the first data element, and a second road corresponding to the longitude and latitude specified by the second data element;

determine that the first and second roads correspond to a common route link, based on at least a portion of the link information; and

construct a portion of the routing graph that includes the common route link, when the first and second roads correspond to the common route link; and

generate, based on the corresponding link information, textual directions for traversing a path representative of the routing graph.

12. The apparatus of claim 11, wherein the processor configured to process is further configured to:

correlate the first and second roads with stored information to identify first and second route links associated with corresponding ones of the first and second roads;

determine whether the first road intersects the second road; and

construct a portion of the routing graph that includes the identified route links when the first and second roads intersect, the identified route links being connected within the routing graph by a corresponding one of the nodes.

13. The apparatus of claim 12, wherein the processor configured to correlate is further configured to:

access the link information associated with the identified route links, the link information comprising connectivity information.

14. The apparatus of claim 13, wherein the processor configured to determine is further configured to:

process the connectivity information associated with the identified route links to determine whether the first and second roads intersect.

15. The apparatus of claim 12, wherein the processor configured to determine is further configured to:

determine that the first and second roads are directly connected when the first and second roads are associated with the same route link.

16. The apparatus of claim 12, wherein the processor configured to process is further configured to:

discard the second data element when the first and second roads are not directly connected;

identify an additional data element from the received positional information; and

select a second road associated with the additional data element.

17. The apparatus of claim 12, wherein one or more of the first data element and the second data element are representative of a subset of the plurality of positional data elements.

18. The apparatus of claim 17, wherein the processor configured to process is further configured to:

reduce a size of the subset represented by the second data element when the first and second roads are not directly connected;

identify an additional data element that represents the reduced subset; and

select a second road associated with the additional data element representative of the reduced subset.

19. The apparatus of claim 11, wherein the processor configured to process is further configured to:

identify, from the received positional information, a plurality of first positional data elements and a first road corresponding positions associated with the plurality of first data elements;

select a set of candidate roads that could intersect the first road along a travel direction of the first road;

determining whether a shape of a candidate road of the selected set is proximate to a position associated with a second data element in the received positional information; and

constructing a portion of the routing graph that includes route links associated with first road and the candidate road when the shape of the candidate road is proximate to the position associated with the second positional data element.

20. A tangible, non-transitory computer-readable medium storing instructions that, when executed by a processor, perform a method for generating textual directions based on positional data, the method comprising the steps of:

receiving positional information comprising a plurality of positional data elements, the plurality of positional data elements specifying corresponding longitudes and latitudes at corresponding ones of a plurality of times;

processing the received information to generate a routing graph, the routing graph comprising a plurality of nodes and one or more route links that connect the nodes, the one or more route links being associated with corresponding link information, wherein the processing comprises;

identifying, from the received information, a first data element and a second data element, the time specified by the first data element being subsequent to the time specified by the second data element;

selecting a first road corresponding to the longitude and latitude specified by the first data element, and a second road corresponding to the longitude and latitude specified by the second data element;

determining that the first and second roads correspond to a common route link, based on at least a portion of the link information; and

constructing a portion of the routing graph that includes the common route link, when the first and second roads correspond to the common route link; and

generating, based on the corresponding link information, textual directions for traversing a path representative of the routing graph.

21. The computer-readable medium of claim 20, wherein the processing further comprises:

correlate the first and second roads with stored information to identify first and second route links associated with corresponding ones of the first and second roads;

determine whether the first road intersects the second road; and

construct a portion of the routing graph that includes the identified route links when the first and second roads intersect, the identified route links being connected within the routing graph by a corresponding node.

22. The computer-readable medium of claim 21, wherein the determining comprises:

determining that the first and second roads are directly connected when the first and second roads are associated with the same route link.

23. The computer-readable medium of claim 21, wherein processing further comprises:

discarding the second data element when the first and second roads are not directly connected;

identifying an additional data element from the received positional information; and

selecting a second road associated with the additional data element.

24. The computer-readable medium of claim 21, wherein one or more of the first data element and the second data element are representative of a subset of the plurality of positional data elements.

25. The computer-readable medium of claim 24, wherein processing further comprises:

reducing a size of the subset represented by the second data element when the first and second roads are not directly connected;

identifying an additional data element that represents the reduced subset; and

selecting a second road associated with the additional data element representative of the reduced subset.

26. The computer-readable medium of claim 20, wherein the correlating comprises:

accessing the link information associated with the identified route links, the link information comprising connectivity information.

27. The computer-readable medium of claim 26, wherein the determining comprises:

processing the connectivity information associated with the identified route links to determine whether the first and second roads intersect.

28. The computer-readable medium of claim 20, wherein the processing further comprises:

identifying, from the received positional information, a plurality of first positional data elements and a first road corresponding positions associated with the plurality of first data elements;

selecting a set of candidate roads that could intersect the first road along a travel direction of the first road;

determining whether a shape of a candidate road of the selected set is proximate to a position associated with a second data element in the received positional information; and

constructing a portion of the routing graph that includes route links associated with first road and the candidate road when the shape of the candidate road is proximate to the position associated with the second positional data element.