System for joining elements to complex junctions and links in road network representation for vehicles

• US 5,815,161 A
• Filed: 06/12/1996
• Issued: 09/29/1998
• Est. Priority Date: 06/16/1995
• Status: Expired due to Term

• Current Assignee: Continental Automotive GmbH (Continental AG)
• Original Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Inventors: Veenker, Hendrik H., Emmerink, Carla J. M.
• Primary Examiner(s): Jankus, Almis R.
• Application Number:
  US08/662,187
• Time in Patent Office: 839 Days
• Field of Search: 395/140-142, 345/427, 345/428, 345/429, 345/430, 345/433, 345/435, 345/439, 345/440, 345/441-443, 345/348, 345/349, 345/356-358
• US Class Current: 345/440
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering

Abstract

Road data is stored in hierarchically organized levels. A lower level has detailed representations of road links and junctions. At a globalized level an abstracted representation is derived: a set of elementary junctions is joined to a complex junction on the basis of predetermined coherencies among the elements of the set. This repeats until all complex junctions have been found. All external road links between a border element of a particular set and any element of a particular neighboring set are detected, including allowed traffic directions on the external road links. The links are collected to a single complex road link while mapping the allowed traffic directions thereon. This repeats until all complex road links have been found. Remaining elementary and complex junction are represented by a respective single node. Also, each remaining elementary and complex road link is represented by a single higher level road link.

Claims

1. A method for storing geographical road data in multiple hierarchically organized levels by from a relatively lower level that features detailed representations of road links and junctions, deriving at a relatively globalized level an abstracted representation from such detailed representations, characterized by the steps of:

a. at such lower level, joining a set of elementary junctions to a complex junction on the basis of predetermined coherencies among the elementary junctions of the set;

b. repeating step a. until all complex junctions have been found;

c. ascertaining all border elements of a particular set and all elementary external links between those border elements and any element of one particular other set, inclusive of all allowed traffic directions on such elementary external road links, and collectively replacing said elementary external road links by a single complex external road link while mapping said allowed traffic directions thereon;

d. repeating step c. until all complex external road links between sets so paired have been found;

e. representing each remaining elementary junction and each complex junction by a respective single node, while representing each remaining elementary external road link and each complex external road link by a single higher level road link with associated original or mapped traffic directions, respectively.

2. A method as claimed in claim 1, wherein each single higher level road link is represented by a straight line.

3. A method as claimed in claim 2, wherein said representing is effected on a visual display.

4. A method as claimed in claim 3, wherein said ascertaining with respect to a particular complex junction comprises searching in the associated set of elementary junctions for an allowable traffic path that connects an ingoing allowed traffic direction on a first higher level road link to an outgoing allowed traffic direction on a second higher level road link, but if disallowed retaining an inhibiting qualifier for the associated higher level road link pair of the associated complex junction.

5. A method as claimed in claim 4, wherein the length of a higher level complex road link is set to an average length of the associated elementary road links plus a size value of one or both sets of elementary junctions interconnected thereby.

6. A method as claimed in claim 5, wherein said joining comprises executing successive and looped expanding steps from entrance junctions to follower junctions and exit junctions, and backwards from all exit junctions to preceder junctions and entrance junctions, until detecting an ultimate termination of said expanding, whereby all junctions found in said expanding are comprised in the associated set.

7. A storage medium item comprising a stored data structure produced by executing the method as claimed in claim 6.

8. A reader device for interfacing to a storage medium as claimed in claim 7, and comprising access means for selectively accessing said stored data structure for therefrom extracting information pertaining to a plurality of said complex junctions and complex external road links.

9. A reader as claimed in claim 8 and having display means for selectively displaying said complex junctions and complex external road links.

10. A vehicle comprising a navigational system including a reader device as claimed in claim 9.

11. A vehicle comprising a navigational system including a reader device as claimed in claim 8.

12. A method as claimed in claim 2, wherein said ascertaining with respect to a particular complex junction comprises searching in the associated set of elementary junctions for an allowable traffic path that connects an ingoing allowed traffic direction on a first higher level road link to an outgoing allowed traffic direction on a second higher level road link, but if disallowed retaining an inhibiting qualifier for the associated higher level road link pair of the associated complex junction.

13. A method as claimed in claim 1, wherein said representing is effected on a visual display.

14. A method as claimed in claim 1, wherein said ascertaining with respect to a particular complex junction comprises searching in the associated set of elementary junctions for an allowable traffic path that connects an ingoing allowed traffic direction on a first higher level road link to an outgoing allowed traffic direction on a second higher level road link, but if disallowed retaining an inhibiting qualifier for the associated higher level road link pair of the associated complex junction.

15. A method as claimed in claim 1, wherein the length of a higher level complex road link is set to an average length of the associated elementary road links plus a size value of one or both sets of elementary junctions interconnected thereby.

16. A method as claimed in claim 1, wherein said joining comprises executing successive and looped expanding steps from entrance junctions to follower junctions and exit junctions, and backwards from all exit junctions to preceder junctions and entrance junctions, until detecting an ultimate termination of said expanding, whereby all junctions found in said expanding are comprised in the associated set.

17. A storage medium item comprising a stored data structure produced by executing the method as claimed in claim 1.

18. A data processing system for processing and storing geographical road data in multiple hierarchically organized levels by from a relatively lower level that features detailed representations of road links and junctions, deriving at a relatively globalized level an abstracted representation from such detailed representations, said system comprising:

a. joining means for, at such lower level, joining a set of elementary junctions to a complex junction on the basis of predetermined coherencies among the elementary junctions of the set;

b. first sequencer means for cyclically activating the joining means of item a. until all complex junctions have been found;

c. ascertaining means for ascertaining all border elements of a particular set and all elementary external links between those border elements and any element of a particular other set, inclusive of all allowed traffic directions on such elementary external road links, and collectively replacing said elementary external road links by a single complex external road link while mapping said allowed traffic directions thereon;

d. second sequencer means for cyclically activating the ascertaining means of item c. until all complex external road links between sets so paired have been found;

e. representing means for representing each remaining elementary junction and each complex junction by a respective single node, while representing each remaining elementary external road link and each complex external road link by a single higher level road link with associated original or mapped traffic directions, respectively.