(57)【特許請求の範囲】
【請求項１】
地図データ処理装置であって、
地図を複数の区画に分割し、分割した前記区画単位に地図に関する情報を分割した構造と、前記分割した区画単位の地図に関する情報の管理情報を有する構造とを備えた地図データが記録された記録媒体を駆動する記録媒体駆動手段と、
前記区画単位の地図に関する情報の更新データを取得する更新データ取得手段と、
前記記録媒体に記録された地図に関する情報を、前記更新データ取得手段により取得された更新データと前記管理情報を使用して前記区画単位に更新するとともに、前記記録媒体に記録された地図に関する情報と前記更新データ取得手段により取得された更新データと前記管理情報とに基づき地図データの処理を行う処理手段とを備え、
前記地図の異なる複数の縮尺率に対応する複数のレベルを定義し、
前記地図に関する情報は、前記複数のレベルに対応して複数セット設けられ、
前記区画単位の地図に関する情報は、すべてのレベルおいて設けられる少なくとも１つの種類の地図に関する情報と、少なくとも１つのレベルにおいて設けられる他の種類の地図に関する情報とが分離して設けられ、
前記処理手段は、前記１つの種類の地図に関する情報と前記他の種類の地図に関する情報とが分離して設けられた前記区画単位の地図に関する情報を使用して前記地図データの処理を行うことを特徴とする地図データ処理装置。
【請求項２】
請求項１記載の地図データ処理装置において、
前記地図を複数の第１の分割単位に分割し、前記各第１の分割単位を第１の分割単位間で同一の数の複数の第２の分割単位に分割し、前記分割された区画は前記各第２の分割単位に対応し、
前記管理情報は、前記各第１の分割単位ごとに前記複数の第２の分割単位に関する管理情報を有することを特徴とする地図データ処理装置。
【請求項３】
請求項２記載の地図データ処理装置において、
前記管理情報は、さらに、前記複数の第１の分割単位に関する管理情報を有することを特徴とする地図データ処理装置。
【請求項４】
請求項１記載の地図データ処理装置において、
前記地図を各レベルごとに複数の第１の分割単位に分割し、前記各第１の分割単位を第１の分割単位間で同一の数の複数の第２の分割単位に分割し、前記分割された区画は前記各第２の分割単位に対応し、
前記管理情報は、前記各レベルごとに前記複数の第１の分割単位に関する管理情報を有し、前記各第１の分割単位ごとに前記複数の第２の分割単位に関する管理情報を有することを特徴とする地図データ処理装置。
【請求項５】
請求項１記載の地図データ処理装置において、
前記１つの種類の地図に関する情報は、表示手段に地図を表示するため情報であり、
前記他の種類の地図に関する情報は、経路探索に使用する情報を含むことを特徴とする地図データ処理装置。
【請求項６】
地図データ処理装置であって、
地図を複数の区画に分割し、分割した前記区画単位に地図に関する情報を分割した構造と、前記分割した区画単位の地図に関する情報の管理情報を有する構造とを備えた地図データが記録された記録媒体を駆動する記録媒体駆動手段と、
前記区画単位の地図に関する情報の更新データを取得する更新データ取得手段と、
前記記録媒体に記録された地図に関する情報を、前記更新データ取得手段により取得された更新データと前記管理情報を使用して前記区画単位に更新するとともに、前記記録媒体に記録された地図に関する情報と前記更新データ取得手段により取得された更新データと前記管理情報とに基づき地図データの処理を行う処理手段とを備え、
前記地図の複数の異なる縮尺率に対応する複数のレベルを定義し、
前記地図に関する情報は、前記複数のレベルに対応して複数セット設けられ、
前記地図をレベルごとに複数の区画に分割し、レベルごとに、前記分割した区画単位に前記複数セットの地図に関する情報を分割し、
異なるレベルに属する２つの区画内の地理的に共通する位置に、前記２つの区画に対応する地図に関する情報を関連づける接続点が存在し、
前記接続点に関する情報は、前記２つの区画に対応するそれぞれの地図に関する情報において、前記接続点の前記地図内の位置を表す２次元座標値を共通に有し、
さらに、あるレベルの前記接続点の２次元座標値は、より詳細地図をあらわすレベルにおける対応する接続点の２次元座標値が付加されており、
前記処理手段は、前記より詳細地図をあらわすレベルにおける対応する接続点の２次元座標値が付加された前記あるレベルの前記接続点の２次元座標値を使用して、前記地図データの処理を行うことを特徴とする地図データ処理装置。
【請求項７】
請求項６記載の地図データ処理装置において、
前記２次元座標値は、緯度経度に対応する値であることを特徴とする地図データ処理装置。
【請求項８】
請求項６または７記載の地図データ処理装置において、
前記接続点に関する情報は、前記２次元座標値に加えて、前記接続点の前記２次元座標値以外のパラメータを有することを特徴とする地図データ処理装置。
【請求項９】
請求項８記載の地図データ処理装置において、
前記パラメータは、前記接続点の高さ情報を含むことを特徴とする地図データ処理装置。
【請求項１０】
請求項８または９記載の地図データ処理装置において、
前記パラメータは、前記区画単位の地図に関する情報の生成更新に関する時間情報含むことを特徴とする地図データ処理装置。
【請求項１１】
地図データ処理装置であって、
地図を複数の区画に分割し、分割した前記区画単位に地図に関する情報を分割した構造と、前記分割した区画単位の地図に関する情報の管理情報を有する構造とを備えた地図データが記録された記録媒体を駆動する記録媒体駆動手段と、
前記区画単位の地図に関する情報の更新データを取得する更新データ取得手段と、
前記記録媒体に記録された地図に関する情報を、前記更新データ取得手段により取得された更新データと前記管理情報を使用して前記区画単位に更新するとともに、前記記録媒体に記録された地図に関する情報と前記更新データ取得手段により取得された更新データと前記管理情報とに基づき地図データの処理を行う処理手段とを備え、
前記区画単位の地図に関する情報は、地図に関する情報の種類に応じて分離して管理し、
前記地図に関する情報の種類のうち最も優先度の高い種類の地図に関する情報は、所定の大きさを上限値として管理し、
前記処理手段は、前記地図に関する情報の種類のうち最も優先度の高い種類の地図に関する情報が前記所定の大きさを上限値として管理された前記区画単位の地図に関する情報を使用して前記地図データの処理を行うことを特徴とする地図データ処理装置。
【請求項１２】
請求項１１記載の地図データ処理装置において、
前記最も優先度の高い種類の地図に関する情報が、前記更新に伴い前記所定の大きさの上限値を超えるとき、少なくとも前記更新に伴い前記所定の大きさの上限値を超える分の地図に関する情報を、前記最も高い優先度より低い優先度の種類の地図に関する情報として管理することを特徴とする地図データ処理装置。
【請求項１３】
請求項１１または１２記載の地図データ処理装置において、
前記最も優先度の高い種類の地図に関する情報は、少なくとも、表示手段に地図を表示するため情報を含むことを特徴とする地図データ処理装置。
【請求項１４】
請求項１２記載の地図データ処理装置において、
前記最も優先度の高い種類の地図に関する情報は、少なくとも、表示手段に地図を表示するため情報を含み、
前記最も高い優先度より低い優先度の種類の地図に関する情報は、前記最も高い優先度の種類の地図に関する情報よりもより詳細な地図を表示手段に表示できる情報を含むことを特徴とする地図データ処理装置。
【請求項１５】
請求項１〜１４のいずれかに記載の地図データ処理装置において、
前記地図データは、地図表示用データであり、
前記処理手段は、前記記録媒体に記録された地図データと、前記更新データ取得手段により取得された更新データとを接続しながら、表示装置に地図の表示をを行うことを特徴とする地図データ処理装置。
【請求項１６】
請求項１〜１４のいずれかに記載の地図データ処理装置において、
前記地図データは、経路探索用データであり、
前記処理手段は、前記記録媒体に記録された地図データと、前記更新データ取得手段により取得された更新データとを接続しながら、経路探索処理を行うことを特徴とする地図データ処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、地図データ処理装置に関する。
【０００２】
【従来の技術】
従来、ナビゲーション装置で使用される道路地図などの地図データは、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの記録媒体で提供されていた。また、通信を使用して車両搭載のナビゲーション装置に地図データを提供することも行われている。
【０００３】
【発明が解決しようとする課題】
しかし、記録媒体などで提供される大容量の地図データの一部を効率よく更新し、新旧の地図データを効率よく整合性をもたせて使用できる仕組みが提供されていなかった。
【０００４】
本発明は、記録媒体などで提供される大容量の地図データの一部を効率よく更新し、新旧の地図データを効率よく整合性をもたせて使用できる地図データの構造を有する地図データを使用する地図データ処理装置を提供する。
【０００５】
【課題を解決するための手段】
請求項１の発明は、地図データ処理装置に適用され、地図を複数の区画に分割し、分割した区画単位に地図に関する情報を分割した構造と、分割した区画単位の地図に関する情報の管理情報を有する構造とを備えた地図データが記録された記録媒体を駆動する記録媒体駆動手段と、区画単位の地図に関する情報の更新データを取得する更新データ取得手段と、記録媒体に記録された地図に関する情報を、更新データ取得手段により取得された更新データと管理情報を使用して区画単位に更新するとともに、記録媒体に記録された地図に関する情報と更新データ取得手段により取得された更新データと管理情報とに基づき地図データの処理を行う処理手段とを備え、地図の異なる複数の縮尺率に対応する複数のレベルを定義し、地図に関する情報は、複数のレベルに対応して複数セット設けられ、区画単位の地図に関する情報は、すべてのレベルおいて設けられる少なくとも１つの種類の地図に関する情報と、少なくとも１つのレベルにおいて設けられる他の種類の地図に関する情報とが分離して設けられ、処理手段は、１つの種類の地図に関する情報と他の種類の地図に関する情報とが分離して設けられた区画単位の地図に関する情報を使用して地図データの処理を行うことを特徴とするものである。
請求項２の発明は、請求項１記載の地図データ処理装置において、地図を複数の第１の分割単位に分割し、各第１の分割単位を第１の分割単位間で同一の数の複数の第２の分割単位に分割し、分割された区画は各第２の分割単位に対応し、管理情報は、各第１の分割単位ごとに複数の第２の分割単位に関する管理情報を有することを特徴とするものである。
請求項３の発明は、請求項２記載の地図データ処理装置において、管理情報は、さらに、複数の第１の分割単位に関する管理情報を有することを特徴とするものである。
請求項４の発明は、請求項１記載の地図データ処理装置において、地図を各レベルごとに複数の第１の分割単位に分割し、各第１の分割単位を第１の分割単位間で同一の数の複数の第２の分割単位に分割し、分割された区画は各第２の分割単位に対応し、管理情報は、各レベルごとに複数の第１の分割単位に関する管理情報を有し、各第１の分割単位ごとに複数の第２の分割単位に関する管理情報を有することを特徴とするものである。
請求項５の発明は、請求項１記載の地図データ処理装置において、１つの種類の地図に関する情報は、表示手段に地図を表示するため情報であり、他の種類の地図に関する情報は、経路探索に使用する情報を含むことを特徴とするものである。
請求項６の発明は、地図データ処理装置に適用され、地図を複数の区画に分割し、分割した区画単位に地図に関する情報を分割した構造と、分割した区画単位の地図に関する情報の管理情報を有する構造とを備えた地図データが記録された記録媒体を駆動する記録媒体駆動手段と、区画単位の地図に関する情報の更新データを取得する更新データ取得手段と、記録媒体に記録された地図に関する情報を、更新データ取得手段により取得された更新データと管理情報を使用して区画単位に更新するとともに、記録媒体に記録された地図に関する情報と更新データ取得手段により取得された更新データと管理情報とに基づき地図データの処理を行う処理手段とを備え、地図の複数の異なる縮尺率に対応する複数のレベルを定義し、地図に関する情報は、複数のレベルに対応して複数セット設けられ、地図をレベルごとに複数の区画に分割し、レベルごとに、分割した区画単位に複数セットの地図に関する情報を分割し、異なるレベルに属する２つの区画内の地理的に共通する位置に、２つの区画に対応する地図に関する情報を関連づける接続点が存在し、接続点に関する情報は、２つの区画に対応するそれぞれの地図に関する情報において、接続点の地図内の位置を表す２次元座標値を共通に有し、さらに、あるレベルの接続点の２次元座標値は、より詳細地図をあらわすレベルにおける対応する接続点の２次元座標値が付加されており、処理手段は、より詳細地図をあらわすレベルにおける対応する接続点の２次元座標値が付加されたあるレベルの接続点の２次元座標値を使用して、地図データの処理を行うことを特徴とするものである。
請求項７の発明は、請求項６記載の地図データ処理装置において、２次元座標値は、緯度経度に対応する値であることを特徴とするものである。
請求項８の発明は、請求項６または７記載の地図データ処理装置において、接続点に関する情報は、２次元座標値に加えて、接続点の２次元座標値以外のパラメータを有することを特徴とするものである。
請求項９の発明は、請求項８記載の地図データ処理装置において、パラメータは、接続点の高さ情報を含むことを特徴とするものである。
請求項１０の発明は、請求項８または９記載の地図データ処理装置において、パラメータは、区画単位の地図に関する情報の生成更新に関する時間情報含むことを特徴とするものである。
請求項１１の発明は、地図データ処理装置に適用され、地図を複数の区画に分割し、分割した区画単位に地図に関する情報を分割した構造と、分割した区画単位の地図に関する情報の管理情報を有する構造とを備えた地図データが記録された記録媒体を駆動する記録媒体駆動手段と、区画単位の地図に関する情報の更新データを取得する更新データ取得手段と、記録媒体に記録された地図に関する情報を、更新データ取得手段により取得された更新データと管理情報を使用して区画単位に更新するとともに、記録媒体に記録された地図に関する情報と更新データ取得手段により取得された更新データと管理情報とに基づき地図データの処理を行う処理手段とを備え、区画単位の地図に関する情報は、地図に関する情報の種類に応じて分離して管理し、地図に関する情報の種類のうち最も優先度の高い種類の地図に関する情報は、所定の大きさを上限値として管理し、処理手段は、地図に関する情報の種類のうち最も優先度の高い種類の地図に関する情報が所定の大きさを上限値として管理された区画単位の地図に関する情報を使用して地図データの処理を行うことを特徴とするものである。
請求項１２の発明は、請求項１１記載の地図データ処理装置において、最も優先度の高い種類の地図に関する情報が、更新に伴い所定の大きさの上限値を超えるとき、少なくとも更新に伴い所定の大きさの上限値を超える分の地図に関する情報を、最も高い優先度より低い優先度の種類の地図に関する情報として管理することを特徴とするものである。
請求項１３の発明は、請求項１１または１２記載の地図データ処理装置において、最も優先度の高い種類の地図に関する情報は、少なくとも、表示手段に地図を表示するため情報を含むことを特徴とするものである。
請求項１４の発明は、請求項１２記載の地図データ処理装置において、最も優先度の高い種類の地図に関する情報は、少なくとも、表示手段に地図を表示するため情報を含み、最も高い優先度より低い優先度の種類の地図に関する情報は、最も高い優先度の種類の地図に関する情報よりもより詳細な地図を表示手段に表示できる情報を含むことを特徴とするものである。
請求項１５の発明は、請求項１〜１４のいずれかに記載の地図データ処理装置において、地図データは、地図表示用データであり、処理手段は、記録媒体に記録された地図データと、更新データ取得手段により取得された更新データとを接続しながら、表示装置に地図の表示をを行うことを特徴とするものである。
請求項１６の発明は、請求項１〜１４のいずれかに記載の地図データ処理装置において、地図データは、経路探索用データであり、処理手段は、記録媒体に記録された地図データと、更新データ取得手段により取得された更新データとを接続しながら、経路探索処理を行うことを特徴とするものである。
【０００６】
【発明の実施の形態】
図１は、本発明の地図データの構造を有する地図データの授受について説明する図である。車載用ナビゲーション装置１は、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの記録媒体２から、地図データや管理情報や案内検索データなどを読み取る。リムーバブルメモリ３からは、地図データなどの更新データの提供を受ける。リムーバブルメモリ３は、地図データの一部を更新するために更新データ等が記録された取り替え可能な記録媒体である。
【０００７】
また、ナビゲーション装置１は、携帯電話などの通信装置４とも接続可能である。ナビゲーション装置１は、通信装置４を介してインタネット５に接続し、さらにインターネット５を介して地図サーバ６に接続することができる。地図サーバ６は、古い地図データから最新の地図データまでを地図データベース７に保有し、また、古い案内検索データから最新の案内検索データまでを案内検索データベース８に保有する。従って、地図サーバ６は、地図データの一部を更新する更新データをインターネット５を介してナビゲーション装置１に提供することができる。なお、案内検索データとは、ＰＯＩ等の位置情報、種別、名称等の属性情報を格納したデータである。
【０００８】
ナビゲーション装置１は、制御装置１１と不揮発性メモリ１２を有する。制御装置１１は、マイクロプロセッサおよびその周辺回路から構成される。不揮発性メモリ１２は、ナビゲーション装置１の内部に設けられたハードディスクやフラッシュメモリなどの不揮発性メモリである。不揮発性メモリ１２は、ナビゲーション装置１の電源が落とされても、書きこまれたデータが消えない記憶装置であればどのようなものでもよい。
【０００９】
記録媒体２は、一旦ナビゲーション装置１に搭載すると、新たな記録媒体２と入れ替えない限りナビゲーション装置１に搭載したままの状態となる。従って、リムーバブルメモリ３に対して固定メディアと称してもよい。地図データベース７や案内検索データベース８は、新旧すべての地図データや案内検索データなどを有しているためマザーデータのデータベースである。地図サーバ６は、地図データベース７や案内検索データベース８を使用して、初期の（更新前の）地図データなどを有する記録媒体２や、更新用データを有するリムーバブルメモリ３を準備することができる。
【００１０】
図２は、車載用ナビゲーション装置１のブロック図である。ナビゲーション装置１は、制御装置１１、不揮発性メモリ１２、現在地検出装置１３、ＤＶＤ駆動装置１４、メモリ１５、通信インターフェース１６、リムーバブルメモリ読込装置１７、モニタ１８、入力装置１９を有する。
【００１１】
現在地検出装置１３は車両の現在地を検出する現在地検出装置であり、例えば車両の進行方位を検出する方位センサや車速を検出する車速センサやＧＰＳ（Global Positioning System）衛星からのＧＰＳ信号を検出するＧＰＳセンサ等から成る。ＤＶＤ駆動装置１４は、記録媒体２を搭載して地図データなどを読み込む装置である。本実施の形態では、記録媒体２はＤＶＤ−ＲＯＭとする。なお、ＣＤ−ＲＯＭや他の記録媒体であってもよい。
【００１２】
メモリ１５は、現在地検出装置１３によって検出された車両位置情報等を格納したり、制御装置１１が演算した推奨経路上のノード情報やリンク情報等を格納するメモリである。さらに、後述する全メッシュ管理情報を格納したりもする。メモリ１５は制御装置１１のワーキングエリアである。通信インターフェース１６は、通信装置４を接続するインターフェースである。通信インターフェース１６を介して携帯電話の利用や、インターネットとの接続が可能である。リムーバブルメモリ読込装置１７は、リムーバブルメモリ３を装填しリムーバブルメモリ３からデータを読み込むことが可能な装置である。
【００１３】
モニタ１８は、地図や推奨経路や各種情報を表示する表示装置である。モニタ１８は、ナビゲーション装置本体の一部として一体に設けてもよいし、筐体としては別々に設けてもよい。さらに、モニタ１８のみを、ナビゲーション装置本体とケーブルなどによって接続し、分離した位置に設けるようにしてもい。入力装置１９は、経路探索時に車両の目的地等を入力したりする入力装置である。リモコンであってもよいし、モニタ１８の画面上に設けられたタッチパネルなどで構成してもよい。制御装置１１は、現在地検出装置１３で検出された車両の現在地情報と記録媒体２や不揮発性メモリ１２に格納された地図データなどを使用して、道路地図の表示、経路探索、経路誘導等の各種のナビゲーション処理を行う。なお、制御装置１１が実行する各種の処理プログラムは、制御装置１１内部に設けられたＲＯＭ（不図示）に組み込まれている。
【００１４】
−地図データの構造−
上述した地図データのデータ構造について、さらに詳しく説明する。地図データは、地図に関する情報であり、背景（地図表示用）データ、ロケータ用データ、ネットワーク（経路探索用）データ、誘導データ（交差点名称・道路名称・方面名称・方向ガイド施設情報など）などである。背景データは道路や道路地図の背景を表示するためのデータである。ロケータ用データは、車両の現在地の特定やマップマッチングなどに使用されるデータである。ネットワークデータは、道路形状とは直接関係しない分岐情報などから成る経路探索用データであり、主に推奨経路を演算（経路探索）する際に用いられる。誘導データは、交差点の名称などから成るデータであり、演算された推奨経路に基づき運転者等に推奨経路を誘導する際に用いられる。
【００１５】
本実施の形態の地図データは、レベル、ブロック、メッシュという概念で管理する。本実施の形態では、地図データを縮尺率が異なる７つのレベルに分け、最詳細の縮尺率のレベルをレベル０とし、最広域地図のレベルをレベル６とする。各レベルは縮尺率が異なる地図データを含むものであるが、対象となる領域は各レベルとも同じである。すなわち、日本全土が対象であると、各レベルごとに縮尺率が異なる日本全土の地図データを有する。例えば、レベル０では縮尺率１／６２５０、レベル３では縮尺率１／４０００００、レベル４では縮尺率１／１６０００００、レベル６では縮尺率１／１２８００００００の日本全土の地図データを有する。すなわち、レベル０〜６に対応して７つの地図データのセットがある。
【００１６】
図３は、地図データのレベル、ブロック、メッシュの関係を説明する概念図である。代表して、レベル３と４を示している。符号１０１は、本地図データの対象となる領域を示す。日本全土の地図データを扱うとすると、領域１０１は日本全土を含む範囲となる。レベル３もレベル４も同じ範囲の領域を対象としている。レベル３では、領域１０１は、４×４＝１６の複数のブロック１０２に分けられて管理される。一つのブロック１０２は、複数のメッシュ１０３に分けられて管理される。本実施の形態では、ｍ×ｎ枚のメッシュで管理する。各ブロック１０２間の分割メッシュの数は、同じレベルでは同一数ｍ×ｎである。
【００１７】
レベル４では、領域１０１は、２×２＝４の複数のブロック１０４に分けられて管理される。一つのブロック１０４は、複数のメッシュ１０５に分けられて管理される。本実施の形態では、ｐ×ｑ枚のメッシュで管理する。各ブロック１０４間の分割メッシュの数は、同じレベルでは同一数ｐ×ｑである。
【００１８】
レベル３とレベル４では、領域１０１を分割したブロックの数、各ブロックを分割したメッシュの数は異なる。これは、縮尺率の小さい（分母の値が大きい）より広域地図を扱うレベル４と、レベル４に比べて縮尺率の大きい（分母の値が小さい）より詳細地図を扱うレベル３とでは、扱うデータ量も異なるためである。すなわち、各レベルにおいて扱うデータ量に応じた適切な分割を行うようにしている。ただし、同一レベル内では、１つのブロックの大きさおよび１つのメッシュの大きさは同じである。なお、図３の各レベルの分割ブロック数は、１例であり、必ずしもこの数に限られるものではない。
【００１９】
上記ブロック、メッシュの呼び名は、本実施の形態で便宜上名づけたものである。従って、必ずしもこれらの名称に限定されるものではない。メッシュをパーセルと言ってもよいし、ブロックを第１の分割単位、メッシュを第２の分割単位と言ってもよい。また、これらのブロック、メッシュは地理的に分割された単位と言ってもよい。
【００２０】
図４は、ブロック内の全メッシュを管理する全メッシュ管理情報１８１とメッシュデータ１８２の構成を示す図である。メッシュデータ１８２は、前述したメッシュ１０３あるいはメッシュ１０５に対応して設けられる地図データである。全メッシュ管理情報１８１は、ブロック内に含まれる全メッシュデータの管理情報を有し、ブロックごとに設けられる。
【００２１】
図４の全メッシュ管理情報１８１の総メッシュ枚数１８３は、ブロック内に含まれる総メッシュ数である。左下基準位置コード１８４は、ブロックの左下位置の緯度経度に関する位置情報が入る。経度方向メッシュ枚数１８５は、東西の経度方向に並ぶメッシュの数で、図３のレベル３の例ではｍが入る。緯度方向メッシュ枚数１８６は、南北の緯度方向に並ぶメッシュの数で、図３のレベル３の例ではｎが入る。各メッシュ管理情報１８７は、各メッシュデータ１８２を管理する情報であり、ブロック内のメッシュの数分設けられる。
【００２２】
各メッシュデータ１８２は、メッシュ内管理情報１１１、背景（地図表示用）データ１１２、ロケータ用データ１１３、ネットワーク(経路計算用)データ１１４、誘導データ１１５から構成される。メッシュ内管理情報１１１と背景（地図表示用）データ１１２を基本データとし、ロケータ用データ１１３、ネットワークデータ１１４、誘導データ１１５を拡張データとする。基本データは、各レベルすべてに存在するデータである。拡張データは、固有のレベルに存在するデータである。例えば、ネットワークデータは、レベル１、２、３、４に存在し、ロケータデータや誘導データは、レベル０に存在する。なお、拡張データとして、さらに、住所算出用データ、画像データ、ＶＩＣＳデータ、建物属性データ、周辺検索データなどを設けるようにしてもよい。
【００２３】
なお、本実施の形態では、基本データのデータサイズについて上限値を設けて管理する。例えば、上限のデータサイズを３２ＫＢとする。地図データの更新によって、基本データが上限値を超えるようになった場合は、超えた分を拡張データとして管理する。例えば、当初の基本データが２０ＫＢ、拡張データが１０ＫＢのメッシュデータ１８２であって、基本データのみが更新されて４０ＫＢになるような場合を想定してみる。更新後のデータとして、基本データは３２ＫＢ内に収まるように編集し、３２ＫＢを超す８ＫＢの基本データは拡張データとして管理する。従って、拡張データは１８ＫＢとなり、メッシュデータ１８２のサイズは、３０ＫＢから５０ＫＢになる。また、当初の基本データが２０ＫＢ、拡張データが１０ＫＢのメッシュデータ１８２であって、基本データのみが更新されて３０ＫＢになる場合を想定してみる。この場合は、基本データの上限値３２ＫＢを超えないので、増加する１０ＫＢの基本データは、そのまま基本データとして追加される。その結果、更新後の基本データは３０ＫＢで拡張データは１０ＫＢとなり、メッシュデータ１８２のサイズは、３０ＫＢから４０ＫＢになる。以上のように、基本データのデータサイズに上限値を設けるのは次の理由による。
【００２４】
ナビゲーション装置１は、通常の場合、メモリの増設等をせずに何年も使用する場合がある。このため、地図データも、何年も使用するナビゲーション装置１の性能に合わせて固定サイズにするのが望ましい。しかし、建物形状データの整備の進展、地形データの詳細化進展、実地の宅地整備の進展等によって、地図データ量が増えてくることは通常起こり得る。従って、本実施の形態の地図データの構造では、メッシュ単位の地図データの更新を可能としている。
【００２５】
一方、新型のナビゲーション装置が発売された場合には、メモリ量が増える、処理能力が向上する等によってプログラムが扱えるデータ量が増加したり、新規機能の追加あるいは詳細に表示することが出来る様になる等は通常起こり得る。このような場合に、更新後の地図データは、旧型のナビゲーション装置でも新型のナビゲーション装置でも共通に使用できる構造である必要がある。
【００２６】
そのため、本実施の形態では、基本データサイズについて、旧型ナビゲーション装置でも扱えるデータサイズを維持し、これを超える分のデータは拡張データに収録するように編集する。また、旧型では使わない新規機能用データについては拡張データに収録するようにする。
【００２７】
上記において「旧型＆新型」という表現で説明した内容は、「汎用＆高級」「携帯機＆車載機」と置換えた場合においても同様のことが言える。すなわち、本実施の形態の地図データの構造は、処理能力が低い装置から処理能力の高い装置にも共通に使用できる。そして、処理能力が低い装置から処理能力が高い装置が共通に必ず使用する地図データを基本データとする。この基本データの上限サイズを、最も処理能力の低い装置のメモリサイズなどに合わせたデータサイズとする。これにより、処理能力が低い装置から処理能力の高い装置に対して、本実施の形態の地図データを共通に使用することができる。その結果、地図データの管理の効率化やコストダウンが図れる。
【００２８】
なお、当初から準備されている基本データは、処理能力が低い装置から処理能力の高い装置にも共通に使用されるので、優先度の高い種類のデータと言える。また、更新されて増える基本データは、当初から準備されている基本データよりより詳細な地図を表示する背景データや、旧機種では表示しなくても支障がないような優先度の低い背景データと言える。もちろん、更新されて増える基本データであっても、上述の上限値以内に収めて管理できる基本データであれば、当初から準備されている基本データと同一の優先度を有するデータといえる。
【００２９】
上記では、メッシュデータ１８２のデータサイズの上限値については特に規定していない。しかし、ナビゲーション装置１内のメモリの都合から、メッシュデータ１８２についてもデータサイズの上限値を規定してもよい。例えば、メッシュデータ１８２の上限値は１２８ＫＢとするなどである。なお、上記基本データの上限値３２ＫＢや、メッシュデータ１８２の上限値１２８ＫＢは、他の値であってもよい。地図データを当初規定するときのナビゲーション装置の性能や今後予測される性能の向上などを考慮して適切な値を決めればよい。
【００３０】
−ナビゲーション装置での地図データの管理−
図５は、ナビゲーション装置１での地図データの管理の様子を説明する図である。ナビゲーション装置１は、記録媒体２から全メッシュ管理情報および地図データを読み込み、さらに、リムーバブルメモリ３あるいはインターネット５を介して地図サーバ６から更新地図データを読み込み、最新の地図データを使用することができる。
【００３１】
従来のナビゲーション装置の場合、データの読み込み元はＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの記録媒体のみであった。本実施の形態のナビゲーション装置では、記録媒体２中の地図データと更新された地図データとを混在させて使用する。このため、読み書き可能メディアである不揮発性メモリ１２を有する。不揮発性メモリ１２はハードディスクやフラッシュメモリなどの不揮発性メモリで構成され、ナビゲーション装置の電源が落とされてもデータは保持される。不揮発性メモリ１２は、キャッシュメディア１２と呼んでもよい。
【００３２】
不揮発性メモリ１２は、ブロック管理情報１２４を有する。ブロック管理情報１２４は、該当ブロックの全メッシュ管理情報が記録媒体２上にあるのか不揮発性メモリ１２上にあるのかの識別情報を有する。初期値としては、各ブロックの全メッシュ管理情報は記録媒体２上にあるとして設定されている。地図データのメッシュ単位の更新に応じて、更新されたメッシュを有するブロックの全メッシュ管理情報１２５を不揮発性メモリ１２に作成し、ブロック管理情報１２４において、該当ブロックの全メッシュ管理情報は不揮発性メモリ１２上にある旨を設定する。プログラムは、まずブロック管理情報１２４を参照することにより、全メッシュ管理情報が、記録媒体２上にあるのか不揮発性メモリ１２上にあるのかを判断することができる。
【００３３】
符号１２６は、ナビゲーション装置のメモリ１５内にあるメモリであり、全メッシュ管理情報を格納する領域である。以下メモリ１２６と言う。プログラムは、全メッシュ管理情報が記録媒体２上にあるのか不揮発性メモリ１２上にあるのかを判断した後、該当メディアから全メッシュ管理情報を読み出し、メモリ１２６に格納する。メモリ１２６に読み込まれた全メッシュ管理情報１２７は、メッシュ１からメッシュｎまでのメッシュ管理情報を有する。メッシュ管理情報１２８は、位置情報１２９、格納場所１３０、オフセット１３１、サイズ１３２のデータを有する。位置情報１２９はメッシュの緯度経度などで表される位置情報であり、格納場所１３０はデータが記録媒体２にあるのか不揮発性メモリ１２にあるのかを示すデータである。オフセット１３１はメディア（記録媒体２あるいは不揮発性メモリ１２）上の位置を示すデータであり、サイズ１３２は地図データのサイズを示すデータである。
【００３４】
リムーバブルメモリ３でメッシュ単位の地図データが更新されると、該当メッシュの地図データは不揮発性メモリ１２に読み込まれ、地図データ１３３として格納される。従って、格納場所１３０の内容に基づき、更新されていない地図データは記録媒体２へアクセスし、更新された地図データは不揮発性メモリ１２へアクセスすることができる。
【００３５】
−記録媒体内のデータの構成−
次に、記録媒体２のデータについて説明する。記録媒体２は主データファイルを有する。図６は、主データファイルの構成を説明する図である。主データファイルは、全管理情報１５１と、格納データ情報１５２と、レベル管理情報１５３と、ブロック管理情報１５４と、全メッシュ管理情報１５５と、地図データ１５６とを有する。
【００３６】
全管理情報１５１は、フォーマットバージョン・リビジョン、データバージョン・リビジョン、メディア識別情報、作成年月日、作成者、カバーエリア等のデータ全体に関する情報を有する。格納データ情報１５２は、当記録媒体２中に格納しているデータの種別および格納場所を記述する。レベル管理情報１５３は、当記録媒体２中に格納している地図データの階層構造（レベル構造）、個々のレベルに付与される拡張データの種別、およびブロック管理情報の格納位置の情報を有する。このレベル管理情報１５３は、地図データの更新を行った場合、ブロック管理情報の格納場所(記録媒体２か不揮発性メモリ１２)を変更するため、不揮発性メモリ１２にコピーして使用する。
【００３７】
ブロック管理情報１５４は、個々のレベルでの全メッシュ管理情報の区割り情報、全メッシュ管理情報の格納場所、格納位置等の全メッシュ管理情報の管理情報を有する。記録媒体２がＤＶＤ駆動装置１４に搭載されたとき、不揮発性メモリ１２にコピーして使用される。全メッシュ管理情報の格納場所は、初期値として、すべて記録媒体２に設定されている。ブロック管理情報１５４は、レベルの数分作成される。
【００３８】
全メッシュ管理情報１５５は、個々のレベルのブロック単位に格納される。例えば、図６において、レベル０ではｍ個のブロックが存在し、ｍ個の全メッシュ管理情報１５５が存在する。レベル１〜レベル６においても同様である。全メッシュ管理情報１５５は、１つのブロック内に存在する全メッシュの格納場所、位置、サイズ、および履歴情報を有する。
【００３９】
地図データ１５６はメッシュ単位のデータに相当する。地図データ１５６は、記録媒体２内に格納されている全レベル全ブロックのメッシュ数の合計数分格納される。メッシュ単位の地図データの構造は図４に示した通りである。メッシュ単位の地図データは、それぞれ更新サイクルが異なる為、管理情報と更新したデータを不揮発性メモリ１２上で管理し、更新していないデータは、記録媒体２上のデータを使用する。例えば、背景データは、形状、文字等の更新が頻繁に発生するが、他の拡張データの更新はそれほど頻繁に発生しない。この為、不揮発性メモリ１２には、更新したデータを格納した方が不揮発性メモリ１２の容量を有効に使用できる。地図データ上の基本・拡張データは個別に管理するため、メッシュ内管理情報部には、個々のデータの履歴情報、格納場所、格納位置、サイズを管理する。
【００４０】
−不揮発性メモリ内のデータ構成−
不揮発性メモリ１２は、図５に示すように、ブロック管理情報１２４、全メッシュ管理情報１２５、地図データ１３３を有し、さらに、格納データ情報（不図示）とレベル管理情報（不図示）も有する。データはファイル形式で格納され、格納データ情報とレベル管理情報は主管理ファイル（不図示）として格納される。ブロック管理情報１２４はブロック管理ファイルとして格納され、全メッシュ管理情報１２５は全メッシュ管理情報ファイルとして格納され、地図データ１３３は地図データファイルとして格納される。
【００４１】
−主管理ファイル−
主管理ファイル（不図示）は、記録媒体２からコピーした格納データ情報と、レベル管理情報を格納する。格納データ情報は、当記録媒体２中のメッシュ単位のデータ以外のデータ（例えば、案内検索データ等）が更新されて不揮発性メモリ１２上に格納する際に、記録媒体２内の主データファイル中の格納データ情報をコピーして作成される。メッシュ単位のデータ以外のデータの更新データを不揮発性メモリ１２に格納する毎に、対応する管理情報の格納場所を記録媒体２から不揮発性メモリ１２に変更する。
【００４２】
また、格納データ情報はメディア識別情報を保持し、本キャッシュ情報の元となる記録媒体２との対応を図る。起動時に、本情報と記録媒体２内のメディア識別情報を比較して、一致する場合は問題ない。しかし、本情報が異なる場合(別の記録媒体が挿入されている)、不揮発性メモリ１２上の各情報で管理している、格納場所、位置、サイズが記録媒体２と不整合を起こすため、不揮発性メモリ１２上の更新データが使用できない。この様な状況が発生した場合は、記録媒体２内のデータのみでナビゲーションを行う。
【００４３】
レベル管理情報は、記録媒体２中に格納している地図データのいずれかのメッシュが更新されて不揮発性メモリ１２に格納された際に、記録媒体２内のレベル管理情報をコピーして作成される。地図データを不揮発性メモリ１２に格納する毎に該当するレベルのブロック管理情報の格納場所を記録媒体２から不揮発性メモリ１２に変更する。この際、ブロック管理情報の位置情報、サイズも不揮発性メモリ１２内の値に更新する。
【００４４】
−ブロック管理ファイル−
ブロック管理ファイルは、記録媒体２がＤＶＤ駆動装置１４に搭載されたとき、記録媒体２内の各レベルのブロック管理情報１５４を不揮発性メモリ１２にコピーして作成される。各ブロックの全メッシュ管理情報の格納場所は、初期値として、すべて記録媒体２として設定されている。地図データを更新して不揮発性メモリ１２に格納する際に、更新する地図データに該当するレベルのブロック管理情報を更新する。更新する地図データに該当する全メッシュ管理情報の格納場所を記録媒体２から不揮発性メモリ１２に変更する。この際、位置情報、サイズも不揮発性メモリ１２内の値に変更する。ブロック管理ファイルは、レベル単位で作成される。この際のファイル名称は、レベルをキーとして作成するものとする。これにより、ブロック管理ファイル名を記述しなくても良くなり、レベル管理情報サイズを節約することが出来る。
【００４５】
−全メッシュ管理情報ファイル−
全メッシュ管理情報ファイルは、該当ブロック内のメッシュの地図データを初めて更新して不揮発性メモリ１２に格納する際に、記録媒体２内の地図データに該当するブロックの全メッシュ管理情報をコピーして作成される。地図データの格納場所を記録媒体２から不揮発性メモリ１２に変更する。この際、地図データの位置情報、サイズも不揮発性メモリ１２内の値に更新する。その後、さらに該当ブロック内のメッシュが更新された場合は、すでに不揮発性メモリ１２内にある該当ブロックの全メッシュ管理情報ファイルを更新する。全メッシュ管理情報ファイルは、ブロック単位で作成される。この際のファイル名称は、レベルとブロック管理情報をキーとして作成するものとする。これにより、全メッシュ管理情報ファイル名を記述しなくても良くなり、ブロック管理情報サイズを節約することが出来る。
【００４６】
−地図データファイル−
地図データファイルは、地図データを更新して不揮発性メモリ１２に格納する際に作成する。作成の単位は、メッシュ単位とする。更新した地図データに該当する全図メッシュ管理情報は、記録媒体２内のものをコピーして作成し、実際に更新した基本・拡張データの格納場所、格納位置、サイズのみを不揮発性メモリ１２内の値に更新する。更新を行っていない、基本・拡張データは、記録媒体２内のデータを参照する。地図データファイルは、メッシュ単位で作成される。この際のファイル名称は、レベルとブロック管理情報と全図メッシュ管理情報をキーとしで作成するものとする。これにより、地図データファイル名を記述しなくても良くなり、図管理情報、ブロック管理情報サイズを節約することが出来る。
【００４７】
図４は、図３の一つのメッシュ１０３あるいはメッシュ１０５のデータ構成を示す図である。メッシュのデータは、メッシュ内管理情報１１１、背景（地図表示用）データ１１２、ロケータ用データ１１３、ネットワーク(経路計算用)データ１１４、誘導データ１１５から構成される。メッシュ内管理情報１１１と背景（地図表示用）データ１１２を基本データとし、ロケータ用データ１１３、ネットワークデータ１１４、誘導データ１１５を拡張データとする。基本データは、各レベルすべてに存在するデータである。拡張データは、固有のレベルにのみ存在するデータである。例えば、ネットワークデータは、レベル１、２、３、４にのみ存在し、ロケータデータや誘導データは、レベル０にのみ存在する。なお、拡張データとして、さらに、住所算出用データ、画像データ、ＶＩＣＳデータ、建物属性データ、周辺検索データなどを設けるようにしてもよい。
【００４８】
−地図データの基本・拡張データについて−
図４で示したように、地図データは、メッシュ内管理情報１１１と背景（地図表示用)データ１１２の基本データと、ロケータ用データ１１３、ネットワークデータ１１４、誘導データ１１５の複数の拡張データで構成される。地図データを構成する個々のデータ(フレーム)について以下説明する。
【００４９】
−メッシュ内管理情報−
メッシュ内管理情報１１１は、メッシュで分割された地図データ固有の情報および、格納している背景・拡張データの格納場所・位置・サイズ等の情報を記述する。図７は、メッシュ内管理情報１１１の構成を示す図である。メッシュ内管理情報１１１は、メッシュ情報１６１、背景管理情報１６２、拡張データ識別情報１６３、拡張データ管理情報１６４から構成される。
【００５０】
メッシュ情報１６１には、メッシュ内管理情報のサイズ、当メッシュの縦・横方向の実サイズ情報等の基本情報を格納する。背景管理情報１６２には、当メッシュの背景データ（地図表示用データ）に関する管理情報を格納する。具体的には、履歴情報、格納場所、格納位置、オフセット、サイズが格納される。履歴情報は、例えば更新情報の管理番号が格納され、値が大きいほど新しいデータであることを示す。格納場所には、記録媒体２、不揮発性メモリ１２の何れにデータを格納しているかの識別フラグが格納される。格納位置には、背景デ一タの格納位置を記述する。記録媒体２の場合、主データファイル先頭からのオフセット、不揮発性メモリ１２上の場合は、当該地図データファイル先頭からのオフセットとなる。サイズには、背景データの実サイズを格納する。
【００５１】
背景データは、１メッシュの領域をさらにｎ×ｍに分割して管理される。この為、本背景管理情報は、ｎ×ｍ個存在する。背景データの更新は、このｎ×ｍに分割された分割メッシュ単位とする。
【００５２】
拡張データは、前述したように、全レベルに全種類の拡張データが付与される訳ではない。また、付与可能な情報であっても、全てのメッシュに付与される訳ではない。例えば、水域のみのメッシュには、ネットワークデータは付かない。このため、拡張データ識別情報１６３では、当該メッシュに付与可能な拡張データの種別と、その付与状態を記述する。この付与可能な拡張データ数分、本情報で指定順に、拡張データ管理情報１６４が配置される。
【００５３】
拡張データ管理情報１６４には、個々の拡張データの管理情報を格納する。管理内容は、背景データと同じとする。拡張データの履歴情報は、拡張データ単位に管理される。
【００５４】
−背景データ−
背景データ（地図表示用データ）１１２は、メッシュ単位で管理してもよいが、本実施の形態では、さらに１メッシュの領域をｎ×ｍに分割して管理される。これは、携帯電話のような小さな画面やメモリででもデータを扱うことを可能とするためである。背景データ１１２の更新は、この分割した１単位（分割メッシュ）毎に行う。背景データの正規化サイズは、１分割メッシュあたり２５６×２５６（座標値は、０〜２５５）とする。１メッシュは、例えば４×４分割メッシュで作成する。このため、１メッシュ当たりの正規化サイズは、１０２１×１０２１となる。分割メッシュ座標２５５＝隣の分割メッシュの０となるため、２５６×４−３＝１０２１となる。
【００５５】
他の地図データに比べて正規化サイズが小さいが、背景の描画を想定した場合、３２０×２６０程度の領域に最大でも１分割メッシュしか表示しないため、実用上問題はない。また、１座標に使用するビット数を削減できる為、データ全体のサイズの削減も計れる。
【００５６】
背景形状は、最大２５６個のレイヤで管理し、レイヤ単位の描画属性で描画する。既存のナビゲーション用データは、背景データは１６程度のクラスに分割して描画属性を割り当てているが、市街図等の背景の種別が多い場合は、クラスが足りなくなり、うまく色分け等ができない。このため、既存のクラスに当たるレイヤを２５６個に拡大する。描画順は、データ格納順とする。既存のナビゲーション用データでは、同一種別の形状は、全て連続して格納している。この為、同一種別であっても描画順の異なる形状（高速高架下の道路と高速を跨ぐ道路など）を正しく表示できない、又は不必要なクラスを生成していた。形状の描画順をデータ格納順とする事で、レイヤの増加を抑える事ができる。
【００５７】
既存のナビゲーション用データの場合、表示用の道路形状と、マップマッチング・ネットワーク用道路形状を共用しているものもある。これは、表示と探索の道路形状を供用する事で、データ量の削減が計れる為である。本実施の形態では、背景データとして道路形状の格納をレベル単位で切り替える。背景形状として道路形状を格納するメリットとしては、地図描画の際に、背景・道路・文字等の複数のデータ群をアクセスせずに、１度のアクセスで地図が描画できる。また、背景としての道路で良いため、思い切ったデフォルメ、連結が可能となる為、表示データ量の削減・表示速度の向上が望める。
【００５８】
−ロケータ用データ−
ロケータ用データでは、道路をリンクとノードとリンク列という概念で表す。ノードは交差点や道路上特に指定された点を言う。リンクはノード間の道路に該当し、リンク列は１本の道路を複数のリンクで表したものである。ロケータ用道路データは、道路地図の最下層レベル０に存在し、自車位置の確認、探索結果の経路座標の取得、細街路探索等に用いる。ロケータ用データとしての道路データの構造は、既存のナビグーション用データと同様の情報を保持している。すなわち、同じ属性の道路がリンク列の形で管理された道路データの集合として管理している。道路属性は、リンク列に付与するものと、リンクあるいはノードに付与する物に大別される。
【００５９】
リンク列に付与する属性としては、道路種別、有料/無料区分、インフラ対象属性、経路計算対象フラグ等が挙げられる。リンクあるいはノードに付与する属性としては、リンク種別、幅員、交差リンク情報、規制情報、補間転座標情報が挙げられる。ロケータ用データの正規化座標は、２０４８×２０４８とする。ロケータ用データは、座標精度を要求される為、背景データ（１０２１×１０２１）と異なる正規化サイズのデータとする。
【００６０】
メッシュ単位にロケータ用データの更新を行った場合、隣接メッシュとの道路の接続をどのようにするかについて説明する。
【００６１】
ロケータ用データのリンク列データは、そのリンク列に存在するノードに関するデータの並びである。ノードに関するデータには、そのノードの位置座標、そのノードに接続するリンク番号等のデータが入る。ノードの位置座標は、正規化座標値を使用する。
【００６２】
図８は、１本の道路が隣接するメッシュにまたがって存在する場合について説明する図である。メッシュ１７１とメッシュ１７２が隣接し、リンク１７３とリンク１７５で表される１本の道路がメッシュ１７１とメッシュ１７２にまたがって存在する。メッシュの境界に位置する道路上に接続点を設け、それをノードとする。メッシュ１７１では接続点のノードとしてノード１７４が設けられ、メッシュ１７２では接続点のノードとしてノード１７６が設けられる。
【００６３】
ノードに関するデータには、ノードの位置座標とどちらか一方向につながるリンク番号が格納される。例えば、ノード１７４にはノード１７４の位置座標と右方向へ接続するリンク１７５のリンク番号が格納される。ノード１７６にはノード１７６の位置座標と左方向へ接続するリンク１７３のリンク番号が格納される。
【００６４】
メッシュ１７１とメッシュ１７２が同一履歴を有するデータであれば、接続するリンク番号により接続先が特定できる。しかし、メッシュ１７２のデータが更新されリンク１７５のリンク番号が変わる場合も生じる。そのような場合には、メッシュ境界における接続先をリンク番号では特定できなくなる。
【００６５】
本実施の形態では、データが更新されている場合、隣接するメッシュに同一の位置座標を有する接続点があるか否かを検索することにより、接続先を特定する。すなわち、接続点の正規化座標値を使用してメッシュ間の接続を行う。隣接メッシュ自体の特定は、従来通りメッシュの位置情報等を使用して行う。
【００６６】
なお、実地で道路の新規追加等が行われた場合等には、一部のメッシュのみを更新すると更新していないメッシュ側に接続する道路が無い場合がある。このような場合には、接続先が実際には存在していても、データ上は行き止まり扱いで処理を行う。このような場合には、隣接メッシュのロケ一夕用データも更新されていることが望ましい。従って、インターネット経由で地図サーバ６に接続可能な場合は、隣接メッシュの地図データの更新リクエストを自動送信するようにしてもよい。あるいは、地図データの更新リクエストの送信を使用者に促すような表示等をしてもよい。
【００６７】
−ネットワーク(経路計算用)データ−
ネットワークデータは、基準となるレベル１（縮尺率１／２５０００）を最下層として、上位の複数のレベルに拡張データとして格納する。ネットワークデータは、ロケータ用データと同様に、リンク、ノード、リンク列の概念を使用して表す。ネットワークデータは、交差点を表すノードの接続情報を表すものである。各ノードは、自ノード情報と接続される隣接ノード情報を有する。自ノード情報には、自ノードの位置座標が格納され、隣接ノード情報には自ノードに接続されるすべてのノードの情報が格納される。接続されるノードのノード情報には、そのノードのノード番号やそのノードに接続するリンク番号が格納される。
【００６８】
１つのネットワークデータの領域は、対応する地図データの領域と同じものとし、１メッシュの正規化サイズは２０４８×２０４８とする。
【００６９】
ネットワークデータの構造で、既存のナビゲーション用データと大きく異なる点は、隣接メッシュ間およびレベル間のノード、リンクの関連付けである。既存のナビゲーション用データの場合、隣接・レベル間の同一ノードの関連付けを、インデックス番号や、オフセットを用いて直接参照している。これに対して、本実施の形態では、メッシュ単位でのデータ更新が行われ、新旧のデータを混合して使用する。このため、従来のインデックス番号や、オフセットによる直接参照ができない。
【００７０】
隣接および上位下位のメッシュのネットワークデータの履歴情報が同一の場合は、従来と同様にインデックス番号等を用いた参照を行う事が出来る。しかし、履歴情報が異なる場合には、インデックス番号等を用いた参照を行うことができない。従って、本実施の形態では、ロケータ用データと同様に、メッシュ境界の接続点の座標値をキーとして使用する。レベル間を対応づけるための接続点は、必ずしもメッシュ境界にあるものではなく、上位レベル下位レベルの双方に存在するノードが選ばれる。
【００７１】
単純に、座標値をキーとして、隣接図の同一ノードを検索する場合、最下位（最詳細）レベルであればメッシュ境界上で交差する道路以外は座標値の重複がない。これは、最下位レベルの正規化座標の解像度でノード座標が定義されているからである。このため、検索時間を無視すれば必ず検索することができる。しかし、上位レベルのネットワークデータの場合、同一座標に複数のノードが存在することもあり得るため、単純な座標値のみをキーとしたのでは、検索できない。すなわち、下位レベルで異なる座標値で定義された近接した２つのノードが、上位レベルにいくと、丸められて同じ座標値で示されることがある。このような場合、どちらのノードであるかが特定できず、正しく検索することができない。
【００７２】
このため、本実施の形態では、座標キーに加えて、最下層レベルの座標値もキーとする。これにより、上位レベルにおいて重複ノードであっても、副キーの最下層レベルの座標キーが異なるため、正しく相手を検索する事が可能となる。また、最下層レベルにおいても重複ノードの発生が考えられるため、最下層の座標値に４ビット（値の範囲は０〜１５）の拡張座標を付加する。
【００７３】
従って、上位レベルのノード正規化座標を（Ｘｈ，Ｙｈ）、下位レベルのノード正規化座標を（Ｘｌ，Ｙｌ）、拡張座標をαとすると、ある上位レベルのノードの正規化座標は、（Ｘｈ，Ｙｈ）と（Ｘｌ，Ｙｌ）と（α）の組み合わせとして定義できる。
【００７４】
以上により、新旧データが混在していても、隣接メッシュ間の接続のみならず、レベル間の接続も確実に行うことができる。なお、レベル間の対応するメッシュの特定については、各レベルにレベル間対応テーブルを設けて行う。レベル間対応テーブルには、当該レベルのノードが下位レベルのどのメッシュのどのノードに対応するかの情報が入っている。従って、このレベル間対応テーブルと上述した正規化座標の定義を使用して、レベル間の接続点の対応づけを行う。このレベル間対応テーブルと上述した正規化座標を用いることで、下位レベルの一部のメッシュのみを更新した場合でも、更新後も変化していない道路については未更新の上位レベルデータとの接続を維持することができる。また、更新したメッシュにおける新規道路や形状が変化した道路については、未更新の上位レベルデータとは接続できないが、誤接続は回避できる。
【００７５】
通常メッシュの位置は、メッシュの左下角の緯度経度で表される。すなわち、全メッシュ管理情報の位置情報１２９には、メッシュの左下角の緯度経度に対応する位置情報が格納される。また、メッシュの正規化座標は、メッシュの左下角を原点とする。従って、前述した正規化座標は、緯度軽度によるメッシュの位置情報を考慮すると、地図内の位置を緯度経度に対応した２次元座標値であらわしていることになる。この２次元座標値は緯度経度に対応する値であるため、ナビゲーション装置の別、規格の別などに影響されない普遍的な値と言える。すなわち、隣接するメッシュや上下のメッシュ間の接続を、普遍的なキーを使用して行うことになる。
【００７６】
なお、上位レベルのノードの正規化座標は、上述の定義に限らず、（Ｘｈ，Ｙｈ）と（Ｘｌ，Ｙｌ）の組み合わせや、（Ｘｈ，Ｙｈ）と（α）の組み合わせで表すように定義してもよい。
【００７７】
また、下位レベルのノード正規化座標（Ｘｌ，Ｙｌ）には、必ずしも最下層のレベルの座標を使用しなくてもよい。適度に下層なレベルの座標を使用すればよい。拡張座標αは、正規化座標以外のパラメータであり、例えば、そのノードの高さデータである。また、データの生成更新に関する時間データ（情報）としてもよい。さらに、高さデータと時間データの両方としてもよい。αのデータの大きさは４ビット以上としてもよい。
【００７８】
また、上述の正規化座標の定義は、該当レベルにおける２次元座標（Ｘｈ，Ｙｈ）以外に、他のレベルの座標（Ｘｌ，Ｙｌ）あるいは高さデータ（α）などのパラメータを使用している。このパラメータは、２次元座標に追記情報を付与してレベル間の接続状況を記述する手法としているので、本実施の形態ではレベル間対応キーと呼ぶ。また、２．５次元空間キーと呼んでもよい。
【００７９】
本実施の形態では、各レベルにレベル間対応テーブルを設けて、レベル間のノードの対応を行っている。従って、各レベルのレベル間対応キーは、必ずしも下位レベルの正規化座標をすべて含む必要はない。例えば最下層レベルの正規化座標のみを含めばよい。レベル０のノード正規化座標を（Ｘ０，Ｙ０）、レベル１のノード正規化座標を（Ｘ１，Ｙ１）、レベル２のノード正規化座標を（Ｘ２，Ｙ２）、レベル３のノード正規化座標を（Ｘ３，Ｙ３）とすると、各レベルのノードのレベル間対応キーは、次のように表される。レベル０のレベル間対応キーは（Ｘ０，Ｙ０）、レベル１のレベル間対応キーは（Ｘ１，Ｙ１）と（Ｘ０，Ｙ０）の組み合わせ、レベル２のレベル間対応キーは、（Ｘ２，Ｙ２）と（Ｘ０，Ｙ０）の組み合わせ、レベル３のレベル間対応キーは、（Ｘ３，Ｙ３）＆（Ｘ０，Ｙ０）の組み合わせとなる。
【００８０】
−誘導データ−
誘導データは、最下層レベル０の地図データにのみ存在し、経路探索結果のルートの案内時に使用する。誘導データは、交差点名称の情報、道路名称の情報、方面名称の情報、方向ガイドの情報、スポットガイドの情報、周辺目標物の情報、道路建造物の情報などが格納される。
【００８１】
−リムーバブルメモリでデータ更新−
図９は、リムーバブルメモリ３で地図データを更新し、目的地付近のデータを読み出し、経路探索を行うフローチャートである。更新データはリムーバブルメモリ３で提供される。図９のフローチャートの制御は、制御装置１１で実行される。
【００８２】
ナビゲーション装置１の電源をオンすると、図９のフローチャートによるプログラムが起動される。ステップＳ１では、更新データの有無を判断する。更新データの有無の判断とは、更新データが格納されたリムーバブルメモリ３が搭載されているかどうかを判断する。更新データが有ると判断すると、ステップＳ２に進む。
【００８３】
ステップＳ２では、リムーバブルメディア３内の更新データを参照し、記録媒体２のデータに対して更新の必要なデータの全メッシュ管理情報を、記録媒体２から読み出し、不揮発性メモリ１２に書き込む。ステップＳ３では、更新データに従って、不揮発性メモリ１２に記録した全メッシュ管理情報を書き換える。ステップＳ４では、不揮発性メモリ１２に記録された全メッシュ管理情報を基に目的地付近のデータを読み出す。更新データは不揮発性メモリ１２に書きこむことを前述した。しかし、ここでは、リムーバブルメモリ３をそのまま搭載し、更新データをリムーバブルメモリ３から読み込むこととする。更新されていない地図データは、記録媒体２から読み込む。
【００８４】
一方、ステップＳ１で更新データがないと判断すると、ステップＳ５に進む。ステップＳ５では、更新の履歴が有るか否かを判断する。更新の履歴があるか否かは、不揮発性メモリ１２のブロック管理情報１２４をアクセスして判断する。ステップＳ５で更新の履歴が有ると判断すると、ステップＳ６に進む。ステップＳ６では、ブロック管理情報１２４を参照して、今までに順次書き換えてきた全メッシュ管理情報を不揮発性メモリ１２から読み出す。ステップＳ７では、ブロック管理情報１２４を参照して、不揮発性メモリ１２上に無い他の全メッシュ管理情報を記録媒体２から読み出す。ステップＳ８では、不揮発性メモリ１２および記録媒体２から読み出した全メッシュ管理情報を基に、ステップＳ４と同様に、目的地付近のデータを読み出す。
【００８５】
ステップＳ５で更新の履歴がないと判断すると、ステップＳ９に進む。ステップＳ９では、全メッシュ管理情報を記録媒体２から読み出す。次に、ステップＳ１０において、記録媒体２から読み出した全メッシュ管理情報を基に、記録媒体２から目的地付近のデータを読み出す。
【００８６】
ステップＳ１１では、読み込まれた地図データに基づいて経路探索を行う。図９のフローチャートでは、目的地付近のデータしか読み込んでいないが、現在地付近のデータも順次読み込んで経路探索を行う。
【００８７】
−地図サーバとの通信を利用したデータ更新−
図１０は、目的地付近のデータをインターネット５を介して地図サーバ６から読み込んで更新し、現在地付近および目的地付近のデータを読み出し、経路探索を行うフローチャートである。更新データはリムーバブルメモリ３および地図サーバ６から提供される。図１０のフローチャートの制御は、制御装置１１で実行される。
【００８８】
ナビゲーション装置１の電源をオンすると、図１０のフローチャートによるプログラムが起動される。ステップＳ２１では、全メッシュ管理情報の読み出し等の初期化処理を行う。図１１は、この初期化処理のフローチャートである。
【００８９】
図１１のステップＳ１０１では、更新の履歴が有るか否かを判断する。更新の履歴があるか否かは、不揮発性メモリ１２のブロック管理情報１２４をアクセスして判断する。ステップＳ１０１で更新の履歴が有ると判断すると、ステップＳ１０２に進む。ステップＳ１０２では、ブロック管理情報１２４を参照して、今までに順次書き換えてきた全メッシュ管理情報を不揮発性メモリ１２から読み出す。ステップＳ１０３では、ブロック管理情報１２４を参照して、不揮発性メモリ１２上に無い他の全メッシュ管理情報を記録媒体２から読み出す。ステップＳ１０４では、不揮発性メモリ１２および記録媒体２から読み出した全メッシュ管理情報を基に、現在地付近のデータを読み出す。次に、図１０のステップＳ２２に進む。
【００９０】
一方、ステップＳ１０１で更新の履歴がないと判断すると、ステップＳ１０５に進む。ステップＳ１０５では、全メッシュ管理情報を記録媒体２から読み出す。ステップＳ１０６において、記録媒体２から読み出した全メッシュ管理情報を基に、記録媒体２から現在地付近のデータを読み出す。次に、図１０のステップＳ２２に進む。
【００９１】
図１０に戻って、ステップＳ２２以降において目的地付近のデータを読み込む。ステップＳ２２では、地図サーバ６に新しいデータを要求し、新しいデータが存在する場合は、通信によって更新データ（目的地付近）をダウンロードする。ステップＳ２３では、更新データの有無を判断する。更新データの有無の判断とは、地図サーバ６から更新データが送られてきたか否かを判断する。更新データが有ると判断すると、ステップＳ２４に進み、更新処理を行う。
【００９２】
図１２は、この更新処理のフローチャートである。図１２のステップＳ１１１では、目的地付近のデータの更新の履歴、すなわち今までに目的地付近のデータ更新があるか否かを判断する。更新があると判断するとステップＳ１１２に進む。ステップＳ１１２では、地図サーバ６から送信された更新データに従って、すでに不揮発性メモリ１２に存在する全メッシュ管理情報を書き換える。その後、ステップＳ１１５に進む。
【００９３】
一方、ステップＳ１１１で、今までに目的地付近のデータ更新はないと判断するとステップＳ１１３に進む。ステップＳ１１３では、地図サーバ６から送信された更新データを参照し、記録媒体２のデータに対して更新の必要なデータの全メッシュ管理情報を、記録媒体２から読み出し、不揮発性メモリ１２に書き込む。ステップＳ１１４では、更新データに従って、不揮発性メモリ１２に記録した全メッシュ管理情報を書き換える。その後、ステップＳ１１５に進む。
【００９４】
ステップＳ１１５では、書き換えた全メッシュ管理情報を不揮発性メモリ１２からメモリ１２６に読み出す。ステップＳ１１６では、不揮発性メモリ１２から読み出した全メッシュ管理情報を基に目的地付近のデータを読み出す。次に、図１０のステップＳ２６に進む。
【００９５】
図１０のステップＳ２３において、地図サーバ６から送信された更新データがないと判断すると、ステップＳ２５に進む。ステップＳ２５では、既に存在するデータから目的地付近のデータを読み出す。すなわち、記録媒体２からか、前に更新されたデータの場合は不揮発性メモリ１２からか読み出す。ステップＳ２６では、読み込まれた地図データを基づいて経路探索を行う。
【００９６】
−レベル間対応キーを使用した経路探索−
図１３は、レベル間対応キーを使用した経路探索のフローチャートである。ステップＳ３１では、現在位置情報と目的地情報より、近傍の道路リンクをそれぞれ特定する。ステップＳ３２では、求められた各近傍の道路リンクから対応する経路計算用データのリンクを特定する。ステップＳ３３では、何階層（レベル）探索かを判断する。現在地と目的地の距離に応じて何階層探索かを判断する。現在地と目的地が近接している場合は、１階層経路探索処理を行い、距離が離れると、２階層経路探索処理あるいは３階層経路探索処理を行う。
【００９７】
経路探索において、通常、現在地と目的地近辺は最下層レベル（詳細側）のネットワークデータを使用する。従って、現在地と目的地が近接している場合は、すべて最下層レベルのネットワークデータを使用する、一方、現在地と目的地が離れている場合は、経路探索時間の短縮の観点から、中間の経路探索は上層レベル（広域側）のネットワークデータを使用する。従って、現在地と目的地近辺は最下層レベルのネットワークデータを使用し、中間の経路探索は上層レベルのネットワークデータを使用する。すなわち、２階層経路探索処理あるいは３階層経路探索処理を行う。
【００９８】
ステップＳ３３で、１階層経路探索処理を行うと判断した場合はステップＳ３４に進む。２階層経路探索処理を行うと判断した場合はステップＳ３５に進む。３階層経路探索処理を行うと判断した場合はステップＳ３６に進む。
【００９９】
図１４は、１階層経路探索処理のフローチャートである。ステップＳ２０１では、新たな隣接する候補ノードを抽出する。この場合、隣接する候補リンクを抽出するようにしてもよい。ステップＳ２０２では、経路探索に必要とする隣り合うメッシュの履歴情報が同じか否かを判断する。同じであると判断するとステップＳ２０７に進み、同じでないと判断するとステップＳ２０３に進む。ステップＳ２０７では、通常のポインタ・インデックスを参照して、隣接するノードを特定する。通常のポインタ・インデックスとは、ノード番号やノードＩＤを言う。
【０１００】
ステップＳ２０３では、自ノードが接続点か否かを判断する。接続点とはメッシュ間を接続するための点であり、１階層経路探索においてはメッシュ境界に位置する点が設定される。自ノードが接続点でないと判断するとステップＳ２０７に進み、自ノードが接続点でありかつ隣接ノードが接続点であると判断するとステップＳ２０４に進む。自ノードが接続点でない場合とは、自ノードに接続する隣接ノードはすべてそのメッシュ内に存在することを意味する。自ノードが接続点である場合は、隣接するメッシュ内の隣接ノードもまた接続点である。
【０１０１】
ステップＳ２０４では、自ノードと隣接ノードのレベル間対応キーを参照する。ステップＳ２０５で、自ノードと隣接ノードのレベル間対応キーが一致しているか否かを判断する。一致していると判断するとステップＳ２０８に進み、一致していないと判断するとステップＳ２０６へ進む。自ノードと隣接ノードのレベル間対応キーが一致しているということは、隣接ノードが特定できたことを意味し、隣接メッシュの同じレベル間対応キーを持つノードへ接続をする。
【０１０２】
ステップＳ２０６では、自ノードを行き止まり点として処理する。すなわち、レベル間対応キーが一致する隣接ノードが見つからなかったことは、経路がそこで途切れているこを意味する。なお、ステップＳ２０４、ステップＳ２０５の処理では、隣接メッシュ間に接続点が１つずつ存在する前提で説明をした。しかし、メッシュ境界に接続点が複数ある場合もある。そのような場合は、自ノードが隣接メッシュのどの接続点とつながるのかを検索する必要がある。従って、隣接メッシュの複数の接続点について、隣接ノードが特定できるまでステップＳ２０４とステップＳ２０５の処理を繰り返す必要がある。
【０１０３】
ステップＳ２０３で自ノードが接続点でないと判断した場合、ステップＳ２０７に進み、通常のポインタ・インデックスを参照して隣接するノードを特定する。これは、自ノードと隣接ノードは、１メッシュのデータ内にあるからである。なお、ポインタ・インデックスを参照した隣接ノードの特定は、レベル間対応キーを参照した隣接ノードの特定より、処理が簡単で速い。
【０１０４】
ステップＳ２０８では、特定されたノード情報を使用してダイクストラによる経路探索処理を行い、ステップＳ２０９に進む。ステップＳ２０９では、すべての経路探索の処理が終了したかを判断し、終了していないと判断する場合はステップＳ２０１に戻る。終了していると判断すると、１階層経路探索処理を終了する。
【０１０５】
図１５は、２階層経路探索処理のフローチャートである。ステップＳ２１１では、現在位置側と目的地側の下層レベルのメッシュを使用した経路探索処理を行う。これは、図１４の１階層経路探索処理と同じ処理である。ステップＳ２１２では、下層レベルと上層レベルのノードを接続する処理を行う。図１６は、ステップＳ２１２の処理の詳細を示すフローチャートである。
【０１０６】
図１６のステップＳ２２１において、前述したレベル間対応テーブルより新たな上層候補ノードを抽出する。レベル間対応テーブルは、上層レベル側（広域側）に設けられ、下層レベル側（詳細側）のどのメッシュのどのノードに対応するかの情報が格納されている。ステップＳ２２２では、対応する上層と下層のメッシュの履歴情報が同じか否かを判断する。ステップＳ２２２で、対応する上層と下層のメッシュの履歴情報が異なると判断した場合はステップＳ２２３に進む。
【０１０７】
ステップＳ２２３では、レベル間対応テーブル内の下層レベルのノードのレベル間対応キーを参照する。ステップＳ２２４では、レベル間対応テーブル内の下層レベルのノードのレベル間対応キーと、探索で求められた下層メッシュ内のノードのレベル間対応キーが一致するか否かを判断する。一致すると判断した場合はステップＳ２２７に進み、一致しないと判断した場合はステップＳ２２５に進む。ステップＳ２２５では、下層レベルの自ノードを行き止まり点として処理する。
【０１０８】
一方、ステップＳ２２２で対応する上層レベルと下層レベルのメッシュの履歴情報が同じと判断した場合は、ステップＳ２２６に進む。ステップＳ２２６では、ノードＩＤ番号を参照（通常処理）して上層レベルのノードを特定する。ステップＳ２２７では、特定された下層ノードに対応する上層ノードを候補として保存する。ステップＳ２２８では、処理が終了したか否かを判断し、まだ続行する場合はステップＳ２２１に戻り処理を繰り返す。終了すると判断する場合は、図１６の下層レベルと上層レベルのノードを接続する処理を終了して、図１５のステップＳ２１３に進む。
【０１０９】
ステップＳ２１３では、上層レベルのメッシュを使用した経路探索処理をする。ステップＳ２１３の処理は、図１４の１階層経路探索処理と同様の処理であるので、その説明を省略する。ステップＳ２１４では、下層レベルと上層レベルで求めた候補経路の組み合わせより最短経路を求める。
【０１１０】
以上説明したように、本実施の形態の地図データの構造や地図データの処理方法を使用した場合、次のような効果を奏する。
（１）メッシュ単位で地図データの更新ができるので、地図データの一部のみ更新する場合、地図データが格納されたＤＶＤ−ＲＯＭなどの記録媒体全体を新しいものにする必要がない。更新の最小単位をメッシュ単位、すなわち基本・拡張データ単位とする事が可能となり、不必要なデータ更新に掛かる通信量(コスト)も低減することができる。また、個々の基本、拡張データの更新のサイクルを異ならせることが可能となる。
（２）更新データをインターネット経由の通信によっても提供するので、迅速にかつ安い費用で最新の更新データを提供することができる。
（３）メッシュデータを基本データと拡張データとに分離しているので、地図表示のみしか必要ないナビゲーション装置や、経路探索や誘導処理を行うようなナビゲーション装置があっても、共通の地図データを使用することが可能である。さらに、拡張データにおいても、データの種類に応じて分離している。これにより、ある拡張データは必要であるが、他の拡張データは必要ない場合も、同じ仕組みの更新データ提供で対応できる。また、背景データと他のロケータ用データやネットワークデータを分離して管理している。このため、地図描画の際に、背景・道路・文字等の複数のデータ群をアクセスせずに、１度のアクセスで地図が描画できる。さらに、背景としての道路で良いため、思い切ったデフォルメ、連結が可能となり、表示データ量の削減・表示速度の向上が望める。
（４）メッシュデータを基本データと拡張データとに分離しているので、携帯電話などの簡易な装置や車載用ナビゲーション装置などの高級な装置にも、同一の地図データベースで地図データの提供をすることができる。例えば、携帯電話での地図表示やナビゲーションでは、基本データのみを提供する。車載用ナビゲーション装置には、基本データと拡張データを提供する。
（５）隣接メッシュ間や上下レベル間のデータの接続に、緯度経度に対応する２次元座標値を使用するようにしているので、データ更新の方式が機種に依存したり、規格に依存したりすることを防止することができる。すなわち、緯度経度に対応する２次元座標は普遍的なデータと言えるので、これらのデータを使用することにより、データ更新の方式を標準化できる。
（６）２次元座標値プラスアルファのパラメータを使用しているので、ノード間の特定が確実に行うことができる。例えば、高さデータをプラスアルファのパラメータとすると、道路が高架して交差する接続点であっても、確実に区別することができる。また、下層レベルの座標値をプラスアルファのパラメータとすると、下層レベルの解像度でノードなどが特定できる。すなわち、縮尺率の異なる上下レベル間においても、データを確実に接続することができる。
（７）不揮発性メモリに全メッシュ管理情報を格納しながら、地図データを管理しているので、更新データの管理を容易かつ確実に行うことができる。これにより、ナビゲーション装置のプログラム開発などが容易となる。
（８）各境界ノードの接続先を得る為に同一座標値を持つ境界ノードを隣接メッシュから検索する手法を全てのメッシュについて行なうのではなく更新メッシュのみについて行ない、更新の無いメッシュについては従来のポインタ参照式の検索手法を用いるようにしている。これにより、データ処理速度の低下を最小限に出来る。
（９）全国分の更新データの一括配信を受けるのではなく、ユーザが選んだ地域のみの配信を受けるので、その受信時間は必要最小限で済む。また、全ての地図データを読み書き可能な大容量記憶装置に収録するのではないため、ユーザが要求する更新データのみを収録可能な記憶容量で十分である。
（１０）また、上記実施の形態において、レベル間対応キーの一部として拡張座標αを設け、このパラメータを、例えば、そのノードの高さデータや、データの生成更新に関する時間データ（情報）としてもよい旨説明した。このような拡張座標αはメッシュ境界にある全ての境界ノードに持たせる必要はなく、一部の特殊なノードにのみ持たせるようにしてもよい。例えば、メッシュ境界上で交差し同一座標を持つ境界ノードにのみ持たすようにしてもよい。これにより、データ量の増加やデータ処理速度の低下を最小限に出来る。
【０１１１】
上記の実施の形態では、ナビゲーション装置の制御装置１１が実行する制御プログラムはＲＯＭに格納されている例で説明をしたが、この内容に限定する必要はない。制御プログラムやそのインストールプログラムをＤＶＤなどの記録媒体で提供してもよい。なお、記録媒体はＤＶＤに限定する必要はなく、ＣＤ−ＲＯＭ、磁気テープやその他のあらゆる記録媒体を使用するようにしてもよい。
【０１１２】
さらに、それらのプログラムをインターネットなどに代表される通信回線などの伝送媒体を介して提供することも可能である。すなわち、プログラムを、伝送媒体を搬送する搬送波上の信号に変換して送信することも可能である。プログラムを記録媒体やインターネットで提供する場合は、図１と同じような構成で提供すればよい。例えば、記録媒体２をプログラム提供の記録媒体にし、地図サーバ６をアプリケーションプログラムを提供するサーバーとすればよい。
【０１１３】
また、上述の制御プログラムをパソコン上で実行させてカーナビゲーション装置を実現するようにしてもよい。その場合、現在地検出装置１３や入力装置１９などは、パソコンの所定のＩ／Ｏポートなどに接続するようにすればよい。
【０１１４】
上記の実施の形態では、リムーバブルメモリ３から更新データを提供する例を説明したが、この内容に限定する必要はない。更新用データをＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどに書きこんで、記録媒体２を一時的に入れ替えて提供するようにしてもよい。
【０１１５】
上記の実施の形態では、記録媒体２から初期の地図データを読み込む例を説明したが、この内容に限定する必要はない。初期の地図データをインターネット５を介して受け取って不揮発性メモリ１２に格納し、その後前述した手法で更新管理するようにしてもよい。また、インターネット５を介して必要な地図データをその都度受け取り、その都度不揮発性メモリ１２に格納し、その後更新がある場合は、前述した手法で更新管理をしてもよい。
【０１１６】
上記の実施の形態では、ナビゲーション処理として経路探索の例を説明したが、この内容に限定する必要はない。上記地図データを使用して、地図表示、経路誘導などの各種のナビゲーション処理を行うことができる。
【０１１７】
上記の実施の形態では、不揮発性メモリ１２はナビゲーション装置１の内部に設けられる例を説明したが、この内容に限定する必要はない。ケーブルなどによって接続される外部記憶装置であってもよい。
【０１１８】
上記の実施の形態では、背景（地図表示用）データを基本データとし、ネットワークデータを拡張データとする例を説明したが、この内容に限定する必要はない。例えば、ネットワークデータを基本データとするようにしてもよい。これは、地図を表示しないアプリケーションに地図データ（ネットワークデータ等）を使用する場合などである。具体的には、経路探索をし、車両の進行方向を矢印などでのみ誘導するようなアプリケーションに使用する場合などである。このようなナビゲーション装置においては、背景（地図表示用）データは必要がないからである。このとき、ネットワークデータが最も優先度の高いデータとなり、ネットワークデータのみがメッシュ単位に更新される場合も生じる。すなわち、基本データは、それぞれのアプリケーションにおいて、例えば所定の複数の機種に共通に使用する最も優先度の高い種類の地図データとすればよい。
【０１１９】
上記では、種々の実施の形態および変形例を説明したが、本発明はこれらの内容に限定されるものではない。本発明の技術的思想の範囲内で考えられるその他の態様も本発明の範囲内に含まれる。
【０１２０】
【発明の効果】
本発明は、以上説明したように構成しているので、次のような効果を奏する。メッシュ単位で地図データの更新ができるので、地図データの一部のみ更新する場合、地図データが格納されたＤＶＤ−ＲＯＭなどの記録媒体全体を新しいものにする必要がない。
また、メッシュデータを基本データと拡張データとに分離しているので、地図表示のみしか必要ないナビゲーション装置や、経路探索や誘導処理を行うようなナビゲーション装置があっても、共通の地図データを使用することが可能である。さらに、基本データである背景データのみを、思い切ったデフォルメ、表示データ量の削減が可能となり、表示速度の向上が望める。
さらに、隣接メッシュ間や上下レベル間のデータの接続に、緯度経度に対応する２次元座標値を使用するようにしているので、データ更新の方式が機種に依存したり、規格に依存したりすることを防止することができる。さらに、２次元座標値プラスアルファのパラメータを使用しているので、メッシュ間やレベル間の接続点ノードの特定を確実に行うことができる。
【図面の簡単な説明】
【図１】本発明の地図データの構造を有する地図データの授受について説明する図である。
【図２】車載用ナビゲーション装置のブロック図である。
【図３】地図データのレベル、ブロック、メッシュの関係を説明する概念図である。
【図４】図３の一つのメッシュのデータ構成を示す図である。
【図５】ナビゲーション装置での地図データの管理の様子を説明する図である。
【図６】主データファイルの構成を説明する図である。
【図７】メッシュ内管理情報の構成を示す図である。
【図８】１本の道路が隣接するメッシュにまたがって存在する場合について説明する図である。
【図９】リムーバブルメモリで地図データを更新し、目的地付近のデータを読み出し、経路探索を行うフローチャートである。
【図１０】目的地付近のデータをインターネットを介して地図サーバから読み込んで更新し、現在地付近および目的地付近のデータを読み出し、経路探索を行うフローチャートである。
【図１１】図１０のステップＳ２１の初期化処理のフローチャートである。
【図１２】図１０のステップＳ２４の更新処理のフローチャートである。
【図１３】レベル間対応キーを使用した経路探索のフローチャートである。
【図１４】１階層経路探索処理のフローチャートである。
【図１５】２階層経路探索処理のフローチャートである。
【図１６】図１５のステップＳ２１２の処理の詳細を示すフローチャートである。
【符号の説明】
１  ナビゲーション装置
２  記録媒体
３  リムーバブルメモリ
４  通信装置
５  インタネット
６  地図サーバ
７  地図データベース
８  案内検索データベース
１１  制御装置
１２  不揮発性メモリ
１３  現在地検出装置
１４  ＤＶＤ駆動装置
１５  メモリ
１６  通信インターフェース
１７  リムーバブルメモリ読込装置
１８  モニタ
１９  入力装置
【図１】
0004037167.tif 000002
【図２】
0004037167.tif 000003
【図３】
0004037167.tif 000004
【図４】
0004037167.tif 000005
【図５】
0004037167.tif 000006
【図６】
0004037167.tif 000007
【図７】
0004037167.tif 000008
【図８】
0004037167.tif 000009
【図９】
0004037167.tif 000010
【図１０】
0004037167.tif 000011
【図１１】
0004037167.tif 000012
【図１２】
0004037167.tif 000013
【図１３】
0004037167.tif 000014
【図１４】
0004037167.tif 000015
【図１５】
0004037167.tif 000016
【図１６】
0004037167.tif 000017