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