Method for creating a directory of road sections, method for ascertaining all road sections within a search area, and computer program

• US 9,214,097 B2
• Filed: 02/08/2008
• Issued: 12/15/2015
• Est. Priority Date: 04/03/2007
• Status: Expired due to Fees

• Current Assignee: Robert Bosch GmbH
• Original Assignee: Robert Bosch GmbH
• Inventors: Vogel, Andreas, Mueller, Guido
• Primary Examiner(s): Reyes, Mariela
• Assistant Examiner(s): Almani, Mohsen
• Application Number:
  US12/305,542
• Publication Number:
  US 20090234877A1
• Time in Patent Office: 2,867 Days
• Field of Search: 701/202, 701/208, 701/209, 707/773
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3874 Structures specially adapted for data searching and retrieval
• CPC Class Codes: G09B 29/00 Maps; Plans; Charts; Diagrams, e.g. route diagram star maps G09B27/04; devices for holding or supporting maps A47B97/02; for computing purposes G06G1/14, G09B1/16; display boards G09F

Abstract

A method for creating a directory of road sections of a digital road map for a navigation system is provided. Furthermore, a method for ascertaining all road sections within a search area is provided. Moreover, a computer program for performing a method for creating a directory of road sections and a method for ascertaining all road sections within a search area is provided.

Claims

1. A method for creating a directory of road sections of a digital road map portion for a navigation system, wherein the directory receives a data structure of an ordered N-tree, in which the road sections are stored in nodes, the method comprising:

a) assigning a geographic location to each of the road sections;

b) assigning an orientation to each of the road sections;

c) defining a search tree condition for the road map portion, wherein;

(i) the road map portion is partitioned into N sublevels by a root road section, precisely one of which sublevels contains the root road section;

(ii) the sublevels of the road map portion are situated in relation to one another as a function of respective orientations of the sublevels relative to the root road section; and

(iii) all road sections are assigned to precisely one of the sublevels of the road map portion and thus precisely one subtree of the node;

d) selecting one of the road sections;

e) searching for the selected road section in the tree, wherein the search ends at a terminal node having at most N−

1 subtrees, none of which contains the selected road section;

f) appending the selected road section as a leaf to the terminal node according to the search tree condition;

g) repeating steps d) through f) until each road section has been selected precisely once; and

h) storing the directory on a data carrier.

2. The method according to claim 1, wherein the road sections from substep c)(iii) are assigned to the sublevel of the road map portion in which the road sections lie completely, otherwise to the sublevel in which the road section from substep c)(i) lies.

3. The method according to claim 1, wherein N=3.

4. The method according to claim 3, wherein the three sublevels are formed by:

a) defining a first straight line through a starting point and an end point of the root road section;

b) forming two additional straight lines parallel to the first straight line and to one another, thereby enclosing the root road section completely between the two additional straight lines; and

c) situating the three sublevels as a function of the orientation of the three sublevels relative to the root road section, as “

left”

, “

middle”

, and “

right”

.

5. The method according to claim 1, wherein N=5.

6. The method as recited in claim 5, wherein the five sublevels are formed by:

a) forming a rectangle which contains the root road section;

b) forming half-lines as extensions of sides of the rectangle; and

c) situating the five sublevels as a function of the orientation of the five sublevels relative to the root road section, as “

left”

, “

middle”

, “

right”

, “

before”

, and “

after”

.

7. The method according to claim 1, wherein pointers are stored in each node, each pointer pointing to subsequent nodes.

8. The method according claim 1, wherein step (c) further comprises:

(iv) for each sublevel, iteratively repeating substeps (i) through (iii).

9. A non-transitory computer-readable data storage medium containing a computer program having program code which, when executed by a computer, performs a method for creating a directory of road sections of a digital road map portion for a navigation system, wherein the directory receives a data structure of an ordered N-tree, in which the road sections are stored in nodes, the method comprising:

a) assigning a geographic location to each of the road sections;

b) assigning an orientation to each of the road sections;

c) defining a search tree condition for the road map portion, wherein;

(i) the road map portion is partitioned into N sublevels by a root road section, precisely one of which sublevels contains the root road section;

(ii) the sublevels of the road map portion are situated in relation to one another as a function of respective orientations of the sublevels relative to the root road section; and

(iii) all road sections are assigned to precisely one of the sublevels of the road map portion and thus precisely one subtree of the node;

d) selecting one of the road sections;

e) searching for the selected road section in the tree, wherein the search ends at a terminal node having at most N−

1 subtrees, none of which contains the selected road section;

f) appending the selected road section as a leaf to the terminal node according to the search tree condition;

g) repeating steps d) through f) until each road section has been selected precisely once; and

h) storing the directory on a data carrier.

10. The non-transitory computer-readable data storage medium according to claim 9, wherein step (c) of the method further comprises:

(iv) for each sublevel, iteratively repeating substeps (i) through (iii).