Route exploration method of navigation apparatus

• US 5,168,452 A
• Filed: 02/28/1991
• Issued: 12/01/1992
• Est. Priority Date: 12/28/1987
• Status: Expired due to Term

• Current Assignee: Aisin AW Company Limited (Aisin Corp.), Kabushiki Kaisha Shinsangyokaihatsu
• Original Assignee: Aisin AW Company Limited (Aisin Corp.), Kabushiki Kaisha Shinsangyokaihatsu
• Inventors: Yamada, Takashi, Nimura, Mitsuhiro, Yokoyama, Shoji, Toyama, Yasuhiro
• Primary Examiner(s): Black, Thomas G.
• Application Number:
  US07/662,504
• Time in Patent Office: 642 Days
• Field of Search: 364/443, 364/444, 364/449, 340/990, 340/995
• US Class Current: 701/202
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G08G 1/096827 where the route is computed onboard
• CPC Class Codes: G08G 1/0969 having a display in the form of a map

Abstract

In a navigation apparatus for setting a route from a designated departure point to a destination and providing guidance along the route, there are provided, as map data used in route exploration, node data [FIG. 15(b)] comprising position information and information relating to the attributes thereof, intersection data [FIGS. 2-5(b), FIG. 15(b)] comprising information relating to intersections, and road data [FIGS. 2-5(a), FIG. 15(c)] comprising information related to roads. Information such as roads between intersections and intersections which are the starting and end points of roads are obtained from the intersection data and road data, and an optimum route is retrieved by comparing routes. The map data is put into the form of a layered structure, as shown in FIG. 1, a branch road network is developed in an upper-layer (2) connected to a trunk road network with respect to a higher-order layer (1) of the trunk road network, block division is performed, and exploration from a lower-order layer to intersections connected to a road network of the higher-order layer is successively repeated. The foregoing makes it possible to perform processing upon limiting the range of exploration, and to raise the speed of exploration processing. In addition, the work area needed for exploration can be reduced and storage data can be conserved.

Claims

1. A route exploration method in a navigation apparatus for setting a route from a designated departure point to a destination and providing guidance along the route, which comprises:

(a) providing intersection data and roud data in blocks arranged in a higher order and lower order layered format;

(b) designating a departure point and a destination point;

(c) checking positional relationship of blocks containing said departure point and said destination by deciding if the departure point block is remote from the destination block;

(d) setting the departure point and destination in lower layer blocks, in which a road network has a high density, when the departure point block is not remote from the desitnation block;

(e) inputting intersection and road datas of the departure point block;

(f) detecting first connecting intersection of upper layer first blocks, in which a road network has a low density in the departure block, when the eparture point block is remote from the destination block;

(g) setting the departure point and setting the connecting intersection as the destination in the departure block, and as the departure point in the upper layer first blocks;

(h) exploring from the departure point to the desitnation in the departure block;

(i) inputting intersection and road datas of the destination block;

(j) detecting second connecting intersection of the upper layer second blocks in the destination block;

(k) setting the second connecting intersection as the destination in the upper layer second blocks; and

(l) repeating from (a) to (k) until a departure-point block and a destination block become the same or mutually adjacent blocks.

2. A route exploration method in a navigation apparatus according to claim 1, which comprises:

(a'"'"') inputting intersection and road datas of the departure point block when the departure point and the destination are in mutually adjacent blocks;

(b'"'"') detecting third connecting intersection connecting the departure point block to the destination block;

(c'"'"') setting the departure point and setting the connecting intersection as the destination;

(d'"'"') exploring from the departure point to the destination in the departure block;

(e'"'"') inputting intersection and road datas of the destination block;

(f'"'"') setting the destination as the departure point;

(g'"'"') exploring from the departure point to the destination in the destination block.

3. A route exploration method in a navigation apparatus according to claim 1, which comprises:

(a") inputting intersection and road datas of the departure point block when the departure point and the destination are in the same block;

(b") setting the departure point and the destination;

(c") exploring from the departure to the destination.

4. A route exploration method in a navigation apparatus according to claim 1, characterized by said road data having left-right turn prohibition information.