JP3547644B2 - Navigation device - Google Patents

Description

[0001]
TECHNICAL 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 unit at high speed.
[0002]
[Prior art]
The in-vehicle navigation device performs route guidance to a destination for a driver whose geography is unknown. This in-vehicle navigation device is configured to detect a correlation between a traveling locus road shape obtained from a speed sensor and a direction sensor, or a vehicle position detected by decoding an absolute position of a Global Positioning System (hereinafter referred to as GPS). The user is informed of the vehicle position by displaying the map. The user sets a route from the departure place to the destination by inputting a departure place and a destination before traveling on such a navigation apparatus, 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.
[0003]
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 subject to the route search increases accordingly. 2. Description of the Related Art Techniques for preventing an increase in calculation time required for a route search and a storage capacity of a memory used for a search process 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 the designated departure point and destination is specified, and based on the connection information between the layers, the specified layer is moved to a higher layer. In some cases, a route search is performed up to a connection point or a portion, and the process is further shifted to a higher hierarchy to repeatedly perform a route search from the connection point (portion).
[0004]
As a conventional technique for performing a route search based on such hierarchically structured map data, for example, there is one shown in FIG. 9, reference numeral 101 denotes an upper layer. The upper layer 101 is a map of a main arterial road network having intersection numbers a, b, c,... And constitutes one block A. Reference numeral 102 denotes a lower layer. The 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 road between the blocks is pseudo-intersection so that the processing unit 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 amount of each of the blocks A, B, C, D,.
[0005]
A route search method in a navigation device having such a map data structure will be described. For example, it is assumed that the departure point is the intersection number c in the block B of the lower layer, and the destination is the intersection number d in the block D of the lower layer. In this case, first, in the 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 a route to the intersection number d (the intersection number a of the block A corresponds to the upper layer 101). Search for and go 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 starting point to the destination is performed.
[0006]
[Problems to be solved by the invention]
However, in the above-described conventional on-vehicle navigation device, according to the method of Conventional Example 1, when a route shape is obtained from lower-level map data, a link is not divided at an intermediate portion thereof. Since the number of interpolation points of the link shape is unnecessarily large with respect to the resolution for display and the number of links is also plural, the data amount of the display data may increase, which hinders speeding up of route guidance display. Was a factor.
[0007]
SUMMARY OF THE INVENTION The present invention solves such a conventional problem, and provides 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 unit at high speed. The purpose is to provide.
[0008]
[Means for Solving the Problems]
In order to achieve the above object, the present invention develops a map data into a hierarchical structure based on the information amount of a road network, and expands a hierarchy from a lower hierarchy with more information on the road network to an upper hierarchy with less information on the road network. And a data structure having connection information that associates a common road between the respective layers. Based on the map data, a layer including the designated departure point and destination is specified, and the connection information between the respective layers is specified. Based on the specified hierarchy, a route search is performed up to a point connecting to the upper hierarchy, and furthermore, a transition is made to the upper hierarchy to repeatedly perform a route search from the connection point, and the map data includes upper / lower hierarchy. Are described by associating the link of the map data of the upper hierarchy with the link of the map data of the lower hierarchy, and linking the link shape of the map data of the upper hierarchy to the lower hierarchy. Stored in the map data, and when searching for a route in the lower hierarchy, when the link in the lower hierarchy corresponds to a link in the upper hierarchy, shift the route search from the lower hierarchy to the upper hierarchy, and shift the route search from the lower hierarchy to the upper hierarchy In this case, the point is that the route search processing can be completed up to both ends of the corresponding link in the upper hierarchy. Further, as another aspect of the present invention, in order to perform a route search, a link of map data of a higher hierarchy corresponding to a link of map data of a lower hierarchy as a link shape to map data of a lower hierarchy, The destination node of the link of the map data is described, and the route shape can be displayed based on this description.
[0009]
In the present invention, road shapes (link shapes) extending over upper / lower layers are stored in map data. The conditions for that are:
(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 accuracy as the link shape of the upper layer.
That is.
[0010]
With this configuration, not only the route search is performed at high speed, but also the route obtained as a result of the route search can be displayed at high speed. Can be speeded up.
[0011]
BEST MODE FOR CARRYING OUT THE INVENTION
Hereinafter, embodiments of the present invention will be described 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 an azimuth sensor, and this azimuth sensor 1 uses an optical gyro for detecting an absolute traveling azimuth of an automobile. Reference numeral 2 denotes a distance sensor that generates a pulse according to the number of rotations of the wheels, and 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 GPS receiver 5 receives radio waves transmitted from a plurality of satellites and calculates reception points. (Latitude, longitude) can be obtained. 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 provided in the vehicle interior. The display / operation unit 8 is provided on a liquid crystal display 8A for displaying a map and the current traveling position and direction of the automobile in color, and is provided on a front surface of the liquid crystal display 8A. A switch for instructing enlargement or reduction of the display map, a switch for instructing a route search, a switch for selecting a destination from the place names displayed on the liquid crystal display 8A, and the like. Is provided. Reference numeral 9 denotes an apparatus main body, which is installed in a trunk room of an automobile.
[0012]
Next, the configuration of the apparatus main body 9 will be described. Reference numeral 10 denotes a CPU (Central Processing Unit) for performing various calculations, 11 denotes a ROM (Read Only Memory) in which programs for various calculations performed by the CPU 10 are stored, 12 denotes an azimuth sensor 1, a distance sensor 2, a GPS receiver 5, a CD A memory (DRAM) 13 for storing data from the ROM driver 6 and the like and calculation results of the CPU 10, etc., and a backup 13 for holding necessary data even when power supply to the apparatus main body 9 is stopped. A memory (SRAM) 14 is a memory (kanji, font ROM) in which patterns of characters and symbols to be displayed on the liquid crystal display 8A are stored, and 15 is a display image formed based on map data and current position data of the vehicle. An image processor 16 for executing map data, current position data and kanji, A memory (VRAM) for synthesizing kanji characters and fonts such as street names and road names such as expressways output from the print ROM 14 and storing an image to be displayed on the liquid crystal display 8A, and 17 converts the output data of the VRAM 16 into color signals. A color signal is output from the RGB conversion circuit 17 to the liquid crystal display 8A. 18 is a communication interface. The liquid crystal display 8A, highways, other roads street name is displayed together with such facility name, so that the vehicle mark for displaying a further current position of the own vehicle on the display map is displayed.
[0013]
FIG. 2 is a diagram showing an example of the format of map data stored in the CD-ROM 7. In FIG. 2, reference numeral 20 denotes a disc label, reference numeral 21 denotes drawing parameters, reference numeral 22 denotes map leaf management information, reference numerals 23 and 24 denote map leaves (maps), and reference numeral 25 denotes a route map storing map data for route search. The leaves 23 and 24 store background data, character data, road data, and the like, and store data for each unit map obtained by dividing a topographical map of the whole of Japan by latitude and longitude. The map data has a hierarchical structure by setting a map leaf (level 2) 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. The map display levels A, B, and C describe B more than A and C more 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 of each map display level into a plurality of areas, and 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, facility names, and the like displayed on a map, and the background layer stores data for drawing roads, facilities, and the like, such as roads, facilities, seas, and backgrounds 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.
[0014]
FIG. 3 is a diagram illustrating an example of a 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, a middle map address and size table 37, and a lower map address and size table 38. As the breakdown of the upper map data, the upper map data is No. 1, No. 2, No. The middle map data is stored as No. 3,... 1, No. 2, No. .., And as a breakdown of the lower-level map data, the lower-level map data 1, No. 2, No. 3, etc. are stored.
[0015]
FIG. 4 is a diagram showing an example of a data format of management information in route map data in one hierarchy. This 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 the 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.
[0016]
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 and n5 represent nodes, respectively. 1, No. 2, No. Are represented by 3,. These nodes n1, n2, n3, n4, and n5 correspond to, for example, intersections on a map. 4, l, l2, l3, l4, and l5 represent links, respectively, and the link data No. of the link table 42 in FIG. 1, No. 2, No. Are represented by 3,. These links l1, l2, l3, l4, and l5 correspond to, for example, intersections on a map and roads between the intersections.
[0017]
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 acquired from the link table 42 in FIG. In the example of FIG. 5, since three links 11, 12, and 11 are connected to the node n1, the node data No. 1 to the link data No. of the link table 42. 1, No. 2, No. Data acquisition is carried out to 3.
[0018]
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 example, the link data No. The connection destination of the link data No. 1 is the node l2. The connection destination of No. 2 is the node 13 and the link data No. The connection destination of 3 is the node 13. Therefore, the link data No. 1 to the node data No. of the node table 41. 2 is obtained, and the link data No. 2 in the link table 42 is obtained. 2 to the node data No. of the node table 41. Data acquisition is carried out to 3.
[0019]
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 then the process returns to the second stage.
[0020]
The above processing is repeatedly performed 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, it is determined that 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 ends.
[0021]
Next, the operation for shifting from the lower-level map data to the upper-level map data in the above algorithm will be described. FIG. 6 is a diagram illustrating an operation of shifting from a lower hierarchy to an upper hierarchy using a road node. In FIG. 6, the map data No. m, the node data number of the node k is No. k is set. In the lower-level map data, the node data number of the node p of the map data is No. p is set. In the node data in the node table 41 of the lower layer map data, the node p in the lower layer map data is the map data No. of the upper layer. m of the node number No. It is described that k corresponds. 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 has been completed in the lower layer map data is transferred through nodes (No. p of the lower layer and No. k of the upper layer) that are present in both the upper layer and the lower layer. Then, after transferring the state of the node that has been searched in the lower hierarchy to the map data in the upper hierarchy, the route search is advanced in the map data in the upper hierarchy, thereby completing the shift of the route search to the upper hierarchy.
[0022]
FIG. 7 is a diagram illustrating an operation of shifting 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-level map data correspond to the upper-level map data Nos. m link number No. 2 and the destination node of the link is node No. a, No. b. As a result, the state in which the route search has been completed in the map data of the lower hierarchy is transferred as the connection information, the link existing in common to the upper hierarchy and the lower hierarchy. 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]
【The invention's effect】
As is clear from the above description, the present invention provides a vehicle-mounted navigation device with map data 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 hierarchies to lower hierarchies, it has a data structure with connection information that associates common roads between the hierarchies, and based on this map data, specifies the hierarchies including the designated departure point and destination, Based on the connection information between the respective layers, a route search is performed up to a point connected to a higher layer in the specified layer, and furthermore, a higher level is searched for and a route search from the connection point is repeatedly performed. the upper / lower layer over the link, is described in association with the link of the map data of the upper layer to the link of the map data of the lower layer, the upper layer Storing link shape of the map data of the lower layer in the map data, in route search in the lower hierarchy, and link of the lower layer proceeds from the lower hierarchical route search when corresponding to link the upper layer to the upper layer, the lower When the route search is shifted from the hierarchy to the upper hierarchy, the route search processing can be completed to both ends of the corresponding link in the upper hierarchy, so that not only the route search is performed at high speed but also the route obtained as a result of the route search. Can also be displayed at a high speed when displaying, and the speed of the entire route guidance processing operation by the route search can be increased.
[Brief description of the drawings]
FIG. 1 is a block diagram showing a configuration of an on-vehicle 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. 4 is a diagram illustrating an example of a format of map data according to another embodiment in another expression. FIG. 4 is a diagram illustrating an example of a data format of management information in map data in one layer in the embodiment. FIG. 6 is a model diagram for explaining an algorithm when performing a route search in the embodiment. FIG. 6 is a diagram for explaining a transition operation from a lower hierarchy to an upper hierarchy using a road node in the embodiment. FIG. 8 is a diagram for explaining an operation of shifting from a lower hierarchy to an upper hierarchy using a road link in the embodiment. Figure [EXPLANATION OF SYMBOLS] describing the route search method in a data structure diagram 9 conventional navigation device showing a correspondence between the link in the map data links and the upper layer in the map data layers
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 Main unit 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 Fig. Leaf management information 23, 24 Fig. 31 Map data overall configuration 32 Management information 33 Upper map data 34 Middle map data 35 Lower map data 36 Upper Map address and size table 37 Middle map address and size table 38 Lower map address and size table 40 Address and size table 41 Node table 42 Link table 43 Node coordinate table 44 Link shape table

Claims (2)

A navigation device that performs a route search from a designated departure point to a destination, sets a route, and provides route guidance according to the set route. The navigation device has a hierarchical structure based on the information amount of the road network. Storage means for expanding a hierarchy from a lower hierarchy having a large amount of network information to an upper hierarchy having a small amount of road network information, and storing map data having connection information of each hierarchy; and the designated departure point based on the map data. And a hierarchy including the destination is specified, and based on the connection information between the respective hierarchies, a route search is performed up to a point where the specified hierarchy is connected to a higher hierarchy, and further moved to a higher hierarchy to move from the connected point to a higher hierarchy. Route search means for performing a route search from the departure point to the destination by repeatedly performing the route search, and the map data includes upper / lower layers. For the link to be passed, 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 link shape of the map data of the upper layer is stored in the map data of the lower layer,
At the time of route search of the lower layer, when the link of the lower layer corresponds to the link of the upper layer, the route search is shifted from the lower layer to the upper layer, and when the route search is shifted from the lower layer to the upper layer, the route search of the upper layer is performed. A navigation device wherein a route search process can be completed up to both ends of a corresponding link. In order to perform a route search, a link of the map data of the upper layer corresponding to the link of the map data of the lower layer, and a destination node of the link of the map data of the upper layer, as a link shape, are added to the map data of the lower layer. 2. The navigation device according to claim 1, wherein a route shape is displayed based on the description.

Images