Shortcut generator

• US 6,885,937 B1
• Filed: 12/10/1998
• Issued: 04/26/2005
• Est. Priority Date: 12/10/1998
• Status: Expired due to Term

• Current Assignee: Tomtom North America Incorporated (TomTom NV)
• Original Assignee: Tele Atlas North America (TomTom NV)
• Inventors: Suranyi, Edward Joseph
• Primary Examiner(s): ARTHUR JEANGLAUDE, GERTRUDE
• Application Number:
  US09/208,709
• Time in Patent Office: 2,329 Days
• Field of Search: 701/26, 701/28, 701/202, 701/208, 701/209, 701/210, 701/35, 701/200, 340/988, 340/990, 340/995, 731/78.R
• US Class Current: 701/208
• CPC Class Codes: G09B 29/106 using electronic means

Abstract

An electronic map is stored as a collection of nodes and links. Roads in the map are assigned priorities for pathfinding purposes. A node'"'"'s priority originally corresponds to the priority of the road associated with the node. Electronic maps can be made more useful by adding short cuts to the map. A short cut generator is disclosed that creates short cuts by building compound links and/or raising the priority of certain nodes. A compound link is a link that represents travel along multiple links of the electronic map.

Claims

1. A method for adding short cuts to an electronic map, comprising the steps of:

storing a set of nodes and links of said electronic map, said links being associated with link priorities;

exploring outward from said nodes using a processor, said step of exploring includes determining which nodes are not useful;

creating new link priorities for a set of said links that were traversed during said exploring and do not terminate at a node determined to be not useful;

building compound links, said compound links may include one or more links with said new link priorities; and

storing said compound links in said electronic map, said compound links represent said short cuts.

2. A method according to claim 1, further comprising the steps of:

storing node priorities for said nodes in said electronic map;

creating new node priorities for a set of said nodes connected by one or more of said links having a new link priority; and

storing said new node priorities in said electronic map.

3. A method according to claim 2, further comprising the step of:

storing one or more u-turn indications for paths traversed during said exploring that include a u-turn, said step of creating new link priorities does not consider links on paths associated with said stored u-turn indications.

4. A method according to claim 2, further comprising the step of:

receiving an original map file, said original map file includes said nodes in said electronic map;

said steps of storing said new node priorities and storing said compound links include generating a new file; and

said new file includes said new node priorities, said compound links and said nodes in said electronic map from said original map file.

5. A method according to claim 2, wherein:

said step of building compound links includes traversing along successive links until a choice of links of at least a scan priority and building a new link representing travel along said traversed successive links.

6. A method according to claim 2, wherein said step of exploring outward includes the steps of:

setting usefulness for a set of nodes to infinity prior to exploring;

checking a particular node'"'"'s usefulness when traversing to said particular node while exploring;

changing said particular node'"'"'s usefulness if said particular node is not useful;

checking usefulness for one or more nodes behind said particular node if said particular node is not useful; and

changing said usefulness for appropriate ones of said one or more nodes behind said particular node if said appropriate ones of said one or more nodes behind said particular node are not useful.

7. A method according to claim 2, wherein said step of creating new link priorities includes the steps of:

identifying a first group of nodes, said first group of nodes were visited during said step of exploring and are at a current scan level or higher;

backtracking along paths to said first group of nodes;

changing priorities to a current scan priority for links along said paths to said first group of nodes that have a priority equal to one level below said current scan priority.

8. A method according to claim 2, wherein said step of creating new node priorities includes the steps of:

examining forward links for a node under consideration;

determining a highest priority level that there is a choice, based on said step of examining; and

setting said new node priority to said determined highest priority if said determined highest priority is less than a current scan priority.

9. A method according to claim 8, wherein:

said steps of examining forward links, determining a highest priority level and setting said new node priority to are performed for each node at a current scan level.

10. A method according to claim 2, wherein:

said steps of exploring outward, creating new link priorities, creating new node priorities and building compound links are performed at each of a plurality of scan levels.

11. A method according to claim 10, further including the step of:

identifying every node at a current scan level prior to said step of exploring being performed at said current scan level, said step of exploring is performed on each node identified in said step of identifying.

12. A processor readable storage medium storing an electronic map, said electronic map having short cuts added to said electronic map according to the method of claim 2.

13. An apparatus including a processor readable storage medium storing an electronic map, said electronic map having short cuts added to said electronic map according to the method of claim 2.

14. A processor readable storage medium storing an electronic map, said electronic map having short cuts added to said electronic map according to the method of claim 1.

15. An apparatus including a processor readable storage medium storing an electronic map, said electronic map having short cuts added to said electronic map according to the method of claim 1.

16. A method for adding short cuts to an electronic map, comprising the steps of:

assigning node priorities for nodes in said electronic map, said nodes being connected by links, said links having link priorities;

exploring outward from said nodes using a processor;

storing one or more u-turn indications for paths traversed during said exploring that include a u-turn;

creating new link priorities for a set of said links on paths that were traversed during said exploring, said step of creating new link priorities does not consider paths associated with said stored u-turn indications;

creating new node priorities for a set of said nodes connected by one or more of said links having a new link priority;

building compound links;

storing said new node priorities in said electronic map; and

storing said compound links in said electronic map, said compound links represent said short cuts.

17. A method for enhancing the use of an electronic map by adding the use of short cuts, comprising the steps of:

storing nodes and links of said electronic map, said links having link priorities;

exploring outward from said nodes using a processor, said step of exploring includes determining which nodes are not useful;

creating new link priorities for a set of said links that were traversed during said exploring and do not terminate at a node determined to be not useful;

building compound links, said compound links may include one or more links with said new link priorities;

storing said compound links in said electronic map, said compound links represent said short cuts;

storing a designation of an origin in said electronic map;

storing a designation of a destination in said electronic map;

determining a path from said origin to said destination, said path including at least one of said compound links; and

reporting said path.

18. A method according to claim 17, further comprising the steps of:

storing node priorities for said nodes in said electronic map;

creating new node priorities for a set of said nodes connected by one or more of said links having a new link priority; and

storing said new node priorities in said electronic map.

19. A method according to claim 17, further comprising the step of:

storing one or more u-turn indications for paths traversed during said exploring that include a u-turn, said step of creating new link priorities does not consider links on paths associated with said stored u-turn indications.

20. A processor readable storage medium having processor readable code embodied on said processor readable storage medium, said processor readable code for programming a processor to perform a method comprising the steps of:

storing a set of nodes and links of an electronic map, said links being associated with link priorities;

exploring outward from said nodes using a processor, said step of exploring includes determining which nodes are not useful;

creating new link priorities for a set of said links that were traversed during said exploring and do not terminate at a node determined to be not useful;

building compound links, said compound links may include one or more links with said new link priorities; and

storing said compound links in said electronic map, said compound links represent said short cuts.

21. A processor readable storage medium according to claim 20, said method further comprising the steps of:

storing node priorities for said nodes in said electronic map;

creating new node priorities for a set of said nodes connected by one or more of said links having a new link priority; and

storing said new node priorities in said electronic map.

22. A processor readable storage medium according to claim 21, wherein said method further comprising the steps of:

storing one or more u-turn indications for paths traversed during said exploring that include a u-turn, said step of creating new link priorities does not consider links on paths associated with said stored u-turn indications.

23. A processor readable storage medium according to claim 21, wherein said step of exploring outward includes the steps of:

setting usefulness for a set of nodes to infinity prior to exploring;

checking a particular node'"'"'s usefulness when traversing to said particular node while exploring;

changing said particular node'"'"'s usefulness if said particular node is not useful;

checking usefulness for one or more nodes behind said particular node if said particular node is not useful; and

changing said usefulness for appropriate ones of said one or more nodes behind said particular node if said appropriate ones of said one or more nodes behind said particular node are not useful.

24. A processor readable storage medium according to claim 21, wherein:

said steps of examining forward links, determining a highest priority level and setting said new node priority to are performed for each node at a current scan level.

25. An apparatus, comprising:

an input device;

a processor readable storage medium; and

a processor in communication with said input device and said processor readable storage medium, said processor readable storage medium storing code to program aid processor to perform the method comprising the steps of;

storing a set of nodes and links of an electronic map, said links being associated with link priorities,

exploring outward from said nodes using a processor, said step of exploring includes determining which nodes are not useful,

creating new link priorities for a set of said links that were traversed during said exploring and do not terminate at a node determined to be not useful,

building compound links, said compound links may include one or more links with said new link priorities, and

storing said compound links in said electronic map, said compound links represent said short cuts.

26. An apparatus according to claim 25, wherein said method further comprising the steps of:

storing one or more u-turn indications for paths traversed during said exploring that include a u-turn, said step of creating new link priorities does not consider links on paths associated with said stored u-turn indications.

27. An apparatus according to claim 25, wherein said method further comprising the steps of:

storing a designation of an origin in said electronic map;

storing a designation of a destination in said electronic map;

determining a path from said origin to said destination, said path including at least one of said compound links; and

reporting said path.

28. An apparatus according to claim 25, wherein said method further comprising the steps of:

storing node priorities for said nodes in said electronic map;

creating new node priorities for a set of said nodes connected by one or more of said links having a new link priority; and

storing said new node priorities in said electronic map.

29. An apparatus according to claim 28, wherein said step of exploring outward includes the steps of:

setting usefulness for a set of nodes to infinity prior to exploring;

checking a particular node'"'"'s usefulness when traversing to said particular node while exploring;

changing said particular node'"'"'s usefulness if said particular node is not useful;

checking usefulness for one or more nodes behind said particular node if said particular node is not useful; and

changing said usefulness for appropriate ones of said one or more nodes behind said particular node if said appropriate ones of said one or more nodes behind said particular node are not useful.

30. An apparatus according to claim 28, wherein:

said steps of examining forward links, determining a highest priority level and setting said new node priority to are performed for each node at a current scan level.