"地図情報をメッシュに分割して記憶する記憶手段であって、前記メッシュに設けられたノードと前記ノード間を接続するリンクとで道路網を規定し、前記ノードに接続されるリンクの情報と当該リンクが属する前記メッシュの情報とを含む接続リンク情報を有する道路網データを、前記地図情報に含めて前記メッシュごとに記憶する地図情報記憶手段と、前記地図情報記憶手段から所望の前記道路網データを取得する道路網データ取得手段と、前記道路網データ取得手段にて取得された前記道路網データの前記接続リンク情報に基づき、前記リンクが前記メッシュを跨がない場合は、当該メッシュの前記道路網データの前記接続リンク情報から、前記リンクが前記メッシュを跨ぐ場合は、当該リンクの両端の前記ノードが含まれる2つの前記メッシュの前記道路網データの前記接続リンク情報から、前記リンクの端部に接続される前記ノードの情報であるリンク端ノード情報を算出するリンク端ノード情報算出手段と、を備える、地図情報処理装置。前記リンク端ノード情報算出手段にて算出された前記リンク端ノード情報を格納するリンク端ノード情報格納手段をさらに備え、前記リンク端ノード情報は、前記接続リンク情報に含まれる前記リンクが属する前記メッシュの情報に基づき、前記リンクに対応付けて前記メッシュごとに前記リンク端ノード情報格納手段に格納されることを特徴とする、請求項1に記載の地図情報処理装置。前記リンク端ノード情報格納手段は、前記リンク端ノード情報算出手段によって算出された前記リンク端ノード情報と、前記リンク端ノード情報算出手段によって算出されなかった前記リンク端ノード情報とを区別可能に格納することを特徴とする、請求項2に記載の地図情報処理装置。前記リンク端ノード情報算出手段は、前記リンクが属する前記メッシュの前記道路網データを前記道路網データ取得手段が取得しない場合は、前記リンク端ノード情報を算出しないことを特徴とする、請求項1に記載の地図情報処理装置。前記道路網データは、前記メッシュを3つ以上跨るリンクを含まないことを特徴とする、請求項1に記載の地図情報処理装置。前記道路網データ取得手段は、処理の対象となるメッシュである対象メッシュの前記道路網データと、前記対象メッシュに隣接するメッシュである隣接メッシュの前記道路網データとを取得することを特徴とする、請求項5に記載の地図情報処理装置。前記隣接メッシュは、前記対象メッシュを基準として、上、右上、右、右下、下、左下、左、左上の各メッシュを含むことを特徴とする、請求項6に記載の地図情報処理装置。前記道路データ取得手段が取得した前記道路網データに含まれるリンクが属する前記メッシュは、前記対象メッシュまたは前記隣接メッシュであることを特徴とする、請求項7に記載の地図情報処理装置。前記道路データ取得手段が取得した前記道路網データに含まれるノードが属する前記メッシュは、前記対象メッシュまたは前記隣接メッシュであることを特徴とする、請求項7に記載の地図情報処理装置。前記リンク端ノード情報に含まれる前記ノードにノード番号を付し、当該ノード番号と前記ノードのオフセットとを対応付けるノードオフセットテーブルをさらに備えることを特徴とする、請求項1に記載の地図情報処理装置。前記接続リンク情報に含まれる前記リンクにリンク番号を付し、当該リンク番号と前記リンクのオフセットとを対応付けるリンクオフセットテーブルをさらに備えることを特徴とする、請求項1に記載の地図情報処理装置。前記接続リンク情報と前記リンク端ノード情報とに基づき、前記道路網の接続関係を算出する道路網接続関係算出手段をさらに備えることを特徴とする、請求項1に記載の地図情報処理装置。前記接続リンク情報と前記リンク端ノード情報とに基づき、前記道路網の接続関係を算出する道路網接続関係算出手段をさらに備え、前記道路網接続関係算出手段は、前記リンク端ノード情報算出手段によって前記リンク端ノード情報が算出されなかった場合は、当該算出されなかった前記リンク端ノード情報に含まれる前記ノードに対する前記道路網の接続関係を算出しないことを特徴とする、請求項3に記載の地図情報処理装置。特許文献1において、ノードからリンクへの接続関係を示す情報を一方側接続情報とし、リンクが処理の対象となる対象メッシュと、当該対象メッシュに隣接する隣接メッシュとを跨いで存在する場合、リンクのいずれか一端に接続されるノードは隣接メッシュ内に存在するため、当該ノードの一方側接続情報も隣接メッシュ内に存在することになる。しかし、特許文献1では、上記の対象メッシュ内で一方側接続情報に基づく他方側接続情報を生成しているすなわち、単一のメッシュ内でのみ接続情報を生成しているため、上記のようにリンクが対象メッシュと隣接メッシュとを跨いで存在している場合は、リンクから対象メッシュのノードへの他方側接続情報を生成することができないという問題があった。本発明は、これらの問題を解決するためになされたものであり、リンクがメッシュを跨って存在する場合であってもリンクとノードとの接続情報を生成することが可能な地図情報処理装置を提供することを目的とする。上記の課題を解決するために、本発明による地図情報処理装置は、地図情報をメッシュに分割して記憶する記憶手段であって、メッシュに設けられたノードとノード間を接続するリンクとで道路網を規定し、ノードに接続されるリンクの情報と当該リンクが属するメッシュの情報とを含む接続リンク情報を有する道路網データを、地図情報に含めてメッシュごとに記憶する地図情報記憶手段と、地図情報記憶手段から所望の道路網データを取得する道路網データ取得手段と、道路網データ取得手段にて取得された道路網データの接続リンク情報に基づき、リンクがメッシュを跨がない場合は、当該メッシュの道路網データの接続リンク情報から、リンクがメッシュを跨ぐ場合は、当該リンクの両端のノードが含まれる2つのメッシュの道路網データの接続リンク情報から、リンクの端部に接続されるノードの情報であるリンク端ノード情報を算出するリンク端ノード情報算出手段とを備える。本発明によると、地図情報をメッシュに分割して記憶する記憶手段であって、メッシュに設けられたノードとノード間を接続するリンクとで道路網を規定し、ノードに接続されるリンクの情報と当該リンクが属するメッシュの情報とを含む接続リンク情報を有する道路網データを、地図情報に含めてメッシュごとに記憶する地図情報記憶手段と、地図情報記憶手段から所望の道路網データを取得する道路網データ取得手段と、道路網データ取得手段にて取得された道路網データの接続リンク情報に基づき、リンクがメッシュを跨がない場合は、当該メッシュの道路網データの接続リンク情報から、リンクがメッシュを跨ぐ場合は、当該リンクの両端のノードが含まれる2つのメッシュの道路網データの接続リンク情報から、リンクの端部に接続されるノードの情報であるリンク端ノード情報を算出するリンク端ノード情報算出手段とを備えるため、リンクがメッシュを跨って存在する場合であってもリンクとノードとの接続情報を生成することが可能となる。本発明の実施の形態について、図面に基づいて以下に説明する。実施の形態まず、本発明の実施の形態による地図情報処理装置の構成について説明する。図1は、本発明の実施の形態による地図情報処理装置の構成の一例を示すブロック図である。図1に示すように、本実施の形態による地図情報処理装置は、入力部1と、位置検出部2と、地図情報記憶部3と、プロセッサ4と、表示部5と、音声出力部6とを備えている。入力部1は、使用者の操作または指示に基づく指示信号をプロセッサ4に伝達する操作スイッチ群であり、入力手段として機能する。位置検出部2は、例えば、GPSGlobalPositioningSystem受信機、車速センサ、加速度センサ、角速度センサ等を用いて位置検出を行う位置検出手段として機能する。位置検出部2は、本実施の形態による地図情報処理装置を保持する移動体の現在位置を検出し、検出した現在位置を示す位置情報をプロセッサ4に伝達する。地図情報記憶部3地図情報記憶手段は、例えば、地図情報を記録する媒体としてハードディスクドライブにより構成される地図情報記憶手段として機能する。地図情報記憶部3には、後述の地図情報が予め記憶されている。プロセッサ4は、入力部1から取得した指示信号、位置検出部2から取得した位置情報、および地図情報記憶部3から読み出した地図情報に基づき、各種の地図情報処理を行う地図情報処理手段として機能する。また、プロセッサ4は、描画メモリ図示せず、描画処理部図示せず、表示制御部図示せずを有しており、所定の図形は描画処理部によって描画メモリに描画され、描画メモリに描画された内容例えば、所定の図形は表示制御部によって表示部5に表示される。プロセッサ4にて行われる各種の地図情報処理としては、位置検出部2から取得した位置情報と地図情報記憶部3から読み出した地図情報とに基づいて移動体の現在位置を推定するマップマッチング処理や、出発地から目的地までの経路を算出する経路探索処理や、経路探索処理によって得られた経路に従って出発地から目的地まで案内を行う経路誘導処理や、現在位置周辺の地図表示処理や、都市、道路、施設、住所、電話番号、交差点等の各種情報を検索する各種検索処理等が含まれる。また、地図情報記憶部3から読み出した地図情報に基づき、マップマッチング処理により推定された現在位置を中心とした地図の描画や、当該描画された地図上に上記の地図情報処理によって得られた移動体の現在位置、経路探索処理によって得られた好適な経路、当該経路に従って出発地から目的地まで案内を行うための案内情報の描画や、各種入力情報の描画や、検索によって得られた各種情報の描画等、プロセッサ4の描画処理部による描画処理も上記の地図情報処理に含まれる。表示部5は、例えば、液晶ディスプレイからなる表示装置であり、表示手段として機能する。表示部5は、プロセッサ4の描画処理部による上記各種の描画処理に従って描画メモリに描画された内容を、プロセッサ4の表示制御部の制御に基づいて表示する。音声出力部6は、プロセッサ4によって行われた各種の地図情報処理の結果として得られた情報を音声で使用者に伝える音声出力手段として機能する。音声出力部6は、例えば、経路探索処理によって得られた好適な経路に従って出発地から目的地まで案内を行うための情報や、検索によって得られた各種情報等を音声で使用者に伝える。次に、地図情報記憶部3に記憶される地図情報について説明する。地図情報記憶部3に記憶される地図情報は、地図を所定の間隔の緯度および経度によって囲まれた4辺形の領域で区画されたメッシュごとに管理される。すなわち、地図情報記憶部3は、地図情報をメッシュに分割して記憶している。また、地図情報は、情報の詳細さの度合いによって階層化され、各階層で区画されたメッシュごとに管理される。また、階層を識別するために、最も詳細な情報を有する階層から順に0,1,2、と各階層に対して番号階層番号を付与する。また、各階層において、メッシュを識別するために、各メッシュに対して固有の番号メッシュ番号を付与する。例えば、ある階層のメッシュが、地図における緯度方向に16分割、かつ、経度方向に16分割して得られる256個の領域であるとすると、当該階層の各メッシュには0~255のメッシュ番号が付与される。なお、以下では、処理の対象となるメッシュを対象メッシュ、当該対象メッシュに隣接するメッシュを隣接メッシュとも称する。図2は、本実施の形態による地図情報記憶部3に記憶された地図情報のデータ構造の一例を示す図である。図2に示すように、地図情報記憶部3に記憶される地図情報は、地図管理情報、地図データ、検索情報を有している。以下、地図管理情報、地図データ、検索情報について順に説明する。まず、地図管理情報について説明する。地図管理情報は、地図情報のバージョンを示すバージョン情報や、階層ごとに各地図データを管理する階層管理情報や、各種の検索情報を管理する検索管理情報等を有している。また、階層管理情報は、各メッシュのメッシュ番号、地図情報における地図データの格納位置、データサイズ等の情報を階層ごとに有している。次に、地図データについて説明する。地図データは、地図データヘッダ、道路網データ、背景データ、名称データ、経路誘導データを有し、各階層の各メッシュに対応して設けられている。また、地図データヘッダは地図データ内の各データを管理する情報を有し、道路網データは各メッシュにおける道路網を示す情報を有し、背景データは河川、海等を示す面データや、線状の河川、鉄道等を示す線データや、施設シンボル等を示す点データを有し、名称データは地名、河川、海、鉄道、施設等の名称の情報を有し、経路誘導データは交差点等での経路案内に必要な情報を有している。次に、検索情報について説明する。検索情報は、都市、道路、施設、住所、電話番号、交差点等の各種情報を検索するための各種の検索情報を有している。図3は、地図データに含まれる道路網データの構造の一例を示す図である。道路網データは、交差点または道路上の地点を示すノードと、ノード間を接続する道路を示すリンクとで規定される道路網のデータであり、図3に示すように、道路網データヘッダ、ノードリスト、リンクリスト、形状リストを有する。以下、道路網データヘッダ、ノードリスト、リンクリスト、形状リストについて順に説明する。まず、道路網データヘッダについて説明する。道路網データヘッダは、都市計画法に基づいて計画された道路の有無を示す計画道路有無情報と、メッシュ内に存在するノードの数を示すノード数と、メッシュ内に存在するリンクの数を示すリンク数と、道路網データにおけるノードリスト、リンクリスト、および形状リストの格納位置やデータサイズを示すリスト管理情報といった、道路網データの管理に必要な情報を有する。次に、ノードリストについて説明する。ノードリストは、メッシュ内に存在する各ノードに対応して設けられたノードレコードを有する。ここで、ノードリストにおけるノードレコードの並び順に合わせたノード番号を各ノードレコードに付与するものとする。また、ノードレコードは、ノードの地理的位置を示すノード座標と、ノードに接続するリンクの数を示す接続リンク数と、ノードに接続する各リンクに対応する情報を示す接続リンク情報を接続リンク数分だけ示す接続リンクテーブルとを有する。なお、以下では、ノードに接続するリンクのことを接続リンクとも称する。さらに、接続リンク情報は、ノードに接続するリンクが属するメッシュの情報である接続リンクメッシュ情報と、ノードに接続するリンクの情報である接続方向および接続リンク番号とを有する。接続リンクメッシュ情報は、ノードに接続するリンクが属するメッシュを隣接メッシュコードで示す。すなわち、接続リンクメッシュ情報は、対象メッシュおよび隣接メッシュに対して隣接メッシュコードを対応付けることで示される。図4は、本実施の形態による隣接メッシュコードの一例を示す図である。図4に示すように、隣接メッシュは、対象メッシュを基準として上、右上、右、右下、下、左下、左、左上の各メッシュを含んでおり、対象メッシュおよび隣接メッシュは隣接メッシュコード0~8で示される。このうち、対象メッシュの隣接メッシュコードを0で示し、隣接メッシュの隣接メッシュコードを1~8で示す。本実施の形態において、地図情報記憶部3から読み出された道路網データに含まれるリンクおよびノードのそれぞれが属するメッシュは、対象メッシュまたは隣接メッシュであり、当該属するメッシュを隣接メッシュコードで示している。このように、各メッシュを、対象メッシュを基準とした隣接メッシュコードで示すことによって、各メッシュをメッシュ固有の情報で示す場合に比べて情報量を削減することができる。接続方向は、ノードに接続するリンクが当該ノードに対して順方向または逆方向のいずれの方向に接続しているのかを示す。リンクが順方向の場合はノードをリンクの始点始点ノードとし、リンクが逆方向の場合はノードをリンクの終点終点ノードとする。図5は、本実施の形態によるリンクの接続方向の一例を示す図である。図5に示すように、リンクLx接続リンクLxは、ノードNx1とノードNx2との間を接続している。ノードNx1を始点ノードとし、ノードNx2を終点ノードとすると、リンクLxは、始点ノードNx1に対して順方向であり、終点ノードNx2に対して逆方向となる。なお、始点ノードおよび終点ノードは、道路網データ作成時に任意に定められるものとする。接続リンク番号は、ノードに接続するリンクの番号であるリンク番号を示す。次に、リンクリストについて説明する。リンクリストは、メッシュ内に存在する各リンクに対応して設けられたリンクレコードを有する。ここで、リンクリストにおけるリンクレコードの並び順に合わせたリンク番号を各リンクレコードに付与するものとする。また、リンクレコードは、リンクの道路種別、幅員、リンク長等の各種属性を示すリンク属性情報と、リンクに対応する形状レコードの形状リストにおける格納位置を示す形状レコード格納位置とを有する。本実施の形態において、リンクレコードには、リンクに接続するノードを示す情報始点ノードおよび終点ノードのノード番号が格納されていない。従って、地図情報記憶部3に記憶される道路網データのデータ量を削減することができる。また、リンクが複数のメッシュを跨る場合後述するにおいて、当該リンクは始点ノードが存在するメッシュに属するものとし、リンクレコードは当該リンクが属するメッシュのリンクリストに格納されるものとする。従って、リンクが複数のメッシュを跨る場合は、リンクレコードをリンクの両端のノードが存在するメッシュの双方に格納しないためすなわち、リンクの一端のノードが存在するメッシュのリンクリストのみにリンクレコードを格納するため、地図情報記憶部3に記憶される道路網データのデータ量を削減することができる。次に、形状リストについて説明する。形状リストは、メッシュ内に存在するリンクに対応して設けられた形状レコードを有する。また、形状レコードは、リンクの道路形状の形状点の数を示す形状点数と、リンクの道路形状を折れ線近似で表し、表された折れ線の頂点である形状点の地理的位置を示す形状点リストとを有する。図6は、本実施の形態による道路網の一例を示す図である。図6において、例えば、メッシュMAを対象メッシュとした場合、メッシュMBは対象メッシュMAの右側に隣接する隣接メッシュである。また、メッシュMCは隣接メッシュMBの右側に隣接しているが、対象メッシュMAに隣接していない。すなわち、メッシュMCは対象メッシュMAの隣接メッシュではない。図7は、本実施の形態による図6のメッシュMAにおけるノードリストに格納される各ノードレコードの一例を示す図である。図7に示すように、メッシュMAのノードリストには、ノード番号0,1,2,3がそれぞれ付与されたノードNA0,NA1,NA2,NA3のノードレコードが格納されている。また、上述で説明したように、各ノードレコードとしてノード座標、接続リンク数、接続リンクテーブルが格納されており、さらに、接続リンクテーブルには接続リンク情報として、接続リンクメッシュ情報、接続方向、接続リンク番号が格納されている。図8は、本実施の形態による図6のメッシュMAにおけるリンクリストに格納される各リンクレコードの一例を示す図である。図8に示すように、メッシュMAのリンクリストには、リンク番号0,1,2がそれぞれ付与されたリンクLA0,LA1,LA2のリンクレコードが格納されている。なお、ノードNA0に接続するリンクLB0はメッシュMBに属するため、リンクLB0のリンクレコードはメッシュMAのリンクリストには格納されていない。図9は、本実施の形態による図6のメッシュMBにおけるノードリストに格納される各ノードレコードの一例を示す図である。図9に示すように、メッシュMBのノードリストには、ノード番号0,1,2がそれぞれ付与されたノードNB0,NB1,NB2のノードレコードが格納されている。図10は、本実施の形態による図6のメッシュMBにおける各リンクリストの一例を示す図である。図10に示すように、メッシュMBのリンクリストには、リンク番号0,1,2,3がそれぞれ付与されたリンクLB0,LB1,LB2,LB3のリンクレコードが格納されている。上記より、本実施の形態による地図情報記憶部3地図情報記憶手段は、地図情報をメッシュに分割して記憶する記憶手段であって、メッシュに設けられたノードと、ノード間を接続するリンクとで道路網を規定し、ノードに接続されるリンクの情報と当該リンクが属するメッシュの情報とを含む接続リンク情報を有する道路データを、地図情報に含めてメッシュごとに記憶している。次に、図11~13を用いて、道路網補助データについて説明する。道路網補助データは、プロセッサ4の道路網データ取得手段が地図情報記憶部3から読み出した取得した所望の道路網データに基づいて生成され、読み出された道路網データとともにメッシュごとにプロセッサ4のメモリに格納される。道路網補助データは、リンク端ノードテーブル、リンクオフセットテーブル、ノードオフセットテーブルを有する。なお、地図情報記憶部3から所望の道路網データを取得する動作は、プロセッサ4の道路網データ取得手段が行う。図11は、本実施の形態によるリンク端ノードテーブルの一例を示す図である。図11に示すように、リンク端ノードテーブルは、メッシュ内に存在するリンクに対応して設けられたリンク端ノードレコードを有する。また、リンク端ノードレコードは、リンクに接続されるノードの情報を有し、始点ノードが属するメッシュの隣接メッシュコードを示す始点ノードメッシュ情報と、始点ノードのノード番号と、終点ノードが属するメッシュの隣接メッシュコードを示す終点ノードメッシュ情報と、終点ノードのノード番号とを有する。ここで、始点ノードメッシュ情報と始点ノード番号とを合わせて始点ノード情報と称し、終点ノードメッシュ情報と終点ノード番号とを合わせて終点ノード情報と称する。また、始点ノード情報、終点ノード情報のいずれか一方または両方をリンク端ノード情報と称する。上記のようなリンク端ノードテーブルを生成することによって、リンク端ノードテーブルに基づいて、リンクに接続するノードを直ちに求めることができる。図12は、本実施の形態によるリンクオフセットテーブルの一例を示す図である。図12に示すように、リンクオフセットテーブルには、リンクリストにおけるリンクレコードのオフセットリンクリストの先頭から対象となるリンクレコードの先頭までのバイト数が格納されている。すなわち、リンクオフセットテーブルは、接続リンク情報に含まれるリンクにリンク番号を付し、当該リンク番号とリンクのオフセットとを対応付けている。リンクオフセットテーブルを生成することによって、ノードレコードに格納されている接続リンク情報の接続リンク番号に基づいて、リンクリストのリンクレコードを直ちに取得することができる。図13は、本実施の形態によるノードオフセットテーブルの一例を示す図である。図13に示すように、ノードオフセットテーブルには、ノードリストにおけるノードレコードのオフセットノードリストの先頭から対象となるノードレコードの先頭までのバイト数が格納されている。すなわち、ノードオフセットテーブルは、リンク端ノード情報に含まれるノードにノード番号を付し、当該ノード番号とノードのオフセットとを対応付けている。ノードオフセットテーブルを生成することによって、リンク端ノードテーブルに格納されているノード番号に基づいて、ノードリストのノードレコードを直ちに取得し、リンクに接続するノードを求めることができる。次に、本実施の形態による地図情報処理装置の動作について説明する。まず、本実施の形態によるリンクとメッシュとの関係について説明する。図14は、本実施の形態によるリンクとメッシュとの関係の一例を示す図である。図14に示すように、3つのメッシュのうち最も左側のメッシュを対象メッシュとしており、中央のメッシュを隣接メッシュとしている。図14aでは、リンク接続リンクLaの一端のノードは対象メッシュ内に存在し、他端のノードは隣接メッシュではない最も右側のメッシュ内に存在している。そして、リンクLaは、両端のノードを接続するように、3つのメッシュに跨って存在している。本実施の形態では、リンクが図14aに示すように3つのメッシュに跨って存在する場合は、図14bに示すように隣接メッシュ内に新たにノードを生成し、図14aに示すリンクLaを、図14に示すリンクLa1とリンクLa2とに分割することによって、リンクが2つのメッシュに跨って存在するようにしている。すなわち、本実施の形態では、道路網データ作成時に予め、リンクが3つ以上のメッシュを跨る場合は、当該リンクを2つのメッシュを跨るように分割しておく。例えば、現在地が対象メッシュ内に存在し、現在地周辺でマップマッチング処理や経路探索処理を行なう場合において、図14aに示すように、リンクが3つのメッシュに跨って存在する場合は、対象メッシュの道路網と当該対象メッシュから3つ離れたメッシュ最も右側のメッシュの道路網とが直接的に接続しているため、対象メッシュ、隣接メッシュ、および対象メッシュから3つ離れたメッシュの道路網データを地図情報記憶部3から取得して処理を行う必要がある。一方、図14bに示すように、リンクが2つのメッシュに跨るように存在する場合は、対象メッシュおよび隣接メッシュの道路網データのみを地図情報記憶部3から取得すれば処理を行うことができる。このように、リンクが3つ以上のメッシュに跨って存在する場合は、2つのメッシュに跨るようにリンクを分割することによって、対象メッシュから3つ以上離れたメッシュの道路網データを地図情報記憶部3から取得する必要がなくなり、道路網データの効率的な読み出しが可能となる。また、地図情報記憶部3から読み出す道路網データのデータ量が削減されるため、地図情報記憶部3に対するアクセスが早くなる。以下、本実施の形態では、リンクは2つのメッシュに跨って存在するものとして説明する。次に、道路網補助データの生成について説明する。図15は、本実施の形態による道路網補助データを生成する処理動作を示すフローチャートであり、経路探索処理やマップマッチング処理において、現在地を含むメッシュと、当該メッシュに隣接する隣接メッシュとの道路網補助データを生成する。また、図16は、本実施の形態によるプロセッサ4におけるメモリの内容の一例を示す図であり、プロセッサ4のメモリに格納される各データを用いて、道路網補助データの生成、あるいは後述の隣接ノードの算出を行う。以下では、図6に示す道路網を一例として説明する。図6において、現在地が存在するメッシュをメッシュMA隣接メッシュコード=0とし、メッシュMAの右側に隣接する隣接メッシュをメッシュMB隣接メッシュコード=3とする。メッシュMB以外の隣接メッシュ隣接メッシュコード=1,2,4~8はメッシュMBと同様であるため、ここでは説明を省略する。なお、道路網補助データは、プロセッサ4による処理によって生成され、特に、リンク端ノード情報は、リンク端ノード情報算出手段によって算出される。図15に示すように、道路網補助データを生成する処理動作が開始されると、プロセッサ4は、現在地が存在するメッシュメッシュMAの道路網データ図3参照を地図情報記憶部3から読み出し、プロセッサ4のメモリに格納する図16参照。具体的には、メッシュMAのノードリスト図7参照、リンクリスト図8参照、形状リスト図示せずを読み出すステップS1501。ステップS1501の後、メッシュMAのリンク端ノードテーブルをプロセッサ4のメモリに生成し図16参照、生成されたリンク端ノードテーブルのすべてのリンク端ノードレコードに対して初期化を行うステップS1502。すなわち、始点ノードメッシュ情報は無効を示す値例えば、0xFに設定し、始点ノード番号は所定の値例えば、0xFFFFに設定し、終点ノードメッシュ情報は無効を示す値例えば、0xFに設定し、終点ノード番号は所定の値例えば、0xFFFFに設定する。図17は、本実施の形態によるメッシュMAに対して生成されたリンク端ノードテーブルの一例を示す図である。図17に示すように、メッシュMAのリンク端ノードテーブルにおける各リンクLA0,LA1,LA2に対応するリンク端ノードレコードには、上記の各値が設定される。ステップS1502の後、メッシュMAのリンクオフセットテーブルをプロセッサ4のメモリに生成し図16参照、道路網データのリンクリストにおける各リンクレコードのオフセットを算出してリンクオフセットテーブルに設定するステップS1503。なお、リンクレコードのオフセットは、初期値を0すなわち、リンクリストにおける先頭のリンクレコードのオフセット値を0とし、各リンクレコードのサイズバイト数を累積的に加算して得られる値であるものとする。ステップS1503の後、すべてのメッシュ隣接メッシュコード=0~8の道路網データを地図情報記憶部3から読み出したか否かの判断を行うステップS1504。ステップS1504において、すべてのメッシュの道路網データを読み出していないと判断した場合は、ステップS1501に移行し、次のメッシュの道路網データを読み出す。ここでは、メッシュMAの次のメッシュであるメッシュMBの道路網データを読み出す。具体的には、メッシュMBのノードリスト図9参照、リンクリスト図10参照、形状リスト図示せずを読み出す。以降、メッシュMBに対する処理ステップS1502,1503はメッシュMAに対する処理と同様である。一例として、ステップS1502にて生成初期化されたメッシュMBのリンク端ノードテーブルを図18に示す。上記のステップS1501~ステップS1504の処理を、現在地が存在するメッシュとすべての隣接メッシュに対して順に行う。すなわち、隣接コード0~8の順に処理を行う。一方、ステップS1504において、すべてのメッシュの道路網データを読み出したと判断した場合は、読み出したメッシュの道路網データに基づいて、道路網補助データの生成を行うステップS1505。具体的には、ステップS1502にて生成された各メッシュにおけるリンク端ノードテーブルの設定や、各メッシュのノードオフセットテーブルをプロセッサ4のメモリに生成し図16参照、道路網データのノードリストにおける各ノードレコードのオフセットを算出してリンクオフセットテーブルに設定するステップS1503。道路網補助データの生成の詳細については後述する。ステップS1505の後、すべてのメッシュの道路網補助データの生成を終了したか否かの判断を行うステップS1506。ステップS1506において、すべてのメッシュの道路網補助データの生成を終了していないと判断した場合は、ステップS1505に移行し、次のメッシュの道路網補助データを生成する。上記のステップS1505,1506の処理を、現在地が存在するメッシュとすべての隣接メッシュに対して順に行う。すなわち、隣接コード0~8の順に処理を行う。一方、ステップS1506において、すべてのメッシュの道路網補助データの生成を終了したと判断した場合は、道路網補助データの生成する処理動作を終了する。上記より、プロセッサ4によって現在地が存在するメッシュおよび隣接メッシュの道路網データが読み出され、読み出された道路網データに基づいて、図16に示すような各メッシュの道路網補助データリンク端ノードテーブル、リンクオフセットテーブル、ノードオフセットテーブルが生成される。また、本実施の形態では、前述の通り、リンクが3つ以上のメッシュに跨る場合はリンクを分割し、リンクが2つのメッシュに跨るようにしているため、プロセッサ4の道路網データ取得手段は、処理の対象となるメッシュである対象メッシュの道路網データと、対象メッシュに隣接するメッシュである隣接メッシュの道路網データといを地図情報記憶部3から読み出せばよい。従って、3つ以上離れた不要なメッシュの道路網データの読み出しを防止することができる。次に、道路網補助データの生成の詳細について説明する。図19は、本実施の形態による道路網補助データの生成の詳細な処理動作を示すフローチャートである。図19に示す道路網補助データの生成は、図15のステップS1505における処理に対応しており、上述の通り各メッシュに対して順に行われる。図15のステップS1501~1504の処理によって、すべてのメッシュの道路網データが取得されると、プロセッサ4は、図16に示すように、対象メッシュのノードオフセットテーブルをプロセッサ4のメモリに生成するステップS1901。ステップS1901の後、プロセッサ4のメモリに生成されている参照レコードオフセット図16参照の初期化例えば、0に設定を行うステップS1902。参照レコードオフセットは、参照するノードレコードのオフセットを記憶するために用いられる。初期化を行うことによって、参照レコードオフセットは、対象メッシュのノードリストの先頭のノードレコードを参照する。以下、各ノードレコードに対応するノードを対象ノードとも称する。ステップS1902の後、対象メッシュのノードリストから、参照レコードオフセットが示すノードレコードを選択するステップS1903。例えば、メッシュMAの場合は、ステップS1903の処理を行うたびに、図7に示すノード番号0~3のノードレコードが順に選択される。すなわち、対象メッシュのすべてのノードレコードに対して、後述のステップS1904~1912の処理が行われる。同様に、メッシュMBの場合は、ステップS1903の処理を行うたびに、図9に示すノード番号0~2のノードレコードが順に選択される。以下のステップS1904~1908では、ステップS1903にて選択されたノードレコードの接続リンク情報を順に参照して処理を行う。例えば、メッシュMA場合は、図7に示すノード番号0のノードレコードがステップS1903にて選択されたとき、接続リンク情報A00~A03に対して順に処理を行う。ステップS1903の後、図15のステップS1502で生成初期化された各メッシュのリンク端ノードテーブルから、接続リンク情報の接続リンクメッシュ情報が示すメッシュのリンク端ノードテーブルを選択するステップS1904。例えば、メッシュMAの場合は、図7に示すノード番号0のノードレコードの接続リンク情報A00,A01,A03では、接続リンクメッシュ情報が0隣接メッシュコード=0であるためメッシュMAのリンク端ノードテーブルを選択し、接続リンク情報A02では、接続リンクメッシュ情報が3隣接メッシュコード=3であるためメッシュMBのリンク端ノードテーブルを選択する。ステップS1904の後、ステップS1904にて選択されたリンク端ノードテーブルから、接続リンク情報の接続リンク番号が示すリンク端ノードレコードを選択するステップS1905。ステップS1905の後、接続リンク情報の接続方向が順方向か否かの判断を行うステップS1906。ステップS1906にて順方向であると判断された場合において、対象ノードは接続リンク番号が示すリンクの始点ノードであるため、ステップS1905にて選択したリンク端ノードレコードに始点ノード情報始点ノード番号、始点ノードメッシュ情報を格納するステップS1907。すなわち、始点ノード番号として、対象ノードのノード番号を格納する。また、始点ノードメッシュ情報として、ステップS1903にて選択したノードレコードの接続リンク情報の接続リンクメッシュ情報と対象メッシュとの関係に基づいて、接続リンクメッシュ情報が対象メッシュを示す場合は、対象メッシュを示す隣接メッシュコードを格納し、接続リンクメッシュ情報と対象メッシュとが異なる場合は、接続リンクメッシュ情報が示すメッシュを基準とした対象メッシュの隣接メッシュコードを格納する。始点ノード情報の格納後、ステップS1909に移行する。一方、ステップS1906にて順方向でないすなわち、逆方向であると判断された場合において、対象ノードは接続リンク番号が示すリンクの終点ノードであるため、ステップS1905にて選択したリンク端ノードレコードに終点ノード情報終点ノード番号、終点ノードメッシュ情報を格納するステップS1908。すなわち、終点ノード番号として、対象ノードのノード番号を格納する。また、終点ノードメッシュ情報として、ステップS1903にて選択したノードレコードの接続リンク情報の接続リンクメッシュ情報と対象メッシュとの関係に基づいて、接続リンクメッシュ情報が対象メッシュを示す場合は、対象メッシュを示す隣接メッシュコードを格納し、接続リンクメッシュ情報と対象メッシュとが異なる場合は、接続リンクメッシュ情報が示すメッシュを基準とした対象メッシュの隣接メッシュコードを格納する。終点ノード情報の格納後、ステップS1909に移行する。図20,21は、対象メッシュがメッシュMAの場合における、ステップS1906~ステップS1908の処理後に得られるメッシュMA,MBのリンク端ノードテーブルの格納状態の一例を示す図である。図20,21に示すように、図7に示すノード番号0のノードレコードの接続リンク情報A00に基づき、図20に示す接続リンク番号0LA0のリンク端ノードレコードの始点ノード情報が格納される。また、図7に示すノード番号0のノードレコードの接続リンク情報A01に基づき、図20に示す接続リンク番号1LA1のリンク端ノードレコードの終点ノード情報が格納される。また、図7に示すノード番号0のノードレコードの接続リンク情報A02に基づき、図21に示す接続リンク番号0LB0のリンク端ノードレコードの終点ノード情報が格納される。また、図7に示すノード番号0のノードレコードの接続リンク情報A03に基づき、図20に示す接続リンク番号2LA2のリンク端ノードレコードの始点ノード情報が格納される。また、図7に示すノード番号1のノードレコードの接続リンク情報A10に基づき、図20に示す接続リンク番号0LA0のリンク端ノードレコードの終点ノード情報が格納される。また、図7に示すノード番号2のノードレコードの接続リンク情報A20に基づき、図20に示す接続リンク番号1LA1のリンク端ノードレコードの始点ノード情報が格納される。また、図7に示すノード番号3のノードレコードの接続リンク情報A30に基づき、図20に示す接続リンク番号2LA2のリンク端ノードレコードの終点ノード情報が格納される。図22は、対象メッシュがメッシュMBの場合における、ステップS1906~ステップS1908の処理後に得られるメッシュMBのリンク端ノードテーブルの格納状態の一例を示す図である。上記の対象メッシュがメッシュMAである場合と同様に、対象メッシュがメッシュMBの場合もリンク端ノードテーブルの各リンク端ノードレコードに対してリンク端ノード情報始点ノード情報、終点ノード情報が格納される。ただし、メッシュMBのリンク番号2であるリンクLB2の終点ノードはメッシュMCに属しているが、当該メッシュMCはメッシュMAに隣接していないため、メッシュMCの道路網データは地図情報記憶部3から読み出されず、上記の処理は行われない。従って、図22に示すように、リンク番号2のリンクLBのリンク端ノードレコードの終点ノードメッシュ情報および終点ノード番号は初期値のまますなわち、無効値のままとなっている。このようにすることによって、地図情報記憶部3から読み出されていないメッシュMCに対して道路網を接続することは不要であることが分かる。ステップS1907あるいはステップS1908の後、参照レコードオフセットが示すノードレコードにおけるすべての接続リンク情報に対してステップS1903~ステップS1908の処理が終了したか否かの判断を行うステップS1909。ステップS1909において、すべての接続リンク情報に対してステップS1903~ステップS1908の処理が終了していないと判断された場合は、ステップS1904に移行し、ステップS1903にて選択されたノードレコードにおける次の接続リンク情報について上記と同様の処理を行う。一方、ステップS1909において、すべての接続リンク情報に対してステップS1903~ステップS1908の処理が終了したと判断された場合は、参照レコードオフセットが示すノードレコードのオフセットを、ノードオフセットテーブルの対象ノードに対応する箇所に格納するステップS1910。ステップS1910の後、対象メッシュのノードリストのすべてのノードレコードに対してステップS1904~ステップS1910の処理が終了したか否かの判断を行うステップS1911。ステップS1911において、すべてのノードレコードに対する処理が終了していないと判断された場合は、参照レコードオフセットに対して、現在の参照レコードオフセットに対象ノードのノードレコードのサイズを加えた値に更新すなわち、参照レコードオフセットを更新し、次のノードレコードのオフセットを示すようにするステップS1912。ステップS1912の後、ステップS1903に移行し、上記と同様の処理を行う。一方、ステップS1911において、すべてのノードレコードに対する処理が終了したと判断された場合は、対象メッシュの道路網補助データの生成の処理動作を終了する。上記より、1つのメッシュ内に存在するリンク例えば、図6のリンクLA0については、当該メッシュのノードリストに基づいてリンク端ノード情報が得られ、また、2つのメッシュに跨って存在するリンク例えば、図6のリンクLB0については、リンク両端のノード例えば、リンクLB0の場合はノードNA0,NB0が属するメッシュ例えば、メッシュMA,MBのノードリストに基づいてリンク端ノード情報が得られる。すなわち、プロセッサ4のリンク端ノード情報算出手段は、道路網データ取得手段にて取得された道路網データの接続リンク情報に基づき、リンクがメッシュを跨がない場合は、当該メッシュの道路網データの接続リンク情報から、リンクがメッシュを跨ぐ場合は、当該リンクの両端のノードが含まれる2つのメッシュの道路網データの接続リンク情報から、リンクの端部に接続されるノードの情報であるリンク端ノード情報を算出する。また、例えば図22に示すように、リンク端ノードテーブルは、プロセッサ4のリンク端ノード情報算出手段によって算出されたリンク端ノード情報と、算出されなかったリンク端ノード情報例えば、図22の初期値とを区別可能に格納しているため、地図情報記憶部3から読み出していないメッシュに対して道路網の接続を行う処理を防止することができる。また、プロセッサ4のリンク端ノード情報算出手段は、リンクが属するメッシュの道路網データをプロセッサ4の道路網データ取得手段が取得しない場合は、リンク端ノード情報を算出しないため、地図情報記憶部3から読み出していないメッシュに対する不要な処理を防止することができる。また、上記のように生成されたリンク端ノードテーブルを参照することによって、一方のノードから1本のリンクを介して到達する他方のノード以下、隣接ノードとも称するを、リンクが隣接メッシュに跨って2つのメッシュに跨って存在するか否かに関わらず直ちに求めることができる。例えば、メッシュMAのノードNA0に接続するメッシュMAのリンクLA0リンク番号0に対して、リンク端ノードテーブル図20参照のリンク番号0に対応するリンク端ノードレコードの終点ノード情報から、ノード番号1であるノードNA1が隣接ノードであることが分かる。また、メッシュMAのノードNA0に接続するメッシュMBのリンクLB0に対して、リンク端ノードテーブル図22参照のリンク番号0に対応するリンク端ノードレコードの始点ノード情報から、メッシュMBのノード番号0であるNB0が隣接ノードであることが分かる。次に、隣接ノードの算出について説明する。経路探索やマップマッチングの処理では、道路網データと道路網補助データとに基づいて、隣接ノードの算出を繰り返すことによって道路網を辿る。図23は、本実施の形態による隣接ノードを算出する処理動作を示すフローチャートであり、ある対象ノードに対する隣接ノードに関する情報を隣接ノードレコードとして生成し、プロセッサ4のメモリに設けられた隣接ノードリスト図16参照に登録格納する処理について示す。なお、当該処理は、プロセッサ4において、接続リンク情報とリンク端ノード情報とに基づき、道路網の接続関係を算出する道路網接続関係算出手段が行う。ここで、隣接ノードリストに登録する隣接ノードレコードは、隣接ノードが属するメッシュの隣接メッシュコードを示す隣接ノードメッシュ情報と、隣接ノードのノード番号を示す隣接ノード番号とを有する。以下では、具体例として、対象ノードを図6に示すメッシュMAのノードNA0とし、当該ノードNA0の隣接ノードNA1,NA2,NB0,NA3を求める場合について説明する。また、図24は、対象ノードを図6に示すメッシュMAのノードNA0とした場合における、図23に示す処理によって得られた隣接ノードリストの一例を示す図である。隣接ノードを算出する処理動作が開始されると、まず、参照メッシュ情報の初期化、参照レコードオフセットの初期化、隣接ノードリストの初期化を行うステップS2301。参照メッシュ情報の初期化では、プロセッサ4のメモリに設けられた参照メッシュ情報図16参照に、対象ノードが属するメッシュ対象メッシュの隣接メッシュコードを格納する。また、参照レコードオフセットの初期化では、対象ノードが属するメッシュのノードオフセットテーブルから、対象ノードのノード番号に対応するノードレコードオフセットを求めて参照レコードオフセット図16参照に設定する。また、隣接ノードリストの初期化では、隣接ノードリストに登録されている隣接レコードがないようにする。上記の各初期化によって、参照メッシュ情報にはメッシュMAの隣接メッシュコードが格納され、参照レコードオフセットにはノードNA0のノードレコードのオフセットが格納される。以下のステップS2302~ステップS2306では、参照レコードオフセットが示すノードレコードの接続リンク情報を順に参照することによって処理を行う。すなわち、ここでは、図7に示すノード番号0NA0における接続リンク情報A00~A03を順に参照することによって処理を行う。ステップS2301の後、図15のステップS1505にて生成された各メッシュのリンク端ノードテーブルから、接続リンク情報の接続リンクメッシュ情報が示すメッシュに対応するリンク端ノードテーブルを選択するステップS2302。例えば、接続リンク情報A00,A01,A03については、接続リンクメッシュ情報が0隣接ノードコード=0であるため、対象メッシュMAのリンク端ノードテーブル図20参照を選択する。また、接続リンク情報A02については、接続リンクメッシュ情報が3隣接ノードコード=3であるため、隣接メッシュMBのリンク端ノードテーブル図22参照を選択する。ステップS2302の後、ステップS2302にて選択したリンク端ノードテーブルから、接続リンク情報の接続リンク番号が示すリンク端ノードレコードを選択するステップS2303。例えば、接続リンク情報A00,A01,A03については、接続リンク番号がそれぞれ0,1,2であるため、対象メッシュMAのリンク端ノードテーブル図20参照のリンク番号0,1,2に対応するリンク端ノードレコードをそれぞれ選択する。また、接続リンク情報A02については、接続リンク番号が0であるため、隣接メッシュMBのリンク端ノードテーブル図22参照のリンク番号0に対応するリンク端ノードレコードを選択する。ステップS2303の後、接続リンク情報のリンク番号が示すリンクの接続方向が順方向か否かの判断を行うステップS2304。ステップS2304において、リンクの接続方向が順方向であると判断された場合、対象ノードはリンクの始点ノードであり、隣接ノードはリンクの終点ノードに対応するため、ステップS2303にて選択したリンク端ノードレコードの終点ノードメッシュ情報、終点ノード番号を、それぞれ隣接ノードレコードの隣接ノードメッシュ情報、隣接ノード番号に設定し、設定した隣接ノードレコードを隣接ノードリストに格納登録するステップS2305。ただし、終点ノードメッシュ情報が0および0xF以外の場合は、終点ノードメッシュ情報が示すメッシュを、対象メッシュを基準とする隣接メッシュコードに変換してから隣接ノードメッシュ情報に設定する。終点ノードを隣接ノードリストに格納後、ステップS2307に移行する。例えば、接続リンク情報A00については、対象メッシュMAのリンク端ノードテーブル図20参照のリンク番号0に対応するリンク端ノードレコードの終点ノードメッシュ情報0、終点ノード番号1のそれぞれを、隣接ノードレコード0の隣接ノードメッシュ情報、隣接ノード番号のそれぞれに設定し、設定した隣接ノードレコード0を隣接ノードリストに格納する図24参照。また、接続リンク情報A03については、対象メッシュMAのリンク端ノードテーブル図20参照のリンク番号2に対応するリンク端ノードレコードの終点ノードメッシュ情報0、終点ノード番号3のそれぞれを、隣接ノードレコード3の隣接ノードメッシュ情報、隣接ノード番号のそれぞれに設定し、設定した隣接ノードレコード3を隣接ノードリスト図24参照に格納する。なお、対象ノードがメッシュMBのノードNB0の場合において、接続リンク情報B02については、対象メッシュMBのリンク端ノードテーブル図22参照のリンク番号2に対応するリンク端ノードレコードの終点ノードメッシュ情報0xF、終点ノード番号0xFFFFのそれぞれを、隣接ノードレコード図示せずの隣接ノードメッシュ情報、隣接ノード番号のそれぞれに設定し、設定した隣接ノードレコードを隣接ノードリスト図示せずに格納する。このように、隣接ノードレコードに無効値が設定されるため、対象ノードNB0に対してリンクLB2を介して接続される隣接ノードがないことが分かる。ステップS2304において、リンクの接続方向が順方向ではないすなわち、逆方向であると判断された場合、対象ノードはリンクの終点ノードであり、隣接ノードはリンクの始点ノードに対応するため、ステップS2303にて選択したリンク端ノードレコードの始点ノードメッシュ情報、始点ノード番号を、それぞれ隣接ノードレコードの隣接ノードメッシュ情報、隣接ノード番号に設定し、設定した隣接ノードレコードを隣接ノードリストに格納登録するステップS2306。ただし、始点ノードメッシュ情報が0および0xF以外の場合は、始点ノードメッシュ情報が示すメッシュを、対象メッシュを基準とする隣接メッシュコードに変換してから隣接ノードメッシュ情報に設定する。始点ノードを隣接ノードリストに格納後、ステップS2307に移行する。例えば、接続リンク情報A01については、対象メッシュMAのリンク端ノードテーブル図20参照のリンク番号1に対応するリンク端ノードレコードの始点ノードメッシュ情報0、始点ノード番号2のそれぞれを、隣接ノードレコード1の隣接ノードメッシュ情報、隣接ノード番号のそれぞれに設定し、設定した隣接ノードレコード1を隣接ノードリストに格納する図24参照。また、接続リンク情報A02については、メッシュMBのリンク端ノードテーブル図22参照のリンク番号0に対応するリンク端ノードレコードの始点ノードメッシュ情報0、始点ノード番号0のそれぞれを、隣接ノードレコード2の隣接ノードメッシュ情報、隣接ノード番号のそれぞれに設定するのだが、始点ノードメッシュ情報0はメッシュMBが対象メッシュである場合の隣接メッシュコードで示されているため、当該始点ノードメッシュ情報0をメッシュMAが対象メッシュである場合の隣接メッシュコード3に変換する必要がある。従って、変換した始点ノードメッシュ情報3、隣接ノード番号0のそれぞれを隣接ノードレコード2の隣接ノードメッシュ情報、隣接ノード番号のそれぞれに設定し、設定した隣接ノードレコード2を隣接ノードリストに格納する図24参照。ステップS2305あるいはステップS2306の後、参照レコードオフセットが示すノードレコードにおけるすべての接続リンク情報に対してステップS2302~ステップS2306の処理が終了したか否かの判断を行うステップS2307。ステップS2307において、すべての接続リンク情報に対してステップS2302~ステップS2306の処理が終了していないと判断された場合は、ステップS2302に移行し、次の接続リンク情報について上記と同様の処理を行う。一方、すべての接続リンク情報に対してステップS2302~ステップS2306の処理が終了したと判断された場合は、隣接ノードを算出する処理動作を終了する。上記の処理を行うことによって、図24に示すような隣接ノードリストが得られ、得られた隣接ノードリストを参照することによって、対象ノードNA0の隣接ノードがノードNA1,NA2,NB0,NA3であることが直ちに分かる。また、隣接ノードリストに登録された各ノードに対して上記の処理を行うことによって、さらに次の隣接ノードが求まる。すなわち、上記の処理を繰り返し行うことによって、1本のリンクにより接続されているノードを順次求めることができる。なお、隣接ノードリストの隣接ノードレコードにおける隣接ノード番号が無効0xFFFFの場合は、当該無効の隣接ノードを求めないようにする。すなわち、プロセッサ4の道路網接続関係算出手段は、リンク端ノード情報が算出されなかった場合は、当該算出されなかったリンク端ノード情報に含まれるノードに対する道路網の接続関係を算出しない。このようにすることによって、地図情報記憶部3から読み出していないメッシュに対する不要な処理の発生を防止することができる。以上のことから、リンクがメッシュを跨って存在する場合であってもリンクとノードとの接続情報を生成することが可能となり、道路網を迅速に辿ることができる。なお、本実施の形態による地図情報処理装置の入力部1図1参照は、操作スイッチ群であるものとして説明したが、操作スイッチ群以外にも、表示部5の表示面に装着されたタッチパネル図示せず、リモートコントロールスイッチ図示せず、音声認識装置図示せず等を入力手段として使用してもよい。また、本実施の形態において、リンクレコードは、始点ノードが属するメッシュのリンクリストのみに格納されるが、終点ノードが属するメッシュのリンクリストのみに格納するようにしてもよい。また、本実施の形態において、リンク端ノードテーブルのリンク端ノードレコードに格納されるノードのメッシュ情報を隣接メッシュコードで示したが、隣接メッシュコードに代えて、各メッシュに固有のメッシュ番号などで示してもよい。また、本実施の形態において、リンク端ノード情報はリンクリストとは別に設けられたが、リンクリストのリンクレコード内に設けるようにしてもよい。また、本実施の形態において、リンクが3つ以上のメッシュに跨って存在する場合は、予め2つのメッシュに跨るようにリンクを分割したが、リンクを分割しなくてもよい。このとき、リンクが所属するメッシュの接続リンクメッシュ情報として隣接メッシュコードが使用できないため、隣接メッシュコードに代えてメッシュ番号を接続リンクメッシュ情報として示してもよい。なお、本発明は、その発明の範囲内において、実施の形態を適宜、変形、省略することが可能である。"