WO2013121560A1 - Map information processing device - Google Patents

Abstract

The purpose of the invention is to enable a reduction in time needed for a process that traces a road network. A map information processing device stores road network data in a map information storage unit (3). Said road network data is stored as information that indicates a connection relationship between a node defining the road network and a link. Said road network data comprises connection link information, which contains: information about the link, which is connected to the node; and information about a mesh to which the link belongs. On the basis of the connection link information, a processor (4) finds and stores in memory, neighboring node information that indicates a neighboring node, which is a node connected from a specified node via one link. After finding the neighboring node information of all the neighboring nodes for all the nodes contained in the acquired road network data, the processor (4) perform a process on map information using the road network data and the neighboring node information.

Description

Map information processing device

The present invention relates to a map information processing apparatus, and more particularly to a map information processing apparatus that performs map information processing including map matching processing and route search processing based on map data.

In a general map information processing apparatus, map data includes information on a road network including information on nodes indicating specific points such as intersections and information on links indicating roads between nodes. The map data is divided for each mesh (unit) divided into rectangular shapes and stored in the map data storage unit.

A conventional map information processing apparatus has, as map data, connection information (one-side connection information) indicating a connection relationship from a link to a node (or a node to a link), and a node to a link (or a link to a node). The connection information (the other side connection information) indicating the connection relationship is stored in the map data storage unit, and the map information processing using them is performed. However, the method of storing both the one-side connection information and the other-side connection information has a problem that the amount of map data to be stored becomes enormous as the range of the map to be handled increases.

In the map information processing apparatus of Patent Document 1, only one side connection information is stored as map data, and the other side connection information is supplemented as necessary, whereby the amount of map data stored in the map data storage unit in advance is reduced. Techniques to reduce it have been proposed. The map information processing apparatus of Patent Document 1 stores only one-side connection information indicating a connection relationship from a link to a node (or from a node to a link), and the mesh information necessary for map information processing is stored from the map data storage unit. The map data is read out, and the other side connection information indicating the connection relation from the node to the link (or from the link to the node) is generated based on the one side connection information included in the map data. The map processing is not performed using only one-side connection information stored in advance, but is executed after complementing the other-side connection information necessary for processing, so that the processing speed similar to the conventional one is maintained. The

JP 2002-365077 A

When a road network is traced in map matching or route search processing, it is necessary to obtain another node (adjacent node) connected from the node via one link for each traced node. In Patent Document 1, in order to obtain an adjacent node of each node, first, each link connected to the node is obtained from connection information indicating a connection relation from the node to the link, and then, a connection relation from the link to the node is obtained. It is necessary to take a procedure such as obtaining other nodes (that is, adjacent nodes) connected to each link connected to the node from the connection information to be expressed. As described above, since the adjacent node cannot be obtained directly, there is a problem that it takes time to follow the road network.

The present invention has been made to solve the above-described problems, and an object of the present invention is to provide a map information processing apparatus capable of reducing the time required for processing to follow a road network.

The map information processing apparatus according to the present invention is a storage means for dividing and storing map information into meshes, defining a road network with nodes provided in the mesh and links connecting the nodes, and connecting to the nodes Map information storage means for storing for each mesh the road network data having connection link information including information on the link to be linked and information on the mesh to which the link belongs, and a desired road from the map information storage means Adjacent node calculation for obtaining adjoining node information indicating an adjoining node that is a node connected through a single link from a specific node based on road network data acquisition means for acquiring network data and connection link information of the acquired road network data Included in the acquired road network data, the adjacent node information storing means for storing the adjacent node information obtained by the adjacent node calculating means, and the acquired road network data Map information processing means for obtaining adjacent node information of all adjacent nodes for all nodes, storing the information in the adjacent node information storage means, and processing the map information using the road network data and the adjacent node information; Prepare.

According to the present invention, the map information processing means can immediately acquire the adjacent node by referring to the adjacent node information. Therefore, the process of tracing the road network can be performed at high speed, and map information processing such as route search and map matching can be performed at high speed.

It is a block diagram which shows an example of a structure of the map information processing apparatus which concerns on embodiment of this invention. It is a figure which shows an example of the data structure of the map information memorize | stored in the map information storage part which concerns on embodiment of this invention. It is a figure which shows an example of the structure of the road network data which concerns on embodiment of this invention. It is a figure which shows an example of the adjacent mesh code | cord | chord which concerns on embodiment of this invention. It is a figure which shows an example of the relationship between the link which concerns on embodiment of this invention, and a mesh. It is a figure which shows an example of the connection direction of the link which concerns on embodiment of this invention. It is a figure which shows an example of the road network represented by a node and a link. It is a figure which shows an example of each node record stored in the node list in the mesh MA of FIG. It is a figure which shows an example of each link record stored in the link list in the mesh MA of FIG. It is a figure which shows an example of each node record stored in the node list in the mesh MB of FIG. It is a figure which shows an example of each link list in the mesh MB of FIG. It is a figure which shows an example of the node offset table which concerns on embodiment of this invention. It is a figure which shows an example of the link offset table which concerns on embodiment of this invention. It is a figure which shows an example of the adjacency list which concerns on embodiment of this invention. It is a flowchart which shows the processing operation | movement which produces | generates the road network auxiliary data which concern on embodiment of this invention. It is a figure which shows an example of the adjacent node table and adjacent offset table corresponding to the mesh MA of FIG. It is a figure which shows an example of the adjacent node table and adjacent offset table corresponding to the mesh MB of FIG. It is a figure which shows an example of the adjacency table which concerns on embodiment of this invention. It is a figure which shows an example of the adjacent relationship table corresponding to the mesh MA of FIG. It is a figure which shows an example of the adjacency table corresponding to the mesh MB of FIG. It is a flowchart which shows the production | generation process of road network auxiliary data in the map information processing apparatus concerning embodiment of this invention. It is a figure which shows an example of the content of the memory used for the production | generation process of the road network auxiliary data which concerns on embodiment of this invention. It is a figure which shows the specific example of the registration content of the adjacent node table of the adjacent list in step ST130 and step ST150 of FIG. It is a flowchart which shows the detail of a process of step ST130 of FIG. It is a flowchart which shows the detail of a process of step ST150 of FIG. It is a flowchart which shows the calculation process of an adjacent node in the processor of the map information processing apparatus concerning embodiment of this invention.

Embodiments of the present invention will be described below based on the drawings.

<Configuration of map information processing device>
First, the configuration of the map information processing apparatus according to the embodiment of the present invention will be described.

FIG. 1 is a block diagram showing an example of the configuration of the map information processing apparatus according to the embodiment of the present invention. As shown in FIG. 1, the map information processing apparatus according to the present embodiment includes an input unit 1, a position detection unit 2, a map information storage unit 3, a processor 4, a display unit 5, and an audio output unit 6 described below. I have.

The input unit 1 is a group of operation switches that transmit an instruction signal based on a user operation or instruction to the processor 4 and functions as an input unit.

The position detection unit 2 functions as a position detection unit that performs position detection using, for example, a GPS (Global Positioning System) receiver, a vehicle speed sensor, an acceleration sensor, an angular velocity sensor, and the like. The position detection unit 2 detects the current position of the moving object that holds the map information processing apparatus according to the present embodiment, and transmits position information indicating the detected current position to the processor 4.

The map information storage unit 3 (map information storage means) functions as map information storage means constituted by a hard disk drive as a medium for recording map information, for example. The map information storage unit 3 stores map information described later in advance.

The processor 4 functions as a map information processing unit that performs various types of map information processing based on the instruction signal acquired from the input unit 1, the position information acquired from the position detection unit 2, and the map information read from the map information storage unit 3. To do. The processor 4 also performs display processing in the display unit 5 and includes a drawing memory (not shown), a drawing processing unit (not shown), and a display control unit (not shown) for use in the control. Yes. The drawing processing unit draws the image in the drawing memory, and the display control unit reads the image drawn in the drawing memory and sends it to the display unit 5, whereby the image is displayed on the display unit 5.

Various types of map information processing performed by the processor 4 include a map matching process for estimating the current position of the moving object based on the position information acquired from the position detection unit 2 and the map information read from the map information storage unit 3. , Route search processing to calculate the route from the departure point to the destination, route guidance processing to guide from the departure point to the destination according to the route obtained by the route search processing, map display processing around the current position, city Various search processes for searching various information such as roads, facilities, addresses, telephone numbers, intersections, and the like are included.

Further, based on the map information read from the map information storage unit 3, drawing of the map centered on the current position estimated by the map matching process, and movement obtained by the above map information processing on the drawn map The current position of the body, a suitable route obtained by route search processing, drawing of guidance information for guiding from the departure point to the destination according to the route, drawing of various input information, and various information obtained by searching Drawing processing by the drawing processing unit of the processor 4 such as drawing is included in the map information processing.

The display unit 5 is a display device made up of a liquid crystal display, for example, and functions as a display means. The display unit 5 displays the contents drawn in the drawing memory in accordance with the various drawing processes by the drawing processing unit of the processor 4 based on the control of the display control unit of the processor 4.

The voice output unit 6 functions as a voice output unit that conveys information obtained as a result of various types of map information processing performed by the processor 4 to the user by voice. The voice output unit 6 conveys, for example, information for performing guidance from the departure point to the destination according to a suitable route obtained by the route search process, various information obtained by the search, and the like by voice.

<Map information>
The map information memorize | stored in the map information storage part 3 is demonstrated. The map information stored in the map information storage unit 3 is managed for each mesh partitioned by a quadrilateral area surrounded by latitude and longitude at predetermined intervals. That is, the map information storage unit 3 stores map information divided into meshes. Further, the map information is hierarchized according to the degree of detail of information, and is managed for each mesh sectioned in each hierarchy.

In order to identify each hierarchy, a number (hierarchy number) is assigned to each hierarchy in the order of 0, 1, 2,... From the hierarchy having the most detailed information. In each layer, a unique number (mesh number) is assigned to each mesh in order to identify each mesh.

For example, if a mesh of a certain layer is defined as 256 regions obtained by dividing the map into 16 in the latitude direction and 16 in the longitude direction, each mesh in the layer has 0 to 255. Either mesh number is assigned. Hereinafter, a mesh to be processed may be referred to as a “target mesh”, and a mesh adjacent to the target mesh may be referred to as an “adjacent mesh”.

FIG. 2 is a diagram illustrating an example of a data structure of map information stored in the map information storage unit 3 according to the present embodiment. As shown in FIG. 2, the map information includes map management information, map data, and search information (data for searching various information such as cities, roads, facilities, addresses, telephone numbers, intersections, etc.). .

The map management information includes version information indicating the version of map information, hierarchy management information for managing each map data for each hierarchy, search management information for managing various search information, and the like. The hierarchy management information has information such as the mesh number of each mesh, the storage position of each map data in the map information, and the data size for each hierarchy.

The map data has a map data header, road network data, background data, name data, and route guidance data, and is prepared for each mesh in each layer. The map data header has information for managing each data in the map data. The road network data has information indicating the road network in each mesh. The background data includes plane data indicating rivers, seas, etc., line data indicating linear rivers, railways, etc., and point data indicating facility symbols. The name data includes character string data indicating a place name, a river name, a facility name, and the like. The route guidance data includes information necessary for route guidance at an intersection or the like.

<Road network data>
The road network data included in the map data of the map information will be described in more detail. FIG. 3 is a diagram illustrating an example of the structure of road network data. The road network data is road network data defined by node information indicating intersections and specific points on the road and link information indicating roads connecting the nodes. As shown in FIG. 3, the road network data includes a road network data header, a node list, a link list, and a shape list.

(A) Road network data header The road network data header included in the road network data includes a planned road presence / absence information indicating the presence / absence of a road planned based on the city planning method, and a node indicating the number of nodes existing in the mesh. Necessary for managing road network data such as the number, the number of links indicating the number of links present in the mesh, and the list management information indicating the storage location and data size of the node list, link list, and shape list in the road network data Information.

(B) Node list The node list included in the road network data has a node record provided corresponding to each node existing in the mesh. Assume that each node record is assigned a node number corresponding to the order of node records in the node list.

The node record of each node is a connection link having node coordinates indicating the geographical position of the node, the number of connection links indicating the number of links connected to the node, and connection link information which is information of the link connected to the node. It consists of a table. The connection link table includes the same number of connection link information as the links connected to the node.

The connection link information includes connection link mesh information indicating a mesh to which a link connected to the node belongs, a connection direction of a link connected to the node, and a number (connection link number) for specifying the link. Hereinafter, a link connected to a node is also referred to as a “connection link”.

The connection link mesh information is information for specifying the mesh to which the connection link of the node belongs. In the present embodiment, the connection link mesh information is indicated by an “adjacent mesh code” that specifies the mesh to which the connection link belongs in the relative position to the mesh (target mesh) to which the node belongs. The adjacent mesh code has a value associated with each of the target mesh and the adjacent mesh.

FIG. 4 is a diagram illustrating an example of an adjacent mesh code. The adjacent meshes are meshes adjacent to the upper, upper right, right, lower right, lower, lower left, left, upper left of the target mesh. The target mesh and the adjacent mesh are indicated by adjacent mesh codes “0” to “8”. It is. As shown in FIG. 4, in this embodiment, the adjacent mesh code of the target mesh is indicated by “0”, and the adjacent mesh code of each adjacent mesh is the upper, upper right, right, lower right, lower, lower left of the target mesh. "1" to "8" in the order of left and upper left. Here, “up”, “down”, “left”, and “right” represent planar directions on the map. For example, “north”, “south”, “west”, Corresponds to “East”.

As described above, in the map information processing apparatus of the present embodiment, in the road network data, the mesh to which each connection link belongs is specified using the adjacent mesh code indicating the relative position to the target mesh. In this case, the amount of information can be reduced compared to the case where each connected mesh is indicated by a mesh number unique to each mesh.

However, with this method, it is necessary to consider the case where the connection link spans multiple meshes. For example, when a connection link straddles two meshes, it is necessary to define which mesh the connection link belongs to. In the present embodiment, the direction attribute is given to each link so that the mesh to which each link belongs is determined to be one. In other words, assuming that one end of the link is the start point (start node) and the other end is the end point (end node), each link is defined as belonging to the mesh on the side including the start point (of course, the end point is It may be defined as belonging to the containing mesh). Thereby, even if a connection link straddles a plurality of meshes, the mesh to which it belongs is determined to be one. Note that the direction (start point and end point) of each link is determined in advance when the road network data is created.

Further, in the adjacent mesh code shown in FIG. 4, since a mesh that is two or more away from the target mesh (a mesh outside the adjacent mesh) is not a specific target, the connection link spans three or more meshes. In such a case, the mesh to which the connection link belongs may not be specified. For example, if the end point of a connection link is connected to a node located in the target mesh, and the connection link spans three or more meshes, the start point of the connection link is the mesh outside the adjacent mesh. To position. In this case, the mesh to which the connection link belongs (mesh in which the start point node is located) cannot be expressed using the adjacent mesh code.

In this embodiment, as a countermeasure, a link spanning three or more meshes is divided into a plurality of links. For example, as shown in FIG. 5A, it is assumed that there is a link (connection link) La straddling three meshes, and the left mesh is the target mesh among the three meshes. That is, the center mesh is an adjacent mesh, and the right mesh is an outer mesh than the adjacent mesh. As shown in FIG. 5A, the node at one end of the link La exists in the target mesh, and the node at the other end exists in a mesh outside the adjacent mesh.

In the present embodiment, when there is a link La straddling three meshes as described above, as shown in FIG. 5B, a new node is generated in the adjacent mesh, and the link La is converted into two links La1, Divide into La2. Since the links La1 and La2 obtained as a result straddle two meshes, the mesh to which they belong can be specified by the adjacent mesh code. This division processing is performed in advance when the road network data is created. Even when there are links over four or more meshes, the above method may be repeated and divided into a plurality of links.

There are other advantages to this method of dividing a link straddling three or more meshes into a plurality of links straddling two meshes. For example, if the current location exists in the target mesh and map matching processing or route search processing is performed around the current location and the link exists across three meshes as shown in FIG. In addition to the road network data of the mesh, it is necessary to obtain and process from the map information storage unit 3 the road network data of the mesh that is two distances away from the target mesh (the rightmost mesh in FIG. 5A).

On the other hand, as shown in FIG. 5 (b), if there is only a link straddling two meshes, processing can be performed by acquiring only the road network data of the target mesh and the adjacent mesh from the map information storage unit 3. it can. That is, by dividing a link straddling three or more meshes into links straddling two meshes, there is no need to acquire road network data of a mesh two or more away from the target mesh from the map information storage unit 3, The road network data can be read efficiently. Further, since the amount of road network data read from the map information storage unit 3 is reduced, access to the map information storage unit 3 is accelerated.

Hereinafter, for the sake of simplicity of explanation, the description will be made on the assumption that there is no link across three or more meshes (or link division processing across three or more meshes is performed in advance).

As described above, in this embodiment, each link has a direction attribute (start point and end point). The “connection direction” included in the connection link information illustrated in FIG. 3 is information indicating whether the node is connected to the start point side or the end point side of the connection link. The connection direction when the node is the start point of the connection link is defined as “forward direction”, and the connection direction when the node is the end point of the connection link is defined as “forward direction”.

For example, as shown in FIG. 6, the link Lx connects the node Nx1 and the node Nx2 (the arrow indicates the direction of the link Lx), the node Nx1 is the start node, and the node Nx2 is the end node. Suppose that In this case, the connection direction of the link Lx to the start node Nx1 is the forward direction, and the connection direction of the link Lx to the end node Nx2 is the reverse direction. It should be noted that which link is set as the start point (or end point) is determined in accordance with the direction of each link when the road network data is created.

(C) Link list The link list included in the road network data has a link record provided corresponding to each link existing in the mesh. The link record has link attribute information indicating various attributes such as a road type, a width, and a link length of the link, and a shape record storage position indicating a storage position of the shape record corresponding to the link in the shape list. Each link record is given a link number corresponding to the order of the link records in the link list.

In the present embodiment, the link record does not store information indicating the connection relationship from the link to the node (node numbers indicating the start point node and the end point node). Thereby, the data amount of the road network data memorize | stored in the map information storage part 3 can be reduced rather than before.

When a link straddles a plurality of meshes, the link belongs to the mesh in which the start point node exists. The link record is stored in a link list corresponding to the mesh to which the link belongs. Thereby, even when a link straddles a plurality of meshes, one link list for storing the link record of the link is determined. As a result, the link record is not duplicated and stored in the link list of the two meshes in which the nodes at both ends of the link exist (that is, only in the link list of the mesh in which the node at one end of the link exists). The amount of road network data stored in the map information storage unit 3 can be reduced.

(D) Shape List The shape list has shape records provided corresponding to links existing in the mesh. The shape record includes a shape point number indicating the number of shape points of the road shape of the link, and a shape point list indicating the road shape of the link by broken line approximation and indicating the geographical position of the shape point which is the vertex of the represented broken line. Have.

(E) Specific Example of Road Network Data Here, specific examples of the node list and link list included in the road network data are shown.

FIG. 7 is a diagram showing an example of a road network represented by links and nodes. FIG. 7 shows links and nodes in the three meshes MA, MB, and MC (the arrows indicate the directions of the links). For example, when the mesh MA is the target mesh, the mesh MB is an adjacent mesh adjacent to the right side of the target mesh MA. Further, the mesh MC is adjacent to the right side of the adjacent mesh MB, but is not adjacent to the target mesh MA. That is, the mesh MC is not an adjacent mesh of the target mesh MA.

FIG. 8 is a diagram showing an example of each node record stored in the node list of the mesh MA in FIG. As shown in FIG. 8, the node list of the mesh MA stores node records of nodes NA0, NA1, NA2, and NA3 to which node numbers 0, 1, 2, and 3 are assigned, respectively. Further, as described above with reference to FIG. 3, each node record stores node coordinates, the number of connection links, and a connection link table. Further, the connection link table includes connection links as connection link information. Link mesh information, connection direction, and connection link number are stored.

Here, it is assumed that the connection link mesh information is represented by the adjacent mesh code shown in FIG. The information on the connection direction of the connection link represents 0 when the link connection direction is the forward direction and 1 when the link connection direction is the reverse direction. Further, in the mesh MA, the links LA0, LA1, and LA2 whose starting points are located in the mesh MA are given link numbers 0, 1, and 2 (these are the links of the link records shown in FIG. 9). Corresponding to the number). Similarly, in the mesh MB, it is assumed that the links LB0, LB1, LB2, and LB3 whose starting points are located in the mesh MB are assigned link numbers 0, 1, 2, and 3 (these are shown in FIG. 10). Corresponding to the link number of each link record).

FIG. 9 is a diagram illustrating an example of a link record stored in the link list of the mesh MA in FIG. As shown in FIG. 9, in the link list of mesh MA, link records A0, A1, A2 of links LA0, LA1, LA2 belonging to mesh MA (where the start point is located in mesh MA) are link numbers 0, 1, 2, respectively. Has been granted and stored. The link LB0 is connected to the node NA0 in the mesh MA, but belongs to the mesh MB (the start point is located in the mesh MB), so the link record of the link LB0 is stored in the link list of the mesh MA. Not.

FIG. 10 is a diagram showing an example of each node record stored in the node list of the mesh MB of FIG. As shown in FIG. 10, node records of nodes NB0, NB1, and NB2 to which node numbers 0, 1, and 2, respectively, are stored are stored in the node list of the mesh MB. Similarly to FIG. 8, each node record stores node coordinates, the number of connection links, and a connection link table. Further, the connection link table includes connection link mesh information, connection direction as connection link information. And the connection link number is stored.

FIG. 11 is a diagram illustrating an example of a link record stored in the link list of the mesh MB in FIG. As shown in FIG. 11, in the link list of mesh MB, link records of links LB0, LB1, LB2, and LB3 belonging to mesh MB are stored with link numbers 0, 1, 2, and 3, respectively. .

Thus, in this embodiment, the road network is defined by the nodes provided in the mesh and the links connecting the nodes. In the map information storage unit 3 (map information storage means) of the map information processing apparatus, road network data (map information) including link information connected to a node and connection link information including information of a mesh to which the link belongs is stored. , Divided for each mesh and stored.

<Road network assistance data>
When a road network is traced in map matching or route search processing, for each node to be traced, it is necessary to obtain another node (adjacent node) connected from the node via one link. In the map information processing apparatus according to the present embodiment, road network auxiliary data for efficiently (high-speed) executing processing for obtaining adjacent nodes is created. The road network auxiliary data is generated by the processor 4 based on the road network data read from the map information storage unit 3 and stored in the memory of the processor 4 together with the road network data.

The road network auxiliary data includes a node offset table, a link offset table, an adjacency list, an adjoining offset table, and an adjacency relationship table, which will be described below.

(A) Node Offset Table FIG. 12 is a diagram illustrating an example of a data configuration of the node offset table. The node offset table stores a node record offset (the number of bytes from the beginning of the node list to the beginning of each node record) indicating the recording position of the node record of each node in the node list. Since each node record offset is a fixed-length record, the storage position of the node record offset corresponding to the node can be known from the node number of each node. Therefore, the processor 4 can access the node record of the desired node immediately by referring to the node offset table and acquire the node record.

(B) Link Offset Table FIG. 13 is a diagram illustrating an example of a data configuration of the link offset table. The link offset table stores a link record offset (number of bytes from the top of the link list to the top of each link record) representing the recording position of the link record of each link in the link list. Since each link record offset is a fixed-length record, the storage position of the link record offset corresponding to the link is known from the link number of each link. Therefore, the processor 4 can access the link record of a desired link immediately by referring to the link offset table and acquire the link record.

(C) Adjacency list FIG. 14 is a diagram illustrating an example of the data structure of the adjacency list. The adjacent list includes an adjacent node table corresponding to each node. In the adjacent node table, adjacent node records, which are information for specifying each adjacent node of the corresponding node, are stored side by side in association with the connection link connected to the adjacent node.

The adjacent node record includes adjacent node mesh information in which the mesh to which the adjacent node belongs is expressed by an adjacent mesh code and the adjacent node number that is the node number of the adjacent node, and is associated with the connection link connected to the adjacent node. ing. Therefore, the processor 4 can immediately obtain an adjacent node for an arbitrary node by referring to the adjacent list.

However, as shown in FIG. 3, in the road network data of the present embodiment, the node list stores information (connection link information) indicating the connection relationship from the node to the link. Does not store information indicating the connection relationship from link to node. That is, in the road network data, only information on nodes connected to one side of each link is described, and information on which node is adjacent to the node is not described. Therefore, the processor 4 searches for adjacent nodes of each node in advance, and creates an adjacent list based on the search result.

Here, an outline of a method in which the processor 4 creates an adjacency list from road network data (a method of searching an adjacent node of each node) will be described. In the following, when a certain node is specified as an “adjacent node”, a node that serves as a reference for specifying the node as an adjacent node is referred to as an “original node”.

For example, when nodes N1 and N2 are connected to both ends of a certain link L1, with node N1 as a reference, node N2 is an adjacent node of node N1 via link L1, and node N1 becomes its original node . In this case, the link L1 may be referred to as “the original node of the link L1”, and the link L2 may be referred to as “the connection node of the link L1”.

Conversely, with node N2 as a reference, node N1 is an adjacent node of node N2 via link L1, and node N2 is its original node. In this case, the link L2 may be referred to as “the original node of the link L1”, and the link L1 may be referred to as “the connection node of the link L1”.

Thus, the two nodes N1 and N2 connected to the link L1 can both be an original node and an adjacent node of the link L1. That is, when the nodes at both ends of the link L1 are exchanged, it can be determined that two nodes that appear as original nodes (or adjacent nodes) are adjacent to each other via the link L1.

Therefore, for example, when the first record in which the node N1 is described as the original node of the link L1 and the second record in which the node N2 is described as the original node of the link L1 are respectively stored in the memory, When the records are exchanged, a record in which the adjacent node is described in each of the storage locations is obtained. That is, the third record in which the node N2 is described as the original node of the link L1 is obtained at the place where the first record is stored, and the node N1 is linked to the place where the second record is stored. A second record described as the original node of L1 is obtained.

Referring to the first and third records (or the second and fourth records), it can be seen that one end of the link L1 is connected to the node N1, and the other end is connected to the node N2. That is, it can be determined that the node N1 and the node N2 are adjacent to each other via the link L1.

Using this property, the processor 4 searches for adjacent nodes of each node from the connection link information of the node list, and creates an adjacent list based on the search result.

(D) Adjacent Offset Table FIG. 15 is a diagram illustrating an example of the data configuration of the adjacent offset table. The adjacent offset table stores an adjacent node table offset (number of bytes from the head of the adjacent list to the head of each adjacent node table) indicating the recording position of each adjacent node table in the adjacent list. Since each adjacent node table offset is a fixed-length record, the storage position of the adjacent node table offset of the node can be known from the node number of each node. Therefore, the processor 4 can immediately access the adjacent node table of the desired node by referring to the adjacent offset table to obtain the adjacent node table.

(E) Specific Example of Adjacency List FIG. 16 is a diagram illustrating an example of the adjacency node table of the adjacency list corresponding to the mesh MA in FIG. 7 and an adjacency offset table associated therewith. As shown in FIG. 16, the adjacent list of the mesh MA includes an adjacent node table corresponding to each of the nodes NA0, NA1, NA2, and NA3 belonging to the mesh MA. In the adjacent offset table of the mesh MA, adjacent node table offsets indicating the storage positions of the adjacent node tables corresponding to the nodes NA0, NA1, NA2 and NA3 are stored.

The adjacent node table of the node NA0 is composed of adjacent node records NNRA00, NNRA01, NNRA02, and NNRA03 corresponding to the connection nodes LA0, LA1, LA2, and LB0 of the node NA0. These adjacent node records NNRA00, NNRA01, NNRA02, and NNRA03 correspond to connection link information A00, A01, A02, and A03 described in the node record of the node NA0 in the node list (FIG. 8). Each of the adjacent node records NNRA00, NNRA01, NNRA02, and NNRA03 represents the adjacent nodes NA1, NA2, NA3, and NB0 connected to the node NA0 through the connection nodes LA0, LA1, LA2, and LB0.

Further, the adjacent node table of the node NA1 is composed of an adjacent node record NNRA10 corresponding to the connection node LA0. The adjacent node record NNRA10 corresponds to the connection link information A10 described in the node record of the node NA1 in the node list (FIG. 8), and represents the adjacent node NA0 connected to the node NA0 via the connection node LA1. . Similarly, the adjacent node table of the node NA2 includes an adjacent node record NNRA20 that is associated with the connection node LA1 and represents the adjacent node NA0. The adjacent node table of the node NA3 includes an adjacent node record NNRA30 that is associated with the connection node LA2 and represents the adjacent node NA0.

FIG. 17 is a diagram showing an example of an adjacent node table of an adjacent list corresponding to the mesh MB of FIG. 7 and an adjacent offset table associated therewith. As shown in FIG. 17, the adjacent list of the mesh MB is provided with an adjacent node table corresponding to each of the nodes NB0, NB1, and NB2 belonging to the mesh MB. The adjacent offset table of the mesh MB stores adjacent node table offsets indicating the storage positions of the adjacent node tables corresponding to the nodes NB0, NB1, and NB2.

The adjacent node table of the node NB0 includes adjacent node records NNRB00, NNRB01, NNRB02, and NNRB03 corresponding to the connection nodes LB0, LB1, LB2, and LB3 of the node NB0. These adjacent node records NNRB00, NNRB01, NNRB02, and NNRB03 correspond to connection link information B00, B01, B02, and B03 described in the node record of the node NB0 in the node list (FIG. 10). Each of the adjacent node records NNRB00, NNRB01, NNRB02, and NNRB03 represents the adjacent nodes NA0, NB1, NC0, and NB2 connected to the node NB0 via the connection nodes LB0, LB1, LB2, and LB3.

Similarly, the adjacent node table of the node NB1 includes an adjacent node record NNRB10 that is associated with the connection node LB1 and represents the adjacent node NB0. The adjacent node table of the node NB2 includes an adjacent node record NNRB20 associated with the connection node LB3 and representing the adjacent node NB0.

As described above, since the offset of the adjacent node table of the corresponding node is known from the node number, the processor 4 can immediately acquire the adjacent node table by referring to the adjacent offset table. Then, the adjacent node of the desired node can be immediately obtained from the acquired adjacent node table. Therefore, the processor 4 can efficiently (at a high speed) execute processing for obtaining an adjacent node.

(F) Adjacency Table FIG. 18 is a diagram showing the configuration of the adjacency table. The adjacency table indicates the storage position in the memory of the processor 4 of each adjoining node record representing two nodes that are adjacent to each other.

The adjacency table is composed of adjacency records associated with each link. The association between the adjacency record and the link is made by specifying the adjacency record with the link number of the link corresponding to the adjacency record.

Each of the adjacent relationship records includes a first adjacent node record offset and a second adjacent node record offset. The first and second adjacent node record offsets indicate offsets of adjacent node records corresponding to two nodes that are adjacent to each other. The offset of the adjacent node record is information indicating the storage position of each adjacent node record. For example, when the adjacent list is stored in the memory in the ascending order of the adjacent mesh code, the adjacent mesh code is “0”. It can be represented by the number of bytes from the head of the adjacent list to the corresponding adjacent node record. Thus, the first and second adjacent node record offsets can point to adjacent node records in any mesh's adjacent list.

(G) Specific Example of Adjacency Table FIG. 19 is a diagram showing an adjacency table corresponding to the mesh MA in FIG. In the adjacency table of the mesh MA, adjacency records (first and second adjacent node record offsets) corresponding to the links LA0, LA1, and LA2 belonging to the mesh MA are stored.

For example, the link LA0 connects the node NA0 and the node NA1 that are adjacent to each other. Therefore, in the adjacency record corresponding to the link LA0, the offset of the adjoining node record NNRA00 corresponding to the link LA0 and representing the node NA1 is stored as the first adjoining node record offset, and as the second adjoining node record offset The offset of the adjacent node record NNRA10 associated with the link LA0 and representing the node NA0 is stored.

Similarly, in the adjacency record corresponding to the link LA1, the offset of the adjacent node record NNRA01 corresponding to the link LA1 and representing the node NA2 is stored as the first adjacent node record offset, and the second adjacent node record offset As the offset of the adjacent node record NNRA20 associated with the link LA1 and representing the node NA0.

Further, in the adjacency record corresponding to the link LA2, the offset of the adjoining node record NNRA02 corresponding to the link LA2 and representing the node NA3 is stored as the first adjoining node record offset, and as the second adjoining node record offset The offset of the adjacent node record NNRA30 associated with the link LA2 and representing the node NA0 is stored.

FIG. 20 is a diagram showing an adjacency table corresponding to the mesh MB of FIG. In the adjacency relationship table of the mesh MB, adjacency relationship records (first and second adjacent node record offsets) corresponding to the links LB0, LB1, LB2, and LB3 belonging to the mesh MB are stored.

For example, the link LB2 is interposed between the adjacent node NB0 and the node NC0, but when the target mesh is the node MA, the mesh MC to which the node NC0 belongs is not an adjacent mesh. When the processor 4 does not acquire a node record other than the target mesh and the adjacent mesh, since the node record of the node NC0 is not acquired, the adjacent node record corresponding to the link LB2 as the connection link of the node NC0 is not created. . In that case, since the second adjacent node record offset of the adjacency record corresponding to the link LB2 cannot be specified, the second adjacent node record offset is set to a value indicating “invalid” as shown in FIG. Is done.

<Operation of map information processing device>
(A) Road Network Auxiliary Data Generation Processing FIG. 21 is a flowchart showing road network auxiliary data generation processing in the processor 4 of the map information processing apparatus according to this embodiment. In route search processing and map matching processing, FIG. The operation of generating road network auxiliary data for the target mesh including the current location and the adjacent mesh adjacent to the target mesh is shown.

FIG. 22 is a diagram showing an example of the contents of the memory of the processor 4 used for the road network auxiliary data generation process. The memory of the processor 4 stores the storage position, the number of records, and the like in order to manage the data, list, and table shown in FIG.

In the following, as a specific example of the road network auxiliary data created by the map information processing apparatus, in the road network shown in FIG. 7, the road network when the mesh MA is the target mesh (adjacent mesh code = 0) where the current location exists. Indicates ancillary data. In this specific example, the processing for the adjacent mesh will be described only for the mesh MB adjacent to the right side of the mesh MA (adjacent mesh code = 3). Processing for adjacent meshes other than mesh MB (adjacent mesh codes = 1, 2, 4 to 8) is the same as the processing for mesh MB, and thus description thereof is omitted.

When the generation process of the road network auxiliary data is started, the processor 4 reads the road network data from the target mesh where the current location is located and its neighboring mesh (step ST100) and the corresponding road network auxiliary data. An initialization process (step ST110) is executed. These processes are executed in the order of the numbers of adjacent mesh codes. That is, the order of meshes for performing each process is the order of the target mesh first, and then the upper, upper right, right, lower right, lower, lower left, left, and upper left adjacent meshes of the target mesh.

In step ST100, the processor 4 reads the target mesh and the road network data (FIG. 3) of the adjacent mesh from the map information storage unit 3 in the order of the numbers of the adjacent mesh codes, and in that order, the processor as shown in FIG. 4 memory.

For example, for the target mesh MA shown in FIG. 7, the node list of FIG. 8, the link list of FIG. 9, and the shape list (not shown) are read from the map information storage unit 3, and the processor 4 of FIG. Store in memory. Also for the adjacent mesh MB, the node list of FIG. 10, the link list of FIG. 11, and the shape list (not shown) are read and stored in the memory of the processor 4 as shown in FIG.

When there is no corresponding mesh or when the road network data cannot be acquired due to a reading error or the like, the road network data including only the road network header with the number of nodes and the number of links being 0 is stored in the memory.

In step ST110, a node offset table (FIG. 12), a link offset table (FIG. 13), an adjacent list (FIG. 14), an adjacent offset table (FIG. 15), and an adjacency table corresponding to the road network data read in step ST100. (FIG. 18) is created in the memory of the processor 4 as shown in FIG. 22, and they are initialized as follows based on the road network data.

∙ Set the offset of each node record in the node offset table. For the link offset table, the offset of each link record is set. For the adjacent offset table, an offset of each adjacent node table is set.

For the adjacent list, all adjacent node records (adjacent node mesh information and adjacent node number) of each adjacent node table are set as follows. That is, the adjacent node mesh information is set to a value indicating “invalid” (eg, 0xF), and the adjacent node number is also set to a value indicating “invalid” (eg, 0xFFFF).

For the adjacency table, all adjacency records (first and second adjacent node record offsets) are set as follows. That is, both the first and second adjacent node record offsets are set to a value representing “invalid” (for example, 0xFFFFFFFF).

When there is no mesh to be read, or when road network data (FIG. 3) cannot be acquired due to a read error or the like (when the number of nodes and the number of links in the road network header is 0), each of the above lists And do not create tables.

When the processes of steps ST100 and ST110 are completed for all of the target mesh and the adjacent mesh (YES in step ST120), the process proceeds to step ST130.

In step ST130, the processor 4 performs the following processing for each of the target mesh and the adjacent mesh. The process of step ST130 is also executed in the order of adjacent mesh code numbers. Here, the mesh to be processed is referred to as “the mesh”.

In Step ST130, based on the node list of the mesh, the processor 4 sets the offset of the adjacent node records of the two nodes that are adjacent to each other in the mesh adjacent relationship table via the links belonging to the mesh. Store as first and second adjacent node record offsets. That is, a set of adjacent node records associated with the same link belonging to the mesh from the adjacent list is stored with their respective offsets as first and second adjacent node record offsets. At the same time, the original node of the connection link is registered in each of the adjacent node records registered in the first and second adjacent node record offsets. If the corresponding mesh does not exist or the road network data (FIG. 3) of the corresponding mesh cannot be read, the processing target is shifted to the next mesh without performing the above processing.

FIG. 23 is a diagram for explaining the operation of the map information processing apparatus related to the generation processing of the road network auxiliary data, and shows a specific example of the registration contents of the adjacent node table of the adjacent list in step ST130 and step ST150. . For example, in the case of the road network data shown in FIG. 7, the adjacency relationship table stores the first and second adjacent node record offsets corresponding to each link as shown in FIG. 19 and FIG. As shown in the column “Registered Node (ST130)” in FIG. 23, the original node of each link is registered in the adjacent node record.

The process of step ST130 will be described in detail later.

When the process of step ST130 is completed for all of the target mesh and the adjacent mesh (YES in step ST140), the process proceeds to step ST150.

In step ST150, the processor 4 performs a process of replacing the nodes (original nodes) registered in the two adjacent node records indicated by the adjacent relationship records (first and second adjacent node record offsets) for each mesh. . The process of step ST150 is also executed in the order of adjacent mesh code numbers. Here again, the mesh to be processed is referred to as “the mesh”.

In step ST130, two nodes that are adjacent to each other are registered in the two adjacent node records indicated by the adjacent relationship records (first and second adjacent node record offsets). Since these two nodes are both the original nodes of the links corresponding to the adjacency records, if they are registered after being exchanged, the adjacent nodes of the original nodes are registered in the respective adjacent node records.

If the corresponding mesh does not exist or the road network data (FIG. 3) of the corresponding mesh cannot be read, the processing target is transferred to the next mesh.

For example, in the case of the road network data shown in FIG. 7, the node shown in the “Registered Node (ST150)” column of FIG. 23 is registered in the adjacent node record of the adjacent node table by the process of step ST150. As can be seen from FIG. 23, the node registered at this time is adjacent to the node (original node) registered in step ST130. That is, it can be seen that the registered content of the adjacent node record is the adjacent node of each node by the process of step ST150.

The process of step ST150 will be described in detail later.

When the process of step ST150 is completed for all of the target mesh and the adjacent mesh (YES in step ST160), the road network auxiliary data generation process is terminated.

As a result, as shown in FIG. 22, each road network data of the target mesh where the current location is located and the adjacent mesh thereof, and the road network auxiliary data of the target mesh and the adjacent mesh obtained based on the road network data are obtained. , And stored in a predetermined position in the memory of the processor 4.

As described above, the processor 4 also functions as an adjacent node calculation means for obtaining an adjacent node record (adjacent node information) indicating an adjacent node of a specific node (target node) based on the connection link information of the road network data.

In this embodiment, since the link is divided so as not to straddle two or more meshes, it is sufficient to obtain only the road network data of the target mesh and its neighboring meshes from the map information storage unit 3. That is, since it is not necessary to acquire road network data of meshes separated by 2 meshes or more, the amount of data to be handled is small and processing efficiency is improved.

(B) Details of Step ST130 The process of step ST130 of FIG. 21 will be described in more detail. FIG. 24 is a flowchart showing details of the process in step ST130. In step 130, the processor 4 performs the following processing.

First, in step ST200, node records in the node list of the mesh are selected in the order of node numbers. That is, nodes located in the mesh are selected in the order of node numbers. Hereinafter, the node selected in step ST200 is referred to as “the node”.

For example, when the mesh is the mesh MA of FIG. 7, each time step ST200 is executed, the node records of node numbers 0, 1, 2, and 3 shown in FIG. Similarly, when the mesh is MB, node records of node numbers 0, 1, and 2 shown in FIG. 10 are selected in order.

In the next step ST210, the connection link information of the node is selected in the order stored in the connection link table. Hereinafter, the connection link information selected in step ST210 is referred to as “the connection link information”, and the link corresponding to the connection link information is referred to as the “connection link”.

For example, when the mesh is MA, connection link information A00, A01, A02, A03, A10, A20, and A30 of FIG. 8 is selected in order each time step ST210 is executed. Similarly, when the mesh is MB, connection link information B00, B01, B02, B03, B10, and B20 shown in FIG. 10 are selected in order.

In the next step ST220, it is determined whether there is a mesh to which the connection link belongs. That is, in the road network data, when the number of nodes corresponding to the mesh indicated by the connection link mesh information of the connection link information is 0, or the mesh indicated by the connection link mesh information of the connection link information is outside the adjacent mesh. If it is a mesh (for example, mesh MC in FIG. 7), it is determined that there is no mesh to which the connection link belongs.

Also, when the road network data of the adjacent mesh cannot be read, it is determined that there is no mesh to which the connection link belongs. For example, when the node is the node NA0, the connection link LB0 belongs to the adjacent mesh MB, but when the road network data of the mesh MB cannot be read, it is determined that there is no mesh to which the connection link LB0 belongs.

If it is determined that there is no mesh to which the connection link belongs (YES in step ST220), the process proceeds to step ST260 described later. Otherwise, after performing the following steps ST230 to ST250, the process proceeds to step ST260.

In Step ST230, a mesh adjacency table indicated by the connection link mesh information of the connection link information is selected, and an adjacency record specified by the connection link number of the connection link information is selected from the adjacency table.

For example, if the mesh is MA and the node is NA0, and the connection link is LA0, the adjacency corresponding to the link LA0 indicated by the connection link information A00 from the adjacency table (FIG. 19) of the mesh MA A record is selected. When the connection link is LA1, the adjacency record corresponding to the link LA1 indicated by the connection link information A01 is selected. When the connection link is LA2, the adjacency record corresponding to the link LA2 indicated by the connection link information A02 is selected. If the connection link is LB0, an adjacency record corresponding to the link LB0 indicated by the connection link information A03 is selected from the adjacency relationship table of mesh MB (FIG. 20). The same applies to other cases.

Subsequently, the process proceeds to step ST240, and the offset of the adjacent node record corresponding to the connection link is stored in the adjacent relation record selected in step ST230. At this time, if the first adjacent node record offset is “invalid”, the offset is stored as the first adjacent node record offset, and the first adjacent node record offset is not “invalid”. In the case (when another offset is already stored as the first adjacent node offset), the offset is stored as the second adjacent node record offset.

19 and 20 show storage results of the adjacency records (first and second adjacent node record offsets) after step ST240 is executed for all nodes of mesh MA and MB and their connection links. is there.

As described above, the mesh to be processed in step ST130 changes in the order of the adjacent mesh code, and the node selected in step ST200 changes in the order of the node number. Therefore, if the mesh is MA and the node is NA0, when the connection link is LA0, LA1, LA2, the first and second adjacent node record offsets of the corresponding adjacency records are both “Invalid”. Therefore, in the adjacency record corresponding to the connection links LA0, LA1, and LA2 in the adjacency table of the mesh MA, as shown in FIG. 19, as the first adjacent node record offset, the connection links LA0, LA1, and LA2 Stores the offsets of the corresponding adjacent node records NNRA00, NNDA01, and NNRA02.

Also, when the connection link is LB0, the first and second adjacent node record offsets of the corresponding adjacent relationship record are both “invalid”. Accordingly, as shown in FIG. 20, the offset of the adjacent node record NNRA03 corresponding to the connection link LB0 is set as the first adjacent node record offset of the adjacent relationship record of the mesh MB corresponding to the connection link as the first adjacent node record offset. Stored.

On the other hand, when the connection link LA0 of the node NA1, the connection link LA1 of the node NA1, and the connection link LA2 of the node NA2 are the connection links, the first adjacent node record offset is “invalid” by the above processing. Is no longer (other offsets are already stored). Accordingly, as shown in FIG. 19, the offsets of the adjacent relationship records NNRA10, NNDA20, and NNRA30 corresponding to them are stored as the second adjacent node record offset.

The same applies when the mesh becomes a mesh MB, and the contents of each adjacency record (first and second adjacent node record offsets) are as shown in FIG. When the node is mesh NB0 and the connection link is LB0, the adjacent node record NNRA03 is stored in the first adjacent node record offset as described above. Therefore, when the connection link is LB0 in the mesh NB0, the offset of the adjacent relationship record NNRB00 corresponding to the link is stored as the second adjacent node record offset.

Note that in the adjacency record corresponding to the link LB2, since the node NC0 belongs to the mesh MC and the processing of step ST130 is not executed for the mesh MC, the second adjacent node record offset is “invalid” as shown in FIG. Will remain.

Thus, in step ST240, the offset of the adjacent node record corresponding to the two nodes in the adjacent relationship is stored in each of the adjacent relationship records via the link corresponding to the adjacent relationship record.

For example, the node NA0 and the node NA1 are adjacent to each other via the link LA0. However, as shown in FIG. 19, in the adjacent relationship record associated with the link LA0, the node NA1 is matched with the adjacent relationship. And the offset of the adjacent node record NNRA10 representing the node NA0 are stored.

In subsequent step ST250, a process of registering the node in the adjacent node record corresponding to the connection link is performed. That is, in the adjacent node record corresponding to the connection link, the adjacent mesh code of the mesh viewed from the target mesh is stored as adjacent node mesh information, and the node number of the node is stored as the adjacent node number.

At this time, not the adjacent node of the connection link but the node that is the original node of the connection link is registered in the adjacent node record. Since the offset of each adjacent node record is stored in the adjacent relationship record corresponding to the connection link in step ST240, if the adjacent relationship record corresponding to the connection link is referred to, the original node of the connection link is registered. The adjacent node record is known.

The column of “registered node (ST130)” in FIG. 23 shows all nodes of the mesh MA and MB and nodes registered in the adjacent node record when step ST250 is executed for the connection link. ing.

For example, if the mesh is MA and the node is NA0, the connection link is LA0, LA1, LA2, LB0, and the node NA0 that is the original node is registered in the adjacent node record corresponding to each connection link. Is done. The same applies when the mesh is MA and the node is other.

Also, when the mesh is MB and the node is NB0, the connection link is LB0, LB1, LB2, LB3, and the node NB0 that is the original node is registered in the adjacent node record corresponding to each connection link. Is done. The same applies to the case where the mesh is an MB and the node or the like is otherwise.

Thus, in step ST250, the original node of the connection link is registered in the adjacent node record corresponding to the connection link.

For example, as shown in FIG. 19, in the adjacent node record NNRA00 representing the adjacent node NA1 of the node NA0 via the connection link LA0, the original node NA0 is registered. Conversely, the node NA1 which is the original node is registered in the adjacent node record NNRA10 representing the adjacent node NA0 of the node NA1 via the link LA0. Also, by the above-described step ST240, the adjacent relationship table stores offsets of adjacent node records corresponding to the nodes NA0 and NA1 as adjacent relationship records corresponding to the link LA0.

If it is determined in step ST220 that there is no mesh to which the connection link belongs, steps ST230 to ST250 are not executed. In this case, the adjacency record corresponding to the connection link LB0 remains “invalid”.

Subsequently, in step ST260, it is determined whether or not the above processing has been completed for all connection link information of the node. If all are completed, the process proceeds to step ST270, and if not completed, the process returns to step ST210.

Further, in step ST270, it is determined whether or not the above processing has been completed for all node records in all node lists of the mesh. If all are not completed, the process returns to step ST200. If all are completed, the process of step ST130 is terminated, and the process proceeds to step 140 of FIG.

In step 130, by performing such processing, the offsets of the adjacent node records of the nodes adjacent to each other are stored in the adjacent relationship table, and the original node of each connection node is registered in the adjacent node table. .

(C) Details of Step ST150 The process of step ST150 of FIG. 21 will be described in more detail. FIG. 25 is a flowchart showing the detailed operation of step ST150.

First, in step ST300, the processor 4 selects a predetermined adjacency record from the adjacency table of the mesh. The selected adjacency record changes each time step ST300 is executed, and is selected in order from the top of the adjacency table of the mesh.

Subsequently, in Step ST310, it is checked whether or not the first adjacent node record offset of the adjacent relationship record selected in Step ST300 is “invalid”. If it is “invalid”, the process proceeds to step ST340, and if it is not “invalid”, the process proceeds to step ST320.

In step ST320, it is checked whether or not the second adjacent node record offset of the adjacent relationship record selected in step ST300 is “invalid”. If it is “invalid”, the process proceeds to step ST325, and if it is not “invalid”, the process proceeds to step ST330.

In step ST325, the value indicating “invalid” is stored in the adjacent node mesh information and the adjacent node number included in the adjacent node record indicated by the first adjacent node record offset. For example, in the adjacency record corresponding to the link LB2 in FIG. 20, the second adjacent node record offset is “invalid”. In this case, as shown in FIG. 23, the adjacent node record offset NNRB02 indicated by the first adjacent node record offset is set to “invalid”. After the process of step ST325, the process proceeds to step ST340.

In step ST330, the node registered in the adjacent node record indicated by the first adjacent node record offset and the adjacent node record indicated by the second adjacent node record offset in the adjacency record selected in step ST300 are registered. Replace with a node.

In the adjacent node record indicated by the first and second adjacent node record offsets of the adjacent relationship record, the original node of the link corresponding to the adjacent relationship record is registered. As described above, since the nodes at both ends of each link can be both original nodes and adjacent nodes, when the nodes at both ends of the link are replaced, the two nodes that appear as the original nodes are respectively It can be determined that there is an adjacent relationship through the link. Therefore, when the original node registered in the adjacent node record corresponding to the same link is replaced, the registered content of each adjacent node record becomes the adjacent node.

For example, when the mesh is MA and the adjacency record selected in step ST300 is an adjacency record corresponding to the link LA0, the first adjacent node record offset is the adjacent node record NNRA00 as shown in FIG. The second adjacent node record offset indicates the adjacent node record NNRA10. Before the process of step ST330, as shown in the column of “Registered Node (ST130)” in FIG. 23, the node NA0 is registered in the adjacent node record NNRA00, and the node NA1 is registered in the adjacent node record NNRA10. In step ST330, the node NA1 is registered in the adjacent node record NNRA00, and the node NA0 is registered in the adjacent node record NNRA10.

As a result, as shown in the column of “Registered Node (ST150)” in FIG. 23, the adjacent node record NNRA00 shows the adjacent node NA1 via the link LA0 of the node NA0, and the adjacent node record NNRA10 An adjacent node NA0 via the link LA0 of NA1 is indicated. After the process of step ST330, the process proceeds to step ST340.

In step ST340, it is determined whether or not the above processing has been completed for all adjacent relationship records of the mesh. If all the processes are completed, the process of step ST150 is terminated and the process proceeds to step ST160 in FIG. 21. If all the processes are not completed, the process returns to step ST300.

In this way, as shown in the column “Registered Node (ST150)” in FIG. 23, the adjacent node of the node is registered in the adjacent node table associated with each node. That is, the adjacent list of the mesh is associated with each node located in the mesh, and all the adjacent nodes are registered. As a result, all adjacent nodes for all nodes included in the road network data (the target mesh and the road network data of all adjacent meshes) acquired by the processor 4 are stored in the memory (adjacent node information storage means) of the processor 4. An adjacent list in which adjacent node records are stored is created. Therefore, the processor 4 can directly determine the adjacent node of each node by referring to the adjacent list.

In the above processing, since the link LB0 extends over the two meshes MA and MB, the adjacent node NA0 via the connection link LB0 of the node NB0 is obtained from only one node list of the mesh MA and mesh MB. I can't. Therefore, in steps ST240 and ST250 (FIG. 24) in step 130, the first adjacent read record offset and the original node NA0 are obtained using the node list of the mesh MA, and the second list is obtained using the node list of the mesh MB. The adjacent read record offset and the original node NB0 are obtained. That is, the adjacent node via the link LB0 straddling the meshes MA and MB is obtained using both node lists of the meshes MA and MB.

(D) Neighboring Node Calculation Processing In route search and map matching processing performed by the map information processing apparatus, processing for tracing the road network is performed. In the process of tracing the road network, the current node is defined as the target node, and an adjacent node (next node) that is adjacent to the target node is obtained. This is done by following the nodes of the road network one after another while repeating the process of defining a node as a new target node and obtaining an adjacent node adjacent to the target node.

FIG. 26 is a flowchart showing an operation in which the map information processing apparatus according to the present embodiment calculates adjacent nodes. In the operation shown in FIG. 26, a node that is currently reached is defined as a target node, its adjacent node is calculated, and a process of registering in the “next node list” provided in the memory of the processor 4 (FIG. 22) is performed. It is.

The next node list has the same data structure as the adjacent list shown in FIG. That is, the next node list has an adjacent node record associated with the connection link of the target node, and the adjacent node record specifies an adjacent node adjacent to the target node via the connection link. Mesh information and adjacent node numbers are stored. The adjacent node mesh information represents the mesh to which the adjacent node belongs by an adjacent mesh code, and the adjacent node number is the node number of the adjacent node. There are as many next node records as there are adjacent nodes of the target node.

When the process of tracing the road network reaches an arbitrary node, the node is defined as the target node, and the calculation process of the adjacent node is started.

First, in step ST400, the next node list is initialized. That is, the number of adjacent nodes registered in the next node list is set to zero.

Then, the following processing of step ST410 to step ST450 is performed in turn referring to the connection link information included in the node record of the target node. For example, when the target node is the node NA located in the mesh MA of FIG. 7, the node record of the target node is the node record of node number 0 in the node list shown in FIG. In this case, the processing of step ST410 to step ST450 is performed in this order on the connection link information A00, A01, A02, A03.

In step ST410, the adjacent node table of the target node is selected. That is, the offset of the adjacent node table of the target node in the adjacent list of the mesh to which the target node belongs (target mesh) is obtained with reference to the adjacent offset table of the target mesh.

In step ST420, an adjacent node record corresponding to the connection link of the target node is selected from the adjacent node table selected in step ST410. For example, when the target node is the node NA in FIG. 7 (corresponding to the node record with node number 0 in FIG. 8), the adjacent node record NNRA00 (LA0) in FIG. 16 corresponds to the connection link information A00 (connection link LA0). 16 is selected for the connection link information A01 (connection link LA1), and the adjacent node record NNRA02 (LA2) of FIG. 16 is selected for the connection link information A02 (connection link LA2). ) Is selected, and the adjacent node record NNRA03 (LB0) in FIG. 16 is selected for the connection link information A03 (connection link LB0).

In step ST430, the adjacent node record selected in step ST420 is stored in the next node list as the next node record representing the adjacent node. When the adjacent node number of the adjacent node record is “invalid” (0xFFFF), it is not stored in the next node list. This prevents a node that cannot follow further from being registered as the next node.

In step ST440, it is checked whether or not the processing in steps ST410 to ST430 has been completed for all the connection link information of the target node. That is, it is confirmed whether or not the processing of step ST410 to step ST430 has been completed for connection link information for the number of connection links described in the node record of the target node. If it has been completed, the calculation process of the adjacent node is completed, and if it has not been completed, the process returns to step ST410.

For example, in the process of tracing the road network, if the target node becomes the node NA in FIG. 7 (corresponding to the node record with node number 0 in FIG. 8), the next node list is adjacent to the MA of the target mesh by the above process. Neighboring node records NNRA00 (LA0), NNRA01 (LA1), NNRA02 (LA2) representing neighboring nodes in the target mesh MA selected from the list (FIG. 16) are stored, and neighboring nodes representing neighboring nodes in the neighboring mesh MB A record NNRA03 (LB0) is stored. Therefore, the processor 4 can immediately obtain the adjacent nodes NA1, NA2, NA3 in the target mesh MA and the adjacent node NB0 in the adjacent mesh MB by referring to the next node list.

As described above, the adjacent node records of all the adjacent nodes are stored as the road network auxiliary data with respect to all the nodes included in the road network data (the road network data of the target mesh and all the adjacent meshes) acquired by the processor 4. By using the adjacent list, the processor 4 can immediately obtain the adjacent node of the target node regardless of whether the connection link crosses the mesh or not, and can quickly follow the road network.

<Modification>
In addition, although the input part 1 (refer FIG. 1) of the map information processing apparatus concerning this Embodiment was demonstrated as what is an operation switch group, it is mounted | worn with the display surface of the display part 5 besides the operation switch group. A touch panel (not shown), a remote control switch (not shown), a voice recognition device (not shown), or the like may be used as input means.

In this embodiment, the link record corresponding to each link is stored only in the link list of the mesh to which the start node belongs, but may be stored only in the link list of the mesh to which the end node belongs. .

In this embodiment, the connection link mesh information indicating the mesh to which the connection link belongs is indicated by the adjacent mesh code. However, instead of the adjacent mesh code, the mesh number unique to each mesh may be indicated.

In the present embodiment, the adjacent node record including the adjacent node mesh information and the adjacent node number is provided as an adjacent list different from the node list, but may be provided in the link record of the link list.

Further, in the present embodiment, when the link exists across three or more meshes, the link is divided in advance so as to straddle two meshes, but the link may not be divided. At this time, since the adjacent mesh code cannot be used as the connection link mesh information of the mesh to which the link belongs, the mesh number may be indicated as the connection link mesh information instead of the adjacent mesh code.

In the present invention, the embodiments can be appropriately modified or omitted within the scope of the invention.

1 input unit, 2 position detection unit, 3 map information storage unit, 4 processor, 5 display unit, 6 audio output unit.

Claims (13)

1. Storage means for storing map information divided into meshes, defining a road network with nodes provided in the mesh and links connecting the nodes, and information on links connected to the nodes Map information storage means for storing road network data including connection link information including information on the mesh to which a link belongs, and storing the information for each mesh included in the map information;
   Road network data acquisition means for acquiring the desired road network data from the map information storage means;
   Based on the connection link information of the acquired road network data, an adjacent node calculation means for obtaining adjacent node information indicating an adjacent node that is a node connected from a specific node via one link;
   Adjacent node information storage means for storing adjacent node information obtained by the adjacent node calculation means;
   Obtaining adjacent node information of all adjacent nodes for all nodes included in the acquired road network data, storing the adjacent node information in the adjacent node information storage unit, and using the road network data and the adjacent node information Map information processing means for processing map information;
   A map information processing apparatus comprising:
2. The adjacent node calculation means obtains the adjacent node information from the connection link information of the road network data of the mesh when nodes at both ends of the link are included in one mesh, and when the link spans a plurality of meshes, The map information processing apparatus according to claim 1, wherein the adjacent node information is obtained from connection link information of road network data of two meshes including nodes at both ends of the link.
3. The map information processing apparatus according to claim 1, wherein the adjacent node information stored in the adjacent node information storage unit includes information indicating an adjacent node for which the adjacent node information could not be obtained.
4. The map information processing apparatus according to claim 1, wherein the road network data does not include a link straddling three or more meshes.
5. The map information processing means, when performing a process of tracing a road network as a process for the map information, obtains a connection relation between nodes and links that define the road network from the connection link information and the adjacent node information. 1. The map information processing apparatus according to 1.
6. The map information processing means, when performing a process of tracing a road network as a process for the map information, does not perform a process of tracing the road network any more for an adjacent node for which adjacent node information could not be obtained. The map information processing apparatus described.
7. The map information processing apparatus according to claim 1, wherein in the connection link information, a mesh to which a link connected to each node belongs is specified using a code representing a relative position with respect to the mesh to which the node belongs.
8. The map information processing apparatus according to claim 7, wherein the code represents a reference mesh and each of upper, upper, right, lower right, lower, lower left, left, and upper left meshes.
9. The map information processing apparatus according to claim 1, wherein in the adjacent node information, a mesh to which each adjacent node belongs is specified using a code representing a relative position with reference to the mesh to which the specific node belongs.
10. The map information processing apparatus according to claim 9, wherein the code indicates a reference mesh and each of upper, upper, right, lower right, lower, lower left, left, and upper left meshes.
11. The road network data acquisition means acquires the road network data of a target mesh that is a mesh to be processed with respect to the map information, and the road network data of an adjacent mesh that is a mesh adjacent to the target mesh. Item 2. The map information processing apparatus according to item 1.
12. The map information processing apparatus according to claim 11, wherein the adjacent mesh includes meshes above, upper right, right, lower right, lower, lower left, left, and upper left of the target mesh.
13. The map information processing apparatus according to claim 11, wherein in the process for the map information, the adjacent mesh is specified using a code representing a relative position with respect to the target mesh.

Images