JPH11174954A - Map data management method, route search device, and storage medium - Google Patents

Abstract

(57) [Summary] [PROBLEMS] To improve the search speed when searching for a node within a certain range from given coordinates. SOLUTION: The arrangement of nodes, such as intersections, in each management area created for each management area is sorted in ascending or descending order with respect to either a latitude coordinate value or a longitude coordinate value, and Information of the sorted nodes is managed in a node table including sub-tables each corresponding to each divided area when the management area is divided by a dividing line parallel to a coordinate axis of the coordinate values used for the sorting. I do.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The present invention relates to a digital map storing a road network as numerical information,
For example, the present invention relates to a map data management method, a route search device, and a storage medium for detecting a position of a vehicle or the like and calculating an optimal route to a destination.

[0002]

2. Description of the Related Art A navigation apparatus to which a conventional map data management method and a route search apparatus are applied is disclosed in, for example, Japanese Patent Application Laid-Open No. 8-128844, in which the current position of a vehicle based on an azimuth and distance detection signal is determined. The position is detected, the map data stored in the map data storage means such as a CD-ROM is accessed, and the position of the vehicle is displayed on a map image near the detected current position of the vehicle. When a destination is input, the road network is searched to find an optimal route to the destination, and guidance is provided by voice or display.

[0003] The map data stored in the map data storage means is used to reduce the amount of memory and the reading time.
The map data is managed by being divided into appropriate sizes for each area, and only the map data of the necessary area is read from the map data storage means into the main memory. As an example of the method of regional division, there is a mesh system used in the national land numerical information of the Geographical Survey Institute of the Ministry of Construction. In this method, as shown in FIG. 16, a rectangular mesh area delimited by equally spaced longitude lines 101 and latitude lines 100 is used as a unit. It is most commonly used because it is easy to check the breaks in the mesh area.

When detecting the current position of the vehicle, a road network around the coordinates of the vehicle position obtained by the sensor is searched, the road on which the vehicle is traveling is estimated, and the position based on the error of the sensor is detected. Correct the misalignment. When a destination is input, a road network near the coordinates of the destination is searched, and the road closest to the destination is set as the end of the route.

[0005] When a road network is described as digital information, for example, as disclosed in Japanese Patent Application Laid-Open No. 8-128844, intersections, dead ends, and boundary lines of a mesh on a road in a management area (mesh). Characteristic points such as intersections with are extracted, and these are defined as “nodes”. A road connecting nodes is called a "link", and a road network is configured by a combination of nodes and links.

[0006] When the longitude and latitude of the vehicle position are measured by GPS, a road around the coordinates of the measured position is searched to estimate a running road. If a destination is set on the map screen, the road closest to the coordinates of the destination is determined.
The end of the route to the destination. In such a navigation device, it is necessary to search for a road within a certain distance range from given coordinates and to specify the closest road. At this time, first, the coordinates of each node in the mesh are checked, and nodes within the search range are extracted. Next, the distance from the reference coordinates is checked for each link connected to each extracted node, and a link passing closest to the given coordinates is selected. As a method for quickly searching whether or not the given coordinates are within the search range, there is a binary search (binary search) (reference literature, Ohmsha. Database organization technique). In the binary search, one of the coordinate values
(Longitude or latitude) as keys, and arrange nodes in ascending or descending order of key values.

For example, as shown in FIGS. 17 (a) and 17 (b), the mesh area M
Are sorted in ascending longitude coordinates, and
As shown in FIG. 18, nodes having the same longitude are sorted by the node table NTBL in ascending order of latitude coordinates. When extracting nodes within a certain range of the search range p from the reference point (x, y) in the mesh area M, as shown in FIG. The search speed is improved by using a binary search to find only nodes within the range.

[0008]

Since the conventional map data management method and route search apparatus have been configured as described above, in the map data, nodes which are feature points on the road have dimensional coordinates. Even if one of the coordinate axes is sorted, the coordinates not used for sorting cannot be narrowed down by the binary search. For example, in the case of FIG. 18, nodes whose longitude coordinates are within the search range can be extracted by a binary search, while whether or not the latitude coordinates are within the search range is determined for all the nodes extracted by the binary search. There was a problem that needed to be checked.

When the road network in the mesh area is divided by large rivers, bays, and mountains,
In some cases, a road having an obstacle between the given coordinates may be selected. For example, when performing a route search, a road network consisting of only main roads may be used except for narrow streets, but there is no main road near the coordinates specified as the destination, and the closest main road is a river. For example, when the vehicle is on the opposite shore, the road on the opposite shore becomes the end of the route, and there is a problem in that a route that cannot reach the destination without making a large turn may be calculated.

SUMMARY OF THE INVENTION The present invention has been made to solve the above problems, and a map data management method, a route search device, and a map data management method capable of improving a search speed when searching for a node within a predetermined range from given coordinates. The purpose is to obtain a storage medium. It is another object of the present invention to provide a map data management method and a route search device that search for only roads where vehicles can surely pass near given coordinates when a road network is divided in a management area. .

[0011]

A map data management method according to the present invention divides map data into a plurality of management areas,
Sort the array of nodes such as intersections in each management area created for each management area in ascending or descending order with respect to either the latitude coordinate value or the longitude coordinate value,
The sorted node information is a node table including a sub-table corresponding to each divided area when the management area is divided by a dividing line parallel to a coordinate axis of the coordinate value used for the sorting. It is intended to be managed.

In the map data management method according to the present invention, the width of a divided area for dividing the management area is changed according to the road data density in the management area, and the search range of the node is determined in accordance with the width of the divided area. The size is changed, and a divided area overlapping the search range centered on the reference point is selected.

In the map data management method according to the present invention, the map data of the management area is divided into a plurality of hierarchies from a wide area to a narrow area according to the size of each divided area when the map data of the wide area is divided. The map is divided into map data having a structure, and the arrangement of the nodes, such as the intersections of the management areas, created with respect to the map data of the narrow area hierarchy, is arranged in ascending order with respect to either the coordinate value of the latitude or the coordinate value of the longitude Or sort in descending order, and sort the information of the nodes with each divided area when dividing the map data of the narrow area hierarchy by a dividing line parallel to a coordinate axis of the coordinate value used for the sorting. The first sub-table, which is stored in association with the map data, and the map data of the narrow area composed of the divided areas are sequentially mapped to the map data of the upper hierarchy. It is obtained so as to manage the node table of the LE.

In the map data management method according to the present invention, the map data has a two-layered structure of map data of a wide area hierarchy and map data of a narrow area hierarchy.

The map data management method according to the present invention is such that the map data has a three-layer structure of map data of a wide area, map data of a medium area, and map data of a small area.

In the map data management method according to the present invention, a map creation range is divided into a plurality of management areas, and for each of the divided management areas, a divided area having no road connection to a region where a road exists is provided. In the case where there are a plurality of divided areas having no connection of the road network in the management area, there is a feature point having a connection relation in the management area. A node table is created by performing area division for each set, and node information is managed in the created node table.

In the map data management method according to the present invention, each divided area is divided into an area where a road is present and an area where no road is present in each of the divided areas. It is managed by a node table composed of sub-tables corresponding to the area where the road exists.

A route search device according to the present invention includes a map data storage means for storing map data for each management area;
A longitude or a latitude is selected as a reference when sorting the node data of the map data for each management area stored by the map data storage means, and the management area is divided by a dividing line parallel to the selected longitude or latitude coordinate axis. Area management means for dividing the inside into a plurality of divided areas, and corresponding to each of the divided areas divided by the area management means, the node data is stored in ascending or descending order of the coordinate values of the selected longitude or latitude. A node data management means for configuring a sorted sub-table, managing the node data in the sub-table, and, when given coordinates serving as a reference point for search, overlapping with a search range centered on the reference point. Area detecting means for selecting a divided area having the following, and whether or not the node data corresponding to each divided area selected by the area detecting means It is obtained by so and a node detecting means for retrieving a node within the search range.

The route search device according to the present invention has a divided area number varying means for changing the number of divided areas according to the road density in the management area, and when the number of divided areas is changed by the divided area number varying means. The area detecting means changes the size of the search range of the node in accordance with the width of the divided area, and selects the divided area overlapping the search range centered on the reference point.

The route search apparatus according to the present invention is characterized in that, for map data having a plurality of hierarchical structures from a wide area hierarchy to a narrow area hierarchy for a management area, an intersection in the management area created with respect to the map data of the narrow area hierarchy For example, a longitude or a latitude is selected as a reference when sorting the arrangement of the nodes, and the information of the nodes sorted in ascending or descending order with respect to any of the coordinate values of the selected longitude or the latitude is selected. A first sub-table held in correspondence with each divided area when the map data of the narrow area is divided by a dividing line parallel to a coordinate axis of the coordinate value used for the sorting, A node table comprising a second sub-table for sequentially associating the map data of the narrow area composed of divided areas with the map data of an upper layer Area management means in which is to be managed.

In the route search apparatus according to the present invention, the management area has a two-layer hierarchical structure including map data of a wide area and map data of a narrow area obtained by dividing the map data of the wide area into a plurality. For the map data having, the longitude or latitude is selected as a reference when sorting the arrangement of nodes such as intersections in the management area created for the map data of the narrow area hierarchy, and the selected longitude or latitude is selected. The information of the nodes sorted in ascending or descending order for any of the coordinate values of the map data of the narrow area hierarchy by a dividing line parallel to the coordinate axes of the coordinate values used for the sorting. The first sub-table held in correspondence with each divided area when divided and the map data of the narrow area composed of each divided area are stored in the wide area The second consists of the subtable node table area management means which corresponds to the map data in which is to be managed.

In the route search device according to the present invention, the management area is a map data of a wide area, map data of a middle area when the wide area map data is divided into a plurality of pieces, and a map data of the middle area. For map data having a three-layer hierarchical structure consisting of map data of a narrow area when each map data is further divided into a plurality of pieces, map data at an intersection in the management area created for the map data of the narrow area is used. A longitude or latitude is selected as a criterion when sorting the arrangement of certain nodes, and the information of the nodes sorted in ascending or descending order with respect to any of the selected longitude or latitude coordinate values, A first server which is held in correspondence with each divided area when the map data of the narrow area is divided by a dividing line parallel to the coordinate axis of the coordinate value used for sorting. The area management means manages the area management unit using a node table including a table and a second sub-table that associates the map data of the narrow-layer hierarchy including the divided areas with the map data of the middle-range hierarchy and the wide-range hierarchy. It is like that.

According to the storage medium of the present invention, a computer selects a longitude or a latitude as a reference when sorting node data of map data for each management area stored by a map data storage means, and selects the selected longitude. Or an area management procedure for dividing and managing the inside of the management area into a plurality of divided areas by a dividing line parallel to a coordinate axis of latitude, and the selected longitude corresponding to each of the divided areas divided by the area management means. Alternatively, a sub-table in which node data is sorted in ascending or descending order of latitude coordinate values is formed, and node data management procedures for managing the node data in the sub-table and coordinates serving as search reference points are given. An area detection procedure for selecting a divided area overlapping with a search range centered on the reference point; and It is obtained by recording a program for executing the node discovery procedures from the node data corresponding to each divided area selected taking out nodes within the search to a computer.

[0024]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS One embodiment of the present invention will be described below. Embodiment 1 FIG. FIG. 1 is a block diagram showing a navigation device to which the map data management method and the route search device according to the first embodiment are applied. This navigation device is mounted on a vehicle, 1 is a distance sensor for detecting a traveling distance, 2 is a direction sensor for detecting the direction of the vehicle, and 3 is an external map storing map data including a road network. A memory (map data storage means), 4 is a computing device (computing means) for estimating the position of the vehicle and an optimal route to the destination, 5 is an input device for designating the destination and the like, and 6 is a display device. Further, a vehicle position detecting means such as a GPS (not shown) is provided. The arithmetic unit 4 includes the distance sensor 1
Based on the input from the azimuth sensor 2 and the input from the azimuth sensor 2, the link with the highest probability that the vehicle is currently running is determined, and the running link is determined. When a destination is set by the input device 5, the arithmetic device 4 calculates an optimal route from the traveling link to the destination link, using the link closest to the destination as the destination link.

Reference numeral 4a denotes area management means, which selects longitude or latitude as a reference when sorting node data of map data for each management area stored in the external map memory 3, and selects the longitude or latitude of the selected longitude or latitude. The inside of the management area is divided into a plurality of divided areas and managed by dividing lines parallel to the coordinate axes. Reference numeral 4b denotes a node data management unit, which is a sub-table in which node data is sorted in ascending or descending order of the selected longitude or latitude coordinate value corresponding to each of the divided areas divided by the area management unit 4a. And manages the node data in the sub-table. Reference numeral 4c denotes an area detecting means for selecting a divided area having an overlap with a search range centered on the reference point when given coordinates serving as a search reference point. When the number of divided areas is changed by the divided area number changing means 41 in accordance with the road density in the management area, the size of the search range is changed in accordance with the width of the divided area in which the number of divided areas is changed. . Reference numeral 4d denotes a node detection unit which extracts nodes within the search range from node data corresponding to each of the divided areas selected by the area detection unit 4c. Reference numeral 41 denotes a divided area number changing unit that changes the number of divided areas according to the road density in the management area. The area management means 4a, the node data management means 4b, the area detection means 4c, and the node detection means 4
d can be stored in a storage medium as a program. The arithmetic unit 4 is constituted by a computer, and the area management means (procedure) 4a, the node detection management means (procedure) 4b, the area detection means (procedure) 4c, and the node detection management means (procedure) 4d are stored as storage media as programs. Can be stored.

Next, the structure of the map data stored in the external map memory 3 will be described. FIG. 2 shows a state where the road map data is divided into regions for each reading unit.
In the figure, reference numeral 3a denotes road map data, and M denotes a road map based on the road map data 3a.
Indicates a grid-like mesh area (management area) when divided by.

FIGS. 3 and 4 show the mesh areas M
The figure shows a divided area # 0 to #n for each latitude range having a fixed width. Mesh area M
The data of each node in the sub table # corresponding to a pair with the divided areas # 0 to #n as a node table NTBL
0 to #n, and in each sub-table, node data is stored in ascending longitude coordinate order.

In FIG. 4, p is a search range, and a and b are nodes immediately after exceeding the minimum longitude of the search range p and nodes immediately before exceeding the maximum longitude. Node table NT
Node data corresponding to the divided area m of the mesh area M is set in the sub table #m of BL. The arithmetic unit 4 cuts out the road around the own vehicle position or the destination coordinates from the road network in the mesh area M in order to determine the traveling link and the destination link. For this purpose, the vehicle position or the destination coordinates are used as reference coordinates, a search range p of a square centered on the reference coordinates is set, and the minimum and maximum values of the longitude and latitude coordinates of the node to be searched are respectively set. Ask. Here, the interval between the dividing lines that divide the mesh area M (the interval between the divided areas) is equal to the length of the side of the search range p.

First, among the divided areas in the mesh area M, a divided area m and a divided area m + 1 which overlap with the search range are selected. Since the length of one side of the search range p is equal to the interval between the divided areas, the overlapping divided area is 1
One or two. In FIG. 4, the divided area m and the divided area m + 1 overlap with the search range. From the sub-table corresponding to the selected divided area m and the divided area m + 1, a node whose longitude coordinate is within the search range is extracted. Since the node data in the sub-table are arranged in ascending order of the longitude coordinates, a node a immediately after the minimum longitude of the search range p and a node b immediately before the maximum longitude of the search range p are found by a binary search, and the nodes in the middle are searched. Take out everything. Therefore, in the divided area m, the range from the node a to the node b in the sub-table #m is targeted.
The same applies to the divided area m + 1.

The existence range of the extracted nodes is the range shown by shading in FIG. 4 and is much smaller than that in the case where there is no divided area because the direction of the latitude is limited by the divided area. For example, when one side of the mesh area M is 10 km and one side of the search range p is 500 m, if the divided area is not set, the binary search of the entire mesh area M is performed twice to obtain 500 m.
The range is narrowed down to × 10 km, and the determination of the latitude coordinates is performed for all the nodes within the range. On the other hand, in the case of having the divided area, the binary search in the divided area is performed four times to narrow down the range to 500 m × 1 km. The number can be reduced by a factor of ten. The number of nodes in the divided area is the mesh area M
Since it is 1/20 of the whole, the speed of the binary search itself is increased, and the influence of the increase in the number of times can be offset. As described above, since the range of the latitude coordinate is limited using the divided area and the range of the longitude coordinate is limited by the binary search, it is not necessary to check the coordinates of each node for many nodes, and the nodes within the required range can be quickly found. Can be taken out.

In the above description, the width of the divided area is equal to one side of the search range p. However, the width of the divided area may be smaller than the search range p. In that case, the number of times of the binary search is further increased, but the existence range of the selected node becomes substantially equal to the search range p.

FIG. 5 does not set the width of one divided area to a fixed width for all the mesh areas, but increases the number of divisions in an urban area with a high road density and divides it in a suburb with a low road density. The mesh boundaries and divided areas when the number is reduced are shown. In FIG. 5, 15 is a mesh boundary,
Reference numeral 17 denotes a divided area boundary, 16a and 16b denote divided areas in which the number of divisions is small in a suburb where the road density is low, and 17a denotes a divided area in which the number of divisions is large in an urban area where the road density is high. In this case, the divided area number changing means 41 changes the number of divided areas according to the road density in the management area, and changes the width of the divided area. The area management means 4a selects longitude or latitude as a reference when sorting node data of map data for each management area stored in the external map memory 3, and selects a longitude or a latitude parallel to the selected longitude or latitude coordinate axis. The management area is managed by a plurality of divided areas in which the number of divisions is changed by dividing lines. At this time, since the area detection unit 4c adjusts the search range p in accordance with the width of the divided area, the search range p is too narrow to find a node or is too wide to process a large number of nodes. Can be avoided.

As described above, according to the first embodiment, the latitude coordinates of a node such as a characteristic point such as an intersection of a road network, a dead end, or an intersection with a boundary of a mesh area in a search range are stored in an area. Since the range is specified using the division and the longitude coordinates are specified by the binary search, there is an effect that the processing target nodes within the search range are narrowed down and the nodes within the necessary range can be quickly extracted.

Further, since the search range p can be adjusted in accordance with the width of the divided area, it is possible to narrow down the processing target nodes within the search range and to quickly extract the nodes within the necessary range to the road density. Accordingly, there is an effect that the operation can be performed flexibly and efficiently.

Embodiment 2 A map data management method and a route search device according to the second embodiment applied to the navigation device will be described. In the second embodiment,
A case in which the area division of the wide area mesh area is matched with the narrow area mesh area when the map data has a hierarchical structure will be described. FIG. 6 is an explanatory diagram showing map data having a hierarchical structure at a wide area level and a narrow area level. FIG. 7 is an explanatory diagram showing an area division structure of a mesh area at a wide area level. FIG. 8 is an explanatory diagram showing an example of a node in which a problem occurs during conventional map data management. FIG. 9 is an explanatory diagram showing each mesh area of map data having three hierarchical levels, and FIG.
Is used when a wide-area mesh region is firstly divided by a medium-level mesh region, and each area of the first-divided middle-level mesh region is secondarily divided by a narrow-level mesh region. FIG. 4 is an explanatory diagram showing a relationship between a primary divided area and a secondary divided area.

In FIG. 6, reference numeral 18 denotes a mesh that defines a wide-area mesh area for a road map, and 19 denotes a mesh that defines a narrow-level mesh area. FIG.
In FIG. 6, NTBL0 is a sub-table of a wide-area level mesh area formed by collecting narrow-area level mesh areas. The wide area level node table is created by collecting the sub tables of the narrow area level mesh area. NTBL1 is a node table for nodes in divided areas in each mesh area at a narrow level.

In FIG. 9, reference numeral 121 denotes a wide area hierarchical mesh for defining a wide area mesh area for a road map;
Reference numeral 122 denotes a middle hierarchical mesh defining a middle level mesh area, and reference numeral 123 denotes a narrow hierarchical mesh defining a narrow level mesh area.

In FIG. 10, NTBL2 is a node table when a wide-area level mesh area is firstly divided by a medium-level mesh area, and NTBL3 is a medium-level mesh area obtained by performing the first-order division. It is a node table when each area is secondarily divided by a mesh area of a narrow area level.

Here, a case where the map data has two layers, a wide area hierarchy and a narrow area hierarchy, will be described with reference to FIGS. 6 and 7. FIG. The map data has two levels, a wide area level and a narrow area level, and the wide area mesh area is 40 km.
It has a range of × 40 km, and the mesh area at the narrow level has a range of 10 km × 10 km. Therefore, in this case,
There are 16 narrow level mesh areas in the wide level mesh area.

As shown in FIG. 7, a wide-area mesh area based on the mesh 18 is firstly divided into small-area mesh areas, and each of the primary-divided areas is further divided. That is, the node table N by each divided area of the mesh area at the narrow area level
TBL1 is once collected for each of the narrow-level mesh areas to form a sub-table of the narrow-level mesh, and further collected to obtain a node table N of the wide-level mesh area.
Create TBL0. As described above, before setting the division area, the nodes in the wide-area mesh are automatically divided into the small-area mesh areas by dividing the wide-area mesh area into the narrow-area mesh areas. Managed.

As shown in FIG. 8, in the conventional map data management method, in order to check which mesh area at a narrow level includes a node in a mesh area at a wide area, a mesh area including the coordinates of the node is determined. In general, a method for obtaining the mesh area 2 is shown in FIG.
At the node A on the boundary between 5, 26, 27, and 28, it cannot be determined which narrow mesh area is included. For this purpose, there is a method in which coordinates are shifted so that no node is placed on the mesh boundary at the data creation stage. However, there is a drawback that the time and effort for creating and updating data are increased. Alternatively, there is a method in which which mesh area is included in the narrow area level as a data item, but there is a disadvantage that the data amount increases. On the other hand, in the second embodiment, if the divided area including the node is examined without examining the coordinates of the node or examining the data of the mesh area at the narrow area level, the node can be set to the narrow area level. It is easy to find out which mesh area is included. Therefore, it is possible to prevent an increase in time and effort for creating map data and an increase in the amount of data.

FIG. 9 shows map data having three hierarchical levels. The wide-area mesh area has 16 areas of the medium-level mesh area, and the middle-level mesh area has a narrow area. It has an area for 16 level mesh areas. Therefore, the wide area level mesh area has 256 areas of the narrow area level mesh area.

In FIG. 10, the wide-area level mesh area is firstly divided by the middle-level mesh area, and each area of the first-order divided middle-level mesh area is defined by the narrow-area mesh area. Subdivide into two. In this case, for example, if the mesh area at the wide area level is 40 km square and the mesh area at the narrow area is 2.5 km square, one side of the secondary division area is 1/16 of one side of the wide area mesh area. Therefore, if four divided areas of the narrow area around the reference coordinates are collected, a practical search can be performed without performing a binary search. In addition, since it is possible to know which narrow-level mesh area contains a wide-area node without going through the middle-level level, the correspondence between the wide-area level and the narrow-area mesh area when performing a route search, etc. The relationship can be taken directly, and the trouble of reading the mid-range level mesh area can be saved.

As described above, according to the second embodiment, the mesh area of the lower hierarchical level for the narrow area obtained by subdividing the mesh area of the upper hierarchical level of the map data having a wide area is replaced with the mesh area of the upper hierarchical level. In order to specify the range using the area division with respect to the mesh area of the lower hierarchical level, the latitude coordinate of the node in the search range is specified in correspondence to the mesh area, and the range is specified by the binary search using the longitude coordinate. There is an effect that a navigation device to which a map data management method and a route search device to which a target node is narrowed down by the area division and a node within a required range can be quickly extracted can be obtained.

Embodiment 3 A map data management method and a route search device according to the third embodiment applied to a navigation device will be described. In the third embodiment,
A case in which area division is performed based on the presence or absence of a road will be described with reference to FIGS. 11 to 13
FIG. 4 is an explanatory diagram showing a mesh region of map data when a sea exists between a region A and a region B. As shown in FIG. 11, since there is a sea between the area A and the area B, no road is connected between the area A and the area B, and it is necessary to make a large roundabout with respect to a straight line distance. It is a situation where you can not go back and forth. In FIG. 12, the reference point S is in the area B. However, when the main road closest to the reference point S is obtained, the road in the area A is selected. Therefore, such a reference point S
When a search is performed with a network having only a main road as a destination, there is a problem in that the conventional system searches for a route that is not connected to the reference point S of the area A in the vicinity of the destination and makes a large circuit. Occur.

FIG. 13 shows a state where the inside of the management area is managed in divided areas in consideration of the road connection state. The area where a road exists is divided into a divided area A and a divided area B where there is no road connection, and a divided area C where there is no road is separately provided and managed. When a reference point S for searching for a nearby road is given, the reference point S
Take out the divided area containing. If the extracted divided area includes a road, the nearest road is selected from the roads in the divided area. If the extracted divided area does not include a road, the divided area having the shortest distance from the reference point S is determined from among the divided areas including the road, and the nearest road is determined from the roads within the determined divided area. select. Thus, it is possible to avoid selecting a road having no connection with the reference point S as a nearby road.

As described above, according to the third embodiment, since the divided area such as the sea where no road exists is separately provided and managed, the divided area such as the impassable sea where there is no road is avoided. A navigation device to which a map data management method and a route search device that apply a map data management method and a route search device that can obtain a trunk road closest to the reference point S that has not been connected to the reference point S can be determined. There is an effect that can be obtained.

Embodiment 4 In the fourth embodiment, a case where the same effect as that of the third embodiment is obtained by adding a division according to the presence or absence of a road to the area division of the first embodiment will be described with reference to FIGS. explain. FIG. 14 is an explanatory diagram showing a mesh area when a division based on the presence or absence of a road is added to the area division of the first embodiment. FIG. 15 shows the fourth embodiment.
5 is a flowchart showing a map data management method of FIG.

FIG. 14 clearly shows the division of the road network by further dividing the inside of each of the divided areas similar to that of the first embodiment according to the presence or absence of a road. In addition to the same area division, each divided area is rectangularly divided into "an area where a road exists" and "an area where no road exists".

The operation will be described with reference to the flowchart of FIG. When a reference point S for searching for surrounding roads is given, first, a divided area including the reference point S is determined (step ST1). In the case of FIG. 14, divided area 2
0, and this divided area is referred to as “search target divided area”. The inclusion relationship between the search range centered on the reference point S and the search target divided area is checked (step ST2). When the search range is entirely within the search target divided area,
Proceed to step ST5. On the other hand, if the entire search range is not within the search target divided area, it is determined whether there is a “partition where a road exists” among the divided areas adjacent to the search target divided area (step ST
3) If there is a "division area where a road exists", the division area is added to the search target division area (step ST4). In the example of FIG. 14, the divided areas adjacent to the divided area 20 are divided area 10 and divided area 1
1, divided area 21, divided area 30, divided area 31
However, since the divided area 11, the divided area 21, and the divided area 31 are "divided areas having no road",
Only the divided areas 10 and 30 are added to the search target divided areas.

Step ST3 and step ST4
In, when there is no divided area that can be added to the search target divided area, the process proceeds to step ST5. Otherwise, the process returns to step ST2. The nodes within the search range centered on the reference point S are extracted from the nodes in the search target divided area (step ST5). Step ST
The road closest to the reference point S is selected from the roads connected to the node extracted in step 5, and is set as the nearest road (step ST6). Therefore, the reference point S
Since the divided area having no connection relation between the divided area and the road network is excluded from the search target in step ST3, only the roads in the area having the connection relation with the reference point S become the search target, and The trouble of searching is avoided.

As described above, according to the fourth embodiment, the inside of each of the divided areas is further rectangularly divided into "areas with roads" and "areas without roads" according to the presence or absence of roads. Thus, it is possible to clearly indicate the division of the road network. Therefore, the "search target divided area where the road exists" including the search range having the reference point S, or the "road exists adjacent to the search range" From the "search target divided area", only the roads that are connected to the nodes in the search range can be set as the search target, and the divided area such as the impassable sea where there is no road is excluded and the divided area is bypassed. Map data that can efficiently determine the main road closest to the reference point S and prevent selecting a road that has no connection with the reference point S as a nearby road The effect of a navigation device according to the physical method and the route search device is obtained.

[0053]

As described above, according to the present invention, the arrangement of nodes, such as intersections, in each management area created for each management area can be determined by using either the coordinate value of latitude or the coordinate value of longitude. Sorted in ascending or descending order, the information of the sorted nodes, each divided area when dividing the management area by a dividing line parallel to the coordinate axis of the coordinate value used for the sorting Since the nodes are managed in the node table including the corresponding sub-tables, when given a coordinate serving as a reference point of the search, the target node is located in the search range centered on the reference point. It is limited to nodes in the divided area overlapping with the range, and it is only necessary to extract each node in the search range from among them, and the node data of the road near the designated reference point is converted to a high level. There is an effect that can be taken in.

Further, according to the present invention, the width of the divided area dividing the management area is changed according to the road data density in the management area, and the size of the node search range is changed in accordance with the width of the divided area. Changed, so that the divided area that overlaps the search range around the reference point was selected,
The size of the node search range can be optimally set according to the width of the divided area, nodes cannot be searched in the search range, and there are a large number of nodes in the search range and the nearest neighbor There is an effect that the calculation time is not required to specify the road, and the node data of the road near the designated reference point can be extracted at high speed.

Further, according to the present invention, the map data of the management area is divided into map data having a plurality of hierarchical structures from a wide area hierarchy to a narrow area hierarchy, and the management area created for the map data of the narrow area is created. The array of nodes, such as intersections, is sorted in ascending or descending order with respect to either the coordinate value of latitude or the coordinate value of longitude, and the information of the sorted nodes is used for the sorting. A first sub-table held in correspondence with each of the divided areas when the map data of the narrow area is divided by a dividing line parallel to the coordinate axis of the coordinate values, and the narrow area hierarchy composed of the divided areas; Is managed in a node table consisting of a second sub-table which sequentially corresponds to the map data of a higher hierarchy. Correspondence can be specified without the need to shift coordinates when creating data or adding data indicating the correspondence, and it is limited to a narrow area divided area around the specified reference point Thus, there is an effect that the node can be retrieved and the node data of the road near the reference point can be extracted at high speed.

Further, according to the present invention, the map data has a two-layer structure of the map data of the wide area hierarchy and the map data of the narrow area hierarchy, so that the node data between the wide area hierarchy and the narrow area hierarchy is provided. Can be specified without the need to shift the coordinates when creating the data or adding data indicating the correspondence, as well as in the narrow area division area around the specified reference point. There is an effect that the node search is limited and the node data of the road near the reference point can be extracted at high speed.

According to the present invention, the map data has a three-layer structure of map data of a wide area, map data of a medium area, and map data of a small area. The correspondence between the node data between the wide area hierarchy and the narrow area hierarchy can be obtained without performing the search for the node only in the divided area of the narrow area around the designated reference point, There is an effect that node data such as a road near the reference point can be extracted at high speed in accordance with the size of the narrow area around the reference point.

Further, according to the present invention, the map creation range is divided into a plurality of management areas, and for each of the divided management areas, an area division of a divided area having no road connection to an area where a road exists, and When there are a plurality of divided areas that do not have a connection relationship with the road network in the management area, a set of feature points that have a connection relation in the management area is managed. The node table is created by dividing the area, and the node information is managed in the created node table. By checking whether it is in the divided area, while ensuring that the route search does not search the large round route,
There is an effect that the node data of the road near the designated reference point can be extracted at high speed.

Further, according to the present invention, each divided area is divided into an area where a road exists and an area where no road exists in each of the divided areas. Is managed using a node table consisting of sub-tables corresponding to the areas where the existing areas exist, so that a divided area having a road including a given reference point can be easily specified, and the presence or absence of a road in an adjacent divided area can be determined. By checking, there is an effect that the node data of the road near the designated reference point can be extracted at high speed while ensuring that the large-scale route is not searched in the route search.

According to the present invention, a longitude or a latitude is selected as a reference when sorting the node data of the map data for each management area, and the management is performed by a dividing line parallel to the selected longitude or latitude coordinate axis. Area management means for managing the area divided into a plurality of divided areas, and corresponding to each of the divided areas divided by the area management means,
A sub-table in which the node data is sorted in ascending or descending order of the selected longitude or latitude coordinate value,
Node data management means for managing the node data in the sub-table; and area detection for selecting a divided area having an overlap with a search range centered on the reference point when given coordinates serving as a reference point for search. Means and node detecting means for extracting nodes within the search range from the node data corresponding to each divided area selected by the area detecting means, so that coordinates serving as search reference points are provided. Is given, the target nodes for the search range centered on the reference point are limited to nodes in the divided area overlapping with the search range, and from this, each node in the search range is Just take it out,
There is an effect that node data of a road near the designated reference point can be extracted at high speed.

Further, according to the present invention, the area detecting means changes the size of the node search range in accordance with the width of the divided area when the number of divided areas is changed by the divided area number changing means. Since the divided area overlapping the search range centered on a point is selected, the size of the node search range can be optimally set according to the width of the divided area, and the search range can be set. Within the search range, there is a large number of nodes in the search range, and it takes no calculation time to specify the nearest road, and the nodes of the road near the designated reference point There is an effect that data can be retrieved at high speed.

Further, according to the present invention, for map data having a plurality of hierarchical structures from a wide area hierarchy to a narrow area hierarchy for a management area, an intersection within the management area created for the map data of the narrow area hierarchy, etc. The longitude or latitude is selected as a reference when sorting the arrangement of the nodes, and the information of the nodes sorted in ascending or descending order with respect to any of the coordinate values of the selected longitude or latitude, A first sub-table held in correspondence with each of the divided areas when the map data of the narrow area is divided by a dividing line parallel to a coordinate axis of the coordinate value used for the sorting; The map data of the narrow-area hierarchy composed of areas is managed in a node table composed of a second sub-table that sequentially corresponds to the map data of a higher hierarchy. With the provision of area management means, it is possible to clearly indicate the correspondence between node data between hierarchies without having to shift coordinates when creating data or adding data indicating the correspondence. The node search is limited to the divided area of the narrow hierarchy around the designated reference point, and the node data of the road near the reference point can be extracted at high speed.

Further, according to the present invention, the management area has a two-layer hierarchical structure composed of map data of a wide area and map data of a narrow area obtained by dividing the map data of the wide area into a plurality. For the map data having, the longitude or latitude is selected as a reference when sorting the arrangement of nodes such as intersections in the management area created for the map data of the narrow area hierarchy, and the selected longitude or latitude is selected. The information of the nodes sorted in ascending or descending order for any of the coordinate values is divided into map data of the narrow area hierarchy by a dividing line parallel to a coordinate axis of the coordinate values used for the sorting. The first sub-table held in correspondence with each divided area and the narrow-area map data composed of the divided areas are stored in the wide-area map. Is provided with an area management means for managing a node table including a second sub-table corresponding to data, so that the correspondence relationship between node data between the wide-area hierarchy and the narrow-area hierarchy is represented by coordinates at the time of data creation. Can be specified without taking the trouble of shifting or adding data indicating the correspondence, and searching for nodes limited to the divided area of the narrow hierarchy around the specified reference point, There is an effect that node data of a road near the reference point can be extracted at high speed.

Further, according to the present invention, the management area is composed of map data of a wide area, map data of a middle area when the map data of the wide area is divided into a plurality of pieces, and map data of the middle area. For map data having a three-layer hierarchical structure composed of map data of a narrow area when the map data is further divided into a plurality of areas, an intersection in the management area created for the map data of the narrow area, and the like. A longitude or a latitude is selected as a reference when sorting the arrangement of the nodes, and the information of the nodes sorted in ascending or descending order with respect to any of the selected longitude or latitude coordinate values is subjected to the sorting. The first sub-table held in correspondence with each divided area when the map data of the narrow area is divided by a dividing line parallel to the coordinate axis of the coordinate value used for the Area management means in a node table comprising a map table and a second sub-table for associating the map data of the narrow-area hierarchy composed of the divided areas with the map data of the middle-range hierarchy and the wide-area hierarchy. As a result, the correspondence between the node data between the wide-area layer and the narrow-area layer can be obtained without passing through the middle-level layer, and limited to the divided area of the narrow-area layer around the designated reference point. By performing the node search in such a manner, there is an effect that node data such as a road near the reference point can be extracted at high speed in accordance with the size of a narrow area around the reference point.

[Brief description of the drawings]

FIG. 1 is a block diagram showing a navigation device to which a map data management method and a route search device according to a first embodiment of the present invention are applied.

FIG. 2 is an explanatory diagram showing a state where road map data is divided into regions for each reading unit by the map data management method and the route search device according to the first embodiment of the present invention.

FIG. 3 is an explanatory diagram showing an area division in each mesh area by the map data management method and the route search device according to the first embodiment of the present invention.

FIG. 4 is an explanatory diagram showing an area division in each mesh area by the map data management method and the route search device according to the first embodiment of the present invention.

FIG. 5 shows a map data management method and a route search device according to the first embodiment of the present invention, in which an urban area having a high road density has a large number of divided areas and a suburban area having a low road density has a small number of divided areas. FIG. 4 is an explanatory diagram showing a mesh boundary and a divided area of FIG.

FIG. 6 is an explanatory diagram showing map data having a hierarchical structure at a wide area level and a narrow area level in the map data management method and the route search device according to the second embodiment of the present invention.

FIG. 7 is an explanatory diagram showing an area division structure of a wide-area mesh region by a map data management method and a route search device according to a second embodiment of the present invention.

FIG. 8 is an explanatory diagram showing an example of a node in which a failure occurs during map data management.

FIG. 9 is an explanatory diagram showing each mesh region of map data having three hierarchical levels by the map data management method and the route search device according to the second embodiment of the present invention.

FIG. 10 is an explanatory diagram showing a relationship between a primary divided area and a secondary divided area by the map data management method and the route search device according to the second embodiment of the present invention.

FIG. 11 is an explanatory diagram illustrating a mesh area of map data when a sea exists between an area A and an area B by the map data management method and the route search device according to the third embodiment of the present invention.

FIG. 12 is an explanatory diagram illustrating a mesh area of map data when a sea exists between an area A and an area B by the map data management method and the route search device according to the third embodiment of the present invention.

FIG. 13 is an explanatory diagram showing a mesh area of map data when a sea exists between an area A and an area B by the map data management method and the route search device according to the third embodiment of the present invention.

FIG. 14 is an explanatory diagram showing a mesh area when a division based on the presence or absence of a road is added to the area division by the map data management method and the route search device according to the fourth embodiment of the present invention.

FIG. 15 is a flowchart illustrating a map data management operation performed by the map data management method and the route search device according to the fourth embodiment of the present invention.

FIG. 16 is an explanatory diagram showing a mesh system used in the national land numerical information of the Geospatial Information Authority of Japan, as an example of area division in a conventional map data management method and a route search device.

FIG. 17 is an explanatory diagram showing a binary search for performing a high-speed search to determine whether or not given coordinates are within a search range in a conventional map data management method and a route search device.

FIG. 18 is an explanatory diagram showing a binary search for performing a high-speed search to determine whether or not given coordinates are within a search range in a conventional map data management method and a route search device.

FIG. 19 is an explanatory diagram of extracting a node within a certain range of a search range p from a reference point in a mesh area M in the conventional map data management method and route search device.

[Explanation of symbols]

3 external map memory (map data storage means), 4a area management means, 4b node data management means, 4c area detection means, 4d node detection means, 41 divided area number variable means, M mesh area (management area), NTBL,
NTBL0, NTBL1, NTBL2, NTBL3 Node table.

Claims (13)

[Claims] 1. A map data management method for managing map data of a road network as numerical information, wherein the map data is divided into a plurality of management areas, and an intersection or the like in each management area created for each management area. Sorting a certain row of nodes in either ascending or descending order of either the latitude coordinate value or the longitude coordinate value, and using the sorted node information as the coordinate axes of the coordinate values used for the sorting. A map data management method which manages data in a node table including sub-tables each corresponding to each divided area when the management area is divided by a dividing line parallel to the above. 2. According to the road data density in the management area,
Changing the width of the divided area that divides the management area, changing the size of the node search range corresponding to the width of the divided area,
2. The map data management method according to claim 1, wherein a divided area that overlaps the search range around a reference point is selected. 3. The map data of the management area is divided into map data having a plurality of hierarchical structures from a wide area hierarchy to a narrow area hierarchy according to the size of each divided area when the wide area map data is divided. , The arrangement of nodes such as intersections of the management area created for the map data of the narrow area hierarchy,
Sorted in ascending or descending order of either the coordinate value of latitude or the coordinate value of longitude, and the information of the sorted nodes is divided by a dividing line parallel to the coordinate axes of the coordinate values used for the sorting. The first sub-table held in correspondence with each of the divided areas when the map data of the narrow area is divided and the map data of the narrow area composed of the divided areas are sequentially stored in an upper layer 3. The map data management method according to claim 1, wherein the map data is managed by a node table including a second sub-table corresponding to the map data. 4. The map data management method according to claim 3, wherein the map data has a two-layer structure of map data of a wide area hierarchy and map data of a narrow area hierarchy. 5. The map data management method according to claim 3, wherein the map data has a three-layer structure of map data of a wide area, map data of a medium area, and map data of a small area. . 6. A map data management method for managing map data of a road network as numerical information, wherein a map creation range is divided into a plurality of management areas, and each of the divided management areas is divided into a road and an area where a road exists. In the above-described management area, when there are a plurality of divided areas having no connection with the road network in the management area, the management is performed. A map data management method, comprising dividing an area for each set of feature points having a connection relationship in an area, creating a node table, and managing node information in the created node table. 7. Each of the divided areas is divided into an area having a road and an area having no road that clearly indicates the presence or absence of a road in each of the divided areas. 2. The map data management method according to claim 1, wherein the map data is managed by a node table including corresponding sub tables. 8. A route search device for detecting a vehicle position and calculating an optimal route to a destination by using a digital map storing a road network as numerical information, wherein a map data is stored for each management area. A data storage unit, a longitude or a latitude is selected as a reference when sorting node data of map data for each management area stored by the map data storage unit, and a division parallel to the selected longitude or latitude coordinate axis is performed. Area management means for dividing the management area into a plurality of divided areas by lines, and managing the divided areas divided by the area management means in ascending order of the coordinate values of the selected longitude or latitude or Node data that constitutes a sub-table in which node data is sorted in descending order and manages the node data in the sub-table Management means, when coordinates serving as a reference point for search are given, area detection means for selecting a divided area having an overlap with a search range centered on the reference point, and each of the areas selected by the area detection means A route search device comprising: node detection means for extracting a node within the search range from node data corresponding to the divided area. 9. A divided area number changing means for changing the number of divided areas according to the road density in the management area, wherein the area detecting means changes the divided area when the divided area number is changed by the divided area number changing means. 9. The route search device according to claim 8, wherein the size of the search range of the node is changed according to the width of the area, and a divided area overlapping the search range around a reference point is selected. 10. An area management means, for map data having a plurality of hierarchical structures from a wide area hierarchy to a narrow area hierarchy for a management area, at an intersection or the like in the management area created for the map data of the narrow area hierarchy. A longitude or latitude is selected as a criterion when sorting the arrangement of certain nodes, and the information of the nodes sorted in ascending or descending order with respect to any of the selected longitude or latitude coordinate values, A first sub-table held in correspondence with each divided area when the map data of the narrow area is divided by a dividing line parallel to a coordinate axis of the coordinate value used for sorting, and each of the divided areas Are managed in a node table consisting of a second sub-table that sequentially corresponds to the map data of a higher hierarchy. Route searching apparatus according to claim 8 or claim 9, wherein the. 11. The area management means has a two-layer hierarchical structure in which the management area is composed of map data of a wide area and map data of a small area when the map data of the wide area is divided into a plurality of pieces. For map data,
A longitude or a latitude is selected as a criterion when sorting the arrangement of nodes such as intersections in the management area created for the map data of the narrow area hierarchy, and any one of the coordinate values of the selected longitude or latitude is selected. The information of the nodes sorted in ascending or descending order with respect to each divided area when the map data of the narrow area is divided by a dividing line parallel to a coordinate axis of the coordinate value used for the sorting. And a first sub-table held in correspondence with the first and second sub-tables, and a second sub-table associated with the map data in the wide-area hierarchy. 10. The route search device according to claim 8, wherein the route search is performed. 12. The area management means comprises a map data of a wide area, a map data of a middle layer when the map data of the wide area is divided into a plurality of pieces, and a map of each of the middle layers. For map data having a three-layer hierarchical structure including map data of a narrow area when the data is further divided into a plurality of pieces, nodes such as intersections in the management area created for the map data of the narrow area, The longitude or the latitude is selected as a reference when performing sorting on the arrangement of the nodes, and the information of the nodes sorted in ascending order or descending order with respect to any of the selected coordinate values of the longitude or the latitude is used for the sorting. The first sub-table held in correspondence with each divided area when the map data of the narrow area is divided by a dividing line parallel to the coordinate axis of the coordinate value used for this purpose And managing the map data of the narrow area composed of the divided areas in a node table including a second sub-table corresponding to the map data of the middle area and the wide area. The route search device according to claim 8 or 9. 13. The computer selects a longitude or a latitude as a criterion for sorting the node data of the map data for each management area stored by the map data storage means, and selects a longitude or a latitude in parallel with the coordinate axis of the selected longitude or the latitude. Area management procedure for dividing the management area into a plurality of divided areas by means of a simple dividing line and managing the divided areas divided by the area management means. A sub-table in which node data is sorted in ascending or descending order, a node data management procedure for managing the node data in the sub-table, and when coordinates serving as search reference points are given, the reference points are defined. An area detection procedure for selecting a divided area having an overlap with the centered search range; and each divided area selected by the area detecting means. A program for causing a computer to execute a node detection procedure for extracting a node within the search range from node data corresponding to (a).