Method and apparatus for determining a route between a starting point and a destination
First Claim
1. A method for determining a route between a starting point (S) and a destination or target (Z), which are located on a road map, and digitally stored in a read-only memory (14).comprising the steps ofdividing the road map into at least two levels of different grid density and regional size;
- storing the maps of said at least two levels in at least two levels (18,
20) of said memory;
assigning a plurality of smaller subregions of fine grid density to a lower one of said levels and assigning one or more larger subregions of coarser grid density to a higher one of said levels;
first analyzing the road maps with the lowest level to find a possible route between the starting point (S) and the destination (Z), andif the results of such analysis are positive, plotting the route based on the memory within said level;
orif the results of said analysis are negative, so that no connecting route between the starting point (S) and the destination (Z) is found,analyzing the road map stored in the memory of the next higher level;
determining when a positive result is obtained; and
then plotting the route based on the contents of the memories in said at least two levels.
1 Assignment
0 Petitions
Accused Products
Abstract
In a method for determining a route between a starting point and a destination which are located on a digitally memorized road map, the problem is to perform the necessary calculations for determining the route within a short time, even for extensive road systems. Otherwise, the results could arrive too late and could no longer lend the driver any aid in making a decision. The object is attained by dividing the road map into at least two levels of different grid density and regional size and storing it in memory. A plurality of smaller subregions of fine grid density are assigned to the lower level, and one or more larger subregions of coarser grid density are assigned to the higher level. Beginning with the lower level of the road map, a possible route is then studied; if the results are negative, a transition is made to the next-higher level, until a positive result is attained. Then the route is plotted within whatever level a positive result was attained in, for instance in the same level or back and forth between the levels.
192 Citations
15 Claims
-
1. A method for determining a route between a starting point (S) and a destination or target (Z), which are located on a road map, and digitally stored in a read-only memory (14).
comprising the steps of dividing the road map into at least two levels of different grid density and regional size; -
storing the maps of said at least two levels in at least two levels (18,
20) of said memory;assigning a plurality of smaller subregions of fine grid density to a lower one of said levels and assigning one or more larger subregions of coarser grid density to a higher one of said levels; first analyzing the road maps with the lowest level to find a possible route between the starting point (S) and the destination (Z), and if the results of such analysis are positive, plotting the route based on the memory within said level;
orif the results of said analysis are negative, so that no connecting route between the starting point (S) and the destination (Z) is found, analyzing the road map stored in the memory of the next higher level; determining when a positive result is obtained; and then plotting the route based on the contents of the memories in said at least two levels. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. A navigation system to determine a route between a starting point (S) and a destination or target point (Z), which are located on a road map, comprising
a computer (10); -
a working memory (12) for said computer; a display and input/output unit (16) coupled to said computer; a read-only memory (14) digitally storing a road map on which said starting points (S) and said destination or target (Z) are stored, wherein said read-only memory (14) comprises at least two read-only memory levels (18,
20), in which one of said memory levels or regions includes the road maps of a plurality of small subregions with fine grid density, and another one of said levels includes the road maps of large subregions of coarser grid density;and wherein said computer reads from said lower level read-only memory into the working memory (12) only those portions of the memory contents representing the respective smaller subregions of finer grid density including the starting point (S) and the destination or target (Z) and, if the starting point and destination and target are not on the same subregions, also those data from the higher level memory including the road maps of larger subregions of coarser grid density and having transitions to the subregions of the lower level and of the finer grid density. - View Dependent Claims (15)
-
Specification