地図データ、地図データ更新装置、地図データ更新プログラム及び地図データの更新方法
【課題】地図データ更新時におけるリンク情報の管理を容易とする。
【解決手段】この地図データでは、各リンクが、始点ノード、同一リンク列における次リンク、及び、上位リンクの各参照情報を有している。また、各リンクはリスト状に記憶されており、リンクの追加や削除の際にもリンクリストにおける位置を変更しないようにすることで、各リンクをリンクリストにおける位置で直接参照できるようにしている。このため、例えば、リンク１，２，４，５からなるリンク列のうち、リンク２及びリンク５がそれぞれ２つに分割された場合にも、リンク２，５をそれぞれ２つに分割する新たなノード６，７を始点ノードとするリンク７，８をリンクリストの末尾に追加するとともに、リンク２の次リンクをリンク３からリンク７に、リンク５の次リンクをリンク６からリンク８に変更すればよい。
【解決手段】この地図データでは、各リンクが、始点ノード、同一リンク列における次リンク、及び、上位リンクの各参照情報を有している。また、各リンクはリスト状に記憶されており、リンクの追加や削除の際にもリンクリストにおける位置を変更しないようにすることで、各リンクをリンクリストにおける位置で直接参照できるようにしている。このため、例えば、リンク１，２，４，５からなるリンク列のうち、リンク２及びリンク５がそれぞれ２つに分割された場合にも、リンク２，５をそれぞれ２つに分割する新たなノード６，７を始点ノードとするリンク７，８をリンクリストの末尾に追加するとともに、リンク２の次リンクをリンク３からリンク７に、リンク５の次リンクをリンク６からリンク８に変更すればよい。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、道路がリンク単位で表され、同一属性の連続する複数のリンクがリンク列として規定された地図データに関するものである。
【背景技術】
【０００２】
従来、ナビゲーション装置用の地図データのフォーマットとして、日本ではＫＩＷＩ／Ａ方式が一般的に用いられている。この方式では、地図上の道路がリンク単位で表され、各リンクは始点ノード及び終点ノードの参照情報を有している。また、この方式に基づく地図データは経路探索の高速化などの目的で複数段階に階層化されており、最下位層の各リンクには識別情報としてのリンクＩＤが付与されている。特に、同一属性の道路の描画の効率化やデータ圧縮などの目的で、属性が同一であって連続するリンクのグループはリンク列として規定されており、リンク列を構成するリンクには連続した値のリンクＩＤが付与されている。これにより、リンク列を上位階層で表現する際には、そのリンク列の始端側及び終端側の各リンクのリンクＩＤに基づき、その間のリンクを特定することができる。
【０００３】
ところで、こうした地図データは、実際の道路の変化等に伴い部分的に更新する必要が生じるが、更新に伴い既存のリンクを複数に分割したり複数のリンクを１つに統合したりする場合には、リンクＩＤの連番性を保つために大規模なリンクＩＤの振り直しを行う必要があり、更新処理の負荷が大きくなってしまうという問題があった。
【０００４】
この問題を解決するため、地図データの最下位層の各リンクに対して固有のリンクＩＤ番号範囲（例えば１０００〜１０９９）を設定し、同一リンク列のリンクには、連続したリンクＩＤ番号範囲（例えば１０００〜１０９９と１１００〜１１９９）を設定する方法が提案されている（特許文献１参照）。このようにすることで、例えば既存のリンクを分割する必要が生じた場合にも、１０００〜１０４９と１０５０〜１０９９とに分割するといったようにリンクＩＤ番号範囲で対応することが可能となり、リンクＩＤ番号の連続性を保つことができる。
【特許文献１】特許第３７２５０２２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、前述した特許文献１に記載の方法では、リンクの分割数がリンクＩＤ番号範囲で対応可能な限界を超えた場合には、後方のリンクＩＤを振り直す必要が生じるため、根本的には問題は解決されていない。ここで、リンクＩＤ番号範囲を十分に大きくしておくことも考えられるが、データ量が大幅に増加してしまうというデメリットがある。しかも、この方法では、リンクＩＤ範囲をどのような割合で分割するかといった複雑なＩＤ管理が必要になるという問題もある。
【０００６】
本発明は、こうした問題にかんがみてなされたものであり、地図データ更新時におけるリンク情報の管理を容易とすることを目的としている。
【課題を解決するための手段】
【０００７】
上記目的を達成するためになされた本発明の請求項１に記載の地図データは、道路がリンク単位で表され、同一属性の連続する複数のリンクがリンク列として規定されたものである。そして、この地図データでは、各リンクが、当該リンクの属するリンク列における次リンクの参照情報を有する。
【０００８】
このような地図データによれば、リンクの有する次リンクの参照情報をたどることでリンク列を特定することができるため、従来のように同一リンク列に属するリンクに連続したリンクＩＤを付与する必要がない。つまり、リンクＩＤを連続にしなければならないという制約がない。このため、地図データの更新に伴い既存のリンクが複数に分割される場合にも、既存のリンクの識別情報を変更することなく更新を行うことができる。この結果、地図データ更新時のデータ変更量を少なくすることができ、リンク情報の管理を容易とすることができる。
【０００９】
また、このような地図データによれば、既存のリンクの分割や統合が生じた場合にも既存のリンクの識別情報については変更する必要がないため、従来の地図データで用いられていたリンクＩＤという識別情報自体を不要とすることができる。具体的には、例えばリンクをリスト状に管理し、リストにおける既存のリンクの位置を変化させないように情報の更新を行うようにすれば、各リンクをリストにおける位置で特定することができる。このようにすることで、リンクＩＤが不要となる分、データ量を削減することができる。
【００１０】
ここで、リストにおける既存リンクの位置を変化させない情報の更新方法としては、例えば、新規リンクをリストの末尾に追加する、既存リンクをリストから削除する際に空白情報として残す（リストにおける順番を詰めない）といった方法が挙げられる。なお、新規リストの追加位置は、リストの末尾に限定されるものではなく、例えば、既存リンクが削除された空白情報部分であってもよく、また、全く異なる記憶領域であってもよい。
【００１１】
特に、このようなリンクの管理方法によれば、従来のようにリンクＩＤをリストから検索する場合に比べ、リストにおける位置を直接参照する分、処理の高速化を図ることができる。
【００１２】
ところで、地図データが複数段階に階層化されている場合の階層間のリンク対応については、例えば、下位階層のリンク列と上位階層のリンクとの対応関係を別途記憶しておくことによって対応付けることが可能であるが、例えば請求項２に記載のように、下位階層の各リンクがその上位階層のリンクの参照情報を有していてもよい。このようにすれば、別途対応関係を記憶することなく、地図データの階層間の対応関係を特定することができる。
【００１３】
一方、本発明の地図データでは、各リンクが、リンク列における次リンクの参照情報を有するが、リンク列における最終リンクについては、次リンクが存在しないため、他のリンクとは異なる情報（例えば終端のリンクであることの情報）を含めることで対応する必要がある。この点、最終リンクについても他のリンクと同様のデータ構成とするためには、例えば請求項３のように、リンク列における最終リンクの次リンクとして、実際には存在しない仮想リンクを設定するとよい。このようにすれば、最終リンクについても他のリンクと同様のデータ構成とすることができる。
【００１４】
次に、請求項４に記載の地図データ更新装置は、請求項１から請求項３までのいずれか１項に記載の地図データのリンクをリスト状に管理し、リストにおける更新対象リンクの位置情報を指定した更新データに基づきリストを更新するものである。そして、この地図データ更新装置では、更新データの指定する位置情報がリストに存在しない場合には、リスト拡張手段が、その位置情報が存在するようにリストを拡張し、情報更新手段が、更新データの指定する位置情報のリンクの情報を更新データに基づき更新する。
【００１５】
このような地図データ更新装置によれば、リストにおける既存のリンクの位置を変化させないように情報の更新を行うことができる。この結果、各リンクをリストにおける位置で特定することができ、従来の地図データで用いられていたリンクＩＤという識別情報自体を不要とすることでデータ量を削減することができる。しかも、従来のようにリンクＩＤをリストから検索する場合に比べ、リストにおける位置を直接参照する分、処理の高速化を図ることができる。
【００１６】
また、請求項５に記載の地図データ更新プログラムは、請求項１から請求項３までのいずれか１項に記載の地図データのリンクをリスト状に管理し、リストにおける更新対象リンクの位置情報を指定した更新データに基づきリストを更新する地図データ更新装置としてコンピュータを機能させるためのものである。具体的には、この地図データ更新プログラムは、更新データの指定する位置情報がリストに存在しない場合には、その位置情報が存在するようにリストを拡張するリスト拡張手段と、更新データの指定する位置情報のリンクの情報を更新データに基づき更新する情報更新手段としてコンピュータを機能させる。
【００１７】
このような地図データ更新プログラムによれば、請求項４に記載の地図データ更新装置としてコンピュータを機能させることができ、これにより前述した効果を得ることができる。
【００１８】
また、請求項６に記載の更新方法は、請求項１から請求項３までのいずれか１項に記載の地図データの更新方法であって、リンクをリスト状に管理し、リストにおける既存のリンクの位置を変化させないように情報の更新を行うことを特徴としている。
【００１９】
このような更新方法によれば、各リンクをリストにおける位置で特定することができ、従来の地図データで用いられていたリンクＩＤという識別情報自体を不要とすることでデータ量を削減することができる。しかも、従来のようにリンクＩＤをリストから検索する場合に比べ、リストにおける位置を直接参照する分、処理の高速化を図ることができる。
【発明を実施するための最良の形態】
【００２０】
以下、本発明が適用された実施形態について、図面を用いて説明する。
［１．地図データの概要］
まず、実施形態の地図データの概要について説明する。
【００２１】
図１は、本実施形態の地図データの基本構造を説明するための説明図である。
本実施形態の地図データは、リンク列を連結リストとして表現する点を特徴としている。具体的には、各リンクが、開始点（始点ノード）の参照情報と、当該リンクの属するリンク列における次リンク（リンク列において一定方向に連続する順番が次のリンク）の参照情報とを持っており、これにより、当該リンクの２端点が特定される。すなわち、従来（ＫＩＷＩ／Ａ）方式の地図データでは、各リンクが、始点ノード及び終点ノードの参照情報を持っているが、本実施形態の地図データでは、終点ノードの参照情報の代わりに次リンクの参照情報を持っており、この情報から終点ノードを特定可能となっている。
【００２２】
例えば図１における左側に示すように、リンクＬ１，Ｌ２，Ｌ３，Ｌ４からなるリンク列において、リンクＬ１は、開始点としてＮ１、次リンクとしてＬ２の参照情報を持ち、リンクＬ２は、開始点としてＮ２、次リンクとしてＬ３の参照情報を持ち、リンクＬ３は、開始点としてＮ３、次リンクとしてＬ４の参照情報を持つ。なお、リンク列における最終リンクであるリンクＬ４には、次リンクが存在しないため、この例では、次リンクとして最終ノード（終点ノード）の参照情報が格納されている。
【００２３】
また、本実施形態の地図データは、更新の際に、既存のリンクの識別情報を変更することなく整合性を維持するようになっている。すなわち、例えば図１における右側に示すように、既存のリンクＬ２が新たなノードＮ６によって２つに分割され、これによりノードＮ６を始点ノードとする新たなリンクＬ５が発生した場合には、新たなリンクＬ５の情報をリンク情報（リンクリスト）の末尾に追加し、既存のリンクＬ２の次リンクをＬ５に変更する。このように、既存リンクの識別情報を変更することなく更新を行うことができる。
【００２４】
なお、図１に例示した地図データでは、上位階層との対応関係を表すリンク列情報として、リンク列を構成する先頭のリンクの参照情報のみを持つようにすることで、データ容量を削減している。
【００２５】
図２は、本実施形態の地図データのデータベースの論理設計を説明するための説明図である。
本実施形態の地図データは、リンクテーブルと、ノードテーブルと、付加的情報テーブルと、形状点情報と、辞書テーブル（種別コード等）とを備える。
【００２６】
リンクテーブルには、リンクＩＤ（主キー）、始点ノードのノードＩＤ（外部キー）、次リンクのリンクＩＤ（外部キー）、上位リンクのリンクＩＤ（外部キー）、辞書テーブル参照ＩＤ、リンク長といったデータが格納される。なお、図２の例では、各リンクが上位リンクの参照情報を有しているため、階層間のリンクの対応関係を別途記憶することなく特定することができる。
【００２７】
また、ノードテーブルには、ノードＩＤ（主キー）、正規化座標Ｘ，Ｙ、隣接ノードのノードＩＤ（外部キー）といったデータが格納される。その他、付加的情報テーブルには、リンクＩＤ、付加的情報といったデータ、形状点情報には、リンクＩＤ（外部キー）、形状序列番号、正規化座標Ｘ，Ｙといったデータ、辞書テーブルには、ＩＤ、種別コードといったデータがそれぞれ格納される。
【００２８】
図３（ａ）は、交差点の論理設計（ノード）を説明するための説明図であり、図３（ｂ）は、道路の論理設計（リンクの設計）を説明するための説明図である。
ノードとは、周知のように、基本的には交差点のことである。なお、従来は、経路用のデータと描画用のデータとを別オブジェクトとしていたが、本実施形態の地図データでは単一オブジェクト化している。
【００２９】
一方、リンクとは、周知のように、道路のことである。各リンクは、始点ノードの参照情報を有し、複数のリンクによってリンク列を構成し、リンク列中の次リンクと結合する。また、この例では、リンク列における最終リンクの次リンクとして、実際には存在しない仮想リンクが設定されている。
【００３０】
このように、本実施形態の地図データでは、従来（ＫＩＷＩ／Ａ）方式の地図データにおいてリンクＩＤを昇順連番にすることで規定していたリンク列を、連結リストとして表現する。このような連結リスト型リンク列のメリットとしては、リンクＩＤの連番性から解放されることが挙げられる。また、始点ノード及び次リンクの２つの情報でリンク間の接続性と連続性を表現することから、重複情報の無い論理設計が可能となることもメリットとして挙げられる。
【００３１】
すなわち、図４に示すように、従来方式の地図データでは、各リンクは、２端点のノードの参照情報を有しているが、リンクの連続性を表現するためには、更に追加の情報（例えば一筆書き情報）が必要であった。
【００３２】
また、このような従来方式の地図データでは、リンク列を構成するリンクのリンクＩＤが連番であることから、リンクの連続性やレベル間の関連を、「リンクＩＤ＝開始側連続番号＋差分番号」の形で表現している。
【００３３】
例えば、図５における左側に示すように、レベル０（最下位層）のリンクＬ２，Ｌ３からなるレベル１のリンクは、開始側連続番号（Ｌ２）と、始端側のリンク（Ｌ２）と終端側のリンク（Ｌ３）とのリンクＩＤの差分とから、Ｌ２−１と表現することができる。また、レベル０のリンクＬ１のみからなるレベル１のリンクは、差分が０であることから、Ｌ１−０と表現される。同様に、レベル０のＬ１〜Ｌ３からなるレベル２のリンクは、Ｌ１−２と表現することができる。このように、リンクＩＤの表現によって、リンク列を構成するリンクを特定することができる。
【００３４】
しかしながら、このようなデータ構造では、地図データの差分更新を行う際に、整合性（序列）維持のため、最下位リンクの変更が、後方のリンクや上位レベルのリンクに対してまで連鎖的な変更を引き起こすという問題があった。例えば図５における右側に示すように、レベル０の既存のリンクＬ１が２つに分割された場合、その後方のリンクのリンクＩＤだけでなく、上位レベルのリンクのリンクＩＤについても更新する必要が生じる。
【００３５】
これに対し、図６に示すように、本実施形態の地図データの差分更新では、リンク間に明示的な参照を定義し、参照関係を直接表現することにより、変更を要する影響範囲を局所化することを可能とした。図６における左側に示す例では、レベル０のリンクＬ４は、上位リンクの参照情報として、レベル１のリンクＬ２の参照情報を有しており、同様にレベル０のリンクＬ５，Ｌ６は、上位リンクの参照情報として、それぞれレベル１のリンクＬ３の参照情報を有している。また、レベル１のリンクＬ２，Ｌ３は、上位リンクの参照情報として、それぞれレベル２のリンクＬ１の参照情報を有している。
【００３６】
このようなデータ構造によれば、従来方式の地図データのような序列維持の制約がないことから、例えば図６における右側に示すようにレベル０の既存のリンクＬ４が２つに分割された場合にも、後方のリンクや上位レベルのリンクの識別情報を変更することなく差分更新を行うことができる。
【００３７】
なお、図６では、下レイヤのリンクが上レイヤのリンクの参照情報を有し、逆に、上レイヤのリンクも下レイヤのリンクの参照情報を有しているが、実際には、例えば図７に示すように、下レイヤのリンクが上レイヤのリンクをただ一つ参照するようにすればよい。このようにすれば、上から下への参照は、参照元を集計することで算出可能であり、このように集計により算出可能な情報は重複情報となるからである。また、各リンクがそれぞれ上位リンクの情報を有している必要はなく、例えばリンク列における１つのリンク（例えば先頭のリンク）のみを上位リンクと関連付けるようにすれば、データ量を一層削減することができる。
【００３８】
［２．ナビゲーション装置の構成］
次に、このような地図データの具体的な使用例として、車両に搭載されるナビゲーション装置の実施例について説明する。
【００３９】
［２−１．全体構成］
図８は、ナビゲーション装置１０の概略構成を表すブロック図である。
このナビゲーション装置１０は、位置検出器１１、地図データ入力器１２、操作デバイス１３、表示装置１４、音声出力装置１５、制御回路１６などを備えている。
【００４０】
位置検出器１１は、当該ナビゲーション装置１０を搭載した車両の現在位置を検出するためのものであり、周知のジャイロスコープ、距離センサ及びＧＰＳ受信機を有している。
【００４１】
地図データ入力器１２は、ＤＶＤ−ＲＯＭやハードディスク装置等の記憶媒体に格納されている地図データ等を入力するための装置である。
操作デバイス１３は、ユーザからの各種指示を入力するためのものであり、表示装置１４の画面前面に配置されたタッチパネルや、ステアリングの近傍に設けられたステアリングスイッチ等が用いられ、地図の縮尺変更やスクロール等の操作や目的地設定などナビゲーション装置１０のすべての操作を行うことが可能である。
【００４２】
表示装置１４は、フルカラー表示が可能なものであり、表示装置１４の画面には位置検出器１１により検出された車両の現在位置を表す現在位置マークと、地図データ入力器１２より入力された地図データと、更に地図上に表示する誘導経路等の付加データとを重ねて表示することができる。
【００４３】
音声出力装置１５は、スピーカ、オーディオアンプなどから構成され、制御回路１６により合成された音声等を出力する。音声出力装置１５は、ナビゲーション装置１０の構成として省くこともできる。その場合、他の装置が備えている音声出力装置（例えば車両本体の音声出力装置）を利用してもよい。
【００４４】
制御回路１６は、通常のコンピュータとして構成されており、内部には周知のＣＰＵ、ＲＯＭ、ＲＡＭ、Ｉ／Ｏ及びこれらの構成を接続するバスラインなどを備えている。そして、ＣＰＵは、ＲＯＭに記憶されているプログラムに従い、位置検出器１１、地図データ入力器１２、操作デバイス１３から入力された各種情報に基づき、所定の処理（後述する地図データ更新処理等）を実行する。
【００４５】
［２−２．地図データの説明］
次に、ナビゲーション装置１０で使用される地図データについて説明する。
図９に示すように、従来（ＫＩＷＩ／Ａ）方式の地図データでは、各リンクが、始点ノード及び終点ノードの参照情報を有している。また、同一属性の連続する複数のリンクがリンク列として規定され、階層間のリンク対応は、リンク列を構成するリンクのリンクＩＤを昇順連番とする前提で、リンク列における始端側及び終端側の各リンクＩＤに基づき特定される。
【００４６】
これに対し、本実施例のナビゲーション装置１０で使用される地図データは、図１０に示すように、各リンクが、始点ノードの参照情報と、同一リンク列における次リンクの参照情報と、上位リンクの参照情報とを有している。また、リンク列における最終リンクに対する次リンクとして、実際には存在しない仮想リンクが設定されている。これにより、最終リンクにも次リンクが存在することとなり、最終リンクを他のリンクと同様のデータ構成とすることができる。なお、この地図データでは、リンクの識別情報がレベル間で独立管理されている。
【００４７】
また、各リンクはリスト状に記憶されており、リンクの追加や削除の際にもリンクリストにおける既存リンクの位置（配列添字）を変更しないようにすることで、各リンクをリンクリストにおける位置（配列添字）で特定できるようにしている。このため、各リンクは、リンクＩＤを有しておらず、その分、従来方式の地図データに比べ、データ量が削減されている。なお、リンクだけでなく、ノードについても同様にリスト状に記憶されており、ノードの追加や削除の際にもノードリストにおける既存ノードの位置（配列添字）を変更しないようにすることで、各ノードをノードリストにおける位置（配列添字）で特定できるようにしている。
【００４８】
［２−３．地図データの更新方法の概要］
次に、ナビゲーション装置１０が実行する地図データの更新方法の概要について説明する。
【００４９】
図９に示した従来（ＫＩＷＩ／Ａ）方式の地図データでは、地図データの差分更新を行う際に、既存のリンクが複数に分割されると、後方のリンクに対してまで連鎖的な変更が生じるという問題がある。例えば図１１に示すように、リンク１１，１２，１３，１４からなるリンク列のうち、既存のリンク１２及びリンク１４がそれぞれ２つに分割された場合、後方のリンクＩＤをすべて変更する必要が生じる。
【００５０】
これに対し、本実施例のナビゲーション装置１０で使用される地図データによれば、後方のリンクに対して連鎖的な変更が生じないようにすることができる。例えば図１２に示すように、リンク１，２，４，５からなるリンク列のうち、既存のリンク２及びリンク５がそれぞれ２つに分割された場合について説明する。この場合、リンク２を２つに分割する新たなノード６を始点ノードとするリンク７と、リンク５を２つに分割する新たなノード７を始点ノードとするリンク８とを、リンクリストの末尾に追加する。ここで、リンク７の始点ノードはノード６、次リンクはリンク３（仮想リンク）、上位リンクはリンク１となる。また、リンク８の始点ノードはノード７、次リンクはリンク６（仮想リンク）、上位リンクはリンク２となる。一方、既存のリンク２については、次リンクをリンク３からリンク７に変更すればよく、同様に、既存のリンク５については、次リンクをリンク６からリンク８に変更すればよい。
【００５１】
［２−４．更新データの説明］
次に、地図データの差分更新を行うための更新データについて説明する。
ナビゲーション装置１０は、更新データを外部から取得することにより、地図データを更新するための処理を実行する。ここで、更新データは、図１３（ａ）〜（ｄ）に示すように、４つの種別に大別される。なお、図面上の各四角形が、意味のあるバイナリ値の並びとなる。
【００５２】
図１３（ａ）は、リンクリストへの新規リンクの追加処理、又は、リンクリストに登録されている既存リンクに関する情報の更新処理をナビゲーション装置１０に実行させるための更新データである。この更新データは、種別データ（リンク追加／更新）と、追加処理又は更新処理を行うリンクの識別情報（リンクリストにおける位置情報）である対象リンクＮｏ．と、始点ノードＮｏ．（始点ノードの参照情報）と、次リンクＮｏ．（次リンクの参照情報）と、その他の情報（上位リンクの参照情報等）とから構成される。
【００５３】
図１３（ｂ）は、リンクリストに登録されている既存リンクの削除処理をナビゲーション装置１０に実行させるための更新データであり、種別データ（リンク削除）と、削除処理を行うリンクの識別情報である対象リンクＮｏ．とから構成される。
【００５４】
図１３（ｃ）は、ノードリストへの新規ノードの追加処理、又は、ノードリストに登録されている既存ノードに関する情報の更新処理をナビゲーション装置１０に実行させるための更新データである。この更新データは、種別データ（ノード追加／更新）と、追加処理又は更新処理を行うノードの識別情報（ノードリストにおける位置）である対象ノードＮｏ．と、その他の情報とから構成される。
【００５５】
図１３（ｄ）は、ノードリストに登録されている既存ノードの削除処理をナビゲーション装置１０に実行させるための更新データであり、種別データ（ノード削除）と、削除処理を行うノードの識別情報である対象ノードＮｏ．とから構成される。
【００５６】
なお、ナビゲーション装置１０が更新データを外部から取得する方法としては、例えば、車両外部のサーバとの間で直接通信を行うことによりダウンロードする方法、ＰＣ等の情報処理装置を介してサーバから間接的に取得する方法、更新データが記憶されたメディアから取得する方法などが考えられる。
【００５７】
［２−５．地図データ更新処理］
次に、更新データを外部から取得することによりナビゲーション装置１０の制御回路１６が実行する地図データ更新処理について、図１４のフローチャートを用いて説明する。
【００５８】
制御回路１６は、地図データ更新処理を開始すると、まずＳ１０１で、未処理の更新データが存在しないか否かを判定する。つまり、取得した更新データのすべてについて、後述するＳ１０２以降の処理を実行したか否かを判定している。
【００５９】
このＳ１０１で、未処理の更新データが存在すると判定した場合には、Ｓ１０２へ移行し、更新データを１エントリ読み込む。
続いて、Ｓ１０３では、Ｓ１０２で読み込んだ更新データのデータ種別を判定する。
【００６０】
そして、Ｓ１０３で、更新データのデータ種別が「リンク追加／更新」であると判定した場合には、Ｓ１０４へ移行し、その更新データの対象リンクＮｏ．が、現在のリンク情報数（リンクリストの項目数）よりも大きいか否かを判定する。ここで、対象リンクＮｏ．が現在のリンク情報数よりも大きい場合とは、現時点のリンクリストに存在しないリンクが対象となっていることを意味する。つまり、リンクリストの末尾に新規リンクを追加する処理を意味する。
【００６１】
このため、Ｓ１０４で、対象リンクＮｏ．が現在のリンク情報数よりも大きいと判定した場合には、Ｓ１０５へ移行し、リンク情報数が対象リンクＮｏ．数となるようにリンクリストを拡張した後、Ｓ１０６へ移行する。
【００６２】
一方、Ｓ１０４で、対象リンクＮｏ．が現在のリンク情報数よりも大きくない（換言すれば、対象リンクＮｏ．が現時点のリンクリストに存在する）と判定した場合には、Ｓ１０５をスキップしてＳ１０６へ移行する。
【００６３】
Ｓ１０６では、リンクリストにおける対象リンクＮｏ．のリンク情報を、更新データの情報（始点ノードＮｏ．、次リンクＮｏ．及び他の情報）で上書きした後、Ｓ１０１へ戻る。これにより、対象リンクＮｏ．のリンク情報として既存リンクの情報が存在していた場合にはその情報が更新されることになり、既存リンクの情報が存在していなかった場合（Ｓ１０５で新たに拡張された箇所である場合や、後述するＳ１０７の処理により無効値が格納されていた場合）には、新規リンクの情報が追加されることになる。
【００６４】
一方、Ｓ１０３で、更新データのデータ種別が「リンク削除」であると判定した場合には、Ｓ１０７へ移行し、リンクリストにおける対象リンクＮｏ．のリンク情報を無効値で埋めた後、Ｓ１０１へ戻る。つまり、対象リンクＮｏ．の既存リンクを削除する。
【００６５】
また、Ｓ１０３で、更新データのデータ種別が「ノード追加／更新」であると判定した場合には、Ｓ１０８へ移行し、その更新データの対象ノードＮｏ．が、現在のノード情報数（ノードリストの項目数）よりも大きいか否かを判定する。ここで、対象ノードＮｏ．が現在のノード情報数よりも大きい場合とは、現時点のノードリストに存在しないノードが対象となっていることを意味する。つまり、ノードリストの末尾に新規ノードを追加する処理を意味する。
【００６６】
このため、Ｓ１０８で、対象ノードＮｏ．が現在のノード情報数よりも大きいと判定した場合には、Ｓ１０９へ移行し、ノード情報数が対象ノードＮｏ．数となるようにノードリストを拡張した後、Ｓ１１０へ移行する。
【００６７】
一方、Ｓ１０８で、対象ノードＮｏ．が現在のノード情報数よりも大きくない（換言すれば、対象ノードＮｏ．が現時点のノードリストに存在する）と判定した場合には、Ｓ１０９をスキップしてＳ１１０へ移行する。
【００６８】
Ｓ１１０では、ノードリストにおける対象ノードＮｏ．のノード情報を、更新データの情報（他の情報）で上書きした後、Ｓ１０１へ戻る。これにより、対象ノードＮｏ．のノード情報として既存ノードの情報が存在していた場合にはその情報が更新されることになり、既存ノードの情報が存在していなかった場合（Ｓ１０９で新たに拡張された箇所である場合や、後述するＳ１１１の処理により無効値が格納されていた場合）には、新規ノードの情報が追加されることになる。
【００６９】
一方、Ｓ１０３で、更新データのデータ種別が「ノード削除」であると判定した場合には、Ｓ１１１へ移行し、ノードリストにおける対象ノードＮｏ．のノード情報を無効値で埋めた後、Ｓ１０１へ戻る。つまり、対象ノードＮｏ．の既存ノードを削除する。
【００７０】
その後、Ｓ１０１で、未処理の更新データが存在しないと判定すると、本地図データ更新処理を終了する。
［３．効果］
以上説明したように、本実施形態の地図データでは、各リンクが、当該リンクの属するリンク列における次リンクの参照情報を有しており、次リンクの参照情報をたどることで、リンク列という構造を明示的に持つことなくリンク列を特定することができる。このため、本実施形態の地図データでは、従来のように同一リンク列に属するリンクに連続したリンクＩＤを付与する必要がない。つまり、リンクＩＤを連続にしなければならないという制約がない。したがって、地図データの更新に伴い既存のリンクが複数に分割される場合にも、既存のリンクの識別情報を変更することなく更新を行うことができる。この結果、地図データ更新時のデータ変更量を少なくすることができ、リンク情報の管理を容易とすることができる。
【００７１】
すなわち、従来（ＫＩＷＩ／Ａ）方式の地図データでは、図１５（ａ）に示すように、既存のリンクが複数に分割されると、リンクＩＤの連番性を保つために、後方のリンクＩＤをすべて振り直す必要が生じる。
【００７２】
一方、前述した特許文献１に記載の地図データでは、図１５（ｂ）に示すように、既存リンクの分割数がそのリンクのリンクＩＤ番号範囲で対応可能な場合には、後方のリンクＩＤを振り直す必要がない。しかしながら、図１５（ｃ）に示すように、既存リンクの分割数がリンクＩＤ番号範囲で対応可能な限界を超えた場合には、後方のリンクＩＤを振り直す必要が生じるため、根本的には問題は解決されていない。ここで、リンクＩＤ番号範囲を十分に大きくしておくことも考えられるが、データ量が大幅に増加してしまうというデメリットがある。しかも、この方法では、リンクＩＤ範囲をどのような割合で分割するかといった複雑なＩＤ管理が必要となるという問題もある。
【００７３】
これに対し、本実施形態の地図データによれば、リンクＩＤを連続にしなければならないという制約自体がないため、後方のリンクＩＤを振り直すことなく地図データを更新することができ、リンク情報の管理を容易とすることができる。
【００７４】
また、各リンクが始点ノード及び次リンクの参照情報を有しており、終点ノードについては次リンクの始点ノードから特定することができるため、従来のように各リンクが始点ノード及び終点ノードの両方の参照情報を有している必要がない。
【００７５】
さらに、本実施形態では、ナビゲーション装置１０が、地図データのリンクをリスト状に管理し、このリンクリストにおける既存のリンクの位置を変化させないように情報の更新を行うようにしている。このため、各リンクをリンクリスト上の何番目の位置であるかという情報（配列添字）で参照することができ、リンクＩＤという識別情報自体を明示的に持つ必要がない分、データ量を削減することができる。しかも、リンクＩＤではなく配列添字を直接参照する分、リンクＩＤをリンクリストから検索する方式に比べ、処理の高速化を図ることができる。
【００７６】
［４．特許請求の範囲との対応］
なお、本実施形態のナビゲーション装置１０が地図データ更新装置に相当し、特に、Ｓ１０４，Ｓ１０５の処理を実行する制御回路１６がリスト拡張手段に相当し、Ｓ１０６，Ｓ１０７の処理を実行する制御回路１６が情報更新手段に相当する。
【００７７】
［５．他の形態］
以上、本発明の実施形態について説明したが、本発明は、上記実施形態に限定されることなく、種々の形態を採り得ることは言うまでもない。
【００７８】
例えば、上記実施形態では、本発明の地図データ更新装置としてナビゲーション装置１０を例示したが、これに限定されるものではなく、ナビゲーション装置用の更新地図データを生成する装置などにも適用することができる。
【図面の簡単な説明】
【００７９】
【図１】実施形態の地図データの基本構造を説明するための説明図である。
【図２】実施形態の地図データのデータベースの論理設計を説明するための説明図である。
【図３】（ａ）は交差点の論理設計（ノード）を説明するための説明図、（ｂ）は道路の論理設計（リンクの設計）を説明するための説明図である。
【図４】従来の地図データにおける各リンクの参照情報の説明図である。
【図５】従来の地図データにおけるリンク情報のデータ構造の説明図である。
【図６】実施形態の地図データにおけるリンク情報のデータ構造の説明図である。
【図７】下レイヤのリンクが上レイヤのリンクをただ一つ参照する例の説明図である。
【図８】ナビゲーション装置の概略構成を表すブロック図である。
【図９】従来（ＫＩＷＩ／Ａ）方式の地図データにおけるリンク情報の説明図である。
【図１０】実施例のナビゲーション装置で使用される地図データにおけるリンク情報の説明図である。
【図１１】従来（ＫＩＷＩ／Ａ）方式の地図データの差分更新の説明図である。
【図１２】実施例のナビゲーション装置で使用される地図データの差分更新の説明図である。
【図１３】更新データの説明図である。
【図１４】地図データ更新処理のフローチャートである。
【図１５】従来方式の地図データの問題点を説明するための説明図である。
【符号の説明】
【００８０】
１０…ナビゲーション装置、１１…位置検出器、１２…地図データ入力器、１３…操作デバイス、１４…表示装置、１５…音声出力装置、１６…制御回路
【技術分野】
【０００１】
本発明は、道路がリンク単位で表され、同一属性の連続する複数のリンクがリンク列として規定された地図データに関するものである。
【背景技術】
【０００２】
従来、ナビゲーション装置用の地図データのフォーマットとして、日本ではＫＩＷＩ／Ａ方式が一般的に用いられている。この方式では、地図上の道路がリンク単位で表され、各リンクは始点ノード及び終点ノードの参照情報を有している。また、この方式に基づく地図データは経路探索の高速化などの目的で複数段階に階層化されており、最下位層の各リンクには識別情報としてのリンクＩＤが付与されている。特に、同一属性の道路の描画の効率化やデータ圧縮などの目的で、属性が同一であって連続するリンクのグループはリンク列として規定されており、リンク列を構成するリンクには連続した値のリンクＩＤが付与されている。これにより、リンク列を上位階層で表現する際には、そのリンク列の始端側及び終端側の各リンクのリンクＩＤに基づき、その間のリンクを特定することができる。
【０００３】
ところで、こうした地図データは、実際の道路の変化等に伴い部分的に更新する必要が生じるが、更新に伴い既存のリンクを複数に分割したり複数のリンクを１つに統合したりする場合には、リンクＩＤの連番性を保つために大規模なリンクＩＤの振り直しを行う必要があり、更新処理の負荷が大きくなってしまうという問題があった。
【０００４】
この問題を解決するため、地図データの最下位層の各リンクに対して固有のリンクＩＤ番号範囲（例えば１０００〜１０９９）を設定し、同一リンク列のリンクには、連続したリンクＩＤ番号範囲（例えば１０００〜１０９９と１１００〜１１９９）を設定する方法が提案されている（特許文献１参照）。このようにすることで、例えば既存のリンクを分割する必要が生じた場合にも、１０００〜１０４９と１０５０〜１０９９とに分割するといったようにリンクＩＤ番号範囲で対応することが可能となり、リンクＩＤ番号の連続性を保つことができる。
【特許文献１】特許第３７２５０２２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、前述した特許文献１に記載の方法では、リンクの分割数がリンクＩＤ番号範囲で対応可能な限界を超えた場合には、後方のリンクＩＤを振り直す必要が生じるため、根本的には問題は解決されていない。ここで、リンクＩＤ番号範囲を十分に大きくしておくことも考えられるが、データ量が大幅に増加してしまうというデメリットがある。しかも、この方法では、リンクＩＤ範囲をどのような割合で分割するかといった複雑なＩＤ管理が必要になるという問題もある。
【０００６】
本発明は、こうした問題にかんがみてなされたものであり、地図データ更新時におけるリンク情報の管理を容易とすることを目的としている。
【課題を解決するための手段】
【０００７】
上記目的を達成するためになされた本発明の請求項１に記載の地図データは、道路がリンク単位で表され、同一属性の連続する複数のリンクがリンク列として規定されたものである。そして、この地図データでは、各リンクが、当該リンクの属するリンク列における次リンクの参照情報を有する。
【０００８】
このような地図データによれば、リンクの有する次リンクの参照情報をたどることでリンク列を特定することができるため、従来のように同一リンク列に属するリンクに連続したリンクＩＤを付与する必要がない。つまり、リンクＩＤを連続にしなければならないという制約がない。このため、地図データの更新に伴い既存のリンクが複数に分割される場合にも、既存のリンクの識別情報を変更することなく更新を行うことができる。この結果、地図データ更新時のデータ変更量を少なくすることができ、リンク情報の管理を容易とすることができる。
【０００９】
また、このような地図データによれば、既存のリンクの分割や統合が生じた場合にも既存のリンクの識別情報については変更する必要がないため、従来の地図データで用いられていたリンクＩＤという識別情報自体を不要とすることができる。具体的には、例えばリンクをリスト状に管理し、リストにおける既存のリンクの位置を変化させないように情報の更新を行うようにすれば、各リンクをリストにおける位置で特定することができる。このようにすることで、リンクＩＤが不要となる分、データ量を削減することができる。
【００１０】
ここで、リストにおける既存リンクの位置を変化させない情報の更新方法としては、例えば、新規リンクをリストの末尾に追加する、既存リンクをリストから削除する際に空白情報として残す（リストにおける順番を詰めない）といった方法が挙げられる。なお、新規リストの追加位置は、リストの末尾に限定されるものではなく、例えば、既存リンクが削除された空白情報部分であってもよく、また、全く異なる記憶領域であってもよい。
【００１１】
特に、このようなリンクの管理方法によれば、従来のようにリンクＩＤをリストから検索する場合に比べ、リストにおける位置を直接参照する分、処理の高速化を図ることができる。
【００１２】
ところで、地図データが複数段階に階層化されている場合の階層間のリンク対応については、例えば、下位階層のリンク列と上位階層のリンクとの対応関係を別途記憶しておくことによって対応付けることが可能であるが、例えば請求項２に記載のように、下位階層の各リンクがその上位階層のリンクの参照情報を有していてもよい。このようにすれば、別途対応関係を記憶することなく、地図データの階層間の対応関係を特定することができる。
【００１３】
一方、本発明の地図データでは、各リンクが、リンク列における次リンクの参照情報を有するが、リンク列における最終リンクについては、次リンクが存在しないため、他のリンクとは異なる情報（例えば終端のリンクであることの情報）を含めることで対応する必要がある。この点、最終リンクについても他のリンクと同様のデータ構成とするためには、例えば請求項３のように、リンク列における最終リンクの次リンクとして、実際には存在しない仮想リンクを設定するとよい。このようにすれば、最終リンクについても他のリンクと同様のデータ構成とすることができる。
【００１４】
次に、請求項４に記載の地図データ更新装置は、請求項１から請求項３までのいずれか１項に記載の地図データのリンクをリスト状に管理し、リストにおける更新対象リンクの位置情報を指定した更新データに基づきリストを更新するものである。そして、この地図データ更新装置では、更新データの指定する位置情報がリストに存在しない場合には、リスト拡張手段が、その位置情報が存在するようにリストを拡張し、情報更新手段が、更新データの指定する位置情報のリンクの情報を更新データに基づき更新する。
【００１５】
このような地図データ更新装置によれば、リストにおける既存のリンクの位置を変化させないように情報の更新を行うことができる。この結果、各リンクをリストにおける位置で特定することができ、従来の地図データで用いられていたリンクＩＤという識別情報自体を不要とすることでデータ量を削減することができる。しかも、従来のようにリンクＩＤをリストから検索する場合に比べ、リストにおける位置を直接参照する分、処理の高速化を図ることができる。
【００１６】
また、請求項５に記載の地図データ更新プログラムは、請求項１から請求項３までのいずれか１項に記載の地図データのリンクをリスト状に管理し、リストにおける更新対象リンクの位置情報を指定した更新データに基づきリストを更新する地図データ更新装置としてコンピュータを機能させるためのものである。具体的には、この地図データ更新プログラムは、更新データの指定する位置情報がリストに存在しない場合には、その位置情報が存在するようにリストを拡張するリスト拡張手段と、更新データの指定する位置情報のリンクの情報を更新データに基づき更新する情報更新手段としてコンピュータを機能させる。
【００１７】
このような地図データ更新プログラムによれば、請求項４に記載の地図データ更新装置としてコンピュータを機能させることができ、これにより前述した効果を得ることができる。
【００１８】
また、請求項６に記載の更新方法は、請求項１から請求項３までのいずれか１項に記載の地図データの更新方法であって、リンクをリスト状に管理し、リストにおける既存のリンクの位置を変化させないように情報の更新を行うことを特徴としている。
【００１９】
このような更新方法によれば、各リンクをリストにおける位置で特定することができ、従来の地図データで用いられていたリンクＩＤという識別情報自体を不要とすることでデータ量を削減することができる。しかも、従来のようにリンクＩＤをリストから検索する場合に比べ、リストにおける位置を直接参照する分、処理の高速化を図ることができる。
【発明を実施するための最良の形態】
【００２０】
以下、本発明が適用された実施形態について、図面を用いて説明する。
［１．地図データの概要］
まず、実施形態の地図データの概要について説明する。
【００２１】
図１は、本実施形態の地図データの基本構造を説明するための説明図である。
本実施形態の地図データは、リンク列を連結リストとして表現する点を特徴としている。具体的には、各リンクが、開始点（始点ノード）の参照情報と、当該リンクの属するリンク列における次リンク（リンク列において一定方向に連続する順番が次のリンク）の参照情報とを持っており、これにより、当該リンクの２端点が特定される。すなわち、従来（ＫＩＷＩ／Ａ）方式の地図データでは、各リンクが、始点ノード及び終点ノードの参照情報を持っているが、本実施形態の地図データでは、終点ノードの参照情報の代わりに次リンクの参照情報を持っており、この情報から終点ノードを特定可能となっている。
【００２２】
例えば図１における左側に示すように、リンクＬ１，Ｌ２，Ｌ３，Ｌ４からなるリンク列において、リンクＬ１は、開始点としてＮ１、次リンクとしてＬ２の参照情報を持ち、リンクＬ２は、開始点としてＮ２、次リンクとしてＬ３の参照情報を持ち、リンクＬ３は、開始点としてＮ３、次リンクとしてＬ４の参照情報を持つ。なお、リンク列における最終リンクであるリンクＬ４には、次リンクが存在しないため、この例では、次リンクとして最終ノード（終点ノード）の参照情報が格納されている。
【００２３】
また、本実施形態の地図データは、更新の際に、既存のリンクの識別情報を変更することなく整合性を維持するようになっている。すなわち、例えば図１における右側に示すように、既存のリンクＬ２が新たなノードＮ６によって２つに分割され、これによりノードＮ６を始点ノードとする新たなリンクＬ５が発生した場合には、新たなリンクＬ５の情報をリンク情報（リンクリスト）の末尾に追加し、既存のリンクＬ２の次リンクをＬ５に変更する。このように、既存リンクの識別情報を変更することなく更新を行うことができる。
【００２４】
なお、図１に例示した地図データでは、上位階層との対応関係を表すリンク列情報として、リンク列を構成する先頭のリンクの参照情報のみを持つようにすることで、データ容量を削減している。
【００２５】
図２は、本実施形態の地図データのデータベースの論理設計を説明するための説明図である。
本実施形態の地図データは、リンクテーブルと、ノードテーブルと、付加的情報テーブルと、形状点情報と、辞書テーブル（種別コード等）とを備える。
【００２６】
リンクテーブルには、リンクＩＤ（主キー）、始点ノードのノードＩＤ（外部キー）、次リンクのリンクＩＤ（外部キー）、上位リンクのリンクＩＤ（外部キー）、辞書テーブル参照ＩＤ、リンク長といったデータが格納される。なお、図２の例では、各リンクが上位リンクの参照情報を有しているため、階層間のリンクの対応関係を別途記憶することなく特定することができる。
【００２７】
また、ノードテーブルには、ノードＩＤ（主キー）、正規化座標Ｘ，Ｙ、隣接ノードのノードＩＤ（外部キー）といったデータが格納される。その他、付加的情報テーブルには、リンクＩＤ、付加的情報といったデータ、形状点情報には、リンクＩＤ（外部キー）、形状序列番号、正規化座標Ｘ，Ｙといったデータ、辞書テーブルには、ＩＤ、種別コードといったデータがそれぞれ格納される。
【００２８】
図３（ａ）は、交差点の論理設計（ノード）を説明するための説明図であり、図３（ｂ）は、道路の論理設計（リンクの設計）を説明するための説明図である。
ノードとは、周知のように、基本的には交差点のことである。なお、従来は、経路用のデータと描画用のデータとを別オブジェクトとしていたが、本実施形態の地図データでは単一オブジェクト化している。
【００２９】
一方、リンクとは、周知のように、道路のことである。各リンクは、始点ノードの参照情報を有し、複数のリンクによってリンク列を構成し、リンク列中の次リンクと結合する。また、この例では、リンク列における最終リンクの次リンクとして、実際には存在しない仮想リンクが設定されている。
【００３０】
このように、本実施形態の地図データでは、従来（ＫＩＷＩ／Ａ）方式の地図データにおいてリンクＩＤを昇順連番にすることで規定していたリンク列を、連結リストとして表現する。このような連結リスト型リンク列のメリットとしては、リンクＩＤの連番性から解放されることが挙げられる。また、始点ノード及び次リンクの２つの情報でリンク間の接続性と連続性を表現することから、重複情報の無い論理設計が可能となることもメリットとして挙げられる。
【００３１】
すなわち、図４に示すように、従来方式の地図データでは、各リンクは、２端点のノードの参照情報を有しているが、リンクの連続性を表現するためには、更に追加の情報（例えば一筆書き情報）が必要であった。
【００３２】
また、このような従来方式の地図データでは、リンク列を構成するリンクのリンクＩＤが連番であることから、リンクの連続性やレベル間の関連を、「リンクＩＤ＝開始側連続番号＋差分番号」の形で表現している。
【００３３】
例えば、図５における左側に示すように、レベル０（最下位層）のリンクＬ２，Ｌ３からなるレベル１のリンクは、開始側連続番号（Ｌ２）と、始端側のリンク（Ｌ２）と終端側のリンク（Ｌ３）とのリンクＩＤの差分とから、Ｌ２−１と表現することができる。また、レベル０のリンクＬ１のみからなるレベル１のリンクは、差分が０であることから、Ｌ１−０と表現される。同様に、レベル０のＬ１〜Ｌ３からなるレベル２のリンクは、Ｌ１−２と表現することができる。このように、リンクＩＤの表現によって、リンク列を構成するリンクを特定することができる。
【００３４】
しかしながら、このようなデータ構造では、地図データの差分更新を行う際に、整合性（序列）維持のため、最下位リンクの変更が、後方のリンクや上位レベルのリンクに対してまで連鎖的な変更を引き起こすという問題があった。例えば図５における右側に示すように、レベル０の既存のリンクＬ１が２つに分割された場合、その後方のリンクのリンクＩＤだけでなく、上位レベルのリンクのリンクＩＤについても更新する必要が生じる。
【００３５】
これに対し、図６に示すように、本実施形態の地図データの差分更新では、リンク間に明示的な参照を定義し、参照関係を直接表現することにより、変更を要する影響範囲を局所化することを可能とした。図６における左側に示す例では、レベル０のリンクＬ４は、上位リンクの参照情報として、レベル１のリンクＬ２の参照情報を有しており、同様にレベル０のリンクＬ５，Ｌ６は、上位リンクの参照情報として、それぞれレベル１のリンクＬ３の参照情報を有している。また、レベル１のリンクＬ２，Ｌ３は、上位リンクの参照情報として、それぞれレベル２のリンクＬ１の参照情報を有している。
【００３６】
このようなデータ構造によれば、従来方式の地図データのような序列維持の制約がないことから、例えば図６における右側に示すようにレベル０の既存のリンクＬ４が２つに分割された場合にも、後方のリンクや上位レベルのリンクの識別情報を変更することなく差分更新を行うことができる。
【００３７】
なお、図６では、下レイヤのリンクが上レイヤのリンクの参照情報を有し、逆に、上レイヤのリンクも下レイヤのリンクの参照情報を有しているが、実際には、例えば図７に示すように、下レイヤのリンクが上レイヤのリンクをただ一つ参照するようにすればよい。このようにすれば、上から下への参照は、参照元を集計することで算出可能であり、このように集計により算出可能な情報は重複情報となるからである。また、各リンクがそれぞれ上位リンクの情報を有している必要はなく、例えばリンク列における１つのリンク（例えば先頭のリンク）のみを上位リンクと関連付けるようにすれば、データ量を一層削減することができる。
【００３８】
［２．ナビゲーション装置の構成］
次に、このような地図データの具体的な使用例として、車両に搭載されるナビゲーション装置の実施例について説明する。
【００３９】
［２−１．全体構成］
図８は、ナビゲーション装置１０の概略構成を表すブロック図である。
このナビゲーション装置１０は、位置検出器１１、地図データ入力器１２、操作デバイス１３、表示装置１４、音声出力装置１５、制御回路１６などを備えている。
【００４０】
位置検出器１１は、当該ナビゲーション装置１０を搭載した車両の現在位置を検出するためのものであり、周知のジャイロスコープ、距離センサ及びＧＰＳ受信機を有している。
【００４１】
地図データ入力器１２は、ＤＶＤ−ＲＯＭやハードディスク装置等の記憶媒体に格納されている地図データ等を入力するための装置である。
操作デバイス１３は、ユーザからの各種指示を入力するためのものであり、表示装置１４の画面前面に配置されたタッチパネルや、ステアリングの近傍に設けられたステアリングスイッチ等が用いられ、地図の縮尺変更やスクロール等の操作や目的地設定などナビゲーション装置１０のすべての操作を行うことが可能である。
【００４２】
表示装置１４は、フルカラー表示が可能なものであり、表示装置１４の画面には位置検出器１１により検出された車両の現在位置を表す現在位置マークと、地図データ入力器１２より入力された地図データと、更に地図上に表示する誘導経路等の付加データとを重ねて表示することができる。
【００４３】
音声出力装置１５は、スピーカ、オーディオアンプなどから構成され、制御回路１６により合成された音声等を出力する。音声出力装置１５は、ナビゲーション装置１０の構成として省くこともできる。その場合、他の装置が備えている音声出力装置（例えば車両本体の音声出力装置）を利用してもよい。
【００４４】
制御回路１６は、通常のコンピュータとして構成されており、内部には周知のＣＰＵ、ＲＯＭ、ＲＡＭ、Ｉ／Ｏ及びこれらの構成を接続するバスラインなどを備えている。そして、ＣＰＵは、ＲＯＭに記憶されているプログラムに従い、位置検出器１１、地図データ入力器１２、操作デバイス１３から入力された各種情報に基づき、所定の処理（後述する地図データ更新処理等）を実行する。
【００４５】
［２−２．地図データの説明］
次に、ナビゲーション装置１０で使用される地図データについて説明する。
図９に示すように、従来（ＫＩＷＩ／Ａ）方式の地図データでは、各リンクが、始点ノード及び終点ノードの参照情報を有している。また、同一属性の連続する複数のリンクがリンク列として規定され、階層間のリンク対応は、リンク列を構成するリンクのリンクＩＤを昇順連番とする前提で、リンク列における始端側及び終端側の各リンクＩＤに基づき特定される。
【００４６】
これに対し、本実施例のナビゲーション装置１０で使用される地図データは、図１０に示すように、各リンクが、始点ノードの参照情報と、同一リンク列における次リンクの参照情報と、上位リンクの参照情報とを有している。また、リンク列における最終リンクに対する次リンクとして、実際には存在しない仮想リンクが設定されている。これにより、最終リンクにも次リンクが存在することとなり、最終リンクを他のリンクと同様のデータ構成とすることができる。なお、この地図データでは、リンクの識別情報がレベル間で独立管理されている。
【００４７】
また、各リンクはリスト状に記憶されており、リンクの追加や削除の際にもリンクリストにおける既存リンクの位置（配列添字）を変更しないようにすることで、各リンクをリンクリストにおける位置（配列添字）で特定できるようにしている。このため、各リンクは、リンクＩＤを有しておらず、その分、従来方式の地図データに比べ、データ量が削減されている。なお、リンクだけでなく、ノードについても同様にリスト状に記憶されており、ノードの追加や削除の際にもノードリストにおける既存ノードの位置（配列添字）を変更しないようにすることで、各ノードをノードリストにおける位置（配列添字）で特定できるようにしている。
【００４８】
［２−３．地図データの更新方法の概要］
次に、ナビゲーション装置１０が実行する地図データの更新方法の概要について説明する。
【００４９】
図９に示した従来（ＫＩＷＩ／Ａ）方式の地図データでは、地図データの差分更新を行う際に、既存のリンクが複数に分割されると、後方のリンクに対してまで連鎖的な変更が生じるという問題がある。例えば図１１に示すように、リンク１１，１２，１３，１４からなるリンク列のうち、既存のリンク１２及びリンク１４がそれぞれ２つに分割された場合、後方のリンクＩＤをすべて変更する必要が生じる。
【００５０】
これに対し、本実施例のナビゲーション装置１０で使用される地図データによれば、後方のリンクに対して連鎖的な変更が生じないようにすることができる。例えば図１２に示すように、リンク１，２，４，５からなるリンク列のうち、既存のリンク２及びリンク５がそれぞれ２つに分割された場合について説明する。この場合、リンク２を２つに分割する新たなノード６を始点ノードとするリンク７と、リンク５を２つに分割する新たなノード７を始点ノードとするリンク８とを、リンクリストの末尾に追加する。ここで、リンク７の始点ノードはノード６、次リンクはリンク３（仮想リンク）、上位リンクはリンク１となる。また、リンク８の始点ノードはノード７、次リンクはリンク６（仮想リンク）、上位リンクはリンク２となる。一方、既存のリンク２については、次リンクをリンク３からリンク７に変更すればよく、同様に、既存のリンク５については、次リンクをリンク６からリンク８に変更すればよい。
【００５１】
［２−４．更新データの説明］
次に、地図データの差分更新を行うための更新データについて説明する。
ナビゲーション装置１０は、更新データを外部から取得することにより、地図データを更新するための処理を実行する。ここで、更新データは、図１３（ａ）〜（ｄ）に示すように、４つの種別に大別される。なお、図面上の各四角形が、意味のあるバイナリ値の並びとなる。
【００５２】
図１３（ａ）は、リンクリストへの新規リンクの追加処理、又は、リンクリストに登録されている既存リンクに関する情報の更新処理をナビゲーション装置１０に実行させるための更新データである。この更新データは、種別データ（リンク追加／更新）と、追加処理又は更新処理を行うリンクの識別情報（リンクリストにおける位置情報）である対象リンクＮｏ．と、始点ノードＮｏ．（始点ノードの参照情報）と、次リンクＮｏ．（次リンクの参照情報）と、その他の情報（上位リンクの参照情報等）とから構成される。
【００５３】
図１３（ｂ）は、リンクリストに登録されている既存リンクの削除処理をナビゲーション装置１０に実行させるための更新データであり、種別データ（リンク削除）と、削除処理を行うリンクの識別情報である対象リンクＮｏ．とから構成される。
【００５４】
図１３（ｃ）は、ノードリストへの新規ノードの追加処理、又は、ノードリストに登録されている既存ノードに関する情報の更新処理をナビゲーション装置１０に実行させるための更新データである。この更新データは、種別データ（ノード追加／更新）と、追加処理又は更新処理を行うノードの識別情報（ノードリストにおける位置）である対象ノードＮｏ．と、その他の情報とから構成される。
【００５５】
図１３（ｄ）は、ノードリストに登録されている既存ノードの削除処理をナビゲーション装置１０に実行させるための更新データであり、種別データ（ノード削除）と、削除処理を行うノードの識別情報である対象ノードＮｏ．とから構成される。
【００５６】
なお、ナビゲーション装置１０が更新データを外部から取得する方法としては、例えば、車両外部のサーバとの間で直接通信を行うことによりダウンロードする方法、ＰＣ等の情報処理装置を介してサーバから間接的に取得する方法、更新データが記憶されたメディアから取得する方法などが考えられる。
【００５７】
［２−５．地図データ更新処理］
次に、更新データを外部から取得することによりナビゲーション装置１０の制御回路１６が実行する地図データ更新処理について、図１４のフローチャートを用いて説明する。
【００５８】
制御回路１６は、地図データ更新処理を開始すると、まずＳ１０１で、未処理の更新データが存在しないか否かを判定する。つまり、取得した更新データのすべてについて、後述するＳ１０２以降の処理を実行したか否かを判定している。
【００５９】
このＳ１０１で、未処理の更新データが存在すると判定した場合には、Ｓ１０２へ移行し、更新データを１エントリ読み込む。
続いて、Ｓ１０３では、Ｓ１０２で読み込んだ更新データのデータ種別を判定する。
【００６０】
そして、Ｓ１０３で、更新データのデータ種別が「リンク追加／更新」であると判定した場合には、Ｓ１０４へ移行し、その更新データの対象リンクＮｏ．が、現在のリンク情報数（リンクリストの項目数）よりも大きいか否かを判定する。ここで、対象リンクＮｏ．が現在のリンク情報数よりも大きい場合とは、現時点のリンクリストに存在しないリンクが対象となっていることを意味する。つまり、リンクリストの末尾に新規リンクを追加する処理を意味する。
【００６１】
このため、Ｓ１０４で、対象リンクＮｏ．が現在のリンク情報数よりも大きいと判定した場合には、Ｓ１０５へ移行し、リンク情報数が対象リンクＮｏ．数となるようにリンクリストを拡張した後、Ｓ１０６へ移行する。
【００６２】
一方、Ｓ１０４で、対象リンクＮｏ．が現在のリンク情報数よりも大きくない（換言すれば、対象リンクＮｏ．が現時点のリンクリストに存在する）と判定した場合には、Ｓ１０５をスキップしてＳ１０６へ移行する。
【００６３】
Ｓ１０６では、リンクリストにおける対象リンクＮｏ．のリンク情報を、更新データの情報（始点ノードＮｏ．、次リンクＮｏ．及び他の情報）で上書きした後、Ｓ１０１へ戻る。これにより、対象リンクＮｏ．のリンク情報として既存リンクの情報が存在していた場合にはその情報が更新されることになり、既存リンクの情報が存在していなかった場合（Ｓ１０５で新たに拡張された箇所である場合や、後述するＳ１０７の処理により無効値が格納されていた場合）には、新規リンクの情報が追加されることになる。
【００６４】
一方、Ｓ１０３で、更新データのデータ種別が「リンク削除」であると判定した場合には、Ｓ１０７へ移行し、リンクリストにおける対象リンクＮｏ．のリンク情報を無効値で埋めた後、Ｓ１０１へ戻る。つまり、対象リンクＮｏ．の既存リンクを削除する。
【００６５】
また、Ｓ１０３で、更新データのデータ種別が「ノード追加／更新」であると判定した場合には、Ｓ１０８へ移行し、その更新データの対象ノードＮｏ．が、現在のノード情報数（ノードリストの項目数）よりも大きいか否かを判定する。ここで、対象ノードＮｏ．が現在のノード情報数よりも大きい場合とは、現時点のノードリストに存在しないノードが対象となっていることを意味する。つまり、ノードリストの末尾に新規ノードを追加する処理を意味する。
【００６６】
このため、Ｓ１０８で、対象ノードＮｏ．が現在のノード情報数よりも大きいと判定した場合には、Ｓ１０９へ移行し、ノード情報数が対象ノードＮｏ．数となるようにノードリストを拡張した後、Ｓ１１０へ移行する。
【００６７】
一方、Ｓ１０８で、対象ノードＮｏ．が現在のノード情報数よりも大きくない（換言すれば、対象ノードＮｏ．が現時点のノードリストに存在する）と判定した場合には、Ｓ１０９をスキップしてＳ１１０へ移行する。
【００６８】
Ｓ１１０では、ノードリストにおける対象ノードＮｏ．のノード情報を、更新データの情報（他の情報）で上書きした後、Ｓ１０１へ戻る。これにより、対象ノードＮｏ．のノード情報として既存ノードの情報が存在していた場合にはその情報が更新されることになり、既存ノードの情報が存在していなかった場合（Ｓ１０９で新たに拡張された箇所である場合や、後述するＳ１１１の処理により無効値が格納されていた場合）には、新規ノードの情報が追加されることになる。
【００６９】
一方、Ｓ１０３で、更新データのデータ種別が「ノード削除」であると判定した場合には、Ｓ１１１へ移行し、ノードリストにおける対象ノードＮｏ．のノード情報を無効値で埋めた後、Ｓ１０１へ戻る。つまり、対象ノードＮｏ．の既存ノードを削除する。
【００７０】
その後、Ｓ１０１で、未処理の更新データが存在しないと判定すると、本地図データ更新処理を終了する。
［３．効果］
以上説明したように、本実施形態の地図データでは、各リンクが、当該リンクの属するリンク列における次リンクの参照情報を有しており、次リンクの参照情報をたどることで、リンク列という構造を明示的に持つことなくリンク列を特定することができる。このため、本実施形態の地図データでは、従来のように同一リンク列に属するリンクに連続したリンクＩＤを付与する必要がない。つまり、リンクＩＤを連続にしなければならないという制約がない。したがって、地図データの更新に伴い既存のリンクが複数に分割される場合にも、既存のリンクの識別情報を変更することなく更新を行うことができる。この結果、地図データ更新時のデータ変更量を少なくすることができ、リンク情報の管理を容易とすることができる。
【００７１】
すなわち、従来（ＫＩＷＩ／Ａ）方式の地図データでは、図１５（ａ）に示すように、既存のリンクが複数に分割されると、リンクＩＤの連番性を保つために、後方のリンクＩＤをすべて振り直す必要が生じる。
【００７２】
一方、前述した特許文献１に記載の地図データでは、図１５（ｂ）に示すように、既存リンクの分割数がそのリンクのリンクＩＤ番号範囲で対応可能な場合には、後方のリンクＩＤを振り直す必要がない。しかしながら、図１５（ｃ）に示すように、既存リンクの分割数がリンクＩＤ番号範囲で対応可能な限界を超えた場合には、後方のリンクＩＤを振り直す必要が生じるため、根本的には問題は解決されていない。ここで、リンクＩＤ番号範囲を十分に大きくしておくことも考えられるが、データ量が大幅に増加してしまうというデメリットがある。しかも、この方法では、リンクＩＤ範囲をどのような割合で分割するかといった複雑なＩＤ管理が必要となるという問題もある。
【００７３】
これに対し、本実施形態の地図データによれば、リンクＩＤを連続にしなければならないという制約自体がないため、後方のリンクＩＤを振り直すことなく地図データを更新することができ、リンク情報の管理を容易とすることができる。
【００７４】
また、各リンクが始点ノード及び次リンクの参照情報を有しており、終点ノードについては次リンクの始点ノードから特定することができるため、従来のように各リンクが始点ノード及び終点ノードの両方の参照情報を有している必要がない。
【００７５】
さらに、本実施形態では、ナビゲーション装置１０が、地図データのリンクをリスト状に管理し、このリンクリストにおける既存のリンクの位置を変化させないように情報の更新を行うようにしている。このため、各リンクをリンクリスト上の何番目の位置であるかという情報（配列添字）で参照することができ、リンクＩＤという識別情報自体を明示的に持つ必要がない分、データ量を削減することができる。しかも、リンクＩＤではなく配列添字を直接参照する分、リンクＩＤをリンクリストから検索する方式に比べ、処理の高速化を図ることができる。
【００７６】
［４．特許請求の範囲との対応］
なお、本実施形態のナビゲーション装置１０が地図データ更新装置に相当し、特に、Ｓ１０４，Ｓ１０５の処理を実行する制御回路１６がリスト拡張手段に相当し、Ｓ１０６，Ｓ１０７の処理を実行する制御回路１６が情報更新手段に相当する。
【００７７】
［５．他の形態］
以上、本発明の実施形態について説明したが、本発明は、上記実施形態に限定されることなく、種々の形態を採り得ることは言うまでもない。
【００７８】
例えば、上記実施形態では、本発明の地図データ更新装置としてナビゲーション装置１０を例示したが、これに限定されるものではなく、ナビゲーション装置用の更新地図データを生成する装置などにも適用することができる。
【図面の簡単な説明】
【００７９】
【図１】実施形態の地図データの基本構造を説明するための説明図である。
【図２】実施形態の地図データのデータベースの論理設計を説明するための説明図である。
【図３】（ａ）は交差点の論理設計（ノード）を説明するための説明図、（ｂ）は道路の論理設計（リンクの設計）を説明するための説明図である。
【図４】従来の地図データにおける各リンクの参照情報の説明図である。
【図５】従来の地図データにおけるリンク情報のデータ構造の説明図である。
【図６】実施形態の地図データにおけるリンク情報のデータ構造の説明図である。
【図７】下レイヤのリンクが上レイヤのリンクをただ一つ参照する例の説明図である。
【図８】ナビゲーション装置の概略構成を表すブロック図である。
【図９】従来（ＫＩＷＩ／Ａ）方式の地図データにおけるリンク情報の説明図である。
【図１０】実施例のナビゲーション装置で使用される地図データにおけるリンク情報の説明図である。
【図１１】従来（ＫＩＷＩ／Ａ）方式の地図データの差分更新の説明図である。
【図１２】実施例のナビゲーション装置で使用される地図データの差分更新の説明図である。
【図１３】更新データの説明図である。
【図１４】地図データ更新処理のフローチャートである。
【図１５】従来方式の地図データの問題点を説明するための説明図である。
【符号の説明】
【００８０】
１０…ナビゲーション装置、１１…位置検出器、１２…地図データ入力器、１３…操作デバイス、１４…表示装置、１５…音声出力装置、１６…制御回路
【特許請求の範囲】
【請求項１】
道路がリンク単位で表され、同一属性の連続する複数のリンクがリンク列として規定された地図データであって、
各リンクが、当該リンクの属するリンク列における次リンクの参照情報を有すること
を特徴とする地図データ。
【請求項２】
当該地図データは複数段階に階層化されており、下位階層の各リンクが、その上位階層のリンクの参照情報を有すること
を特徴とする請求項１に記載の地図データ。
【請求項３】
リンク列における最終リンクの次リンクとして、実際には存在しない仮想リンクが設定されていること
を特徴とする請求項１又は請求項２に記載の地図データ。
【請求項４】
請求項１から請求項３までのいずれか１項に記載の地図データのリンクをリスト状に管理し、前記リストにおける更新対象リンクの位置情報を指定した更新データに基づき前記リストを更新する地図データ更新装置であって、
前記更新データの指定する位置情報が前記リストに存在しない場合には、その位置情報が存在するように前記リストを拡張するリスト拡張手段と、
前記更新データの指定する位置情報のリンクの情報を前記更新データに基づき更新する情報更新手段と、
を備えることを特徴とする地図データ更新装置。
【請求項５】
請求項１から請求項３までのいずれか１項に記載の地図データのリンクをリスト状に管理し、前記リストにおける更新対象リンクの位置情報を指定した更新データに基づき前記リストを更新する地図データ更新装置としてコンピュータを機能させるための地図データ更新プログラムであって、
前記更新データの指定する位置情報が前記リストに存在しない場合には、その位置情報が存在するように前記リストを拡張するリスト拡張手段と、
前記更新データの指定する位置情報のリンクの情報を前記更新データに基づき更新する情報更新手段
としてコンピュータを機能させることを特徴とする地図データ更新プログラム。
【請求項６】
請求項１から請求項３までのいずれか１項に記載の地図データの更新方法であって、
リンクをリスト状に管理し、前記リストにおける既存のリンクの位置を変化させないように情報の更新を行うこと
を特徴とする地図データの更新方法。
【請求項１】
道路がリンク単位で表され、同一属性の連続する複数のリンクがリンク列として規定された地図データであって、
各リンクが、当該リンクの属するリンク列における次リンクの参照情報を有すること
を特徴とする地図データ。
【請求項２】
当該地図データは複数段階に階層化されており、下位階層の各リンクが、その上位階層のリンクの参照情報を有すること
を特徴とする請求項１に記載の地図データ。
【請求項３】
リンク列における最終リンクの次リンクとして、実際には存在しない仮想リンクが設定されていること
を特徴とする請求項１又は請求項２に記載の地図データ。
【請求項４】
請求項１から請求項３までのいずれか１項に記載の地図データのリンクをリスト状に管理し、前記リストにおける更新対象リンクの位置情報を指定した更新データに基づき前記リストを更新する地図データ更新装置であって、
前記更新データの指定する位置情報が前記リストに存在しない場合には、その位置情報が存在するように前記リストを拡張するリスト拡張手段と、
前記更新データの指定する位置情報のリンクの情報を前記更新データに基づき更新する情報更新手段と、
を備えることを特徴とする地図データ更新装置。
【請求項５】
請求項１から請求項３までのいずれか１項に記載の地図データのリンクをリスト状に管理し、前記リストにおける更新対象リンクの位置情報を指定した更新データに基づき前記リストを更新する地図データ更新装置としてコンピュータを機能させるための地図データ更新プログラムであって、
前記更新データの指定する位置情報が前記リストに存在しない場合には、その位置情報が存在するように前記リストを拡張するリスト拡張手段と、
前記更新データの指定する位置情報のリンクの情報を前記更新データに基づき更新する情報更新手段
としてコンピュータを機能させることを特徴とする地図データ更新プログラム。
【請求項６】
請求項１から請求項３までのいずれか１項に記載の地図データの更新方法であって、
リンクをリスト状に管理し、前記リストにおける既存のリンクの位置を変化させないように情報の更新を行うこと
を特徴とする地図データの更新方法。
【図８】
【図９】
【図１０】
【図１３】
【図１４】
【図１５】
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図１１】
【図１２】
【図９】
【図１０】
【図１３】
【図１４】
【図１５】
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図１１】
【図１２】
【公開番号】特開２０１０−３２６４０（Ｐ２０１０−３２６４０Ａ）
【公開日】平成２２年２月１２日（２０１０．２．１２）
【国際特許分類】
【出願番号】特願２００８−１９２５４４（Ｐ２００８−１９２５４４）
【出願日】平成２０年７月２５日（２００８．７．２５）
【出願人】（０００００４２６０）株式会社デンソー (27,639)
【出願人】（５０３００２１６７）株式会社高速屋 (4)
【Ｆターム（参考）】
【公開日】平成２２年２月１２日（２０１０．２．１２）
【国際特許分類】
【出願日】平成２０年７月２５日（２００８．７．２５）
【出願人】（０００００４２６０）株式会社デンソー (27,639)
【出願人】（５０３００２１６７）株式会社高速屋 (4)
【Ｆターム（参考）】
[ Back to top ]