Method for producing a directory of road segments, a method for determining of all road segments within a search area and computer program

摘要

A method is presented, with which a directory of road segments (2) of a digital road map (1, 6a to c) for a navigation system, particularly simple and effective. The directory in this case receives the data structure of an ordered n - tree, in which the road segments (2) are stored in node. The method has the following steps:a) assigning a geographic position relative to each of the road segments (2);b) assigning a orientation to each of the road segments (2);c) defining a search tree condition:(i) by means of the road section (2) of the node, the road map in n sub-planes (6a, b, c) partitioned, of which exactly one the road segment (2) contains;(ii) are the sub-planes as a function of the orientation of the road or street sections (2) arranged with respect to one another;(iii) all of the road segments (2) can be precisely one of the sub-planes, and thus accurately a part of a tree of the node associating;d) selecting one of the road segments (2);e) searching of the selected road section in the tree; the search ends at a node [end node] with a maximum of n - 1 partial trees, none of which the selected section of road (2) contains;f) appending of the selected road or street sections (2) as a blade at the end node according to such tree condition;g) repeating steps (d) to f), to each road section (2) has been selected exactly once;h) storing the directory on a ..