METHOD FOR CREATING A DIRECTORY OF ROAD SECTIONS, METHOD FOR ASCERTAINING ALL ROAD SECTIONS WITHIN A SEARCH AREA, AND COMPUTER PROGRAM

• US 20090234877A1
• Filed: 02/08/2008
• Published: 09/17/2009
• Est. Priority Date: 04/03/2007
• Status: Active Grant

• Current Assignee: Robert Bosch GmbH
• Original Assignee: Robert Bosch GmbH
• Inventors: Vogel, Andreas, Mueller, Guido
• Granted Patent: US 9,214,097 B2
• Time in Patent Office: Days
• 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-11. -11. (canceled)

12. A method for creating a directory of road sections of a digital road map 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, wherein;

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

(ii) the sublevels are situated in relation to one another as a function of the orientation of the road section; and

(iii) all road sections are assigned to precisely one of the sublevels 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.

13. The method according to claim 12, wherein the road sections from step (iii) are assigned to the sublevel in which they lie completely, otherwise to the sublevel in which the road section from step (i) lies.

14. The method according to claim 12, wherein N=3.

15. The method according to claim 14, wherein the three sublevels are formed by:

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

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

c) situating the three sublevels as a function of the orientation of the road section as “

left”

, “

middle”

, and “

right”

.

16. The method according to claim 12, wherein N=5.

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

a) forming a rectangle which contains the road section;

b) forming half-lines along sides of the rectangle, the half-lines having a same orientation in relation to the orientation of the road section;

c) situating the five sublevels as a function of the orientation of the road section as “

left”

, “

middle”

, “

right”

, “

before”

, and “

after”

.

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

19. A method for ascertaining all road sections within a search area of a directory generated according to a method for creating the directory of the road sections of a digital road map 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) defining the search area as a subarea of the road map;

b) selecting a subtree, beginning with the tree;

c) determining a root node of the selected subtree;

d) determining sublevels of the road section stored in the root node;

e) determining with which of the sublevels the search area has overlaps;

f) flagging the road section as a possible search result if the search area has an overlap with the sublevel in which the road section lies;

g) determining remaining sublevels for further search with which the search area has overlaps;

h) determining the subtrees which are assigned to the sublevels determined in step g);

i) flagging the subtrees determined in step h);

j) repeating steps b) through i) until all flagged subtrees have been selected precisely once, the selection being restricted to the subtrees flagged in step i);

k) discarding the road sections flagged in step f) with which the search area has no overlap.

20. The method according to claim 19, wherein the search area is rectangular.

21. 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 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, wherein;

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

(ii) the sublevels are situated in relation to one another as a function of the orientation of the road section; and

(iii) all road sections are assigned to precisely one of the sublevels 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.

22. A machine-readable carrier 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 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, wherein;

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

(ii) the sublevels are situated in relation to one another as a function of the orientation of the road section; and

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

d) selecting one of the road sections;

e) searching for the selected road section in the trees 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.