Computing sign text for branches of an electronic map network

• US 6,559,865 B1
• Filed: 05/19/2000
• Issued: 05/06/2003
• Est. Priority Date: 05/21/1999
• Status: Expired due to Term

• Current Assignee: Tomtom North America Incorporated (TomTom NV)
• Original Assignee: Tele Atlas North America (TomTom NV)
• Inventors: Angwin, George T.
• Primary Examiner(s): Bayerl, Raymond J.
• Application Number:
  US09/574,114
• Time in Patent Office: 1,082 Days
• Field of Search: 345/765, 345/764, 345/853, 345/854, 345/705, 345/708, 345/711, 345/715, 345/808, 345/440, 340/990, 340/995, 340/996, 701/201, 701/202, 701/208, 701/209, 701/211
• US Class Current: 715/765
• CPC Class Codes: G01C 21/3815 Road data
• CPC Class Codes: G08G 1/00 Traffic control systems for road vehicles arrangement of road signs or traffic signals E01F9/00 ; automatic vehicle control B62D
• CPC Class Codes: G09B 29/10 Map spot or coordinate position indicators; Map reading aids optical projection apparatus per se G03B

Abstract

A method and apparatus for computing sign text for exit ramps from limited access highways of an electronic map network. First and second name lists containing names of road elements ahead of and behind respective simple and compound exit ramps are generated. Sign text for simple exit ramps is computed using a first process having the first and second name lists as inputs. Sign text for compound exit ramps is computed using a second process having the first and second name lists as inputs.

Claims

1. A method of computing sign text for branches from a carriageway of a processor readable representation of a network, the method comprising the steps of:

accessing the processor readable representation of a network;

selecting a branch of the processor readable representation of a network for which sign text is to be computed;

initializing a sign text variable;

constructing a first name list for a first road element that crosses the carriageway at a first junction;

constructing a second name list for a second road element that crosses the carriageway at a second junction;

computing sign text for selected branches of the processor readable representation of a network;

wherein the computing step further comprises the steps of;

computing sign text for a simple branch of the processor readable representation of a network using a first process; and

computing sign text for a compound branch of the processor readable representation of a network using a second process;

placing computed sign text into the sign text variable; and

outputting sign text computed for selected branches of the processor readable representation of a network.

2. The method of claim 1, wherein the first name list comprises a route identifier and a street name associated with the first road element, the first road element being located a first distance ahead of the first junction.

3. The method of claim 2, wherein the first distance is adjustable.

4. The method of claim 1, wherein the second name list comprises a route identifier and a street name associated with the second road element, the second road element being located a second distance behind the second junction.

5. The method of claim 4, wherein the second distance is adjustable.

6. The method of claim 1, wherein the processor readable representation of a network is an electronic map of roads.

7. The method of claim 1, further comprising the step of:

storing the computed sign text in a database.

8. The method of claim 7 wherein the database is linked to the processor readable representation of a network.

9. The method of claim 1, further comprising the steps of:

computing a path from an origin in the processor readable representation of a network to a destination in the processor readable representation of a network;

computing sign text for branches of the processor readable representation of a network along the path; and

using the computed sign text for respective branches to build respective maneuver instructions.

10. The method of claim 1, wherein sign text computed for selected branches of the processor readable representation of a network are outputted to an output device or a display.

11. A method of computing sign text for branches from a carriageway of a processor readable representation of a network, the method comprising the steps of:

accessing the processor readable representation of a network;

computing sign text for selected branches of the processor readable representation of a network;

wherein the computing step further comprises the steps of;

computing sign text for a simple branch of the processor readable representation of a network using a first process;

wherein the first process comprises the steps of;

determining whether a route identifier or a street name identifying a first road element connected to the simple branch at a first junction matches an entry in a first name list or a second name list;

determining whether a road class of a second road element connected to the first road element at a second junction is higher than a road class of the first road element; and

determining whether traffic exiting simple branch and continuing along the first road element proceeds in only one direction;

computing sign text for a compound branch of the processor readable representation of a network using a second process; and

outputting sign text computed for selected branches of the processor readable representation of a network.

12. A method of computing sign text for branches from a carriageway of a processor readable representation of a network, the method comprising the steps of:

accessing the processor readable representation of a network;

computing sign text for selected branches of the processor readable representation of a network;

wherein the computing step further comprises the steps of;

computing sign text for a simple branch of the processor readable representation of a network using a first process; and

computing sign text for a compound branch of the processor readable representation of a network using a second process;

wherein the compound branch comprises a fork, the fork comprising a fork handle, a left branch, and a right branch; and

wherein the second process comprises the steps of;

determining whether the left and right branches are leaf ramps;

computing sign text for the leaf ramps using the first process;

determining whether sign text is to be computed for other forks of the compound branch;

determining whether sign texts computed for the left and right branches have a common name;

placing the common name into the fork handle sign text if sign texts computed for the left and right branches are equivalent; and

placing both sign texts into the fork handle sign text if the sign texts computed for the left and right branches are not equivalent; and

outputting sign text computed for selected branches of the processor readable representation of a network.

13. The method of claim 12, further comprising the steps of:

removing duplicate names from the fork handle sign text; and

merging different versions of a same route identifier or a same street name in the fork handle sign text into a general version of the route identifier and the street name.

14. A method of determining sign text for a simple ramp of a processor readable representation of a network, the method comprising the steps of:

determining whether the simple ramp is identified by a route identifier;

determining whether a street name or the route identifier identifying a first road element, connected to the simple ramp at a first junction matches an entry in first and second name lists;

determining whether a second road element connected to the first road element at a second junction has a road class higher than that of the first road element;

determining whether traffic exiting the simple ramp and continuing along the first road element proceeds in only one direction; and

outputting sign text computed to a display.

15. The method of claim 14, wherein the processor readable representation of a network is an electronic map of roads.

16. The method of claim 14, further comprising the step of:

storing the computed sign text in a database.

17. The method of claim 14, further comprising the step of:

storing the computed sign text in the processor readable representation of a network.

18. The method of claim 14, wherein the first name list comprises a name of a route identifier or a street located a first distance ahead of the simple ramp.

19. The method of claim 18, wherein the second name list comprises a name of a route identifier or a street located a second distance behind the simple ramp.

20. The method of claim 19, wherein the first and second distances are adjustable to accommodate changes in a spacing between successive simple ramps.

21. The method of claim 14, wherein the sign text is computed in real time in conjunction with a step to determine a path in the network from an origin to a destination.

22. A method of determining sign text for a compound ramp of a processor readable representation of a network, the compound ramp comprising a fork, the fork comprising a fork handle, a left branch, and a right branch, the method comprising the steps of:

computing sign text for branches which are leaf ramps;

determining whether sign text is to be computed for other forks of the compound branch;

determining whether sign text computed for the left and right branches have a common name;

placing the common name into the fork handle sign text if the sign texts computed for the left and right branches are equivalent; and

placing both sign texts into the fork handle sign text if the sign texts computed for the left and right branches are not equivalent.

23. The method of claim 22, further comprising the steps of:

removing duplicate names from the fork handle sign text; and

merging different versions of a same route identifier or a same street name in the fork handle sign text into a general version of the route identifier and the street name.

24. The method of claim 22, wherein the left branch leads to a second fork in the compound ramp of the network.

25. The method of claim 24, wherein the right branch leads to a third fork in the compound ramp of the network.

26. A method for determining sign text of exit ramps in an electronic map of roads, the exit ramps identifying a road element from a first carriageway of a limited access road to a destination roadway, the method comprising the steps of:

selecting an exit ramp for which sign text is to be computed;

initializing a sign text variable;

constructing a first name list and a second name list;

computing sign text using a first process if the selected exit ramp is a simple ramp, the first and second name lists being inputs to the first process and the computed sign text being placed in the sign text variable;

computing sign text using a second process if the selected exit ramp is a compound ramp, the first and second name lists being inputs to the second process and the computed sign text being placed in the sign text variable; and

outputting the sign text variable to a display.

27. The method of claim 26, wherein the simple ramp begins on the first carriageway of the first limited access road and ends at a destination roadway.

28. The method of claim 27, wherein the destination roadway is a surface street and alternatively a second carriageway of a second limited access road.

29. The method of claim 26, wherein the compound exit ramp comprises a first fork, the first fork further comprising a first left branch and a first right branch.

30. The method of claim 29, wherein the first left branch is a first road element that leads to a second fork having a second left branch and a second right branch and the first right branch is a second road element that leads to a third fork having a third left branch and a third right branch.

31. The method of claim 29, wherein the first left branch is a first leaf ramp that leads to a first destination roadway and the first right branch is a second leaf ramp that leads to a second destination roadway.

32. The method of claim 26, wherein the first name list comprises a route identifier and alternatively a primary street name, the route identifier and the primary street name being associated with a first road crossing a first distance ahead of the selected exit ramp.

33. The method of claim 32, wherein the first distance is adjustable to accommodate changes in a spacing between successive exit ramps.

34. The method of claim 26, wherein the second name list comprises a route identifier and alternatively a primary street name, the route identifier and the primary street name being associated with a second road crossing a second distance behind the selected exit ramp.

35. The method of claim 34, wherein the second distance is adjustable to accommodate changes in a spacing between successive exit ramps.

36. The method of claim 26, wherein the first process comprises the steps of:

determining whether the simple ramp is identified with a route identifier;

determining whether a street name or the route identifier identified with a first road element connected to an end of the simple ramp at a first junction matches an entry in the first and second name lists;

determining whether a second road element connected to the first road element at a second junction ahead of the first junction has a higher road class than the first road element; and

determining whether traffic exiting the simple exit ramp can proceed in only one direction along the first road element.

37. The method of claim 26, wherein the compound ramp comprises a first fork comprising a first fork handle, a first left branch, and a first right branch and wherein the second process comprises the steps of:

(a) computing sign text for the branches which are leaf ramps;

(b) determining whether the sign texts computed for the left and right branches have a common name;

(c) placing the common name into the fork handle sign text if the sign texts computed for the left and right branches are equivalent;

(e) placing both sign texts into the fork handle sign text if the sign texts computed for the left and right branches are not equivalent;

(f) removing duplicate names from the fork handle sign text;

(g) merging different versions of a same route identifier or a same street name in the fork handle sign text into a general version of the route identifier and the street name; and

(h) repeating steps (b) to (g) for other forks of the compound ramp.

38. The method of claim 26, further comprising the step of:

storing computed sign text for selected exit ramps from a first electronic map database containing the electronic map of roads into a second electronic map database.

39. The method of claim 26, further comprising the step of:

storing computed sign text for selected exit ramps of the electronic map of roads while the electronic map of roads is being created.

40. The method of claim 26, wherein sign text for respective exit ramps is sequentially outputted to a display of a system for determining a path from an origin to a destination in response to a user initiated pathfinding request.

41. The method of claim 40, wherein the sign text is computed and outputted in real-time in conjunction with the user initiated pathfinding request.

42. The method of claim 41, wherein sign text for a given exit ramp is outputted to the display until the user passes the given exit ramp, whereupon sign text for the given exit ramp is removed from the display and sign text for a next exit ramp is outputted to the display.

43. A processor readable storage medium having processor readable code embodied on the processor readable storage medium, the processor readable code for programming a processor to perform a method for determining sign text of exit ramps in an electronic map of roads from a first carriageway of a limited access road to a destination roadway, the method comprising the steps of:

constructing a first name list and a second name list;

computing sign text using a first process if the selected exit ramp is a simple exit ramp, a first name list and a second name list being inputs to the first process and the computed sign text being placed in the sign text variable;

computing sign text using a second process if the selected exit ramp is a compound exit ramp, the first and second name lists being inputs to the second process and the computed sign text being placed in the sign text variable; and

outputting the sign text variable to a display.

44. The processor readable storage medium of claim 43, further comprising the step of:

storing the computed sign text in a database.

45. An apparatus for determining sign text of exit ramps in an electronic map of roads from a first carriageway of a limited access road to a destination roadway, the apparatus comprising:

an output device;

a processor, in communication with the output device; and

a processor readable storage medium for storing code, the processor readable storage medium being in communication with the processor, the code capable of programming the processor to perform the steps of;

computing sign text using a first process if a selected exit ramp is a simple exit ramp, a first name list and a second name list being inputs to the first process and the computed sign text being placed in the sign text variable;

computing sign text using a second process if the selected exit ramp is a compound exit ramp, the first and second name lists being inputs to the second process and the computed sign text being placed in the sign text variable, and

outputting the sign text variable to a display.

46. The apparatus of claim 45, wherein the code capable of programming the processor performs the additional step of:

storing the computed sign text in a database.