(57)【特許請求の範囲】
【請求項１】
道路がリンク単位で表現され、これらリンクの接続関係を表す情報によって、道路ネットワークが表現される地図データであって、
前記道路ネットワークを構成する前記リンク毎に、当該リンクに関する属性データであって、このリンクの端点における前記リンクの接続関係を表す情報を有する属性データを備え、これらリンク毎の属性データが配列された構成にされる第一のデータリストと、
前記第一のデータリストにおける前記属性データの配列に従うリンク列上の地点であって、少なくとも当該リンク列を構成する各リンクの端点に対応する地点毎に、この地点の座標を表す座標データを備え、これら地点毎の座標データが、前記第一のデータリストにおける前記属性データの配列に従って、前記リンク列の始点側から順に配列された第二のデータリストと、
を備え、
前記リンク毎の前記属性データは、このリンクの前記端点における前記リンクの接続関係を表す情報として、他リンクが接続される端点毎に、この端点に接続される少なくとも一つ以上のリンクの集合のうち、一つのリンクのみが接続相手として記述された接続リンク情報を有し、更に、このリンク上の各地点に対応する前記座標データの数である座標点数の情報を有した構成にされ、
前記地図データは、コンピュータが実行する処理に利用され、注目するリンク上の各地点の座標を特定する処理の実行時には、前記コンピュータが、前記第一のデータリストにおける先頭の前記属性データから前記注目するリンクの前記属性データまでの前記属性データが有する前記座標点数の情報に基づき、前記第二のデータリストにおける前記注目するリンク上の各地点に対応する前記座標データを参照すること
を特徴とする地図データ。
【請求項２】
同一地点で互いに接続される各リンクの前記属性データが有する、この地点での前記リンクの接続関係を表す前記接続リンク情報の夫々には、前記接続リンク情報に記述された接続相手の前記接続リンク情報を順に参照したときに、この地点に接続される全リンクについての前記接続リンク情報を一通り参照可能なように、前記接続相手が記述され、
前記コンピュータが、注目するリンクの端点に接続されるリンクを特定する処理の実行時には、前記注目するリンクが有する前記端点の前記接続リンク情報を起点に、前記接続リンク情報が示す接続相手の前記端点の前記接続リンク情報を順に参照することによって、前記端点に接続される全リンクについての前記接続リンク情報を一通り参照すること
を特徴とする請求項１記載の地図データ。
【請求項３】
前記リンク毎の前記属性データが有する前記端点毎の前記接続リンク情報には、このリンクの前記端点を中心とした時計回り及び反時計回りのいずれか一方向において、このリンクに隣接するリンクが接続相手として記述されていること
を特徴とする請求項２記載の地図データ。
【請求項４】
道路がリンク単位で表現され、これらリンクの接続関係を表す情報によって、道路ネットワークが表現される地図データを記憶する記憶手段と、
前記記憶手段が記憶する前記地図データを用いた処理を実行する処理実行手段と、
を備える電子機器であって、
前記地図データは、
前記道路ネットワークを構成する前記リンク毎に、当該リンクに関する属性データであって、このリンクの端点における前記リンクの接続関係を表す情報を有する属性データを備え、これらリンク毎の属性データが配列された構成にされる第一のデータリストと、
前記第一のデータリストにおける前記属性データの配列に従うリンク列上の地点であって、少なくとも当該リンク列を構成する各リンクの端点に対応する地点毎に、この地点の座標を表す座標データを備え、これら地点毎の座標データが、前記第一のデータリストにおける前記属性データの配列に従って、前記リンク列の始点側から順に配列された第二のデータリストと、
を備え、
前記リンク毎の前記属性データは、このリンクの前記端点における前記リンクの接続関係を表す情報として、他リンクが接続される端点毎に、この端点に接続される少なくとも一つ以上のリンクの集合のうち、一つのリンクのみが接続相手として記述された接続リンク情報を有し、更に、このリンク上の各地点に対応する前記座標データの数である座標点数の情報を有した構成にされ、
前記処理実行手段は、前記地図データを用いた処理の一つとしての、注目するリンク上の各地点の座標を特定する処理の実行時には、前記第一のデータリストにおける先頭の前記属性データから前記注目するリンクの前記属性データまでの前記属性データが有する前記座標点数の情報に基づき、前記第二のデータリストにおける前記注目するリンク上の各地点に対応する前記座標データを参照すること
を特徴とする電子機器。
【請求項５】
同一地点で互いに接続される各リンクの前記属性データが有する、この地点での前記リンクの接続関係を表す前記接続リンク情報の夫々には、前記接続リンク情報に記述された接続相手の前記接続リンク情報を順に参照したときに、この地点に接続される全リンクについての前記接続リンク情報を一通り参照可能なように、前記接続相手が記述され、
前記処理実行手段は、前記地図データを用いた処理の一つとしての、注目するリンクの端点に接続されるリンクを特定する処理の実行時には、前記注目するリンクが有する前記端点の前記接続リンク情報を起点に、前記接続リンク情報が示す接続相手の前記端点の前記接続リンク情報を順に参照することによって、前記端点に接続される全リンクについての前記接続リンク情報を一通り参照すること
を特徴とする請求項４記載の電子機器。
【請求項６】
前記リンク毎の前記属性データが有する前記端点毎の前記接続リンク情報には、このリンクの前記端点を中心とした時計回り及び反時計回りのいずれか一方向において、このリンクに隣接するリンクが接続相手として記述されていること
を特徴とする請求項５記載の電子機器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、地図データ及び電子機器に関する。
【背景技術】
【０００２】
従来、地図データとしては、車載装置用の地図データが知られている。また、地図データのフォーマットとしては、ＫＩＷＩフォーマットが知られている（例えば、非特許文献１参照）。このフォーマットによれば、道路がリンク及びノードで表現され、地図データには、リンク毎に、リンクの形状・ストリートアドレス等のリンクの属性（特徴）を表すリンクデータが格納される。
【０００３】
また、従来の地図データにおいては、各リンクに対して固有のリンクＩＤが割り当てられる。このリンクＩＤは、当該リンクＩＤに対応するリンクデータと他のデータとの関連付けに用いられる。例えば、リンクＩＤは、リンクの接続関係を表現するために用いられる。従来の地図データにおいては、例えば、リンクデータの複数がまとめられてリンク列データが構成されるが、リンク列データには、リンクを結ぶノードに関するデータであって、リンクＩＤを用いたリンクの接続関係を表すノードデータが格納される。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】藤本  英俊、「カーナビ用地図データフォーマットＫＩＷＩ」、デンソーテクニカルレビュー、２００１年、第６巻、第１号、ｐ．２９−３４
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ところで、上記リンクに関するリンクデータと、リンクの接続関係を表すノードデータとを保持する従来の地図データの構成では、リンクデータとノードデータとで座標情報などの重複する情報を保持する。このため、地図データのコンパクト化に改善の余地があった。
【０００６】
本発明は、こうした問題に鑑みなされたものであり、リンクの接続関係を表す情報を効率的に地図データに格納することにより、地図データをコンパクトにすることを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するためになされた第一の発明（請求項１）は、道路がリンク単位で表現され、これらリンクの接続関係を表す情報によって、道路ネットワークが表現された地図データであって、道路ネットワークを構成する各リンクに対して設けられた当該リンクに関する属性データに、このリンクの端点におけるリンクの接続関係を表す情報が格納されていることを特徴とする（特徴点Ａ）。
【０００８】
また、上記リンク毎の属性データが、このリンクの端点におけるリンクの接続関係を表す情報として、他リンクが接続される端点毎に、この端点に接続される少なくとも一つ以上のリンクの集合のうち、一つのリンクのみが接続相手として記述された接続リンク情報を有することを特徴とする（特徴点Ｂ）。地図データは、コンピュータが実行する処理に利用される。
【０００９】
特徴点Ａによれば、各リンクの属性データに、このリンクと他のリンクとの接続関係を表す情報が格納されているので、地図データにおいては、これらリンク毎の属性データに対して別途、各リンクの接続関係を表すノードデータを、ノード毎に設ける必要がないといった利益が得られる。
【００１０】
但し、ノードデータが地図データに設けられなくても、リンク毎の属性データに、このリンクに接続される全てのリンクについての情報が記述されたのでは、地図データのデータ量を効率的に抑えることはできない。
【００１１】
そこで、本発明では、特徴点Ｂによって、地図データを、リンクの接続関係を効率よくリンク毎の属性データに保持可能なデータ構造としている。即ち、本発明では、互いに接続されるリンクの組が、夫々分担してリンクの接続関係を表す情報を保持するように、地図データを構成している。換言すると、本発明では、単一ノードにおける複数リンクの接続関係を、接続に関与するリンク毎の属性データにて分散して保持することにより、地図データにノードデータを設けなくても済むようにすると共に、接続関係を表す情報を効率的に地図データに保持できるようにしている。
【００１２】
従って、本発明によれば、地図データのデータ量を低減することができ、地図データをコンパクトにすることができる。
また、本発明によれば、リンク毎の属性データは、当該リンク毎の属性データが配列された第一のデータリストとして構成される。また、地図データは、第一のデータリストにおける属性データの配列に従うリンク列上の地点であって、少なくとも当該リンク列を構成する各リンクの端点に対応する地点毎に、この地点の座標を表す座標データを備え、これら地点毎の座標データが、第一のデータリストにおける属性データの配列に従って、リンク列の始点側から順に配列された第二のデータリストを備える。
リンク毎の属性データは、更に、このリンク上の各地点に対応する座標データの数である座標点数の情報を有した構成にされる。
そして、コンピュータは、注目するリンク上の各地点の座標を特定する処理の実行時には、第一のデータリストにおける先頭の属性データから注目するリンクの属性データまでの属性データが有する座標点数の情報に基づき、第二のデータリストにおける注目するリンク上の各地点に対応する座標データを参照する。
このデータ構造によれば、地図データをコンパクトにすることができる。
【００１３】
ところで、上述したように、「端点毎に、この端点に接続されるリンクの集合のうち、一つのリンクのみを接続相手として記述する」程度では、道路ネットワークを構成する各リンクの属性データ全体を参照しなければ、一地点でのリンクの接続関係を正確に特定することはできない。このため、上述の発明によれば、地図データをコンパクトにすることができる一方で、リンクの接続関係を特定するための処理負荷に影響が及ぶ可能性がある。
【００１４】
そこで、同一地点で互いに接続される各リンクの属性データに格納する、この地点でのリンクの接続関係を表す接続リンク情報の夫々には、「接続リンク情報に記述される接続相手の接続リンク情報を順に参照したときに、この地点に接続される全リンクについての接続リンク情報を一通り参照可能なように」、接続相手を記述するのが好ましい（請求項２）。コンピュータは、注目するリンクの端点に接続されるリンクを特定する処理の実行時には、注目するリンクが有する端点の接続リンク情報を起点に、接続リンク情報が示す接続相手の当該端点の接続リンク情報を順に参照することによって、当該端点に接続される全リンクについての接続リンク情報を一通り参照することができる。
【００１５】
このように地図データを構成すれば、接続リンク情報に記述された接続相手の接続リンク情報を順に参照する程度で、道路ネットワークを構成するリンク毎の属性データ全体を参照しなくても、一地点におけるリンクの接続関係を正確に特定することができる。
即ち、このように地図データを構成すれば、地図データに基づいたリンク接続関係の特定作業について、その処理負荷を低減することができ、データアクセス性に優れた地図データを作成することができる。
【００１６】
また、リンク毎及び端点毎の上記接続リンク情報には、対応するリンクの端点を中心とした時計回り及び反時計回りのいずれか一方向において、このリンクに隣接するリンクを接続相手として記述してもよい（請求項３）。このように接続関係を記述すれば、各ノードにおけるリンクの接続関係を、簡単且つ効率的に表現して、地図データを構成することができる。
この他、第二の発明は、上述した地図データを記憶する記憶手段と、記憶手段が記憶する地図データを用いた処理を実行する処理実行手段と、を備える電子機器である。この発明によれば、記憶手段が記憶する地図データをコンパクトにすることができる。
【図面の簡単な説明】
【００１７】
【図１】地図データの概略構成を表す図である。
【図２】基本データ／拡張データとして構成される統合ファイルの構成図である。
【図３】道路データにおける各メッシュ単位データの構成を表す図である。
【図４】道路データにおけるリンクレコード及び座標レコードの構成を表す図である。
【図５】道路データにおける道路管理レコード及びリンクレコード及び座標レコードの各配列の関係を表す図である。
【図６】リンクレコードで表現されるリンクの接続関係に関する説明図である。
【図７】リンクレコードで表現されるリンクの接続関係に関する説明図である。
【図８】道路データにおける複合リンク規制レコードの構成を表す図である。
【図９】制限速度データに関する説明図である。
【図１０】ナビゲーション装置１０の概略構成を表すブロック図である。
【図１１】制御回路１９による地図データの展開方法について説明した図である。
【図１２】リンクテーブルＴＢＬ１２，ＴＢＬ１３及びノードテーブルＴＢＬ２２，ＴＢＬ２３の構成を表す図である。
【図１３】制御回路１９が実行するテーブル作成処理を表すフローチャートである。
【図１４】制御回路１９が実行するリンク始点側データ登録処理を表すフローチャートである。
【発明を実施するための形態】
【００１８】
以下に本発明の実施例について、図面と共に説明する。
＜１  地図データの構造＞
本実施例の地図データは、車両に搭載されるナビゲーション装置に組み込まれるものである。図１に示すように、この地図データは、大きく分けて、メタデータ、基本データ群、拡張データ群、及び、その他のデータ群からなる。
【００１９】
メタデータは、地図データの構造に関する主要な管理情報を有するものである。一方、基本データ群は、地図データに必須のデータ群の中でも特に地図の基本情報を有するものである。この基本データ群には、道路に関する情報を有する道路データ、及び、二次元地図の背景に関する情報を有する背景データが含まれる。
【００２０】
また、拡張データは、地図データに適宜追加される種類のデータである。本実施例の地図データ構造によれば、地図データに格納する拡張データの種類によって複数種類の地図データを作成することができる。この拡張データ群には、例えば制限速度データが含まれる。また、上記「その他のデータ群」としては、地図表示に使用されるイメージデータ群やアイコンデータ群等を挙げることができる。
【００２１】
ところで、上記基本データ及び拡張データの夫々は、地図の収録エリア全体を分割してできるメッシュ単位のデータ群に細分化されている（図１下段参照）。そして、上記基本データ及び拡張データの夫々において、これらのメッシュ単位データ群は、統合メッシュデータとして統合されている。但し、統合メッシュデータは、地図の収録エリア全体に対応するメッシュ単位データ群の全てをまとめるものではなく、メッシュ単位データの複数個をまとめてなるデータとして構成される。即ち、地図の収録エリア全体に対しては、複数の統合メッシュデータが用意される。
【００２２】
更に言及すると、基本データ及び拡張データは、地図の詳細度別に階層化されている。即ち、基本データ及び拡張データの夫々は、地図の収録エリア全体を網羅する上記統合メッシュデータ群が階層毎に設けられた統合ファイルとして構成されている（図２参照）。
【００２３】
図１下段は、最下層（レベル０）のメッシュ及び最下層よりも一つ上の階層（レベル１）のメッシュを示した図である。図１下段に示すように、レベル０のメッシュは、レベル１のメッシュが更に所定数分割（図１では１６分割）されたメッシュとして構成されている。以下では、階層のことを「レベル」とも表現する。
【００２４】
即ち、基本データ及び拡張データの夫々を構成するメッシュ単位データの収録エリアは、レベルが大きくなるほど広がるように設計されている。但し、メッシュ単位データが保持する地図情報はレベルが大きくなるほど粗くなる。高レベルのメッシュ単位データは、長距離の経路探索や、広範囲の地図表示をする際に用いられる。
＜１．１  統合ファイルの構造＞
上述したように基本データ及び拡張データの夫々（基本データとしての道路データ及び背景データ、並びに、拡張データとしての制限速度データ）は、各レベルの統合メッシュデータがまとめられてなる統合ファイルとして構成されるが、具体的に、統合ファイルは、図２に示すように構成される。
【００２５】
即ち、統合ファイルは、レベル別の統合メッシュデータ数を記述したレベル別統合メッシュデータ数リストＬａ１、レベル別の統合メッシュデータオフセットを記述したレベル別統合メッシュデータオフセットリストＬａ２、レベル別の統合メッシュデータからなるレベル別統合メッシュデータリストＬａ３、から構成される。尚、統合メッシュデータ数Ａ０〜ＡＸは、該当レベルの統合メッシュデータの数量を示すものであり、固定長で表現される。
【００２６】
また、統合メッシュデータオフセットは、対応する統合メッシュデータへのオフセット（対応する統合メッシュデータが格納された位置を、基準位置からのバイト位置で表現した値）を示し、固定長で表現される。基準位置としては、当該オフセットが記述される領域の先頭位置や、統合メッシュオフセットリストＬａ２の先頭位置、レベル別統合メッシュデータリストＬａ３の先頭位置等を挙げることができる。尚、該当する統合メッシュデータが存在しない場合には空値（０ｘＦＦＦＦＦＦＦＦ）が記述される。
【００２７】
また、統合メッシュデータは、統合メッシュデータサイズ、メッシュ数Ｍ、メッシュ単位データオフセット１〜Ｍからなるメッシュ単位データオフセットリストＬａ４、及び、メッシュ単位データ１〜Ｍからなるメッシュ単位データリストＬａ５から構成される。統合メッシュデータサイズは、当該統合メッシュデータの合計サイズを示すものであり、固定長で表現される。また、メッシュ数Ｍは、統合メッシュデータに対応する地図の収録エリアに含まれるメッシュの数量を示すものであり、固定長で表現される。
【００２８】
この他、メッシュ単位データオフセットは、対応するメッシュ単位データへのオフセット（対応するメッシュ単位データが格納された位置を、基準位置からのバイト位置で表現した値）を示すものであり、固定長で表現される。ここでの基準位置としては、当該オフセットが記述される領域の先頭位置や、メッシュ単位データオフセットリストＬａ４の先頭位置、メッシュ単位データリストＬａ５の先頭位置等を挙げることができる。尚、対応するメッシュ単位データが存在しない場合には空値が記述される。
【００２９】
また、メッシュ単位データ１〜Ｍは、基本データ及び拡張データの核となる情報を有するものであり、基本データ及び拡張データの夫々の種類に対応したフォーマットで記述されている。以下では、代表的なデータとして、道路データ及び制限速度データの構造を説明する。ちなみに、詳細な説明を省略する背景データは、以下に説明する道路データと同様の思想で、地図を構成する背景の種別を表すレコード群と背景のレイアウト位置（座標）を表すレコード群との関連付けがなされたデータとして構成されている。
＜１．２  道路データのメッシュ単位データ＞
上述したように道路データは、道路に関する情報を有するものであり、道路データのメッシュ単位データは、図３に示すように、ヘッダ、道路管理レコード１〜Ｂ１群から構成される道路管理リストＬｂ１、リンクレコード１〜Ｂ２群から構成されるリンクリストＬｂ２、座標レコード１〜Ｂ３群から構成される座標リストＬｂ３、上位リンクＩＤ１〜Ｂ４群から構成される上位リンクＩＤリストＬｂ４、及び、複合リンク規制レコード１〜Ｂ５群から構成される複合リンクリストＬｂ５等から構成される。
＜１．２．１  ヘッダ＞
道路データのメッシュ単位データに格納されるヘッダは、固定長で表現されるものであり、道路管理レコード数Ｂ１、リンクレコード数Ｂ２、座標レコード数Ｂ３、上位リンクＩＤ数Ｂ４、及び、複合リンク規制レコード数Ｂ５等の情報が格納されてなる。
＜１．２．２  道路管理レコード＞
道路管理レコードは、レコード毎に固定長で表現されるものであり、リンク数等の情報が格納されてなる。道路管理レコードは、同一ストリートを構成する一連のリンク列を管理するレコードであり、上記リンク数は、この道路管理レコードで管理するリンク列を構成するリンクの数を表すものである。即ち、道路データのメッシュ単位データの作成に際しては、当該メッシュ内のリンク群を同一ストリートのリンク列毎にまとめるような思想でグループ化する。そして、道路データのメッシュ単位データには、このグループしたリンク列毎の上記道路管理レコードを格納する。詳細を省略するが、この道路管理レコードには、上記リンク数以外に、対応するストリートの特徴を表すその他のデータが格納される。
＜１．２．３  リンクレコード＞
リンクレコードは、リンクに関する主たる属性情報がレコード毎に固定長で表現されてなるものであり、道路データのメッシュ単位データには、メッシュ内の各リンクに対応するリンクレコードが格納される。
【００３０】
図４（ａ）は、リンクレコードの構成を表す図である。同図に示すように、リンクレコードには、リンク種別、リンク長、及び、車線数の情報が格納される。また、このリンクレコードには、自リンクの始点から終点までの座標点数の情報が格納される。
【００３１】
本実施例の地図データにおいては、リンクの両端にノード（図５（ａ）に示す黒丸）が設定され、その間に、形状補間点（図５（ａ）に示す白丸）が設定される。形状補間点は、リンク両端の間で湾曲するリンクの形状を表現するために必要な点である。各点の座標は、後述する座標レコードにより記述されるが、リンクレコードに記述される座標点数は、当該リンクに設定されたこれらノード及び形状補間点の数に一致する。
【００３２】
また、リンクレコードには、スピードカテゴリ及び制限速度情報有無フラグが記述される。スピードカテゴリは、このリンクに設定された制限速度（法定速度）のカテゴリを表すものである。即ち、制限速度をグループ分けしたときに、対応するリンクの制限速度が、どのグループの速度領域に属するものであるのかを表す。
【００３３】
一方、制限速度情報有無フラグは、自リンクに対応する制限速度管理レコード（図９参照）が拡張データとしての制限速度データに存在するか否かを表すものである。制限速度管理レコードは、スピードカテゴリより詳細な制限速度、即ち、該当リンクの制限速度（法定速度）の詳細な値を示す。
【００３４】
また、本実施例のリンクレコードには、自リンクにおいて車両が通行可能な方向を表すリンク方向属性が記述される。具体的に、リンク方向属性は、リンクの始点から終点方向（順方向）にのみ通行可能であることを示す「順方向通行可能」、リンクの終点から始点方向（逆方向）にのみ通行可能であることを示す「逆方向通行可能」、上記順方向及び逆方向の両方向に通行可能であることを示す「両方向通行可能」、並びに、通行不可能であることを示す「通行禁止」のいずれかの値を採る。
【００３５】
この他、リンクレコードには、自リンクの始点から他リンクへの通行規制（右左折規制等）を表す複合リンク規制レコードが複合リンク規制リストＬｂ５内に存在するか否かを表す始点側複合リンク規制情報有無フラグ、自リンクの終点から他リンクへの通行規制を表す複合リンク規制レコードが複合リンク規制リストＬｂ５に存在するか否かを表す終点側複合リンク規制情報有無フラグ、自リンクの始点側ノードに信号機が存在するか否かを表すフラグ、リンク終点側ノードに信号機が存在するか否かを表すフラグ、上位レベルのメッシュ単位データにリンク始点側ノードに対応するノードが存在するか否かを表すフラグ、及び、上位レベルのメッシュ単位データにリンク終点側ノードに対応するノードが存在するか否かを表すフラグが格納される。
【００３６】
更に、このリンクレコードには、自リンクの始点に接続される他リンクの情報及び自リンクの終点に接続される他リンクの情報が格納される。具体的に、リンクレコードに記述される「自リンクの始点に接続される他リンクの情報」は、始点接続リンク番号及び始点接続属性からなる。始点接続リンク番号は、自リンクの始点に接続される他リンクのリンク番号のことである。但し、本実施例では、リンクリストＬｂ２先頭からのリンクレコードの配列番号のことを「リンク番号」と表現する。即ち、リンクリストＬｂ２先頭からｎ番目のリンクレコードは、リンク番号ｎのリンクレコードである。また、以下で表現するリンク番号ｎのリンクとは、リンクリストＬｂ２先頭からｎ番目のリンクレコードに対応するリンクのことをいう。本実施例の地図データでは、従来の地図データのように、リンクに対して絶対的なリンクＩＤを付与しないので、従来のリンクＩＤに代えて、このリンク番号を用いる。
【００３７】
ちなみに、上記リンクレコードには、上記始点接続リンク番号として、リンク始点に接続される他リンク（複数リンク）の内、所定の規則に従う単一のリンクのリンク番号のみを格納する。この点を含むリンク接続関係の記述方法の詳細については、後述する。
【００３８】
また、リンクレコードにおいて、上記始点接続リンク番号と共に記述される始点接続属性は、自リンクが、その始点において、始点接続リンク番号に対応するリンクの始点及び終点のいずれに接続されるかを表すものである。即ち、始点接続属性は、「始点」又は「終点」のいずれかを表す値を採る。例えば、始点接続属性が「始点」を表す場合には、始点接続リンク番号に対応するリンクの「始点」が、この始点接続リンク番号が記述されたリンクレコードに対応するリンクの始点に接続されることを表す。ちなみに、リンクの始点に接続される同一メッシュ内の他リンクがない場合には、始点接続リンク番号として自リンクのリンク番号が記述され、始点属性情報として「始点」を表す値が記述される。リンクの始点に接続される同一メッシュ内の他リンクがない場合としては、行き止まりである場合や、リンクの始点が隣接メッシュとの境界に位置するノード（後述する境界ノード）であって隣接メッシュのリンクにのみに接続される場合などが挙げられる。本実施例では、メッシュ単位データを閉じたデータとするため、隣接メッシュとの境界に位置する境界ノードを挟むリンクの接続関係については、自己のメッシュ内のリンク接続関係についてのみを記述する。
【００３９】
同様に、リンクレコードに記述される「自リンクの終点に接続される他リンクの情報」は、終点接続リンク番号及び終点接続属性からなる。終点接続リンク番号は、自リンクの終点に接続される他リンクのリンク番号のことである。リンクレコードには、終点接続リンク番号として、リンク終点に接続される他リンク（複数リンク）の内、所定の規則に従う単一のリンクのリンク番号のみが格納される。また、上記終点接続リンク番号と共に記述される終点接続属性は、自リンクが、その終点において、終点接続リンク番号に対応するリンクの始点及び終点のいずれに接続されるかを表すものである。リンクの終点に接続される同一メッシュ内の他リンクがない場合には、終点接続リンク番号として自リンクのリンク番号が記述され、終点属性情報として「終点」を表す値が記述される。
【００４０】
リンクレコードには、上述したリンクに関する属性情報が主として格納される。
＜１．２．４  座標レコード＞
道路データのメッシュ単位データにおいて、座標レコード１〜Ｂ３群からなる座標リストＬｂ３は、リンクリストＬｂ２に登録された各リンクに設定されたノード及び形状補間点の座標（緯度・経度）が、ノード及び形状補間点毎に記述されてなるものである。即ち、各座標レコード１〜Ｂ３は、対応するノード又は形状補間点の座標を表す。
【００４１】
図４（ｂ）は、この座標レコードの構成を表す図である。座標レコードは、固定長で表現され、座標種別、Ｘ座標（経度方向の座標）、Ｙ座標（緯度方向の座標）の情報を有する。座標種別は、対応する点が、境界ノード、境界ノードを除くノード、ダミーノード及び形状補間点のいずれに該当するか否かを表す情報である。
【００４２】
この他、座標レコードには、境界ノードが接続する隣接メッシュの識別情報が格納される。この情報は、座標種別が「境界ノード」である座標レコードのみ、有効な値を示し、他の座標レコードには、空値が記述される。境界ノードは、上述したように隣接メッシュとの境界に位置するノードのことを示すが、「境界ノードが接続する隣接メッシュの識別情報」は、境界ノードが、このメッシュ単位データに対応するメッシュの四辺及び四角のいずれの位置に存在するかを表す情報で記述される。ちなみにメッシュは、図１下段に示すように矩形である。
＜１．２．５  データ配列＞
ここで、道路管理リストＬｂ１における道路管理レコード１〜Ｂ１の配列、リンクリストＬｂ２におけるリンクレコード１〜Ｂ２の配列、座標リストＬｂ３における座標レコード１〜Ｂ３の配列について図５を用いて説明する。
【００４３】
上述したように道路管理レコードは、リンク列を管理するものであり、リンクレコードは、リンクの主たる属性情報を有するものであり、座標レコードは、リンクに設定された各点（ノード及び形状補間点）の座標情報を有するものである。即ち、座標レコードの夫々は、リンクレコードに関連付けられるべきデータであり、リンクレコードは、道路管理レコードに関連付けられるべきデータである。
【００４４】
本実施例では、このような道路管理リストＬｂ１、リンクリストＬｂ２、及び、座標リストＬｂ３間の各レコードの関連付けをリスト内の配列順序を揃えることで実現している。図５（ｂ）は、図５（ａ）に示すストリート、リンク、ノード及び形状補間点の関係にある地図に対して構成する道路管理リストＬｂ１及びリンクリストＬｂ２及び座標リストＬｂ３の関係を表す図である。
【００４５】
本実施例では、図５（ｂ）に示すように、道路管理リストＬｂ１における配列番号１番の道路管理レコード１に対応するリンク列のリンクレコード群を、リンクリストＬｂ２において先頭から配置し、道路管理リストＬｂ１における配列番号２番の道路管理レコード２に対応するリンク列のリンクレコード群を、リンクリストＬｂ２において、道路管理リストＬｂ１における配列番号１番の道路管理レコード１に対応するリンク列のリンクレコード群に続けて配列することにより、道路管理リストＬｂ１とリンクリストＬｂ２との間において、ストリート（リンク列）の配列が同一順序となるように、道路管理リストＬｂ１とリンクリストＬｂ２とを作成し、ストリートに関する複数の属性を関連付けている。
【００４６】
即ち、本実施例では、このように道路管理リストＬｂ１内の道路管理レコード１〜Ｂ１の配列に対応するストリートの配列と、リンクリストＬｂ２内のリンクレコード１〜Ｂ２の配列に対応するストリートの配列とを揃える（同一順序とする）ことにより、道路管理リストＬｂ１及びリンクリストＬｂ２の各レコードを関連付けている。
【００４７】
尚、道路管理レコードにはリンク数の情報が格納されているので、単一の道路管理レコードに対して複数のリンクレコードが関連付けられる場合にも、道路管理リストＬｂ１及びリンクリストＬｂ２の先頭から順にレコードを参照／読み込むことにより、道路管理レコード１〜Ｂ１とリンクレコード１〜Ｂ２との関係を特定することができる。
【００４８】
また、リンクリストＬｂ２に登録されたリンクレコードは、リンク（道路リンク）の第一の属性（特徴）を表す属性データということができ、このリンクに対応する座標レコード群は、当該リンクの第二の属性を表す属性データということができるが、本実施例では、図５（ｂ）に示すように、リンクリストＬｂ２における配列番号１番のリンクレコード１に対応するリンクに設定された点の座標レコード群を、座標リストＬｂ３において先頭から配置し、リンクリストＬｂ２における配列番号２番のリンクレコード２に対応するリンクに設定された点の座標レコード群を、座標リストＬｂ３において、リンクリストＬｂ２におけるリンクレコード１に対応する座標レコード群に続けて配列することにより、リンクリストＬｂ２と座標リストＬｂ３との間において、リンクの配列が同一順序となるように、リンクリストＬｂ２と座標リストＬｂ３とを作成している。
【００４９】
即ち、本実施例では、このように座標リストＬｂ３内の座標レコード１〜Ｂ３の配列に対応するリンクの配列を、リンクリストＬｂ２と揃える（同一順序とする）ことにより、リンクリストＬｂ２及び座標リストＬｂ３の各レコードを関連付けている。尚、リンクレコードには座標点数の情報が格納されているので、このように単一のリンクレコードに対して複数の座標レコードが関連付けられる場合にも、リンクリストＬｂ２及び座標リストＬｂ３の先頭から順にレコードを参照／読み込むことにより、リンクレコード１〜Ｂ２と座標レコード１〜Ｂ３との関係を特定することができる。ちなみに、単一のリンクレコードに対応する座標レコード群は、座標リストＬｂ３内において、そのリンクの始点から終点への点の並び順に、配列される。また、リンク終点の座標レコードについては、隣接するリンク始点の座標レコードと同座標を示すレコードとなるため、その登録を省略することが可能である。
＜１．２．６  リンク接続関係＞
続いて、先程説明を保留したリンクの接続関係の記述方法について説明する。本実施例では、上述したように、リンクレコードには、「自リンクの始点に接続される他リンクの情報」及び「自リンクの終点に接続される他リンクの情報」として、夫々、これらの各端点（始点／終点）に接続される単一リンクに関する情報のみしか記述しない。この点は、ノードデータにより、該当ノードに接続される全てのリンクに関する情報を記述する従来の地図データとは異なる点である。
【００５０】
具体的に、本実施例では、同一ノードに接続される複数リンクの接続関係を、同一ノードに接続される各リンクのリンクレコードにおいて、時計回りに、隣接するリンクのリンク番号を、接続リンク番号（始点接続リンク番号又は終点接続リンク番号）として記述することにより、表現する。即ち、本実施例では、ノードに接続されるリンクの接続関係を、従来のようにノードデータで一括して記述するのではなく、同一ノードに接続される各リンクのリンクレコードで分散して記述する。そして、地図データを使用する際には、これらリンクレコードを、ノードを中心として時計回りに参照することにより、同一ノードに接続されたリンクを特定する。
【００５１】
図６（ａ）は、リンクの接続関係の一例と共に、接続リンク番号の記述方向を示した図である。具体的に、同図の例では、注目リンクＬ０の始点及び終点での他リンクの接続関係を、次のように記載する。図６（ｂ）は、図６（ａ）に示す注目リンクＬ０のリンクレコードに記述する始点接続リンク番号及び終点接続リンク番号を示した図である。この例では、注目リンクＬ０の始点に接続される他リンクは、リンクＬ１，Ｌ２，Ｌ３である。そして、これらリンクＬ１，Ｌ２，Ｌ３の内、注目リンクＬ０から見て時計回りに隣接するリンクは、リンクＬ１である。このため、注目リンクＬ０のリンクレコードには、始点接続リンク番号として、リンクＬ１のリンク番号を記述する。
【００５２】
また、注目リンクＬ０の終点に接続される他リンクは、リンクＲ１，Ｒ２である。そして、これらリンクＲ１，Ｒ２の内、注目リンクＬ０から見て時計回りに隣接するリンクは、リンクＲ１である。このため、注目リンクＬ０のリンクレコードには、終点接続リンク番号として、リンクＲ１のリンク番号を記述する。
【００５３】
続いて、図６（ａ）の例に対して、リンクＬ１，Ｌ２，Ｌ３のリンクレコードに記述する接続リンク番号を、図７（ａ）に示す。
図７（ａ）に示すように、注目リンクＬ０の始点を中心とした時計回り方向において、リンクＬ１に隣接するリンクは、リンクＬ２である。このためリンクＬ１のリンクレコードには、注目リンクＬ０の始点と一致するリンクＬ１の始点又は終点の接続リンク番号（始点接続リンク番号又は終点接続リンク番号）として、リンクＬ２のリンク番号を記述する。また、時計回り方向において、リンクＬ２に隣接するリンクは、リンクＬ３である。このためリンクＬ２のリンクレコードには、注目リンクＬ０の始点と一致するリンクＬ２の始点又は終点の接続リンク番号として、リンクＬ３のリンク番号を記述する。また、時計回り方向において、リンクＬ３に隣接するリンクは、注目リンクＬ０である。このためリンクＬ３のリンクレコードには、注目リンクＬ０の始点と一致するリンクＬ３の始点又は終点の接続リンク番号として、注目リンクＬ０のリンク番号を記述する。
【００５４】
本実施例では、このような複数リンクレコードでの記述によって、注目リンクＬ０始点のリンク接続関係を表現する。
また、図７（ｂ）は、図６（ａ）の例に対して、リンクＲ１，Ｒ２のリンクレコードに記述する接続リンク番号を示すものである。図７（ｂ）に示すように、注目リンクＬ０の終点を中心とした時計回り方向において、リンクＲ１に隣接するリンクは、リンクＲ２である。このためリンクＲ１のリンクレコードには、注目リンクＬ０の終点と一致するリンクＲ１の始点又は終点の接続リンク番号（始点接続リンク番号又は終点接続リンク番号）として、リンクＲ２のリンク番号を記述する。また、時計回り方向において、リンクＲ２に隣接するリンクは、注目リンクＬ０である。このためリンクＲ２のリンクレコードには、注目リンクＬ０の終点と一致するリンクＲ２の始点又は終点の接続リンク番号として、注目リンクＬ０のリンク番号を記述する。
【００５５】
本実施例では、このような複数リンクレコードでの記述によって、注目リンクＬ０終点のリンク接続関係を表現する。
以上、リンク接続関係の表現方法について説明したが、本実施例によれば、このようなリンク接続関係の表現方法を採用しているので、地図データにリンク接続関係を表すノードデータを設ける必要がなく、地図データをコンパクトすることが可能である。
＜１．２．７  上位リンクＩＤ＞
続いて、上位リンクＩＤ（図３参照）について説明する。道路データの各メッシュ単位データに格納される上位リンクＩＤは、対応するリンクの上位レベルリンクのリンク番号を示すものである。この上位リンクＩＤは、固定長で表現される。但し、ここでいう上位レベルリンクのリンク番号は、上位レベルのメッシュ単位データにおけるリンクリストＬｂ２先頭からの配列番号である。この上位リンクＩＤは、当該レベルのリンクと、上位レベルのリンクとの対応関係を定義付ける目的で用いられる。
【００５６】
詳述すると、上位リンクＩＤリストＬｂ４は、リンクリストＬｂ２にリンクレコードが登録されたリンク毎に、リンクリストＬｂ２におけるリンクの配列と同配列で、対応するリンクの上位リンクＩＤ１〜Ｂ４が配列されてなる。このような配列の一致により、上位リンクＩＤリストＬｂ４内の上位リンクＩＤ１〜Ｂ４と、リンクリストＬｂ２内のリンクレコード１〜Ｂ２とは関連付けられている。
＜１．２．８  複合リンク規制レコード＞
続いて、複合リンク規制レコードについて、図８を用いて説明する。道路データのメッシュ単位データに格納される複合リンク規制レコードは、可変長で表現される。この複合リンク規制レコードは、対象リンク番号、脱出ポイント属性、脱出リンク数Ｃ、及び、脱出リンクデータ１〜Ｃの一群からなる脱出リンクリストＬｃが記述されてなる。複合リンク規制レコードは、これらの情報によって、対象リンク番号に対応するリンクの始点又は終点から通行（脱出）可能なリンクである脱出リンクを表す。
【００５７】
具体的に、脱出リンク数Ｃは、脱出リンクリストＬｃに登録された脱出リンクデータの数を表すものであり、脱出リンクリストＬｃを構成する各脱出リンクデータ１〜Ｃは、対象リンク番号に対応するリンクの始点（又は終点）から通行（脱出）可能な脱出リンクの識別情報が記述されてなる。また、脱出ポイント属性は、「始点」又は「終点」のいずれかに対応する値を採る。脱出ポイント属性が「始点」である場合、当該複合リンク規制レコードの脱出リンクリストＬｃは、対象リンク番号に対応するリンクの始点からの脱出リンクを表す。また、脱出ポイント属性が「終点」である場合、当該複合リンク規制レコードの脱出リンクリストＬｃは、対象リンク番号に対応するリンクの終点からの脱出リンクを表す。
【００５８】
また、各脱出リンクデータには、脱出リンクの識別情報として、脱出リンクが存在するメッシュの番号であるメッシュ番号、及び、そのリンクに対応するリンク番号（脱出リンク番号）が記述される。即ち、脱出リンクデータは、メッシュ番号及び脱出リンク番号により、脱出リンクの識別情報が記述された構成にされている。
【００５９】
尚、本実施例の地図データを使用する場合には、この脱出リンクリストＬｃと、上記リンクレコード群で特定されるリンクの接続関係とから、交差点での右折／左折等の通行規制を特定する。
【００６０】
例えば、リンクＬ０の始点において、リンクＬ１，Ｌ２，Ｌ３が接続されている交差点を例に挙げる（図８下段参照）。この場合、リンクＬ０の始点に対応する交差点に対して何ら規制がなければ（但しＵターンを考慮しないものとする）、対象リンク番号がＬ０であり脱出ポイント属性が「始点」である複合リンク規制レコードの脱出リンクリストＬｃには、脱出リンクＬ１，Ｌ２，Ｌ３を示す合計３つの脱出リンクデータが記述される。これに対して、リンクＬ０からリンクＬ３への右折通行が禁止されている場合、脱出リンクリストＬｃには、脱出リンクデータとして、リンクＬ１を脱出リンクとする脱出リンクデータ及びリンクＬ２を脱出リンクとする脱出リンクデータのみが記述されリンクＬ３についての脱出リンクデータが記述されない。このようなリンク接続関係と脱出リンクとの差分情報から、本実施例では、交差点での右折禁止／左折禁止等を特定する。
＜１．３  制限速度データのメッシュ単位データ＞
上述した拡張データとしての制限速度データは、各リンクの制限速度を表すものである。図９（ａ）に示すように、この制限速度データのメッシュ単位データは、ヘッダ及び制限速度管理レコード１〜Ｅ群から構成される制限速度管理リストＬｅを有する。図９（ａ）は、制限速度データのメッシュ単位データの構成を表す図である。
＜１．３．１  ヘッダ＞
制限速度データのメッシュ単位データに格納されるヘッダは、固定長で表現されるものであり、制限速度管理レコード数Ｅ等が記述されてなるものである。
＜１．３．２  制限速度管理レコード＞
制限速度管理レコードは、レコード毎に固定長で表現されるものであり、対応するリンクの順方向制限速度及び逆方向制限速度が記述された構成にされている。尚、制限速度がない（無制限である）リンクに対しては、無制限であることを示す値が、順方向制限速度や逆方向制限速度として記述される。また、対応するリンクが一方通行である場合には、順方向制限速度及び逆方向制限速度の内、通行不可能な方向に対応する制限速度が、データがないことを示す空値で記述される。
【００６１】
また、制限速度管理レコードの夫々は、一つのリンクに対して一つのみ設けられて、制限速度管理リストＬｅに登録される。具体的に、制限速度管理リストＬｅは、図９（ｂ）に示すように、対応するメッシュのリンクリストＬｂ２にリンクレコードが登録されたリンク毎に、当該リンクリストＬｂ２におけるリンクの配列と同配列で、対応するリンクの制限速度管理レコード１〜Ｅが配列されてなる。図９（ｂ）は、リンクレコード１〜Ｂ２の配列と、制限速度管理レコード１〜Ｅの配列との関係を表す図である。
【００６２】
但し、制限速度情報有無フラグが「情報無し」との値に設定されたリンクレコードに対応する制限速度管理レコードは、制限速度管理リストＬｅ内に登録されない。即ち、制限速度管理リストＬｅには、リンクリストＬｂ２において配列番号の若いリンクレコードに対応したリンクの順に、当該リンクの制限速度管理レコードを配列し、リンクレコードに対応する制限速度管理レコードがない場合には、そのリンクレコードに対応する制限速度管理レコードを格納すべき位置に、配列番号が次のリンクレコードに対応する制限速度管理レコードを詰めて配置する。
【００６３】
本実施例の地図データにおいては、このようにして、道路データにおける各リンクレコード１〜Ｂ２と、制限速度データにおける各制限速度管理レコード１〜Ｅとを関連付ける。
＜１．４  地図データのまとめ＞
以上に地図データの構成について説明したが、本実施例によれば、従来技術と同様に、道路をリンク単位で表現して、これらリンクの接続関係を表す情報により道路ネットワークを表現した地図データを作成する。
【００６４】
但し、地図データを作成するに当っては、地図構成部品に関する複数種類のデータを、地図構成部品毎ではなく、データの種類毎に分けてまとめて、データリスト化する。例えば、リンクに関する複数種類の属性データ（リンクレコード、座標レコード、制限速度管理レコード等）を、リンク毎ではなく、これら属性データの種類毎に分けてまとめて、データリスト化する（リンクリストＬｂ２、座標リストＬｂ３、制限速度管理リストＬｅ等）。従って、本実施例によれば、地図データの内容変更を簡単に行うことができる。
【００６５】
これについて言及すれば、従来技術では、部品毎に複数種類のデータがまとめられた地図データ構造となっているため、特定種類の属性データを更新するだけの地図データの更新であっても、地図データ全体を更新する必要があったが、本実施例によれば、特定種類の属性データを更新するだけの地図データの更新であれば、当該特定種類の属性データ群からなるデータリストを、旧バージョンのデータリストと入れ替えるだけで、地図データの更新が完了する。従って、本実施例の地図データ構造によれば、地図データの更新が容易である。
【００６６】
また、この地図データ構造によれば、地図データを構成する各種データリスト（特には拡張データ）の組合せを変更することで、地図データの内容変更を容易に実現できるため、複数種類の地図データを容易に作成することができる。例えば、地図データから制限速度データを削除したり、地図データに制限速度データを追加したりすることにより、制限速度の詳細情報を持たせた地図データ及び制限速度の詳細情報を外した地図データを容易に作成することができる。その結果として、顧客のニーズに合わせた様々な種類の地図データを販売することができる。また、地図データを構成するデータリストを個別に販売して、ユーザによりカスタマイズ可能に地図データを販売することもできる。
【００６７】
また、上記データリスト化によっては、各データリストにおける同一リンクに関する属性データ（レコード）を関連付ける必要があるが、本実施例では、これをデータリスト内での配列によって実現するようにし、関連付けのためにリンクＩＤ等を用いなくても済むようにした。従って、本実施例によれば、地図データをコンパクトにすることができる。
【００６８】
更に言えば、各レコードを極力固定長化することによって、レコード先頭にリンクＩＤはおろかデータ境界を表すコードを記述しなくとも済むようにすると共に、参照元レコードにおいて参照先レコードのアドレスを記載しなくても済むようにした。従って、この点によっても、本実施例の地図データは、データのコンパクト化に有利に働く。また、固定長化すれば、読込対象のレコードの格納位置を、レコード長とデータリスト先頭からのレコードの配列番号で特定することができるので、各レコードへのアクセス性が向上する。
【００６９】
更に言及すれば、従来の地図データには、ノード毎に、リンクの接続関係を表すノードデータを設けていたが、本実施例によれば、リンクの接続関係に関する情報を分散して、リンクレコードに保持するようにした。よって、地図データには、ノードデータを設ける必要がなく、従来のようにリンクデータとノードデータとで座標情報などの重複情報を保持しなくて済む。従って、本実施例によれば、この点でも地図データをコンパクトにすることができる。
【００７０】
特に、本実施例では、リンクの属性を表す属性データとしてのリンクレコードに、リンクの接続関係を表す情報として、始点接続リンク番号及び終点接続リンク番号を一つのみ記述するようにし、複数リンクが接続されているノード（リンクの始点又は終点）においても、単一の接続相手の識別情報（リンク番号）しか記述しないようにした。
【００７１】
即ち、同一ノードに接続される各リンクのリンクレコードにおいては、図６及び図７に示す手法で接続リンク番号を記述することによって、効率的に、リンクの接続関係を表す情報を、同一ノードに接続される複数リンクのリンクレコードで保持するようにした。従って、本実施例によれば、地図データのデータ量を効率的に抑えることができる。
【００７２】
また、本実施例の地図データ構造によれば、接続リンク番号を順々に参照することで、同一ノードに接続されるリンクのリンクレコードを一通り簡単に参照することができ、同一ノードにおけるリンクの接続関係を効率的に特定できるようにした。従って、本実施例のように、リンクの接続関係に関する情報を分散して、リンクレコードに保持するようにしても、ナビゲーション装置におけるリンクの接続関係特定のための処理負荷の増大を極力抑えることができる。
【００７３】
また、本実施例の地図データ構造によれば、接続関係の記述に、リンクリストＬｂ２でのリンク配列番号を用いるようにしたので、各リンクに対するリンクＩＤの設定も不要である。従って、この点でも、本実施例の地図データ構造によれば、データのコンパクト化に非常に有利に働く。
＜２  ナビゲーション装置の構成＞
続いては、上記構成の地図データを搭載するナビゲーション装置１０の構成について説明する。
＜２．１  基本構成＞
図１０に示すナビゲーション装置１０は、位置検出装置１１、地図データ入力装置１３、操作デバイス１５、音声出力デバイス１６、表示デバイス１７、及び、制御回路１９を備えた構成にされている。
【００７４】
位置検出装置１１は、ナビゲーション装置１０を搭載した車両の現在位置を検出するためのものであり、例えば、周知のジャイロスコープ、距離センサ及びＧＰＳ受信機等を有した構成にされる。
【００７５】
一方、地図データ入力装置１３は、上述の地図データが格納された記録媒体（具体的にはハードディスクやＤＶＤ）を有するものであり、この記録媒体に格納された地図データを制御回路１９に入力可能に構成されたものである。尚、地図データ入力装置１３は、地図データを記憶保持するハードディスク装置に加えてＤＶＤドライブを備えた構成にすることができる。このように地図データ入力装置１３を構成すれば、ナビゲーション装置１０は、ＤＶＤメディアを通じてオプション販売される地図データの追加データを、ハードディスク装置にインストール可能な構成にすることができる。また、ナビゲーション装置１０には、地図データを配布するセンタと無線通信可能な通信機（図示せず）を設けることができ、ナビゲーション装置１０は、この通信機を通じて受信したデータに基づいて、地図データ入力装置１３が保持する地図データを更新する構成にされてもよい。
【００７６】
操作デバイス１５は、ユーザからの指示を制御回路１９に入力するためのものであり、表示デバイス１７に配置されたタッチパネルや、ナビゲーション装置１０の本体表面やリモートコントローラに設けられた操作スイッチ群等により構成される。この操作デバイス１５を通じて、ユーザは、地図の縮尺変更やスクロール等の操作や目的地設定などナビゲーション装置１０のあらゆる操作を行うことが可能である。
【００７７】
また、音声出力デバイス１６は、スピーカ等から構成され、制御回路１９からの信号を受けてユーザへの案内音声等を出力するものである。この他、表示デバイス１７は、フルカラー表示が可能なものであり、この表示デバイス１７には、例えば、位置検出装置１１により検出された車両の現在位置を表す現在位置マークや誘導経路等が、地図データ入力装置１３より入力された地図データに基づく地図画像に重ねて表示される。
【００７８】
また、制御回路１９は、周知のマイクロコンピュータと同様の構成にされており、内部にＣＰＵ１９ａ、ＲＯＭ１９ｂ、ＲＡＭ１９ｃ、Ｉ／Ｏ及びこれらの構成を接続するバスラインなどを備える。そして、ＣＰＵ１９ａは、ＲＯＭ１９ｂに記憶されているプログラムに従って、位置検出装置１１、地図データ入力装置１３、及び、操作デバイス１５から入力された信号（情報）に基づく処理を実行する。
【００７９】
具体的に、制御回路１９は、ＣＰＵ１９ａによるプログラムの実行により、地図データ入力装置１３から地図データをメッシュ毎に読み込んで、ＲＡＭ１９ｃに展開する。そして、この展開後地図データに基づいて地図表示や経路探索・経路案内等の処理を実行する。
＜２．２  地図データの読込＞
続いては、制御回路１９が、地図データ入力装置１３から地図データを読み込んでＲＡＭ１９ｃに展開する処理について説明する。制御回路１９は、地図データ入力装置１３から地図データをメッシュ毎に読み込んでＲＡＭ１９ｃに展開するが、この際には、図１１に示すように、地図データ入力装置１３が記憶するオリジナルの地図データを、地図データを参照するアプリケーションプログラム（以下、単に「アプリ」と称する。）毎の専用地図データＭＡ１〜ＭＡ３に変換する。そして、これらアプリ毎の専用地図データＭＡ１〜ＭＡ３を、ＲＡＭ１９ｃに展開後地図データとして格納する。
【００８０】
具体的には、表示デバイス１７に地図画像を描画する処理を司るアプリケーションプログラムである描画アプリ、操作デバイス１５を通じてユーザから指定された目的地までの誘導経路を探索する処理を司るアプリケーションプログラムである経路探索アプリ、及び、走行道路周辺の道路案内（誘導経路の案内や、走行位置前方の交通規制の案内や、レーン案内等）を行うアプリケーションプログラムである経路案内アプリの夫々について、該当アプリに必要な情報を、地図データ入力装置１３が記憶するオリジナルの地図データから抽出・整理した専用地図データＭＡ１〜ＭＡ３を、ＲＡＭ１９ｃに格納する。
【００８１】
以下では、描画アプリにより参照される上記専用地図データを、描画用地図データＭＡ１と表現し、経路探索アプリにより参照される上記専用地図データを、経路探索用地図データＭＡ３と表現し、経路案内アプリにより参照される上記専用地図データを、経路案内用地図データＭＡ２と表現する。
【００８２】
ちなみに、上記記載からも理解できるように、制御回路１９は、地図データを地図データ入力装置１３から読み込んで展開するプログラムの他に、ＲＯＭ１９ｂに記録された描画アプリ、経路探索アプリ、及び、経路案内アプリを実行して、ナビゲーション装置１０としての機能を実現する。
【００８３】
さて、上記描画用地図データＭＡ１は、地図画像の表示デバイス１７への表示に必要十分な情報がまとめられた地図データとして作成され、経路探索用地図データＭＡ３は、目的地までの誘導経路探索に必要十分な情報がまとめられた地図データとして作成され、経路案内用地図データＭＡ２は、表示デバイス１７及び音声出力デバイス１６を通じた道路案内に必要十分な情報がまとめられた地図データとして作成される。
【００８４】
詳述すると、これらアプリ毎及びメッシュ毎の専用地図データＭＡ１〜ＭＡ３は、夫々、対応するメッシュ内のリンクに関する情報がまとめられたリンクテーブルと、これらリンクの接続点であるノードに関する情報がまとめられたノードテーブルと、を主な構成要素とする。
【００８５】
リンクテーブルＴＢＬ１１〜ＴＢＬ１３は、単一リンクに関する複数種類のデータがまとめて記述された「リンクデータ」を、メッシュ内のリンク毎に有するものであり、ノードテーブルＴＢＬ２１〜ＴＢＬ２３は、単一ノードを介して接続されるリンクの識別情報がまとめて記述された「ノードデータ」を、メッシュ内のノード毎に有するものである。
【００８６】
即ち、地図データ入力装置１３が記憶する地図データを、ＲＡＭ１９ｃに展開する処理では、リンク単体に関する情報を、リンク毎にまとめたリンクテーブルＴＢＬ１１〜ＴＢＬ１３を作成すると共に、地図データにおいてリンク毎に分散して記述されるリンクの接続関係やノードの情報（信号機の有無等）を、ノード毎にまとめたノードテーブルＴＢＬ２１〜ＴＢＬ２３を作成する。
＜２．２．１  リンクテーブル及びノードテーブルの詳細構成＞
図１２（ａ）は、経路探索用地図データＭＡ３を構成するリンクテーブルＴＢＬ１３（上段）及びノードテーブルＴＢＬ２３（下段）のデータ構造の一例を表す図である。
【００８７】
本実施例のリンクテーブルＴＢＬ１１〜ＴＢＬ１３は、リンク番号及び該当リンクの詳細属性が記述されたリンク詳細属性情報を構成要素とするリンクデータをメッシュ内のリンク毎に有する。具体的に、図１２（ａ）に示す例によれば、経路探索用のリンクテーブルＴＢＬ１３には、リンク番号に続いて、リンク種別、リンク長、制限速度、及び、一方通行規制の情報等がリンク詳細属性情報として記述されたリンクデータが登録される。
【００８８】
尚、リンクデータに記述されるリンク番号は、リンクリストＬｂ２に登録された該当リンクの配列番号を示し、リンクデータに記述されるリンク種別は、対応するリンクレコードに記されたリンク種別を起源（出所）とする。同様に、リンクデータに記述されるリンク長は、対応するリンクレコードに記されたリンク長を起源とする。
【００８９】
この他、リンクデータに記述される一方通行規制の情報は、対応するリンクレコードに記されたリンク方向属性を起源とする。更に、リンクデータに記述される制限速度は、対応するリンクレコードに記述されたスピードカテゴリ、又は、対応するリンクの制限速度管理レコードが示す順方向制限速度及び逆方向制限速度を起源とする。リンクデータには、上記制限速度として、対応するリンクの制限速度管理レコードが示す順方向制限速度及び逆方向制限速度が、この制限速度が適用される車線の向きの情報と共に記述されるが、対応するリンクの制限速度管理レコードがない場合には、スピードカテゴリが示す速度領域に基づく値（例えば速度領域の代表値）が記述される。
【００９０】
また、ノードテーブルＴＢＬ２１〜ＴＢＬ２３は、ノード番号、該当ノードでのリンク接続数、このノードに接続されるリンクについてのリンク番号が配列されたリンク接続情報、このノードの座標を表すノード座標情報、及び、座標及び接続関係以外についてのノードの詳細属性が記述されたノード詳細属性情報を構成要素とするノードデータを、メッシュ内のノード毎に有する。
【００９１】
具体的に、ノード番号は、各ノードテーブルＴＢＬ２１〜ＴＢＬ２３への登録順に、連続した番号としてノードデータに付されるものである。また、ノードデータに記述されるリンク接続数は、リンク接続情報としてリンク番号が登録されたリンクの数に一致する。また、リンク接続情報は、上述したように、該当ノードに接続される各リンクのリンク番号の一群からなるが、ここで使用されるリンク番号は、当然のことながら、該当リンクのリンクリストＬｂ２における配列番号に一致する。
【００９２】
また、図１２（ａ）に示す例によれば、経路探索用のノードテーブルＴＢＬ２３には、上記ノード詳細属性情報として、経路探索に必要な右左折規制情報が記述される。右左折規制情報としては、具体的に、当該ノードに進入するリンクであって、当該ノードでの右折及び左折のいずれか一方が禁止されたリンクのリンク番号と禁止内容（右折禁止／左折禁止／右左折の両者禁止のいずれか）とが記述される。
【００９３】
ちなみに、ノードデータを構成するリンク接続情報は、当該ノードに接続される各リンクのリンクレコードが示す始点接続リンク番号及び終点接続リンク番号及び始点接続属性及び終点接続属性（図４（ａ）参照）を起源（出所）とする情報であり、ノード座標情報は、該当ノードの座標レコード（図４（ｂ）参照）を起源とし、右左折規制情報は、該当ノードに接続された各リンクの複合リンク規制レコード（図８参照）を、起源とする。
【００９４】
また、図１２（ｂ）は、経路案内用地図データＭＡ２を構成するリンクテーブルＴＢＬ１２（上段）及びノードテーブルＴＢＬ２２（下段）のデータ構造を表す図である。図１２（ｂ）に示すように、経路案内用のリンクテーブルＴＢＬ１２に登録されるリンクデータは、上記リンク詳細属性情報として、リンク種別及び車線数の情報を有する。尚、このリンク詳細属性情報として記述される車線数は、対応するリンクレコードが示す車線数を起源とする。また、経路案内用のノードテーブルＴＢＬ２２に登録されるノードデータは、上記ノード詳細属性情報として、前方に信号機があることを案内するための信号機情報を有する。尚、この信号機情報は、対応するノードでの信号機の有無を表すものであり、ノードに接続されるリンク群の各リンクレコードが示す始点側信号機有無フラグ及び終点側信号機有無フラグを起源とする。
【００９５】
また、図示を省略するが、描画用地図データＭＡ１のリンクテーブルＴＢＬ１１としては、例えば、上記リンク詳細属性情報として、リンク種別の情報のみを有した構成のリンクテーブルを挙げることができる。更に、描画用地図データＭＡ１のノードテーブルＴＢＬ２１としては、ノードテーブルＴＢＬ２２と同一構成のノードテーブルを挙げることができる。
＜２．２．２  テーブル作成処理＞
続いて、制御回路１９が、地図データ入力装置１３の地図データからメッシュ毎及びアプリ毎の上記ノードテーブルＴＢＬ２１〜ＴＢＬ２３及びリンクテーブルＴＢＬ１１〜ＴＢＬ１３を作成する際に実行するテーブル作成処理について、図１３を用いて説明する。図１３は、制御回路１９が実行するテーブル作成処理を表すフローチャートである。制御回路１９は、地図データを読み込む際、メッシュ毎に、このテーブル作成処理を実行して、対応するメッシュのリンクテーブル及びノードテーブルであって、アプリ毎のリンクテーブルＴＢＬ１１〜ＴＢＬ１３及びノードテーブルＴＢＬ２１〜ＴＢＬ２３を作成する。
【００９６】
このテーブル作成処理を開始すると、制御回路１９は、まず、テーブル作成を宣言して、内容が空のテーブルであって、対応するメッシュのアプリ毎のリンクテーブルＴＢＬ１１〜ＴＢＬ１３及びノードテーブルＴＢＬ２１〜ＴＢＬ２３をＲＡＭ１９ｃ上に作成する（Ｓ１００）。また、ノードテーブルＴＢＬ２１〜ＴＢＬ２３に登録するノードデータ毎に、１から始まる連続したノード番号を付すため、ノード番号ｖを１に初期化する（Ｓ１１０）。また、注目リンク番号ｗを１に初期化する（Ｓ１２０）。このテーブル作成処理では、リンクリストＬｂ２先頭からリンクレコードを順に参照するが、注目リンク番号ｗは、参照するリンクレコードのリンクリストＬｂ２先頭からの配列番号を表す。以下では、注目リンク番号ｗのリンクレコードに対応するリンクを、注目リンクとも表現する。
【００９７】
Ｓ１２０での処理を終えると、制御回路１９は、変数Ｎに、今回地図データ読込対象とするメッシュのリンクレコード数Ｂ２を設定する（Ｓ１３０）。このリンクレコード数Ｂ２の設定は、道路データのメッシュ単位データに記述されたリンクレコード数Ｂ２に基づいて行うことができる。以下、変数Ｎに設定された値を、単に値Ｎと表現する。
【００９８】
また、この処理を終えると、制御回路１９は、注目リンク番号ｗが値Ｎより大きいか否かを判断し（Ｓ１４０）、値Ｎ以下である場合には（Ｓ１４０でＮｏ）、図１４に示すリンク始点側データ登録処理（Ｓ１５０）、及び、リンク終点側データ登録処理（Ｓ１６０）を実行する。
【００９９】
詳細については後述するが、リンク始点側データ登録処理（Ｓ１５０）では、注目リンクの始点に位置するノードについてのアプリ毎のノードデータを作成して、これを上記アプリ毎のノードテーブルＴＢＬ２１〜ＴＢＬ２３に登録すると共に、当該ノードに接続された各リンクについてのアプリ毎のリンクデータを作成して、これを上記アプリ毎のリンクテーブルＴＢＬ１１〜ＴＢＬ１３に登録する。
【０１００】
また、リンク終点側データ登録処理（Ｓ１６０）では、注目リンクの終点に位置するノードについてのアプリ毎のノードデータを作成して、これを上記アプリ毎のノードテーブルＴＢＬ２１〜ＴＢＬ２３に登録すると共に、当該ノードに接続された各リンクについてのアプリ毎のリンクデータを作成して、これを上記アプリ毎のリンクテーブルＴＢＬ１１〜ＴＢＬ１３に登録する。
【０１０１】
このようにして、リンク始点側データ登録処理（Ｓ１５０）及びリンク終点側データ登録処理（Ｓ１６０）を終了すると、制御回路１９は、注目リンク番号ｗを１加算するように更新した後（Ｓ１７０）、ループ先頭であるＳ１４０に戻って、上記更新後の注目リンク番号ｗに基づいたＳ１４０以降の処理を実行する。そして、注目リンク番号ｗが値Ｎを超えると（Ｓ１４０でＹｅｓ）、当該テーブル作成処理を終了する。
【０１０２】
続いて、Ｓ１５０で実行するリンク始点側データ登録処理について図１４を用いて詳述する。リンク始点側データ登録処理を開始すると、制御回路１９は、ノードデータ登録対象のノードとして、注目リンクの始点に位置するノードを設定する（Ｓ２１０）。ここでは、具体的に、ＲＡＭ１９ｃのノード座標情報作成エリアに、注目リンクの始点に位置するノード座標を登録することにより、ノードデータ登録対象のノードとして、注目リンクの始点に位置するノードを設定する。ちなみに、ノード座標については、注目リンクのリンクレコードに関連付けられた座標レコード群の先頭レコードに記述された座標情報から特定することができる。
【０１０３】
また、この処理を終えると、Ｓ２１０でノードデータ登録対象に設定されたノードについてのノードデータが既にアプリ毎の各ノードテーブルＴＢＬ２１〜ＴＢＬ２３に登録されているか否かを判断する（Ｓ２２０）。そして、該当ノードデータが登録されていると判断すると（Ｓ２２０でＹｅｓ）、Ｓ３３０に移行し、該当ノードデータが登録されていないと判断すると（Ｓ２２０でＮｏ）、Ｓ２３０に移行する。
【０１０４】
Ｓ２３０に移行すると、制御回路１９は、参照リンク番号Ｚｒを、注目リンク番号ｗに設定することにより、リンクレコードを参照するリンクである参照リンクとして、注目リンクを設定する。尚、本実施例の地図データ構造によれば、ノードにおけるリンクの接続関係を把握するには、同一ノードに接続されたリンクに対応するリンクレコードを時計回りに巡回するように参照する必要がある。Ｓ２３０の手順は、このように同一ノードに接続されたリンクに対応するリンクレコードを巡回する際に、最初に参照するリンクレコードを設定するための動作である。
【０１０５】
Ｓ２３０での処理を終えると、制御回路１９は、Ｓ２４０に移行し、ＲＡＭ１９ｃのリンク接続情報作成エリアに、参照リンク番号Ｚｒを追加登録する。これによって、ノードデータ登録対象のノードに接続される当該リンクのリンク番号をリンク接続情報として登録する。
【０１０６】
また、この処理を終えると、参照リンク番号Ｚｒに対応する参照リンクについてのアプリ毎のリンクデータが既にリンクテーブルＴＢＬ１１〜ＴＢＬ１３に登録されているか否かを判断し（Ｓ２５０）、リンクテーブルＴＢＬ１１〜ＴＢＬ１３に登録されていない場合には（Ｓ２５０でＮｏ）、Ｓ２６０の処理を実行した後にＳ２７０に移行し、リンクテーブルＴＢＬ１１〜ＴＢＬ１３に登録されている場合には（Ｓ２５０でＹｅｓ）、Ｓ２６０の処理をスキップして、Ｓ２７０に移行する。
【０１０７】
具体的に、Ｓ２６０では、リンクリストＬｂ２において参照リンク番号Ｚｒに対応するリンク番号のリンクレコードを参照し、このリンクレコード及びこれに関連付けられたレコード（制限速度管理レコード等）に基づいて、参照リンクについてのアプリ毎のリンクデータを作成する。即ち、参照リンクのリンクレコード等に含まれる情報を整理して、経路探索用のリンクテーブルＴＢＬ１３に登録するリンクデータ、経路案内用のリンクテーブルＴＢＬ１２に登録するリンクデータ、及び、描画用のリンクテーブルＴＢＬ１１に登録するリンクデータを作成する。各リンクテーブルＴＢＬ１１〜ＴＢＬ１３に対応するリンクデータの例は、図１２等で説明した通りである。そして、これらアプリ毎のリンクデータの夫々を、対応するリンクテーブルＴＢＬ１１〜ＴＢＬ１３に登録する。
【０１０８】
また、Ｓ２７０では、参照リンク番号Ｚｒを更新する。具体的には、現時点での参照リンク番号Ｚｒに対応する参照リンクのリンクレコードに記述された始点接続リンク番号Ｑｓ又は終点接続リンク番号Ｑｅのいずれか一方を、新たな参照リンク番号Ｚｒに設定することで、参照リンク番号Ｚｒを更新する（Ｚｒ←Ｑｓ又はＺｒ←Ｑｅ）。詳述すれば、現参照リンクの始点が、Ｓ２１０で設定したノードデータ登録対象のノードに一致する場合には、参照リンク番号Ｚｒを、現参照リンクのリンクレコードに記述された始点接続リンク番号Ｑｓに更新する。一方、現参照リンクの終点が、Ｓ２１０で設定したノードデータ登録対象のノードに一致する場合には、参照リンク番号Ｚｒを、現参照リンクのリンクレコードに記述された終点接続リンク番号Ｑｅに更新する。尚、リンク始点側データ登録処理における初回のＳ２７０では、Ｓ２１０で注目リンクの始点に位置するノードを、ノードデータ登録対象のノードに設定する関係上、参照リンク番号Ｚｒを、その時点での参照リンクである注目リンクのリンクレコードに記述された始点接続リンク番号Ｑｓに更新する。尚、参照リンクの始点及び終点のいずれがノードデータ登録対象のノードであるか否かは、各点の座標を比較することにより、特定することができる。
【０１０９】
また、Ｓ２７０での処理を終えると、制御回路１９は、Ｓ２８０に移行し、参照リンク番号Ｚｒが注目リンク番号ｗに一致するか否かを判断する。尚、ここで、参照リンク番号Ｚｒが注目リンク番号ｗに一致する場合には、ノードに接続されたリンクに対応するリンクレコードの参照が時計回りに一通り完了（一巡）したことを意味する。
【０１１０】
そして、参照リンク番号Ｚｒが注目リンク番号ｗに一致しないと判断すると（Ｓ２８０でＮｏ）、処理ループ先頭であるＳ２４０に戻って、更新後の参照リンク番号Ｚｒに対応した参照リンクについてのＳ２４０〜Ｓ２８０の処理を実行する。
【０１１１】
このような繰返し動作により、リンク接続情報作成エリアには、ノードデータ登録対象のノードに接続される各リンクのリンク番号が順に登録され、最終的に、当該ノードについてのリンク接続情報が完成する。また、Ｓ２８０で、参照リンク番号Ｚｒが注目リンク番号に一致すると判断すると（Ｓ２８０でＹｅｓ）、制御回路１９は、Ｓ２９０に移行し、リンク接続情報作成エリアで完成した上記リンク接続情報に基づいて、経路探索用のノードデータを作成し、これを経路探索用のノードテーブルＴＢＬ２３に登録する。
【０１１２】
具体的には、リンク接続情報で特定される当該ノードでのリンク接続関係に基づき、経路探索用のノードデータに格納する上記ノード詳細属性情報を、地図データ入力装置１３が記憶する地図データを参照して作成する。そして、現時点で設定されているノード番号ｖ、リンク接続情報に登録されているリンク数、リンク接続情報作成エリアで完成した上記リンク接続情報、ノード座標情報作成エリアに登録されたノード座標情報、及び、上記作成した経路探索用のノード詳細属性情報を格納したノードデータを作成し、これを経路探索用のノードテーブルＴＢＬ２３に登録する。
【０１１３】
同様に、Ｓ２９０に続くＳ３００では、経路案内用のノードデータを、経路案内用のノードテーブルＴＢＬ２２に登録する。具体的には、リンク接続情報で特定される当該ノードでのリンク接続関係に基づき、経路案内用のノードデータに格納する上記ノード詳細属性情報を作成し、このノード詳細属性情報を、経路探索用のノードデータに格納したノード詳細属性情報に代えて格納してなるノードデータを、経路案内用のノードデータとして作成する。そして、これを、経路案内用のノードテーブルＴＢＬ２２に登録する。
【０１１４】
同様に、Ｓ３００に続くＳ３１０では、描画用のノードデータを、描画用のノードテーブルＴＢＬ２１に登録する。具体的には、リンク接続情報で特定される当該ノードでのリンク接続関係に基づき、描画用のノードデータに格納する上記ノード詳細属性情報を作成し、このノード詳細属性情報を、経路探索用のノードデータに格納したノード詳細属性情報に代えて格納してなるデータを、描画用のノードデータとして作成する。そして、これを、描画用のノードテーブルＴＢＬ２１に登録する。
【０１１５】
また、このようにしてアプリ毎のノードテーブルＴＢＬ２１〜ＴＢＬ２３に、該当ノードについてのノードデータを登録した後には、Ｓ３２０に移行して、ノード番号ｖを１カウントアップする。その後、Ｓ３３０に移行する。
【０１１６】
また、Ｓ３３０では、今般のノードデータの作成に用いたＲＡＭ１９ｃ上の情報作成エリア（リンク属性情報作成エリア及びノード座標情報作成エリア）をクリアして、当該リンク始点側データ登録処理を終了する。以上が、リンク始点側データ登録処理の内容である。
【０１１７】
ちなみに、Ｓ１６０で実行されるリンク終点側データ登録処理は、ノードデータ登録対象ノードを、注目リンクの終点に位置するノードに設定する以外は、リンク始点側データ登録処理の同内容の手順を実行するものである。本実施例では、このような内容のリンク終点側データ登録処理をＳ１６０で実行して、注目リンクの終点に位置するノードのノードデータについても、同様にノードテーブルＴＢＬ２１〜ＴＢＬ２３に登録する。
【０１１８】
以上、ナビゲーション装置１０について説明したが、上述の地図データ構造によれば、地図データをコンパクトすることができる一方で、リンクの接続関係が複数のリンクレコードに分散して表現されるので、ナビゲーション装置側で、リンクの接続関係を、都度地図データを参照して特定するのでは、リンクの接続関係を特定するのに従来装置よりも負荷が掛かってしまう。このため、本実施例では、従来と同様のノードデータを、地図データから作成して、ノードテーブルＴＢＬ２１〜ＴＢＬ２３に登録することで、リンクの接続関係を特定するための処理負荷を、低減するようにした。従って、このナビゲーション装置１０によれば、地図データのコンパクト化により生じる不利益を解消することができる。
【０１１９】
また、このナビゲーション装置１０のように、地図データからノードテーブルＴＢＬ２１〜ＴＢＬ２３を作成すれば、末端のアプリケーションプログラムにおいて、従来の地図データと同様の方式で、地図データにアクセスし、必要な処理を実行することができる。よって、このナビゲーション装置１０によれば、上記地図データ構造の採用により、従前使用されてきたアプリケーションプログラムの大幅な修正が強いられるのを回避することができる。
【０１２０】
また、アプリ毎のリンクテーブルＴＢＬ１１〜ＴＢＬ１３及びノードテーブルＴＢＬ２１〜ＴＢＬ２３を作成することで、データアクセス性が向上し、アプリによる処理性能が向上するといった利点もある。
＜３  最後に＞
以上、本発明の実施例について説明したが、本発明は、上記実施例に限定されるものではなく、種々の態様を採ることができる。例えば、上述した構成の地図データ構造は、車両に搭載されるナビゲーション装置用の地図データ以外の地図データにも適用することができる。具体的には、携帯電話等の携帯端末にインストールされる地図データにも適用することが可能である。
【０１２１】
また、上記実施例では、アプリ毎にリンクテーブルＴＢＬ１１〜ＴＢＬ１３及びノードテーブルＴＢＬ２１〜ＴＢＬ２３を作成するようにしたが、複数アプリに共通するリンクテーブル及びノードテーブルを作成するようにしてもよい。この場合には、リンクテーブル及びノードテーブルの記憶領域を低減することができる。
【０１２２】
この他、上記実施例では、リンクレコードにおいて、このリンクに接続される他のリンクであって、時計回り方向に隣接するリンクのリンク番号を、始点接続リンク番号又は終点接続リンク番号として記述するようにしたが、時計回り方向ではなく、反時計回り方向に隣接するリンクのリンク番号を、始点接続リンク番号又は終点接続リンク番号として記述するようにしてもよい。
【０１２３】
その他、接続リンク番号（始点接続リンク番号又は終点接続リンク番号）には、同一地点に接続されるリンクのリンク番号を、その番号の小さい順又は大きい順に記述して、リンクの接続関係を表現することもできる。例えば、図６（ａ）に示す例において、リンクＬ０，Ｌ１，Ｌ２，Ｌ３のリンク番号の大小関係が、リンクＬ２＞リンクＬ１＞リンクＬ３＞リンクＬ０であるとすると、リンクＬ０のリンクレコードにおける接続リンク番号に、リンクＬ３のリンク番号を記述し、リンクＬ３のリンクレコードにおける接続リンク番号に、リンクＬ１のリンク番号を記述し、リンクＬ１のリンクレコードにおける接続リンク番号に、リンクＬ２のリンク番号を記述し、リンクＬ２の接続リンク番号に、リンクＬ０のリンク番号を記述するといった具合である。
【０１２４】
このような接続リンク番号の記載によっても、同一ノードに接続される複数リンクのリンクレコードの全てを、接続リンク番号に基づいて、一巡するように効率的に参照して、ノードでのリンクの接続関係を把握することができる。特に、リンク番号の小さい順に接続リンク番号を記載すれば、リンクリストＬｂ２の先頭から順に、同一地点に接続されたリンクについてのリンクレコードにアクセスすることができるので、データアクセス性が向上する。
【０１２５】
この他、上記実施例では、地図データ入力装置１３が記録媒体に記憶する地図データを、上記リンクテーブルＴＢＬ１１〜ＴＢＬ１３及びノードテーブルＴＢＬ２１〜ＴＢＬ２３に変換して、ワークメモリ（作業メモリ）であるＲＡＭ１９ｃに書き込むが、地図データの読込については、一旦、地図データ入力装置１３が記録媒体に記憶する地図データを、ＲＡＭ１９ｃにコピーし、このコピーした地図データに基づいて、上記リンクテーブルＴＢＬ１１〜ＴＢＬ１３及びノードテーブルＴＢＬ２１〜ＴＢＬ２３を作成し、これをアプリが参照するＲＡＭ１９ｃの別領域に書き込むようにしてもよい。
【符号の説明】
【０１２６】
１０…ナビゲーション装置、１１…位置検出装置、１３…地図データ入力装置、１５…操作デバイス、１６…音声出力デバイス、１７…表示デバイス、１９…制御回路、１９ａ…ＣＰＵ、１９ｂ…ＲＯＭ、１９ｃ…ＲＡＭ、Ｌａ１…道路管理リスト、Ｌｂ２…リンクリスト、Ｌｂ３…座標リスト、Ｌｂ４…上位リンクＩＤリスト、Ｌｂ５…複合リンク規制リスト、Ｌｅ…制限速度管理リスト、ＭＡ１…描画用地図データ、ＭＡ２…経路案内用地図データ、ＭＡ３…経路探索用地図データ、ＴＢＬ１１〜ＴＢＬ１３…リンクテーブル、ＴＢＬ２１〜ＴＢＬ２３…ノードテーブル
【図２】
0005440218.tif 000002
【図３】
0005440218.tif 000003
【図４】
0005440218.tif 000004
【図５】
0005440218.tif 000005
【図６】
0005440218.tif 000006
【図７】
0005440218.tif 000007
【図８】
0005440218.tif 000008
【図９】
0005440218.tif 000009
【図１０】
0005440218.tif 000010
【図１１】
0005440218.tif 000011
【図１２】
0005440218.tif 000012
【図１３】
0005440218.tif 000013
【図１４】
0005440218.tif 000014
【図１】
0005440218.tif 000015