Method for creating a directory of road sections, method for ascertaining all road sections within a search area, and computer program
First Claim
Patent Images
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
10 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
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. - View Dependent Claims (10)
-
Specification