JP3967187B2 - Map data creation device - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a map data creation device and an information recording medium for creating map data used when performing route search processing in a navigation device or the like.
[0002]
[Prior art]
In general, a vehicle-mounted navigation device has a route search function for searching for an optimum route from a current position of a vehicle to a predetermined destination. According to this route search function, the route with the lowest cost connecting from the starting point to the destination using map data is automatically searched by performing a simulation such as Dijkstra method or horizontal search (BFS) method. The route is stored as a guidance route. And while driving the vehicle, draw this guidance route on the map screen thickly with a different color from other roads, or enlarge this intersection when the vehicle approaches within a certain distance of the intersection where the course should be changed A route guidance operation for guiding the driver to the destination is realized by displaying an arrow indicating the traveling direction.
[0003]
In particular, the route search function described above is performed after the driver gets into the vehicle, and it is desirable that the processing is completed before the vehicle travels. Yes. For example, Japanese Patent Laid-Open No. 9-218047 discloses a “vehicle route calculation device that speeds up route search processing by using a departure area route network in which a route from a departure area to a destination area is calculated in advance. Is disclosed. This departure point area route network is a logical sum of the results of the actual route search between the departure point area including the current position of the vehicle and all other destination areas. This departure area network is preliminarily calculated off-line by EWS and stored in a CD-ROM or the like, read out as needed and stored in a working memory, and between a predetermined departure place and a destination. Used for route search processing.
[0004]
[Problems to be solved by the invention]
By the way, the departure point area route network used in the route search process disclosed in the above-mentioned Japanese Patent Application Laid-Open No. 9-218047 is created for all the destination areas. When the route search processing is performed on the target, there is a lot of waste, and there is a problem that the amount of data read from the CD-ROM or the like and transferred to the working memory increases.
[0005]
In order to reduce the number of links that are subject to the route search process, a pruning zone is provided in the vicinity of the departure area or the destination area, so all links included in this pruning zone are targeted. Compared to the route search process, the optimum link may be excluded from the process. In addition, a departure area route network is created so as to connect the departure area and the destination area. If attention is paid to one departure area and one destination area, there is one route connecting these areas. Or it is limited to two, and other routes are excluded at the stage of creating the departure area route network, so the position of the departure place in the departure area or the position of the destination in the destination area Depending on the case, the other route may be the optimum route with the lowest cost, but this optimum route is not selected in the actual route search process. As described above, in the case where the departure point area route network is used in the conventional vehicle route calculation device, there is a problem that an optimum route may not be searched.
[0006]
The present invention was created in view of the above points, and its purpose is to create a map data creation device capable of creating map data capable of reducing the amount of data read in order to perform an optimum route search, and It is to provide an information recording medium.
[0007]
[Means for Solving the Problems]
In order to solve the above-described problem, the map data creation apparatus of the present invention includes a level 1 area and a level 2 area that are hierarchized, and a dedicated network prepared for each combination of the two level 2 areas. The map data of the hierarchical structure which has has been created, paying attention to one level 1 area, and using the link included in the level 1 area, actually extending the search branch from this focused level 1 area, A route that reaches a higher-level node included in the level 2 area including the level 1 area of interest or in another level 2 area adjacent to the level 2 area is detected, and is associated with the level 1 area of interest. Focusing on the first route information creating means for creating the first route information and the two level 2 areas, the route connecting these level 2 areas is actually used by using the link included in the level 2 area. Search to, and a second path information generation means for generating a second path information corresponding to a dedicated network which is prepared for a combination of the two level-2 areas focusing. By using the first route information included in the map data created using the map data creation device of the present invention, the search branch can be surely extended to the nodes in the level 2 region, so that the optimum route search can be performed. It becomes possible to do. In addition, since the first route information is associated with the original level 1 region that extends the search branch, when the map data of the part necessary for the route search process is read from the CD-ROM or the like. When reading the data of the level 1 area including the departure place and the destination, only the first route information corresponding to the level 1 area can be read together, and the amount of data to be read and the number of times of reading can be reduced. It becomes possible.
[0008]
In addition, the first route information creation unit described above includes a logical mesh generation unit that divides a target level 1 region into a predetermined number and generates a logical mesh corresponding to each divided region; For each of the logical meshes generated by the means, by searching for a path connecting between the link across the boundary of the logical mesh and the boundary node of the other level 2 area other than the level 2 area including the logical mesh For the result of detecting the route to the upper node, by changing the other level 2 area and taking the logical sum, it always reaches the upper node when the search branch is extended from any point in the logical mesh. The first path information for specifying the upper layer transition search range rectangle that is a range that can be reached and for specifying the route to reach the upper node And an upper transition search range rectangle forming means for forming. When searching for a route to the upper node included in the level 2 area using the first route information, it is possible to reliably extract the upper node by searching within the upper layer transition search range rectangle. Thus, efficient route search processing becomes possible.
[0009]
In addition, the above-described upper layer transition search range rectangle creating means may include a plurality of virtual meshes obtained by dividing the level 2 region into a predetermined number when the logical mesh to be searched and the level 2 region overlap or approach each other. It is desirable to search for a path connecting each of the plurality of virtual meshes and the logical mesh instead of the level 2 region. As a result, it is possible to create map data capable of performing efficient route search processing even when the departure point and destination to be subjected to route search processing are close to each other.
[0010]
In addition, focusing on the two logical meshes described above, when a route connecting these two logical meshes is actually searched, and there is a link included only in the level 1 area in the searched route, this link is set to the level. It is desirable to further include an upgrade processing means for performing a process of upgrading to a link included in the two areas. As a result, the link included in the level 1 area can be upgraded to the link in the level 2 area, and when the dedicated network is created by the second path information creating means, it can be included in the path constituting the dedicated network. Therefore, map data capable of performing an optimum route search process can be created.
[0011]
Each of the above-described logical meshes further includes level 1 search range setting means for setting a range in which the number of included nodes and links is equal to or greater than a predetermined value as a level 1 search range. It is desirable to perform upgrade processing for links that are paths that connect logical meshes and that are not included in the level 1 search range corresponding to each of these two logical meshes. Since the number of links and the number of nodes are greatly different even for level 1 areas and logical meshes of the same size, by setting and using a level 1 search range in which the number of links is almost constant, the number of links is almost constant. Can be upgraded, and map data free from quality bias due to regional differences can be created.
[0012]
In addition, the second route information creation means described above searches for a route connecting two level 2 areas using a plurality of search conditions, and each link constituting the route obtained as a result of the search corresponds to which search condition. It is desirable to create the second route information including the search condition information indicating whether or not This makes it possible to create map data that can reduce the number of links to be processed when performing a search process using a dedicated network.
[0013]
Further, the second route information creating means described above searches for a route connecting each of the two level 2 areas and creates second route information corresponding to a route constituting the dedicated network, It is desirable to provide aggregated link creating means for creating a single aggregated link by aggregating a plurality of links that satisfy a specific condition for a route included in the dedicated network. As a result, it is possible to create map data that can further reduce the number of links to be processed when performing a search process using a dedicated network.
[0014]
The information recording medium of the present invention records the first and second route information created by the map data creation device described above, and the first and second route information performs a route search process. Can be read. By performing the route search process using the map data recorded on the information recording medium of the present invention, it is possible to speed up the process by reducing the amount of data to be processed and extract the optimum route.
[0015]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, a map data creation device according to an embodiment to which the present invention is applied will be described with reference to the drawings.
FIG. 1 is a diagram illustrating a configuration of a map data creation device according to an embodiment. As shown in FIG. 1, the map data creation device 10 of the present embodiment has a configuration as a general computer, and includes a CPU 12, a ROM 14, a RAM 16, and a hard disk device (HD) 18. By executing a predetermined map data editing program stored in the hard disk device 18, the map data creating operation in this embodiment is performed.
[0016]
The hard disk device 18 stores map data 20 created using the map data creation device 10 of this embodiment. The hard disk device 18 is an information recording medium on which the map data 20 is recorded. The hard disk device 18 is connected to an in-vehicle navigation device or a personal computer in which map software having a route search function is installed. Usually, the contents of the map data 20 are copied to an information storage medium suitable for distribution such as a DVD-ROM or a CD-ROM.
[0017]
The map data 20 used in the present embodiment is read out in units of rectangular regions (regions) divided by predetermined longitude and latitude. In addition, this map data is hierarchized at five levels according to the level of detail of road information corresponding to the display scale, and the more detailed the map data is, the lower the level corresponding to the most detailed display (the lowest is level 1). Road information is included. Further, a region having a smaller area is set for the lower-level map data, and conversely, a region having a larger area is set for the higher-level map data. In this embodiment, five types of regions of level 1, level 2, level 3, level 4, and level 5 are set in order from the lower side. Among these, map data of the regions of level 1 and 2 is set. And a route search process using map data of a dedicated network prepared separately.
[0018]
FIG. 2 is a diagram showing a format of the map data 20 of the present embodiment. As shown in FIG. 2, the map data 20 of the present embodiment includes a basic part of each region of levels 1 to 5 and a dedicated network. Each basic part of the level 1-5 region includes link information and node information necessary for map matching, etc. in addition to the map drawing information necessary for performing map display processing corresponding to each level region. It is. The dedicated network stores route information for specifying a route connecting these two regions in correspondence with any combination of two level 2 regions.
[0019]
In addition, among the level 1 to 5 regions and the dedicated network described above, each of the levels 1 and 2 and the dedicated network is provided with an extension unit necessary for performing route search processing at high speed.
Specifically, an “extended path calculation adjacent data frame” is added to the basic part of the level 1 region as an extended part. These basic portions and the “extended route calculation adjacent data frame” are read as a set of map data when, for example, the map data of a specific level 1 region including the starting point of the route search process is read.
[0020]
Further, the “address data frame to the dedicated network” is added as an extension to the basic part of the level 2 region. These basic part and “address data frame to dedicated network” are read as a set of map data when the map data of a specific level 2 region is read.
[0021]
In the dedicated network, a “boundary node compatible data frame”, an “upper node compatible data frame”, an “aggregated link expanded data frame”, and an “upper layer transition search range data frame” are added as extensions. By specifying a combination of two level 2 regions and designating a dedicated network corresponding to this combination, a “boundary node compatible data frame”, “higher node compatible data frame”, together with route information connecting between the level 2 regions, “Aggregated link expansion data frame” and “upper layer transition search range data frame” are read as a set of map data.
[0022]
In the map data described above, the contents corresponding to the basic parts of the level 1 to 5 regions are prepared in advance, and the map data creating apparatus 10 of the present embodiment further includes the basic parts of the levels 1 and 2 in this. It is assumed that map data of the dedicated network and each extension unit is created using the map data. Details of the respective expansion units corresponding to the above-described level 1 and 2 regions and the dedicated network will be described later.
[0023]
FIG. 3 is a block diagram showing the map data creation device 10 of the present embodiment in functional blocks. The map data creation device 10 of the present embodiment shown in FIG. 3 creates a logical mesh generation unit 30, a level 1 search range setting unit 32, and an upgrade processing unit 34 in order to create map data 20 including a dedicated network and each expansion unit. The upper layer transition search range rectangle creating unit 36, the dedicated network creating unit 38, and the aggregated link creating unit 40 are configured.
[0024]
The logical mesh generation unit 30 and the upper layer transition search range rectangle creation unit 36 described above are the first route information creation unit, the logical mesh generation unit 30 is the logical mesh generation unit, and the upper layer transition search range rectangle creation unit 36 is the upper layer transition search. Each corresponds to a range rectangle creating means. The dedicated network creation unit 38 and the aggregated link creation unit 40 correspond to the second route information creation unit, the dedicated network creation unit 38 corresponds to the dedicated network creation unit, and the aggregated link creation unit 40 corresponds to the aggregated link creation unit. . Further, the level 1 search range setting unit 32 corresponds to the level 1 search range setting unit, and the upgrade processing unit 34 corresponds to the upgrade processing unit.
[0025]
The map data creation device 10 of this embodiment has such a configuration, and the detailed operation will be described next. FIG. 4 is a flowchart showing an operation procedure of the map data creation device 10 of the present embodiment.
Generation of logical mesh (step 100)
First, the logical mesh generation unit 30 performs a process of generating a logical mesh for each level 1 region. Here, the logical mesh is a partitioned area obtained by dividing a level 1 region into a predetermined number.
[0026]
FIG. 5 is a diagram illustrating a specific example of a logical mesh. In the example shown in FIG. 5, for example, the vertical direction and the horizontal direction of one level 1 region A are each divided into four equal parts, and 16 logical meshes B are generated corresponding to the entire level 1 region A.
Level 1 search range setting (step 101)
Next, the level 1 search range setting unit 32 sets the level 1 search range for all the logical meshes generated in the process of step 100 described above. Here, the level 1 search range is a range in which a predetermined number of links are included around the logical mesh, and is set for each logical mesh.
[0027]
FIG. 6 is a diagram showing a specific example of the level 1 search range. As shown in FIG. 6, the distance L that expands the top, bottom, left, and right of the logical mesh B is increased by 1 km, and the number of links included in the expanded range is counted each time, and this count value is a predetermined number (for example, 1000). ) Is exceeded. If the count value does not exceed the predetermined number, the distance L is further increased by 1 km, and the same counting operation and determination operation are repeated. A rectangular area having a size determined by the distance L when the count value exceeds the predetermined number is set as the level 1 search range P. Of course, since the level 1 search range P is set for each logical mesh, the size of the level 1 search range P is generally different for each logical mesh B.
[0028]
Link upgrade process (step 102)
Next, the upgrade processing unit 34 extracts links that can be reduced in cost from the links that are included in the level 1 region but are not included in the level 2 region, and change from the level 1 to the level 2 link. Perform the upgrade process. Since links in both Level 1 and 2 regions are generally wider than links in Level 1 regions only, the costs under various conditions are lower than other narrow streets. However, there is a case where the cost of the entire route is smaller when traveling on a link included only in the level 1 region like a wide-area farm road. In the upgrade process, a link included only in such a level 1 region is extracted and added to the basic part of the level 2 region. As a result, even if a search process is performed for a link included in the level 2 region, a link that is conventionally included only in the level 1 region and can be reduced in cost is used. The route search process used can be performed.
[0029]
7 and 8 are diagrams illustrating a specific example of the upgrade process. First, the upgrade processing unit 34 extracts the representative node D from the nodes included in the logical mesh B to be processed. As the representative node D, a node closest to the center of the logical mesh B is selected. In FIG. 7, the representative node D is hatched and distinguished from other nodes (white circles). In this way, the representative node D is set for each of all the logical meshes B included in all the level 1 regions.
[0030]
Next, the upgrade processing unit 34 uses the Dijkstra method for all the representative nodes D included in the other logical mesh B starting from the representative node D of one logical mesh B, and is included in the level 1 region. The search is performed until the search branch by the link cannot be extended. There are three types of search (conditions): recommended route (time priority), general road priority, and road width priority. The setting of the search type is an example, and for example, other search types may be included, or one or two of the three types of search conditions may be used. Such search processing is performed starting from the representative nodes D of all the logical meshes.
[0031]
After the search processing between all the representative nodes is completed in this way, the upgrade processing unit 34 extracts the upgrade link using the search result. The upgrade link is extracted using the level 1 search range P set in the processing of step 101 described above. In this extraction process, as shown in FIG. 8, focusing on search links connecting two representative nodes D included in each of the two logical meshes B, they are included in the level 1 search range P corresponding to each logical mesh B. The range not to be upgraded is set as the upgrade range, and the link of the level 1 region included in the upgrade range is selected as the upgrade link.
[0032]
However, a link partially included in the level 1 search range P on the start representative node side of the route search is an upgrade link to level 2 if the start node viewed in the search direction is not in the level 1 search range. It shall be extracted. Further, a link partially including the route search destination representative node side is extracted as an upgraded link if the terminal node viewed in the search direction is not within the level 1 search range.
[0033]
After the extraction of the upgrade link to level 2 is completed for all the representative nodes in this way, the upgrade processing unit 34 performs a process of combining these extracted upgrade links.
FIG. 9 and FIG. 10 are diagrams illustrating specific examples of the upgrade link combining process. If the upgrade link extracted by the above-described upgrade process is originally included in the level 2 region and no new intersection is added in the middle as shown in FIG. 9, the extracted upgrade Instead of adopting the link, the link originally included in the level 2 region is used.
[0034]
In addition, the upgrade link extracted by the upgrade process described above is originally included in the level 2 region, but as shown in FIG. 10, when an intersection occurs in the middle, a plurality of upgrades up to the intersection are performed. A process of separately combining a link and a plurality of upgraded links existing ahead of the intersection is performed.
[0035]
In this way, the upgrade processing unit 34 extracts the upgrade links from the links included in the level 1 region, and when the join processing is performed, the joined links are not subjected to the join processing. If so, the original upgrade link is added to the basic part of the level 2 region as a link of the level 2 region.
[0036]
As a condition for linking Level 1 region links that do not originally exist in Level 2,
-The link ID can be expressed as a difference,
-The link cost record has the same "link attribute"
・ The attributes of the paid section and free section are the same,
・ Bypass flag is the same,
・ Two-way difference (no branching).
[0037]
Level 1 upper layer transition search range rectangle setting process (step 103)
Conventionally, the route to the node included in the level 2 region is searched for using the link of the level 1 region around the departure place, and further the hierarchy using the link of the level 2 region for a destination in a remote place There is known a method for performing a search in an automatic manner. In this method, the number of search links, the number of extracted upper nodes, the distance, and the like are conventionally used as the search end condition when the search branch is extended from the level 1 region including the starting point of the route search to the level 2 region. .
[0038]
Further, when searching for a route to a node included in the level 2 region using such a method, one level is used to reduce the number of times map data is read from a CD-ROM or the like and to speed up the processing. There is a method of including the link data of the adjacent level 1 region satisfying the search end condition in the map data of 1 region.
[0039]
However, the extent to which the search branch is extended to reach the node of the level 2 region is not constant when the road density is different as in an urban area or a suburb. Therefore, if a large number of search links satisfying the search end condition are set so as to be able to cope with all road densities, a search is performed for unnecessary links, and processing is wasted. On the other hand, if the number of search links that satisfy the search end condition is set to be small, the number of links to be searched decreases and an optimal route cannot be searched.
[0040]
In this embodiment, by simply reading the map data (basic part and extension part) of one level 1 region, the link that can reach the node of the level 2 region by reliably following the optimum link is extracted. Yes. Hereinafter, a range including such a link is referred to as a “level 1 upper layer transition search range rectangle”.
[0041]
This level 1 upper layer transition search range rectangle is created using the results of actual search processing performed on all virtual meshes, focusing on each logical mesh. Here, the “virtual mesh” basically corresponds to the level 2 region. However, if the level 2 region containing the logical mesh of interest and the level 2 region to be searched are close or the same, the level 2 region to be searched is divided and each divided region is divided. Is set as a virtual mesh.
[0042]
The upper layer transition search range rectangle creation unit 36 searches for a virtual mesh corresponding to a level 2 region to be searched or a virtual mesh corresponding to a divided region of the level 2 region from one logical mesh of interest.
FIG. 11 is a diagram illustrating a specific example when a search is performed from one logical mesh B to a virtual mesh C corresponding to the level 2 region. This search is performed with respect to each of the forward direction and the reverse direction from the logical mesh B (the direction from the departure point to the destination is the forward direction, and the reverse direction is the direction from the destination to the departure point). Each search condition is given priority to general roads. The search target is a link that connects all the links that span the boundary of the logical mesh B and each boundary node of the virtual mesh C corresponding to the level 2 region. This search process is performed using the links included in the level 1 region.
[0043]
FIG. 12 is a diagram illustrating a specific example in the case where a search is performed from one logical mesh B to a virtual mesh C ′ corresponding to a divided region of the level 2 region. This search is performed from the logical mesh B for each of the forward direction and the reverse direction under the search conditions of the recommended route and the general road priority. This is the same as the case shown in FIG. The search target is a link that connects all of the links that straddle the boundary of the logical mesh B and a link that spans the largest rectangle that is slightly larger than the virtual mesh C ′.
[0044]
FIG. 13 is an explanatory diagram of the maximum rectangle Q set corresponding to the virtual mesh C ′ shown in FIG. When the entire level 2 region corresponds to one virtual mesh C, there is always a boundary node for a road that intersects the boundary. Therefore, the search target can be limited to this boundary node. However, when the level 2 region is equally divided into a predetermined number (for example, 16 divisions), a node does not always exist at the boundary of each divided region (it often does not exist). Further, when such a virtual mesh C ′ is used is a case where the logical mesh B to be searched and the virtual mesh C ′ are very close to each other, it is necessary to consider the level 1 search range to some extent. is there. For this reason, in this embodiment, when the virtual mesh C ′ generated corresponding to the divided region of the level 2 region is used, all the logical meshes B including all or part of the virtual mesh C ′ are included. The above-described maximum rectangle Q is set so as to include the level 1 search range P corresponding to each of these extracted logical meshes B while extracting.
[0045]
Specifically, the upper layer transition search range rectangle setting process is performed according to the following procedures (1) to (3).
(1) First, the upper layer transition search range rectangle creation unit 36 searches for a link extending over the boundary node of the virtual mesh or the maximum rectangle from one link extending over the boundary of the focused logical mesh B. In this search, a search result of the optimum route corresponding to the number of links spanning the boundary node of the virtual mesh or the maximum rectangle is obtained.
[0046]
(2) Next, for each search result, the upper layer transition search range rectangle creation unit 36 traces from the search end node on the virtual mesh side to the search start node on the logical mesh side, and from the link included in the level 2 region. Detects nodes in the path extending to links included only in the level 1 region.
[0047]
FIG. 14 is a diagram illustrating a relationship between a search result and a detection node. In FIG. 14, S indicates a search start node on the logical mesh side, E indicates a search end node on the virtual mesh side, and other numbers 0 to 4 indicate intermediate node numbers. Lv2 indicates a link included in the level 2 region, and Lv1 indicates a link included only in the level 1 region and not included in the level 2 region. In the example shown in FIG. 14, when tracing from the search end node E, the route extends from the link included in the level 2 region to the link included only in the level 1 region when passing through the node 2.
[0048]
The upper layer transition search range rectangle creation unit 36 extracts this node 2 corresponding to the search result shown in FIG. 14 and stores it as an upper transition node, and from this upper transition node to the search start node S on the logical mesh side. Keep the route. If no such upper transition node is found, the entire search result path (from the search end node E to the search start node S) is retained.
[0049]
The above-mentioned storage operation and path maintenance operation of the upper transition node were obtained from each link spanning the boundary of the logical mesh of interest, corresponding to each of the link spanning the boundary node of the virtual mesh or the maximum rectangle. Repeat for all search results. In addition, the same operation regarding (1) and (2) is repeated by changing the search condition.
[0050]
(3) With respect to one logical mesh B, when the holding operation for the paths corresponding to all the upper transition nodes is completed, the upper layer transition search range rectangle creation unit 36 includes all the retained paths. The maximum range is extracted, and an upper layer transition search range rectangle F corresponding to the combination of one logical mesh B and one virtual mesh of interest is set. Further, the data specifying the upper layer transition search range rectangle F set in this way is stored in the upper layer transition search range data frame included in the extension part of the dedicated network.
[0051]
The series of processes shown in the above (1) to (3) is performed for all combinations of the logical mesh and the virtual mesh.
FIG. 15 is a diagram showing a specific example of the upper layer transition search range rectangle set in this way. As shown in FIG. 15, when a large number of links c from a plurality of links a to a higher transition node b that straddle the boundary of the logical mesh B are detected, an upper layer transition search range rectangle that includes all these links c. F is set.
[0052]
Extended path calculation adjacent data frame creation process (step 104)
Next, the upper layer transition search range rectangle creation unit 36 creates an “extended path calculation adjacent data frame” that is an extension part of the level 1 region, and stores it in association with the corresponding level 1 region. The creation of this data is performed based on data relating to the route from the link straddling each logical mesh boundary to the upper transition node extracted when the above-described upper layer transition search range rectangle is set.
[0053]
FIG. 16 is an explanatory diagram of data stored in the extended path calculation adjacent data frame corresponding to the level 1 basic unit. In the example shown in FIG. 16, the level 1 region A is composed of 16 logical meshes B, and the route to the upper transition node extracted corresponding to all the logical meshes B is extracted. At this time, only the routes extending outside the level 1 region are extracted so as not to overlap. In FIG. 16, the branch portion extending around the level 1 region A indicates the path extracted in this way.
[0054]
FIG. 17 is a diagram showing a data format regarding a route extending to an adjacent level 1 region. For example, as shown in FIG. 17A, from the level 1 region to be processed (target region), adjacent level 1 regions 2 ^* , 3 ^* , 5 ^* (numbers with a superscript * are shown in the figure) In the case of creating data to be stored in the extended route calculation adjacent data frame, focusing on the route extending to (indicated by a round numeral in FIG. 17), as shown in FIG. The target region extension corresponding to regions 2 ^* , 3 ^* , 5 ^* is added as an extended path calculation adjacent data frame. As shown in FIG. 18, when there is a link a1 of the level 2 region connected to the upper node R, the data of this link a1 is also stored in the extended path calculation adjacent data frame (only in the level 1 region) (The link a2 included in is not stored). This is because it is possible to use the link regulation as it is when the upper level is shifted. In the example illustrated in FIG. 17, the target region extension created for the three level 1 regions 2 ^* , 3 ^* , and 5 ^* adjacent to the target region has been described. Generally, the target region extension is directly adjacent to the target region. Alternatively, there is a target region extension corresponding to each level 1 region adjacent to the outside, and these are all stored in the extended path calculation adjacent data frame of the target region.
[0055]
Processing for creating data frame corresponding to upper node (step 105)
Next, the upper layer transition search range rectangle creation unit 36 creates an “upper node corresponding data frame” that is an extension unit of the dedicated network. In the upper node corresponding data frame, the data of the upper transition node detected in step 103 described above is stored. However, even if there is a level 2 region node in the middle of the route to the upper transition node, only the data of the upper transition node is stored in the upper node corresponding data frame.
[0056]
Dedicated network creation processing (step 106)
As described above, the dedicated network is network data that stores only information on links and nodes necessary for searching for a route connecting these level 2 regions to each other for every combination of level 2 regions. Since only the links necessary for route search between two level 2 regions are stored, the amount of calculation of route search is considerably less than usual, which is very effective in speeding up route search processing. .
[0057]
The dedicated network creation unit 38 performs a search in each of the forward direction and the reverse direction for each combination of two level 2 regions. This search is performed using boundary nodes and upgrade nodes corresponding to each of the two level 2 regions.
FIG. 19 is an explanatory diagram of the upgrade node. The upgrade node is an upper transition node existing outside the level 1 region and located outside the level 2 region including the level 1 region. In the example shown in FIG. 19, only one upper transition node R1 among the two upper transition nodes R1 and R2 located outside the level 1 region is the upgrade node.
[0058]
A dedicated network is a network in which search results under all search conditions are not duplicated. At this time, all the search conditions used for the link are stored, and when the map data 20 is formatted (when a dedicated network for the map data 20 is created), which search condition is used A flag as search condition information indicating whether or not the link is used for is stored so as to correspond to each link. As a result, the number of links required for each search condition can be reduced, and the search process using the dedicated network can be speeded up.
[0059]
Aggregated link creation process Next, the aggregated link creation unit 40 combines the links with only two difference paths while ignoring the link ID in order to further speed up the search process using the dedicated network. Process. A link combined in this way is called an “aggregated link”. All the two-way links that do not correspond to the non-joining condition shown below are to be joined.
(Non-join condition)
-Do not combine ferry attribute links. Here, the ferry attribute link is a link on the ferry route, and this link is excluded from the objects to be combined.
-Upgrade nodes are not combined.
・ Links within the VICS reflection distance are not connected.
-Adjacent nodes in the dedicated network pointed from the boundary node of the basic part are not aggregated.
[0060]
For the aggregated links thus combined, the aggregated link ID is assigned in ascending order from 0 for each dedicated network. Further, the cost of the aggregated link is associated with the result of cost calculation in advance for each search type.
As described above, the aggregated link creating unit 40 creates aggregated links for the links included in the dedicated network, and updates some information regarding the route connecting the two level 2 regions to each other (step 107). .
[0061]
Further, it is necessary to store information of a plurality of link IDs to be combined with respect to the aggregated link ID so that it can be understood which link is combined to create the aggregated link when combining the links. For this purpose, the aggregated link creating unit 40 creates an “aggregated link expanded data frame” that is an extension unit of the dedicated network, and stores it in association with the corresponding dedicated network (step 108). When the aggregated link is included in the route extracted as a search result, expansion from the aggregated link to the normal link is performed based on the information included in the aggregated link expansion data frame as shown in FIG. Therefore, it is possible to perform guidance processing and drawing processing using the link of the level 2 region after being expanded.
[0062]
Creation of other data frames Next, the dedicated network creation unit 38 creates a "border node-corresponding data frame" that is an extension unit of the dedicated network, and stores it in correspondence with the corresponding dedicated network (step). 109).
[0063]
The adjacent node information included in the basic part of the level 2 region relates to the adjacent level 2 region. Therefore, in order to extend the search branch from any level 2 region to the dedicated network, it is necessary to know which node in the dedicated network corresponds to the adjacent node information of the level 2 region.
[0064]
FIG. 21 is an explanatory diagram of adjacent node information. As shown in FIG. 21A, when adjacent node information is focused on one boundary node in the level 2 region, the adjacent node information is adjacent in another level 2 region (adjacent region) that is adjacent through this boundary node. This data specifies the node N1.
[0065]
As shown in FIG. 21B, the dedicated network creation unit 38 identifies the node N2 in the dedicated network corresponding to the adjacent node information in the level 2 region, and is an extension unit of this dedicated network. Create a "data frame". Since the correspondence between one level 2 region and the boundary node of the dedicated network is 1: N (N is the number of dedicated networks), a new branch is created when extending the search branch from the level 2 region to the dedicated network. However, since the boundary node information included in each dedicated network corresponds to one level 2 region, there is no need for such conversion.
[0066]
In addition, as described above, the information on the upper transition node is stored in the “upper node corresponding data frame” which is an extension part of the dedicated network. It shows which node is included in two regions. Therefore, as in the upgrade node R1 shown in FIG. 19, when the upper transition node is included in another adjacent level 2 region other than the level 2 region including the level 1 region of interest, It is necessary to specify which node in the dedicated network corresponds to the upper migration node. The dedicated network creation unit 38 adds information for specifying a node in the dedicated network corresponding to the upgraded node, updates the content of the “higher node-corresponding data frame” created in step 105 described above, and the corresponding dedicated network (Step 110).
[0067]
The dedicated network described above is newly created separately from the basic part of each region of levels 1 to 5. Therefore, when extending a search branch from any level 2 region to one dedicated network, address information for reading the data of this dedicated network is required. When the dedicated network creation unit 38 creates the dedicated network, it creates an “address data frame to the dedicated network” including the address information as an extension unit, and stores the address data frame corresponding to the dedicated network (step 111). .
[0068]
As described above, by using the extended path calculation adjacent data frame of the map data 20 created using the map data creation device 10 of the present embodiment, the search branch can be surely extended to the nodes of the level 2 region. It is possible to perform an optimum route search. In addition, since this extended route calculation adjacent data frame is associated with the original level 1 region that extends the search branch, a portion of the in-vehicle navigation device or the like necessary for route search processing from a CD-ROM or the like. When reading the map data, it is possible to read only the data corresponding to this level 1 region when reading the data of the level 1 region including the starting point and destination, and the amount of data to be read The number of times can be reduced.
[0069]
Next, a route search process performed using, for example, an in-vehicle navigation device using the map data 20 created by the map data creation device 10 described above will be described.
FIG. 22 is a flowchart showing an operation procedure of route search processing. FIG. 23 is a diagram showing an outline of route search processing.
[0070]
When a route search operation is instructed by the user of the navigation device, first, a starting point and a destination to be route searched are set (step 200). For example, the vehicle position at that time is set as the departure place. In addition, a specific facility designated by the user is set as the destination.
[0071]
Next, map data of the basic part and extension part of the level 1 and level 2 regions that include the starting point and the destination respectively, and the level 2 region that includes the starting point and the level 2 region that includes the destination The map data of the corresponding dedicated network and its extension is read (step 201).
[0072]
As shown in FIG. 23, when the departure point S is specified, the level 1 region A1 including the departure point S and the level 2 region C1 including the level 1 region A1 are specified. Similarly, when the destination E is specified, the level 1 region A2 including the destination E and the level 2 region C2 including the level 2 region A2 are specified. In addition, since a dedicated network is prepared in advance for each combination of two level 2 regions, when two level 2 regions each including a starting point and a destination are specified, a dedicated network determined by this combination is determined. Identified. In this way, the level 1 and 2 regions and the dedicated network are specified, and the map data including their extension is read out.
[0073]
Next, a search process is performed in the upper layer transition search range rectangle corresponding to each of the departure point and the destination, and upper nodes included in each upper layer transition search range rectangle are extracted (step 202).
Next, the search branch is extended from each upper node extracted corresponding to the departure side, and the optimum route to each upper node extracted corresponding to the destination side is searched (step 203). This search is performed using the map data of the level 2 region and the dedicated network. This search is continued until an optimum travel route connecting the departure point and the destination is determined.
[0074]
Next, when an aggregated link is included in the optimum route extracted by the search in step 203, a development process is performed to return this to the original link (step 204).
[0075]
【The invention's effect】
As described above, according to the present invention, the first route information included in the generated map data can be used to reliably extend the search branch to the node in the level 2 region, so that the optimum route search can be performed. It becomes possible to do. In addition, since the first route information is associated with the original level 1 area that extends the search branch, when the map data of the part necessary for the route search process is read from a CD-ROM or the like. When reading the data of the level 1 area including the departure place and the destination, it becomes possible to read only the first route information corresponding to the level 1 area together, and the amount of data to be read and the number of times of reading are reduced. Is possible.
[Brief description of the drawings]
FIG. 1 is a diagram illustrating a configuration of a map data creation device according to an embodiment.
FIG. 2 is a format diagram showing detailed contents of map data.
FIG. 3 is a block diagram showing functional blocks of the map data creation device of the present embodiment.
FIG. 4 is a flowchart showing an operation procedure of the map data creation device of the present embodiment.
FIG. 5 is a diagram illustrating a specific example of a logical mesh.
FIG. 6 is a diagram illustrating a specific example of a level 1 search range.
FIG. 7 is a diagram illustrating a specific example of upgrade processing;
FIG. 8 is a diagram illustrating a specific example of upgrade processing;
FIG. 9 is a diagram illustrating a specific example of a process of combining upgrade links.
FIG. 10 is a diagram illustrating a specific example of a process of combining upgrade links.
FIG. 11 is a diagram illustrating a specific example in the case where a search is performed from one logical mesh B to a virtual mesh C corresponding to a level 2 region.
FIG. 12 is a diagram illustrating a specific example in the case where a search is performed from one logical mesh B to a virtual mesh C ′ corresponding to a divided region of a level 2 region.
13 is an explanatory diagram of a maximum rectangle Q set corresponding to the virtual mesh C ′ shown in FIG.
FIG. 14 is a diagram illustrating a relationship between a search result and a detection node.
FIG. 15 is a diagram illustrating a specific example of an upper layer transition search rectangle.
FIG. 16 is an explanatory diagram of data stored in an extended path calculation adjacent data frame corresponding to a level 1 basic unit;
FIG. 17 is a diagram illustrating a format of data related to a route extending to an adjacent level 1 region.
FIG. 18 is an explanatory diagram of a route extending to an adjacent level 1 region.
FIG. 19 is an explanatory diagram of an upgrade node.
FIG. 20 is a diagram illustrating a specific example of development of aggregated links.
FIG. 21 is an explanatory diagram of adjacent node information.
FIG. 22 is a flowchart showing an operation procedure of route search processing;
FIG. 23 is a diagram showing an outline of route search processing;
[Explanation of symbols]
10 Map data creation device 12 CPU
14 ROM
16 RAM
18 Hard disk device (HD)
20 Map Data 30 Logical Mesh Generation Unit 32 Level 1 Search Range Setting Unit 34 Upgrade Processing Unit 36 Upper-layer Transition Search Range Rectangle Creation Unit 38 Dedicated Network Creation Unit 40 Aggregated Link Creation Unit

Claims (4)

Hierarchized level 1 region and level 2 region are set, and the level 2 region corresponds to a larger area than the level 1 region, and the map data corresponding to the level 1 region includes the level 2 region. Is a map data creation device that creates map data necessary for searching for an optimal route connecting two points to be searched for, including road information that is more detailed than the map data corresponding to ,
One of the two points includes data relating to a route from one of the two points to the other and following a link included in the map data of the level 1 region to reach a node included in the map data of the level 2 region. Means for performing processing corresponding to one level 1 region,
Network data storing link and node information necessary for searching for a route connecting these two level 2 regions to each other when two level 2 regions including each of the two points are specified. A dedicated network creating means for creating map data of the dedicated network that is separate from the map data of the level 1 region and the level 2 region ,
A means for performing processing for associating data relating to a route reaching the node with one level 1 region including one of the two points,
Logical mesh generation means for dividing a level 1 region into a predetermined number and generating a logical mesh corresponding to each divided region;
A link spanning the boundary of each of the plurality of logical meshes corresponding to one level 1 region of interest and a boundary node of other level 2 regions excluding the level 2 region including the one level 1 region of interest By searching for the optimum route between the two level 2 regions, the route from the boundary node of the other level 2 region to the link across each boundary of the logical mesh is obtained. The node of the route extending to the link included only in the level 1 region is detected as the upper transition node, and the route from the link straddling the boundary of the logical mesh to the upper transition node is extracted, and thus extracted. Set the range including the route made as an upper layer transition search range rectangle, In the process of setting the layer transition search range rectangle, a route to the upper transition node detected corresponding to one level 1 region of interest and outside the level 1 region of interest Is associated with this focused level 1 region, and the data of the upper transition node detected during the process of setting the upper layer transition search range rectangle is used for detection of the upper transition node. An upper layer transition search range rectangle creating means for performing processing corresponding to the dedicated network corresponding to a combination of a level 2 region including one level 1 region and another level 2 region of interest;
A map data creation device comprising: In claim 1,
The upper layer transition search range rectangle creating means generates a plurality of virtual meshes obtained by dividing the level 2 region into a predetermined number when the logical mesh to be searched and the level 2 region overlap or approach each other. Set, extract all the logical meshes that contain at least a part of each virtual mesh, and include all the ranges that include the predetermined number of links that exist around each of the extracted logical meshes A map data creation device, wherein a maximum rectangle to be set is set, and a route search is performed using the plurality of maximum rectangles corresponding to each of the plurality of virtual meshes instead of the level 2 region. In claim 1 or 2,
By paying attention to the two logical meshes, a route connecting these two logical meshes is obtained by route search, and when there is a link included in only the level 1 region in the searched route, this link is designated as the level 2 Further comprising upgrade processing means for performing a process of upgrading to a link included in a region before a process of making data related to a route reaching the node correspond to one level 1 region including one of the two points. A featured map data creation device. In any one of Claims 1-3,
A map data creation device, further comprising: aggregated link creation means for creating a single aggregated link by aggregating two-difference links that do not satisfy the non-coupling condition for the routes included in the dedicated network.

Images