US 4,984,168 A · Method and apparatus for determining a route between a starting point and a destination

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.

Claims15

Dependent claims

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;
or
if 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.

9 more elements

Dependencies are inferred from the claim text.

Method and apparatus for determining a route between a starting point and a destination

Life of this patent

Method and apparatus for determining a route between a starting point and a destination

Life of this patent

Abstract

Claims15