JP2000337902A - Navigation device - Google Patents

Abstract

(57) [Summary] [PROBLEMS] To provide a navigation device capable of performing a route search with map data in a hierarchical structure and displaying a search route on display means at high speed. SOLUTION: The map data of the on-vehicle navigation device is formed into a hierarchical structure based on the amount of information of the road network, and a hierarchy is developed from a lower hierarchy with more information on the road network to an upper hierarchy with less information on the road network, In addition, regarding the link extending to the upper / lower layers, the link of the map data of the upper layer is described in association with the link of the map data of the lower layer, and when searching for a route of the lower layer, the link of the lower layer becomes the link of the upper layer. The route search is shifted from the lower hierarchy to the upper hierarchy when it is supported. Thus, the route search and the display thereof are performed at high speed.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a navigation device, and more particularly, to a navigation device capable of performing a route search by using map data in a hierarchical structure and displaying a search route on a display means at a high speed.

[0002]

2. Description of the Related Art An on-vehicle navigation device provides a route guide to a driver whose geography is unknown. This in-vehicle navigation device uses a correlation between a travel locus road shape obtained from a speed sensor and a direction sensor, or a Global Positioning System (hereinafter referred to as GP).
S. The user is informed of the vehicle position by displaying the surrounding map centering on the vehicle position detected by decoding the absolute position. The user sets a route from the departure place to the destination by inputting the departure place and the destination before traveling on such a navigation device, and performs navigation according to the set route. In the navigation, when a route is instructed, a map is displayed on the screen of the display means, and the route is displayed over the map.

In such a navigation device,
When performing a route search, if the distance from the departure point to the destination is long or the density of the road network is high, the number of intersections to be searched for the route will increase accordingly, and the calculation time required for the route search and the Techniques for preventing an increase in the storage capacity of a memory used for search processing have been actively developed. One solution is to develop map data into a hierarchical structure based on the amount of information on the road network, and develop a hierarchy from a lower layer with more information on the road network to an upper layer with less information on the road network. A data structure having connection information between layers is specified. Based on this map data, a layer including a designated departure point and a destination is specified, and based on the connection information between the layers, the specified layer is moved to a higher layer. There is a method in which a route search is performed up to a connection point or a portion, and the process is further moved to a higher hierarchy to repeatedly perform a route search from the connection point (portion).

As a conventional technique for performing a route search based on such hierarchically structured map data, for example, there is one shown in FIG. In FIG. 9, reference numeral 101 denotes an upper layer, and the upper layer 101 includes intersection numbers a, b, c,
Are the maps of the main arterial road network having one block A. Reference numeral 102 denotes a lower layer. This upper layer 2 is a map including a road network of branch lines connected to the main arterial road network of the upper layer 101, and is composed of a plurality of blocks B, C, D,. Have been. In the lower layer 102, the connecting roads between the blocks are pseudo-intersections so that the processing units can be constituted by blocks, such as intersection numbers b and c between blocks C and D of the lower layer 102. Is set. The number of blocks is set so that the information amounts of the blocks A, B, C, D,.

A route search method in a navigation device having such a map data structure will be described. For example, the departure point is the intersection number c in the block B of the lower layer, and the destination is the block D of the lower layer.
Is the intersection number d. In this case, first, in block B on the departure point side, an intersection number in the upper layer 101 corresponding to the vicinity of the departure point is found, and the intersection number d (intersection number a of block A in upper layer 101)
Search for a route up to the upper hierarchy. On the other hand, in the block D on the destination side, similarly, an intersection number in the upper layer 101 corresponding to the vicinity of the destination is found, and up to the intersection number a (the intersection number e of the block A corresponds to the upper layer 101). Search for the route and go up to the upper level. Next, in the upper layer 101, a route search from the intersection number a to the intersection number e in the block A is executed together with the information on the route search in the lower layer 102. In this way, the route 103 is searched in the upper layer 101, and a route search from the departure place to the destination is performed.

[0006]

However, in the above-described conventional on-vehicle navigation device, when the route shape is obtained from the lower map data in the method of the first conventional example, the link is formed by an intermediate portion. Although division does not occur, the number of interpolation points of the shape of each link is more than necessary for display resolution and the number of links is also plural, so the data amount of display data may increase. This is a factor that hinders speeding up of route guidance display.

The present invention solves such a conventional problem, and makes it possible to perform a route search with map data in a hierarchical structure and to display a search route on a display means at high speed. It is an object to provide a navigation device.

[0008]

According to the present invention, in order to achieve the above object, the map data is arranged in a hierarchical structure based on the information amount of the road network, from the lower hierarchy having a large amount of road network information to the information of the road network. In addition to expanding the hierarchy to the upper hierarchy with less number, it has a data structure that has connection information that associates common roads between each hierarchy, and specifies the hierarchy including the designated departure place and destination based on this map data Based on the connection information between the respective hierarchies, a route search is performed up to a point in the specified hierarchy that connects to a higher hierarchy, and a further higher hierarchy is performed to repeatedly perform a route search from the connection point. In the data, for the link extending between the upper and lower layers, the link of the map data of the upper layer is described in association with the link of the map data of the lower layer, and the route of the lower layer is described. In the search, the gist that the link of the lower layer is so as to shift from the lower layer route search when corresponding to the link the higher hierarchy to a higher hierarchy. Further, as another aspect of the present invention, when the link shape of the map data of the upper layer is stored in the map data of the lower layer for the link extending over the upper / lower layers, and when the route search is shifted from the lower layer to the upper layer, The route search processing can be completed to both ends of the corresponding link in the upper hierarchy. Further, in order to perform this route search, dedicated road shape data is stored as upper / lower road shapes in correspondence with lower nodes on lower map data, and the route is determined using the dedicated road shape data. The shape can also be displayed.

According to the present invention, the shape (link shape) of a road extending over upper / lower layers is stored in map data. The conditions for that are as follows: (1) The link shape over the upper / lower layers describes the link of the map data of the upper layer in association with the link of the map data of the lower layer. (2) The corresponding link shape is composed of interpolation points having the same number and the same precision as the link shape of the upper layer. That is.

With this configuration, not only the route search is performed at a high speed, but also the route obtained as a result of the route search can be displayed at a high speed. It is possible to speed up the entire processing operation.

[0011]

Embodiments of the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram showing a configuration of a navigation device according to one embodiment of the present invention. In FIG. 1, reference numeral 1 denotes a direction sensor, and this direction sensor 1 uses an optical gyro for detecting an absolute traveling direction of an automobile. Reference numeral 2 denotes a distance sensor that generates a pulse according to the number of rotations of the wheels. Reference numeral 3 denotes various sensor signals such as an ON / OFF signal of a brake switch, a parking switch, and the like, and a power supply voltage monitoring signal. Reference numeral 4 denotes a sensor signal processing unit for processing sensor signals of the azimuth sensor 1, the distance sensor 2, and the like. Reference numeral 5 denotes a GPS receiver.
The S receiver 5 can obtain the position (latitude and longitude) of the receiving point by receiving and calculating radio waves transmitted from a plurality of satellites. Reference numeral 6 denotes a CD-ROM driver. The CD-ROM driver 6 reads map data from a CD-ROM 7 on which map data is recorded. Reference numeral 8 denotes a display / operation unit installed in the vehicle interior.
A, a touch panel 8B provided on the front of the liquid crystal display 8A, a switch for instructing enlargement or reduction of the display map, a switch for instructing a route search, and a switch for instructing a route search, which are displayed on the liquid crystal display 8A. A switch for selecting a destination from the place names is provided. Reference numeral 9 denotes an apparatus main body, which is installed in a trunk room of an automobile.

Next, the configuration of the apparatus main body 9 will be described.
Reference numeral 10 denotes a CPU (central processing unit) for performing various operations, 1
Reference numeral 1 denotes a ROM (Read Only Memory) in which programs for various operations performed by the CPU 10 are stored. Reference numeral 12 denotes a direction sensor 1, a distance sensor 2, a GPS receiver 5, and a CD-ROM.
A memory (DRAM) 13 for storing data from the ROM driver 6 and the like and calculation results in the CPU 10, and a backup memory 13 for holding necessary data even when power supply to the apparatus main body 9 is stopped. (SRAM), 1
Reference numeral 4 denotes a memory (kanji, font RO) in which patterns such as characters and symbols to be displayed on the liquid crystal display 8A are stored.
M) and 15 are image processors for forming a display image based on map data, current position data of the own vehicle, and the like.
Reference numeral 6 denotes a memory for storing an image to be displayed on the liquid crystal display 8A by synthesizing map data, current position data and kanji output from the CPU 10, kanji such as a town name output from the font ROM 14, road names such as expressways, and fonts. (VRAM) and 17 are RGB conversion circuits for converting output data of the VRAM 16 into color signals, and the color signals are output from the RGB conversion circuit 17 to the liquid crystal display 8A. 18 is a communication interface. On the liquid crystal display 8A, an expressway, other roads, and the like are displayed along with a road name, a facility name, and the like, and an own vehicle mark indicating the current position of the own vehicle is displayed on a display map seller.

FIG. 2 is a diagram showing an example of the format of map data stored in the CD-ROM 7. In FIG. 2, 20 is a disk label, 21 is a drawing parameter, 22 is map information, 23 and 24 are maps (maps),
Reference numeral 25 denotes a route map in which map data for route search is stored, and the above-mentioned leaves 23 and 24 store background data, character data, road data, and the like. Data for each divided unit map is stored. The map data has a hierarchical structure by setting a map leaf (level 0) that roughly describes a wide area to a map leaf (level 0) that describes a narrow area in detail. Each leaf is composed of map display levels A, B and C describing the same area. The map display level is obtained by classifying the degree of detail of the map into ranks. In the map display levels A, B, and C, B is more detailed than A and C is more detailed than B. Each of the map display levels A, B, and C is composed of map display level management information and a plurality of units. The unit describes a divided area obtained by dividing the area at each map display level into a plurality of areas. Each unit includes a unit header, a character layer, a background layer, a road layer, an option layer, and the like. The character layer stores place names, road names, and facility names displayed on a map, and the background layer stores data for drawing roads, facilities, and the like, and roads, facilities, seas, backgrounds, and the like displayed on the liquid crystal display 8A. A color palette for specifying a color is stored. The road layer stores data on coordinates (nodes) and lines (links) describing roads including intersections, for example, node numbers of nodes, latitude and longitude, link numbers of links, link distances, and the like. The road layer stores types of roads, for example, expressways, toll roads, national roads, prefectural roads, and major local roads.

FIG. 3 is a diagram illustrating an example of the format of the route map data stored in the route map 25 in FIG. 2 in another expression. In FIG. 3, reference numeral 31 denotes the entire configuration of the route map data. The route map data includes management information 32, upper map data 33, middle map data 34, and lower map data 35. . The management information includes an upper map address and size table 36.
And a table 37 for the address and size of the middle map and a table 38 for the address and size of the lower map. As the breakdown of the higher-level map data, the higher-level map data is stored as No. 1, No. 2, No. 3,..., And as the breakdown of the middle-level map data, the middle-level map data is stored. Are stored as No.1, No.2, No.3,..., And as a breakdown of the lower-level map data, the lower-level map data is No.1, No.2, No.3,.・ It is stored as follows.

FIG. 4 is a diagram showing an example of a data format of management information in route map data in one hierarchy. The management information describes an address size table 40 describing addresses and sizes of various data in the memory, a node table 41 describing node data on map data, and link data connecting the nodes. It has a link table 42, a node coordinate table 43 describing node coordinate data, and a link shape table 44 describing link shape data. Each node coordinate of the coordinate table 43 stores coordinate data corresponding to each node data of the node table 41, and each link shape of the link shape table 44 stores link shape data corresponding to each link data of the link table 42. Is stored.

The route search operation of the navigation device having such a configuration will be described below with reference to FIGS. FIG. 5 is a model diagram for describing an algorithm when performing a route search in the present embodiment. In FIG. 5, n1, n2, n3, n4, n5
Represent nodes, and are represented by node data No. 1, No. 2, No. 3,... Of the node table 41 in FIG. These nodes n1, n2, n3, n4, n
5 corresponds to an intersection on a map, for example. Also l
(L) 1,12,13,14,15 represent links, respectively, and are represented by link data No.1, No.2, No.3,... Of the link table 42 in FIG. These links l1, l2, l3, l4, and l5 correspond to, for example, intersections on a map and roads between the intersections.

In the route search according to the present embodiment, first, as a first step, the links for the number of links connected to the node n1 starting from n1 in FIG. 5 are obtained from the link table 42 in FIG. In the example of FIG.
Since three links l1, l2, and l1 are connected, data is acquired from the node data No. 1 in the node table 41 to the link data No. 1, No. 2, and No. 3 in the link table 42. Done.

Next, as a second stage, the node number of the connection destination of each link data is obtained, and the node data of each node is obtained from the node table 41. In the above case, the connection destination of the link data No. 1 is the node l2, the connection destination of the link data No. 2 is the node l3, and the connection destination of the link data No. 3 is the node l3. Therefore, data is obtained from the link data No. 1 of the link table 42 to the node data No. 2 of the node table 41, and the link data No. 2 of the link table 42 is obtained from the node data No. 2 of the node table 41. Data acquisition is carried out to 3.

Next, with the next node adjacent to the first node as a new starting point, a connection link to the node is acquired from the link table 42, and thereafter, the process returns to the second stage.

The above processing is repeated on the map data of the lower hierarchy, and if the node or link of the lower hierarchy corresponds to the link of the upper hierarchy, the root of the upper hierarchy matches the root of the lower hierarchy. Then, the search for shifting from the lower hierarchy to the upper hierarchy is completed.

Next, the operation of the above algorithm for shifting from lower level map data to higher level map data will be described. FIG. 6 is a diagram for explaining a transition operation from a lower hierarchy to a higher hierarchy using a road node. In FIG. 6, in the map data of the upper hierarchy, the node data number of the node k of the map data No.m is No.k.
Is set to. In the lower-level map data, the node data number of the node p of the map data is No.
p is set. The node data in the node table 41 of the lower layer map data describes that the node p in the lower layer map data corresponds to the node number No.k of the upper layer map data No.m. I have. Then, this association data becomes connection information between the map data of the upper hierarchy and the map data of the lower hierarchy. As a result, the state in which the route search is completed in the map data of the lower hierarchy is transferred through the nodes (No.p of the lower hierarchy and No.k of the upper hierarchy) which are commonly present in the upper hierarchy and the lower hierarchy. Then, after transferring the state of the node that has been searched in the lower hierarchy to the map data in the upper hierarchy,
By proceeding the route search with the map data of the upper hierarchy, the transition of the route search to the upper hierarchy is completed.

FIG. 7 is a diagram for explaining a transition operation from a lower hierarchy to an upper hierarchy using a road link. In FIG. 7, a route search is performed by the above algorithm on the lower-level map data, and links (links No. 1 and No. 2 of the lower-level map data) in the map data are selected. When these links correspond to a specific link (upper map data link No. 2) of the upper map data, the link data in the link table 42 of the map data of the lower hierarchy is as shown in FIG. The links (No. 1 and No. 2) in the lower layer map data correspond to the link number No. 2 of the upper layer map data No. m.
It is described that the destination nodes of the link are nodes No.a and No.b. As a result, the state in which the route search has been completed in the lower-level map data is transferred as the connection information that is a link that exists in the upper level and the lower level in common. When the hierarchy is shifted by the common link, when the route search process is shifted from the lower hierarchy map data to the upper hierarchy map data, the node corresponding to the lower hierarchy node does not exist in the upper hierarchy map data. Any point may be used as long as it is a point included in the corresponding link in the upper layer (that is, the end point of the link that is commonly present in the upper layer and the lower layer). Therefore, the nodes at both ends of the corresponding link in the map data of the higher hierarchy can be set in a searched state, and the processing can be speeded up.

[0023]

According to the present invention, as is apparent from the above description, the map data is provided to the vehicle-mounted navigation device in a hierarchical structure based on the information amount of the road network from the lower hierarchy having a large amount of road network information. Based on this map data, based on this map data, the designated departure point and destination are determined by expanding the hierarchy to the upper hierarchy with less information on the road network and having connection information that associates a common road between each hierarchy. Based on the connection information between the respective layers, a route search is performed up to a point where the specified layer is connected to a higher layer, and a search for a route from the connection point is further performed after moving to a higher layer. In this manner, in the map data, for the link extending over the upper / lower layers, the link of the upper layer map data is described in association with the link of the lower layer map data. When a lower-layer route search is performed, when the lower-layer link corresponds to a higher-layer link, the route search is shifted from the lower layer to the upper layer. When the route obtained as a result of the search is displayed, the route can be displayed at a high speed, and the speed of the entire route guidance processing operation by the route search can be increased.

As another aspect of the present invention, for a link extending between upper and lower layers, the link shape of the map data of the upper layer is stored in the map data of the lower layer, and the route search is shifted from the lower layer to the upper layer. Then, by enabling the route search processing to be completed to both ends of the corresponding link in the upper hierarchy, various effects such as an increase in the speed of the route search can be obtained.

[Brief description of the drawings]

FIG. 1 is a block diagram showing a configuration of a vehicle-mounted navigation device according to a first embodiment of the present invention.

FIG. 2 is a diagram showing a format example of map data used in the embodiment.

FIG. 3 is a diagram illustrating an example of a format of map data according to the embodiment in another expression.

FIG. 4 is a diagram showing an example of a data format of management information in map data in one layer according to the embodiment.

FIG. 5 is a model diagram for explaining an algorithm when performing a route search in the embodiment.

FIG. 6 is a diagram illustrating an operation of shifting from a lower hierarchy to an upper hierarchy using a road node in the embodiment.

FIG. 7 is a view for explaining a transition operation from a lower hierarchy to an upper hierarchy using a road link in the embodiment.

FIG. 8 is a data configuration diagram showing a correspondence between a link in lower-layer map data and a link in upper-layer map data in the embodiment.

FIG. 9 is a diagram illustrating a route search method in a conventional navigation device.

[Explanation of symbols]

 Reference Signs List 1 direction sensor 2 distance sensor 3 sensor signal 4 sensor signal processing unit 5 GPS receiver 6 CD-ROM driver 7 CD-ROM 8 display / operation unit 8A liquid crystal display 9 device body 10 CPU (central processing unit) 11 ROM (read only memory) 12) Memory (DRAM) 13 Backup memory (SRAM) 14 Memory (Kanji, font ROM) 15 Image processor 16 Memory (VRAM) 17 RGB conversion circuit 18 Communication interface 20 Disk label 21 Drawing parameter 22 Drawing management information 23, 24 Figure 31 Overall Configuration of Map Data 32 Management Information 33 Upper Map Data 34 Middle Map Data 35 Lower Map Data 36 Table of Upper Map Address and Size 37 Table of Middle Map Address and Size Le 38 Table 40 address lower address map and the size and size table 41 the node table 42 link table 43 node coordinate table 44 linked shape table

────────────────────────────────────────────────── ───

[Procedure amendment]

[Submission date] June 17, 1999 (1999.6.1
7)

[Procedure amendment 1]

[Document name to be amended] Drawing

[Correction target item name] Fig. 1

[Correction method] Change

[Correction contents]

FIG.

[Procedure amendment 2]

[Document name to be amended] Drawing

[Correction target item name] Fig. 2

[Correction method] Change

[Correction contents]

FIG. 2

[Procedure amendment 3]

[Document name to be amended] Drawing

[Correction target item name] Figure 3

[Correction method] Change

[Correction contents]

FIG. 3

[Procedure amendment 4]

[Document name to be amended] Drawing

[Correction target item name] Fig. 4

[Correction method] Change

[Correction contents]

FIG. 4

[Procedure amendment 5]

[Document name to be amended] Drawing

[Correction target item name] Fig. 5

[Correction method] Change

[Correction contents]

FIG. 5

[Procedure amendment 6]

[Document name to be amended] Drawing

[Correction target item name] Fig. 7

[Correction method] Change

[Correction contents]

FIG. 7

[Procedure amendment 7]

[Document name to be amended] Drawing

[Correction target item name] Fig. 8

[Correction method] Change

[Correction contents]

FIG. 8

 ──────────────────────────────────────────────────続 き Continuation of the front page (71) Applicant 000004260 DENSO CORPORATION 1-1-1, Showa-cho, Kariya-shi, Aichi (71) Applicant 000237592 FUJITSU TEN LIMITED 1-2-28, Goshodori, Hyogo-ku, Kobe, Hyogo (72) Inventor Keiri Owada Matsushita Communication Industrial Co., Ltd., 4-3-1 Tsunashimahigashi, Kohoku-ku, Yokohama-shi, Kanagawa Prefecture (72) Inventor Takeshi Yagyu 1006 Kazuma Kazuma, Kadoma City, Osaka Prefecture Matsushita Electric Industrial Co., Ltd. 72) Inventor Yasuhiro Toyama 6-18 Harayama, Okamachi, Okazaki City, Aichi Prefecture Inside Aisin AW Co., Ltd. (72) Inventor Hidenobu Suzuki 1 Toyota Town, Toyota City, Aichi Prefecture Toyota Motor Corporation (72) Inventor Hironobu Sugimoto 1 Toyota Town, Toyota City, Aichi Prefecture Inside Toyota Motor Corporation (72) Inventor Hidetoshi Fujimoto Kariya, Aichi Prefecture 1-1-1, Showa-cho, DENSO Corporation (72) Inventor Hiroshi Takeuchi 1-2-2, Goshodori, Hyogo-ku, Kobe, Hyogo Prefecture Inside Fujitsu Ten Limited (72) Inventor Atsushi Ichimura Hyogo, Kobe City, Hyogo Prefecture 1-2-2, Gosho-dori Ward, Fujitsu Ten Co., Ltd. F-term (reference) 2C032 HB06 HB22 HC08 HD16 HD21 2F029 AA02 AB01 AB07 AB13 AC08 AC14 AC16 5H180 AA01 BB13 CC12 FF04 FF05 FF22 FF27 FF33 FF35 FF38 FF38

Claims (3)

[Claims] 1. A navigation device that searches for a route from a designated departure point to a destination, sets a route, and provides route guidance according to the set route, based on the information amount of a road network. A storage unit for storing map data having connection information of each layer while expanding the layers from a lower layer having a large amount of road network information to an upper layer having a small amount of road network information, and A hierarchy including a designated departure point and a destination is specified, a route search is performed up to a point where the specified hierarchy is connected to a higher hierarchy based on the connection information between the respective hierarchies, and further moved to a higher hierarchy to move to the higher hierarchy. Route search means for performing a route search from the departure point to the destination by repeatedly performing a route search from the connecting point; For links extending to lower layers, a link of map data of the upper layer is described in association with a link of map data of the lower layer, and when searching for a route of the lower layer, the link of the lower layer corresponds to a link of the upper layer. A navigation device wherein a route search is shifted from a lower hierarchy to an upper hierarchy. 2. For a link extending between upper and lower layers, the link shape of the map data of the upper layer is stored in the map data of the lower layer, and when the route search is shifted from the lower layer to the upper layer, the corresponding link of the upper layer is stored. 2. The navigation device according to claim 1, wherein the route search process can be completed up to both ends of the link. 3. In order to perform a route search, dedicated road shape data is stored as lower / higher level road shapes in correspondence to lower nodes on lower map data.
2. The navigation device according to claim 1, wherein a route shape is displayed using the dedicated road shape data.