(57)【要約】【課題】リンクの特定が確実にでき、地図データの処理を行うことができる地図データ処理装置を提供すること。【解決手段】地図データ処理装置は、道路上の点をノードとし、隣接するノード間の道路をリンクとして表し、ノードを特定する情報は緯度経度に関する位置情報で構成され、リンクを特定する情報は対象リンク両端のノードの緯度経度に関する位置情報の組み合わせで構成される地図に関する情報を有する地図データを取得する地図データ取得手段と、地図データ取得手段により取得された地図データを使用して地図データの処理を行う処理手段とを備え、処理手段は、対象リンク両端のノードの緯度経度に関する位置情報の組み合わせで構成されるリンクを特定する情報を使用して、地図データの処理を行う。【選択図】図１９
2008233918.tif 000002
【特許請求の範囲】
【請求項１】
地図に関する情報を有し、地図データ処理装置により処理可能な地図データの構造であって、
前記地図に関する情報は、同種の情報要素が複数集合して構成され、
前記地図に関する情報は、前記地図データ処理装置において、前記情報要素単位で更新可能なように構成され、
前記地図に関する情報は、前記情報要素単位の更新に応じて更新される前記地図に関する情報の管理情報が設けられるよう構成されていることを特徴とする地図データの構造。
【請求項２】
請求項１記載の地図データの構造において、
道路上の点をノードとして、隣接するノード間の道路をリンクとして、連続した１以上のリンクの集合をリンク列として道路を表し、
前記情報要素は、１つの前記リンク列に関する情報であることを特徴とする地図データの構造。
【請求項３】
請求項２記載の地図データの構造において、
前記各リンク列に関する情報は、自己のリンク列に含まれるノードの位置情報を有することを特徴とする地図データの構造。
【請求項４】
請求項２〜３のいずれか１項に記載の地図データの構造において、
前記各リンク列に関する情報は、自己のリンク列に関する誘導情報を有することを特徴とする地図データの構造。
【請求項５】
請求項３に記載の地図データの構造において、
前記地図の複数の異なる縮尺率に対応する複数のレベルを定義し、
より広域な地図を表すより小さい値の縮尺率のレベルを上位側レベルとし、
前記地図に関する情報は、前記複数のレベルに対応して複数セット設けられ、
所定レベルの前記リンク列に関する情報に含まれるノードの位置情報は、前記所定レベルにおけるノードの位置情報とともに、前記所定レベルの下位側レベルの対応するノードの位置情報も含むことを特徴とする地図データの構造。
【請求項６】
請求項１記載の地図データの構造において、
前記地図に関する情報は、道路地図を表示するための背景に関する情報であり、
前記情報要素は、１つの表示管理単位の背景に関する情報であることを特徴とする地図データの構造。
【請求項７】
請求項６記載の地図データの構造において、
前記１つの表示管理単位の背景に関する情報は、背景に関する１つのポリゴン、あるいは１つのポリライン、あるいは１つの点に関する情報であることを特徴とする地図データの構造。
【請求項８】
請求項６〜７のいずれか１項に記載の地図データの構造において、
前記１つの表示管理単位の背景に関する情報は、描画順位に関する情報を有し、
前記地図に関する情報は、複数集合した前記１つの表示管理単位の背景に関する情報のいずれかが更新されたとき、前記描画順位に応じて、複数集合した前記１つの表示管理単位の背景に関する情報を並べ替えることが可能な構造であることを特徴とする地図データの構造。
【請求項９】
請求項１記載の地図データの構造において、
前記情報要素は、道路地図を表示するための１つの名称に関する情報であることを特徴とする地図データの構造。
【請求項１０】
請求項９に記載の地図データの構造において、
前記１つの名称に関する情報は、描画順位に関する情報を有し、
前記地図に関する情報は、複数集合した前記１つの名称に関する情報のいずれかが更新されたとき、前記描画順位に応じて、複数集合した前記１つの名称に関する情報を並べ替えることが可能な構造であることを特徴とする地図データの構造。
【請求項１１】
請求項１記載の地図データの構造において、
道路上の点をノードとし、
前記地図に関する情報は、経路計算に使用される前記ノードの接続に関する情報であり、
前記情報要素は、前記ノード単位で管理される情報であることを特徴とする地図データの構造。
【請求項１２】
請求項１１記載の地図データの構造において、
前記ノード単位で管理される情報は、自己のノードに関する情報と、自己のノードに隣接するノードに関する情報を有することを特徴とする地図データの構造。
【請求項１３】
請求項１１〜１２のいずれか１項に記載の地図データの構造において、
前記地図の複数の異なる縮尺率に対応する複数のレベルを定義し、
より広域な地図を表すより小さい値の縮尺率のレベルを上位側レベルとし、
前記地図に関する情報は、前記複数のレベルに対応して複数セット設けられ、
所定レベルの前記ノード単位で管理される情報に含まれるノードの位置情報は、前記所定レベルにおけるノードの位置情報とともに、前記所定レベルの下位側レベルの対応するノードの位置情報も含むことを特徴とする地図データの構造。
【請求項１４】
請求項１記載の地図データの構造において、
道路上の点をノードとし、
前記地図に関する情報は、経路計算に使用される前記ノードの接続に関する情報であり、
前記地図の複数の異なる縮尺率に対応する複数のレベルを定義し、
より広域な地図を表すより小さい値の縮尺率のレベルを上位側レベルとし、
前記地図に関する情報は、前記複数のレベルに対応して複数セット設けられ、
前記情報要素は、所定レベルのノードに関する情報に対応する下位側レベルのノードに関する情報であることを特徴とする地図データの構造。
【請求項１５】
請求項１４に記載の地図データの構造において、
前記ノードに関する情報に含まれるノードの位置情報は、ノードが含まれるレベルにおけるノードの位置情報とともに、前記ノードが含まれるレベルの下位側レベルの対応するノードの位置情報も含むことを特徴とする地図データの構造。
【請求項１６】
地図に関する情報を有し、地図データ処理装置により処理可能な地図データの構造であって、
道路上の点をノードとし、隣接するノード間の道路をリンクとして表し、
前記ノードを特定する情報は、緯度経度に関する位置情報で構成され、
前記リンクを特定する情報は、対象リンク両端のノードの前記緯度経度に関する位置情報の組み合わせで構成されることを特徴とする地図データの構造。
【請求項１７】
請求項１６記載の地図データの構造において、
前記リンクを特定する情報は、前記対象リンク両端のノードの緯度経度に関する位置情報の組み合わせの順序により、該対象リンクの方向を特定することを特徴とする地図データの構造。
【請求項１８】
請求項１６〜１７のいずれか１項に記載の地図データの構造において、
前記地図の複数の異なる縮尺率に対応する複数のレベルを定義し、
より広域な地図を表すより小さい値の縮尺率のレベルを上位側レベルとし、
前記地図に関する情報は、前記複数のレベルに対応して複数セット設けられ、
所定レベルの前記ノードの位置情報は、前記所定レベルにおけるノードの位置情報とともに、前記所定レベルの下位側レベルの対応するノードの位置情報も含むことを特徴とする地図データの構造。
【請求項１９】
請求項１〜１８のいずれか１項に記載の地図データの構造において、
前記情報要素は、自己の情報要素に関する情報が有効か無効かを示す識別情報を有することを特徴とする地図データの構造。
【請求項２０】
請求項１〜１９記載の地図データの構造を有する地図データが記録された記録媒体を搭載する記録媒体駆動手段と、
前記情報要素単位の地図に関する情報の更新データを取得する更新データ取得手段と、
前記記録媒体に記録された地図データと、前記更新データ取得手段により取得された更新データとに基づき、地図データの処理を行う処理手段とを備えたことを特徴とする地図データ処理装置。
【請求項２１】
請求項１〜１９記載の地図データの構造を有する地図データを記録したことを特徴とするコンピュータあるいは地図データ処理装置に読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、地図データの構造、地図データ処理装置、および該地図データの構造を有するデータを記録した記録媒体に関する。
【背景技術】
【０００２】
従来、ナビゲーション装置で使用される道路地図などの地図データは、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの記録媒体で提供されていた。また、通信を使用して車両搭載のナビゲーション装置に地図データを提供することも行われている。
【０００３】
【特許文献１】特開平４−４６３７９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、記録媒体などで提供される大容量の地図データの一部を効率よく更新できる仕組みが提供されていなかった。
【０００５】
本発明は、記録媒体などで提供される大容量の地図データの一部を効率よく更新できる地図データの構造、そのような構造を有する地図データを使用する地図データ処理装置、およびそのような構造を有する地図データを記録した記録媒体を提供することにある。
【課題を解決するための手段】
【０００６】
上記提供を達成するために、請求項１の発明は、地図に関する情報を有し、地図データ処理装置により処理可能な地図データの構造に適用され、地図に関する情報は、同種の情報要素が複数集合して構成され、地図に関する情報は、地図データ処理装置において、情報要素単位で更新可能なように構成され、地図に関する情報は、情報要素単位の更新に応じて更新される地図に関する情報の管理情報が設けられるよう構成されているものである。
請求項２の発明は、請求項１記載の地図データの構造において、道路上の点をノードとして、隣接するノード間の道路をリンクとして、連続した１以上のリンクの集合をリンク列として道路を表し、情報要素は、１つのリンク列に関する情報であることとするものである。
請求項３の発明は、請求項２記載の地図データの構造において、各リンク列に関する情報は、自己のリンク列に含まれるノードの位置情報を有することとするものである。
請求項４の発明は、請求項２〜３のいずれか１項に記載の地図データの構造において、各リンク列に関する情報は、自己のリンク列に関する誘導情報を有することとするものである。
請求項５の発明は、請求項３に記載の地図データの構造において、地図の複数の異なる縮尺率に対応する複数のレベルを定義し、より広域な地図を表すより小さい値の縮尺率のレベルを上位側レベルとし、地図に関する情報は、複数のレベルに対応して複数セット設けられ、所定レベルのリンク列に関する情報に含まれるノードの位置情報は、所定レベルにおけるノードの位置情報とともに、所定レベルの下位側レベルの対応するノードの位置情報も含むこととするものである。
請求項６の発明は、請求項１記載の地図データの構造において、地図に関する情報は、道路地図を表示するための背景に関する情報であり、情報要素は、１つの表示管理単位の背景に関する情報であることとするものである。
請求項７の発明は、請求項６記載の地図データの構造において、１つの表示管理単位の背景に関する情報は、背景に関する１つのポリゴン、あるいは１つのポリライン、あるいは１つの点に関する情報であることするものである。。
請求項８の発明は、請求項６〜７のいずれか１項に記載の地図データの構造において、１つの表示管理単位の背景に関する情報は、描画順位に関する情報を有し、地図に関する情報は、複数集合した１つの表示管理単位の背景に関する情報のいずれかが更新されたとき、描画順位に応じて、複数集合した１つの表示管理単位の背景に関する情報を並べ替えることが可能な構造であることとするものである。
請求項９の発明は、請求項１記載の地図データの構造において、情報要素は、道路地図を表示するための１つの名称に関する情報であることとするものである。
請求項１０の発明は、請求項９に記載の地図データの構造において、１つの名称に関する情報は、描画順位に関する情報を有し、地図に関する情報は、複数集合した１つの名称に関する情報のいずれかが更新されたとき、描画順位に応じて、複数集合した１つの名称に関する情報を並べ替えることが可能な構造であることするものである。。
請求項１１の発明は、請求項１記載の地図データの構造において、道路上の点をノードとし、地図に関する情報は、経路計算に使用されるノードの接続に関する情報であり、情報要素は、ノード単位で管理される情報であることとするものである。
請求項１２の発明は、請求項１１記載の地図データの構造において、ノード単位で管理される情報は、自己のノードに関する情報と、自己のノードに隣接するノードに関する情報を有することとするものである。
請求項１３の発明は、請求項１１〜１２のいずれか１項に記載の地図データの構造において、地図の複数の異なる縮尺率に対応する複数のレベルを定義し、より広域な地図を表すより小さい値の縮尺率のレベルを上位側レベルとし、地図に関する情報は、複数のレベルに対応して複数セット設けられ、所定レベルのノード単位で管理される情報に含まれるノードの位置情報は、所定レベルにおけるノードの位置情報とともに、所定レベルの下位側レベルの対応するノードの位置情報も含むこととするものである。
請求項１４の発明は、請求項１記載の地図データの構造において、道路上の点をノードとし、地図に関する情報は、経路計算に使用されるノードの接続に関する情報であり、地図の複数の異なる縮尺率に対応する複数のレベルを定義し、より広域な地図を表すより小さい値の縮尺率のレベルを上位側レベルとし、地図に関する情報は、複数のレベルに対応して複数セット設けられ、情報要素は、所定レベルのノードに関する情報に対応する下位側レベルのノードに関する情報であることとするものである。
請求項１５の発明は、請求項１４に記載の地図データの構造において、ノードに関する情報に含まれるノードの位置情報は、ノードが含まれるレベルにおけるノードの位置情報とともに、ノードが含まれるレベルの下位側レベルの対応するノードの位置情報も含むこととするものである。
請求項１６の発明は、地図に関する情報を有し、地図データ処理装置により処理可能な地図データの構造に適用され、道路上の点をノードとし、隣接するノード間の道路をリンクとして表し、ノードを特定する情報は、緯度経度に関する位置情報で構成され、リンクを特定する情報は、対象リンク両端のノードの緯度経度に関する位置情報の組み合わせで構成されるものである。
請求項１７の発明は、請求項１６記載の地図データの構造において、リンクを特定する情報は、対象リンク両端のノードの緯度経度に関する位置情報の組み合わせの順序により、該対象リンクの方向を特定することとするものである。
請求項１８の発明は、請求項１６〜１７のいずれか１項に記載の地図データの構造において、地図の複数の異なる縮尺率に対応する複数のレベルを定義し、より広域な地図を表すより小さい値の縮尺率のレベルを上位側レベルとし、地図に関する情報は、複数のレベルに対応して複数セット設けられ、所定レベルのノードの位置情報は、所定レベルにおけるノードの位置情報とともに、所定レベルの下位側レベルの対応するノードの位置情報も含むこととするものである。
請求項１９の発明は、請求項１〜１８のいずれか１項に記載の地図データの構造において、情報要素は、自己の情報要素に関する情報が有効か無効かを示す識別情報を有することとするものである。
請求項２０の発明は、請求項１〜１９記載の地図データの構造を有する地図データが記録された記録媒体を搭載する記録媒体駆動手段と、情報要素単位の地図に関する情報の更新データを取得する更新データ取得手段と、記録媒体に記録された地図データと、更新データ取得手段により取得された更新データとに基づき、地図データの処理を行う処理手段とを備えたものである。
請求項２１の発明は、コンピュータあるいは地図データ処理装置に読み取り可能な記録媒体に適用され、請求項１〜１９記載の地図データの構造を有する地図データを記録したものである。
【発明の効果】
【０００７】
本発明は、地図に関する情報を構成する情報要素単位で更新可能にしているので、地図データの一部のみが更新可能となり、更新に伴う費用の削減、時間の削減が達成できる。
【発明を実施するための最良の形態】
【０００８】
図１は、本実施の形態において、地図表示用データや誘導データや経路計算用データなどの地図データの授受について説明する図である。車載用ナビゲーション装置１は、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの記録媒体２から、地図データや管理情報や案内検索データなどを読み取る。リムーバブルメモリ３からは、地図データなどの更新データの提供を受ける。リムーバブルメモリ３は、地図データの一部を更新するために更新データ等が記録された取り替え可能な記録媒体である。
【０００９】
また、ナビゲーション装置１は、携帯電話などの通信装置４とも接続可能である。ナビゲーション装置１は、通信装置４を介してインタネット５に接続し、さらにインターネット５を介して地図サーバ６に接続することができる。地図サーバ６は、古い地図データから最新の地図データまでを地図データベース７に保有し、また、古い案内検索データから最新の案内検索データまでを案内検索データベース８に保有する。従って、地図サーバ６は、地図データの一部を更新する更新データをインターネット５を介してナビゲーション装置１に提供することができる。なお、案内検索データとは、ＰＯＩ等の位置情報、種別、名称等の属性情報を格納したデータである。
【００１０】
ナビゲーション装置１は、制御装置１１と不揮発性メモリ１２を有する。制御装置１１は、マイクロプロセッサおよびその周辺回路から構成される。不揮発性メモリ１２は、ナビゲーション装置１の内部に設けられたハードディスクやフラッシュメモリなどの不揮発性メモリである。不揮発性メモリ１２は、ナビゲーション装置１の電源が落とされても、書きこまれたデータが消えない記憶装置であればどのようなものでもよい。
【００１１】
記録媒体２は、一旦ナビゲーション装置１に搭載すると、新たな記録媒体２と入れ替えない限りナビゲーション装置１に搭載したままの状態となる。従って、リムーバブルメモリ３に対して固定メディアと称してもよい。地図データベース７や案内検索データベース８は、新旧すべての地図データや案内検索データなどを有しているためマザーデータのデータベースである。地図サーバ６は、地図データベース７や案内検索データベース８を使用して、初期の（更新前の）地図データなどを有する記録媒体２や、更新用データを有するリムーバブルメモリ３を準備することができる。
【００１２】
図２は、車載用ナビゲーション装置１のブロック図である。ナビゲーション装置１は、制御装置１１、不揮発性メモリ１２、現在地検出装置１３、ＤＶＤ駆動装置１４、メモリ１５、通信インターフェース１６、リムーバブルメモリ読込装置１７、モニタ１８、入力装置１９を有する。
【００１３】
現在地検出装置１３は車両の現在地を検出する現在地検出装置であり、例えば車両の進行方位を検出する方位センサや車速を検出する車速センサやＧＰＳ（Global Positioning System）衛星からのＧＰＳ信号を検出するＧＰＳセンサ等から成る。ＤＶＤ駆動装置１４は、記録媒体２を搭載して地図データなどを読み込む装置である。本実施の形態では、記録媒体２はＤＶＤ−ＲＯＭとする。なお、ＣＤ−ＲＯＭや他の記録媒体であってもよい。
【００１４】
メモリ１５は、現在地検出装置１３によって検出された車両位置情報等を格納したり、制御装置１１が演算した推奨経路上のノード情報やリンク情報等を格納するメモリである。さらに、後述するメッシュ管理テーブルを格納したりもする。メモリ１５は制御装置１１のワーキングエリアである。通信インターフェース１６は、通信装置４を接続するインターフェースである。通信インターフェース１６を介して携帯電話の利用や、インターネットとの接続が可能である。リムーバブルメモリ読込装置１７は、リムーバブルメモリ３を装填しリムーバブルメモリ３からデータを読み込むことが可能な装置である。
【００１５】
モニタ１８は、地図や推奨経路や各種情報を表示する表示装置である。モニタ１８は、ナビゲーション装置本体の一部として一体に設けてもよいし、筐体としては別々に設けてもよい。さらに、モニタ１８のみを、ナビゲーション装置本体とケーブルなどによって接続し、分離した位置に設けるようにしてもよい。入力装置１９は、経路探索時に車両の目的地等を入力したりする入力装置である。リモコンであってもよいし、モニタ１８の画面上に設けられたタッチパネルなどで構成してもよい。制御装置１１は、現在地検出装置１３で検出された車両の現在地情報と記録媒体２や不揮発性メモリ１２に格納された地図データなどを使用して、道路地図の表示、経路計算（経路探索）、経路誘導等の各種のナビゲーション処理を行う。なお、制御装置１１が実行する各種の処理プログラムは、制御装置１１内部に設けられたＲＯＭ（不図示）に組み込まれている。
【００１６】
−地図データの構造−
上述した地図データのデータ構造について、さらに詳しく説明する。地図データは、地図に関する情報であり、道路データ、誘導データ、背景データ、名称データ、経路計算用データなどである。道路データは、道路の表示や車両の現在地の特定やマップマッチングなどに使用されるデータである。誘導データは、交差点名称・道路名称・方面名称・方向ガイド施設情報などからなり、演算された推奨経路に基づき運転者等に推奨経路を誘導する際に用いられる。背景データは、道路や道路地図の背景を表示するためのデータである。名称データは、地名や建物の名称などからなり、道路地図を表示するときに使用されるデータである。経路計算用データは、道路形状とは直接関係しない分岐情報などから成るネットワークデータであり、主に推奨経路を演算（経路探索）する際に用いられる。
【００１７】
本実施の形態の地図データは、レベル、ブロック、メッシュという概念で管理する。本実施の形態では、地図データを縮尺率が異なる７つのレベルに分け、最詳細の縮尺率のレベルをレベル０とし、最広域地図のレベルをレベル６とする。各レベルは縮尺率が異なる地図データを含むものであるが、対象となる領域は各レベルとも同じである。すなわち、日本全土が対象であると、各レベルごとに縮尺率が異なる日本全土の地図データを有する。例えば、レベル０では縮尺率１／６２５０、レベル１では縮尺率１／２５０００、レベル２では縮尺率１／１０００００、レベル３では縮尺率１／４０００００、レベル４では縮尺率１／１６０００００、レベル５では縮尺率１／６４０００００、レベル６では縮尺率１／１２８００００００の日本全土の地図データを有する。すなわち、レベル０〜６に対応して７つの地図データのセットがある。レベル０側を下位レベル、レベル６側を上位レベルとする。
【００１８】
図３は、地図データのレベル、ブロック、メッシュの関係を説明する概念図である。代表して、レベル１と２を示している。符号１０１は、本地図データの対象となる領域を示す。日本全土の地図データを扱うとすると、領域１０１は日本全土を含む範囲となる。レベル１もレベル２も同じ範囲の領域を対象としている。レベル１では、領域１０１は、４×４＝１６の複数のブロック１０２に分けられて管理される。一つのブロック１０２は、複数のメッシュ１０３に分けられて管理される。本実施の形態では、ｍ×ｎ枚のメッシュで管理する。各ブロック１０２間の分割メッシュの数は、同じレベルでは同一数ｍ×ｎである。
【００１９】
レベル２では、領域１０１は、２×２＝４の複数のブロック１０４に分けられて管理される。一つのブロック１０４は、複数のメッシュ１０５に分けられて管理される。本実施の形態では、ｐ×ｑ枚のメッシュで管理する。各ブロック１０４間の分割メッシュの数は、同じレベルでは同一数ｐ×ｑである。
【００２０】
レベル１とレベル２では、領域１０１を分割したブロックの数、各ブロックを分割したメッシュの数は異なる。これは、縮尺率の小さい（分母の値が大きい）より広域地図を扱うレベル２と、レベル２に比べて縮尺率の大きい（分母の値が小さい）より詳細地図を扱うレベル１とでは、扱うデータ量も異なるためである。すなわち、各レベルにおいて扱うデータ量に応じた適切な分割を行うようにしている。ただし、同一レベル内では、１つのブロックの大きさおよび１つのメッシュの大きさは同じである。なお、図３の各レベルの分割ブロック数は、１例であり、必ずしもこの数に限られるものではない。
【００２１】
上記分割のたて方向は緯度方向に対応し、横方向は経度方向に対応する。上記ブロック、メッシュの呼び名は、本実施の形態で便宜上名づけたものである。従って、必ずしもこれらの名称に限定されるものではない。メッシュをパーセルと言ってもよいし、ブロックを第１の分割単位、メッシュを第２の分割単位と言ってもよい。また、これらのブロック、メッシュは地理的に分割された単位と言ってもよい。
【００２２】
−道路・誘導データ−
以下、地図データのうち道路データと誘導データについて説明する。道路データと誘導データは、レベル、ブロック、メッシュという概念で管理される。各メッシュのメッシュデータとして道路データと誘導データが準備される。簡単に言うとブロック管理テーブルによりブロックを管理し、メッシュ管理テーブルにより各ブロック内におけるメッシュを管理する。
【００２３】
図４は、ブロック管理テーブルとメッシュ管理テーブルとデータであるメッシュデータとの関係を概略的に示す図である。まず、レベルｘのデータには１つのブロック管理テーブルがあることを示している。ブロック管理テーブルには、そのレベル内におけるすべてのブロックに関する情報がある。例えば、図３のレベル１では１６枚のブロックがあり、対応する１６個のブロック情報がある。レベル２では、レベル１の４枚のブロックが１枚のブロックとして管理されるため、４枚のブロックがあり、対応する４個のブロック情報がある。図４ではさらに、１枚のブロックに１つのメッシュ管理テーブルがあることを示している。
【００２４】
このメッシュ管理テーブルによりメッシュを管理する。例えば、メッシュデータを取得するための記録媒体２や不揮発性メモリ１２へのアクセスを管理する。正確に言うと、メッシュ管理テーブルはメッシュを管理するための情報を有し、制御装置１１がこのテーブルを使用してメッシュを管理する。
【００２５】
図５は、ブロック管理テーブルとメッシュ管理テーブルとメッシュデータとの関係をさらに詳細に説明する図である。ブロック管理テーブル２０１は、ｎ個のブロック管理情報２０２を有する。各ブロックに対応して１つのメッシュ管理テーブル２１１が存在する。メッシュ管理テーブル２１１は、各メッシュの情報２１２〜２１４を格納する。格納順序は、ブロック内の左端下端メッシュを最初のメッシュとし、右隣のメッシュを順次格納し、右端に行くと１行上の左端から右隣に向けて順次格納し、最後は、右端上端メッシュの情報を格納する。ここで、左は西、右は東、下は南、上は北に対応する。左端下端メッシュの情報２１２は、セクタアドレス２２１とメッシュデータのファイル名称２２２と格納場所２２３とから構成される。隣接メッシュ（右）の情報２１３は、ブロック数２２４とメッシュデータのファイル名称２２５と格納場所２２６とから構成される。その後のメッシュの情報は、ブロック数２２４とメッシュデータのファイル名称２２５と格納場所２２６とから構成される。
【００２６】
なお、記録媒体２は、記録領域を複数のセクタで分割し、セクタ内をさらに複数のブロックで分割して管理されている。ブロック数２２４は、１つ手前のメッシュ情報が使用したブロック数を示す。従って、最初のメッシュ情報２２１に格納された先頭セクタアドレスと、その後のメッシュ情報に格納されたブロック数を累積することにより、所望のメッシュのメッシュデータの記録媒体２上の格納場所を計算することができる。
【００２７】
格納場所２２３、２２６には、該当メッシュのメッシュデータが、記録媒体２上に記録されているのか、不揮発性メモリ１２上に記録されているのかを識別するための識別情報が格納されている。不揮発性メモリ１２上に記録されている場合、さらに、その格納先のアドレスや、データサイズが格納さる。なお、格納場所２２３、２２６の代わりに、メッシュデータのファイル名称２２２、２２５を該当メッシュのメッシュデータが、記録媒体２上に記録されているのか、不揮発性メモリ１２上に記録されているのかを識別するための識別情報として使用してもよい。例えば、メッシュデータがまだ記録媒体２のみに記録されている場合は、メッシュデータのファイル名称２２２、２２５にはＮＵＬＬを格納し、不揮発性メモリ１２上に記録されるようになった場合にそのファイル名称を記録する。プログラムは、まず、ファイル名称２２２、２２５がＮＵＬＬか否かを判断し、ＮＵＬＬの場合は、記録媒体２にアクセスに行き、ＮＵＬＬでない場合は、そこに格納されているファイル名称で不揮発性メモリ１２にアクセスに行けばよい。
【００２８】
符号２３１は、メッシュデータの内容を示す。メッシュデータ２３１は、基本的に、リンクテーブル２３２、リンク属性テーブル２３３、リンク間情報テーブル２３４から構成される。各テーブルへのアクセスが可能なように、メッシュデータの最初に、リンクテーブルへのオフセット２３５、リンクテーブルのサイズ２３６、リンク属性テーブルへのオフセット２３７、リンク属性テーブルのサイズ２３８、リンク間情報テーブルへのオフセット２３９、リンク間情報テーブルのサイズ２４０が格納されている。例えば、リンクテーブルのオフセット２３５より、メッシュデータ２３１におけるリンクテーブル２３２の先頭アドレスを取得し、リンクテーブルのサイズ２３６に格納された値（例えばバイト数）分のデータを読み取る。他のテーブルも同様である。
【００２９】
なお、本実施の形態では、道路をリンクとノードとリンク列という概念で表す。ノードは交差点や道路上特に指定された点を言う。リンクは隣接するノード間の道路に該当し、リンク列は１本の道路を連続した複数のリンクで表したものである。ノード間は、補間点により位置情報等が補間される。図６は、リンク列とリンクの構成の一例を示す図である。
【００３０】
図７は、図５のリンクテーブル２３２の内容について説明する図である。リンクテーブル２３２は、１つのメッシュの中に存在するリンク列の総本数が格納されたリンク列本数３０１と、各リンク列１〜ｋのデータが格納されたリンク列３０２を有する。各リンク列３０２は、リンク列情報３１１、履歴情報３１２、削除フラグ３１３、リンク本数３１４、リンク１〜ｍ３１５のデータから構成される。
【００３１】
リンク列情報３１１は、サイズ３２１、リンク列属性３２２、道路名称オフセット３２３、路線番号３２４、レベル間統合リンクＩＤ番号３２５のデータから構成される。サイズ３２１は、リンク列のサイズ３３１とレベル間統合リンクＩＤ番号のサイズ３３２から構成される。リンク列属性３２２は、道路種別コード３４１、ＲＥＳＥＲＶＥＤ（予約）３４２、路線番号有無フラグ３４３から構成される。レベル間統合リンクＩＤ番号３２５は、上位レベルのレベル間統合リンクＩＤ番号３５１を、上位レベルの数分格納する。各下位レベルのレベル間統合リンクＩＤ番号３５１は、レベル番号を識別する識別フラグ（レベルｎ＋１）３６１と、レベルｎ＋１の始点側レベル間対応キー３６２と、レベルｎ＋１の終点側レベル間対応キー３６３とから構成される。レベル間対応キーについては後述する。
【００３２】
各リンク３１５は、リンクのサイズ３７１、属性１＋Ｘ座標３７２、属性２＋Ｙ座標３７３、下位レベルの正規化座標（Ｘ，Ｙ）３７４、下位レベルのＩＤ番号（Ｋ）３７５、同一ノードオフセット３７６、リンク属性へのオフセット３７７、リンク間情報へのオフセット３７８から構成される。このリンク属性へのオフセット３７７により後述するリンク属性テーブルへのアクセスが可能となり、リンク間情報へのオフセット３７８により後述するリンク間情報テーブルへのアクセスが可能となる。
【００３３】
Ｘ座標３７２、Ｙ座標３７３は、正規化座標で表される。正規化座標とは、メッシュ内を、例えば、２０４８×２０４８に区分し、０〜２０４７の数字で表す。通常メッシュの位置は、メッシュの左下角の緯度経度で表される。すなわち、メッシュ管理テーブル２１１には、メッシュの左下角の緯度経度に対応する位置情報が格納される（不図示）。そして、メッシュの正規化座標は、メッシュの左下角を原点とする。従って、正規化座標は、緯度経度によるメッシュの位置情報を考慮すると、地図内の位置を緯度経度に対応した２次元座標値であらわしていることになる。この２次元座標値は緯度経度に対応する値であるため、ナビゲーション装置の別、規格の別などに影響されない普遍的な値と言える。
【００３４】
本実施の形態では、Ｘ座標３７２、Ｙ座標３７３の正規化座標に加えて、下位レベルの正規化座標（Ｘ，Ｙ）３７４、下位レベルのＩＤ番号（Ｋ）３７５を格納する。上位レベルの座標は、そのレベルでの解像度の関係から、下位レベルの近接した複数のノードを包含する場合もある。従って、上位レベルと下位レベルのノードの対応関係がつかめない場合も生じる。そこで、本実施の形態では、下位レベルの正規化座標もデータとして含めることにより、対応する下位レベルのノードとの対応関係を正確に把握することが可能となる。下位レベルのＩＤ番号（Ｋ）３７５とは、正規化座標以外のパラメータであり、例えば、下位レベルにおけるそのノードの高さデータ、データの生成更新に関する時間データ（情報）、あるいはその両方データである。これらのＸ座標３７２、Ｙ座標３７３、下位レベルの正規化座標（Ｘ，Ｙ）３７４、下位レベルのＩＤ番号（Ｋ）３７５を組み合わせることにより、あるレベルのノードが確実に特定でき、レベル間の対応も確実に取れる。これらの組み合わされたデータを、本実施の形態では、レベル間対応キーと言う。あるレベルの２次元キーに他のレベルのパラメータが付加されているので、２．５次元空間キーと呼んでもよい。
【００３５】
本実施の形態では、このレベル間対応キーを使用して、各レベルの各リンクにおけるリンクＩＤ番号を規定する。順方向のリンクＩＤ番号は、リンク列始点側のノードのレベル間対応キーとリンク列終点側のノードのレベル間対応キーによって規定される。逆方向のリンクＩＤ番号は、その逆の組み合わせで規定される。
【００３６】
次に、図５のリンク属性テーブル２３３について説明する。図８は、リンク属性テーブル２３３の内容について説明する図である。リンク属性テーブル２３３は、リンク属性数４０１と、リンク属性４０２とから構成される。リンク属性テーブル２３３は、１つのメッシュの中に存在するすべてのリンクに関する属性データが格納されており、リンク属性の数４０１にはその総数、リンク属性４０２には各リンクの属性データが格納される。各リンク属性４０１は、要素点の数４１１と各要素点の要素点情報４１２と、各要素点の高さ情報４１３とから構成される。各要素点情報４１２は、座標値（Ｘ，Ｙ）４２１、リンク種別コード４２２、種別付加情報４２３、道路幅員（順方向・逆方向）４２４、一方通行（順方向・逆方向）４２５、中間レーン情報（順方向・逆方向）４２６、リンクコスト４２７、ＶＩＣＳリンク番号４２８とから構成される。
【００３７】
なお、要素点とは、図６において示されるノードや補間点を言う。リンクコスト４２７、ＶＩＣＳリンク番号４２８は、リンク（サブリンクではない）に関わる情報であるため、先頭ノードである要素点情報１にのみに設定する。リンク列中間点においては、順方向と逆方向の各方向の情報を保持する。リンク列始点（リンク１）における逆方向側の情報はなく、また、リンク列終点（リンクｍ）における順方向側の情報はない。
【００３８】
次に、図５のリンク間情報テーブル２３４について説明する。図９は、リンク間情報テーブル２３４の内容について説明する図である。リンク間情報テーブル２３４は、リンク間情報の数５０１と、リンク間情報５０２とから構成される。リンク間情報テーブル２３４は、１つのメッシュの中に存在するすべてのリンク間に関する情報データが格納されており、リンク間情報の数５０１にはその総数、リンク間情報５０２には各リンク間の情報データが格納される。各リンク間情報５０２は、情報の数５１１と、交差点名称（順方向・逆方向）５１２、行き先看板名称（順方向・逆方向）５１３、交差点目標物（順方向・逆方向）５１４、交通規制情報５１５などから構成される。
【００３９】
交通規制情報５１５は、進入側のレベルｎのレベル間対応キー５２１と、退出側のレベルｎのレベル間対応キー５２２と、規制内容５２３とから構成される。リンク間情報は、主に誘導時に使用される誘導データである。
【００４０】
−ナビゲーション装置での地図データの更新管理−
以上のようにして構成される地図データ（道路・誘導データ）において、本実施の形態では、リンク列単位、リンク属性単位、リンク間情報単位でデータの更新が可能である。以下、リンク列単位での更新管理について説明する。
【００４１】
図１０は、ナビゲーション装置１での地図データの更新管理の様子を説明する図である。ナビゲーション装置１は、記録媒体２からメッシュ管理テーブルおよび地図データを読み込み、さらに、リムーバブルメモリ３あるいはインターネット５を介して地図サーバ６から更新地図データを読み込み、最新の地図データを使用することができる。
【００４２】
従来のナビゲーション装置の場合、データの読み込み元はＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの記録媒体のみであった。本実施の形態のナビゲーション装置では、記録媒体２中の地図データと更新された地図データとを混在させて使用する。このため、読み書き可能メディアである不揮発性メモリ１２を有する。不揮発性メモリ１２はハードディスクやフラッシュメモリなどの不揮発性メモリで構成され、ナビゲーション装置の電源が落とされてもデータは保持される。不揮発性メモリ１２は、キャッシュメディア１２と呼んでもよい。
【００４３】
不揮発性メモリ１２は、図５で説明したブロック管理テーブル１２４を有する。ブロック管理テーブル１２４は、該当ブロックのメッシュ管理テーブルが記録媒体２上にあるのか不揮発性メモリ１２上にあるのかの識別情報およびそのアクセスアドレスを有する。新しい地図データを初めて使用するとき、まずはじめに、記録媒体２に格納されたブロック管理テーブルを不揮発性メモリ１２に読みこむ。初期値としては、各ブロックのメッシュ管理テーブルは記録媒体２上にあるとして設定されている。その後、地図データのリンク列単位の更新があると、更新されたリンク列のメッシュを有するブロックのメッシュ管理テーブル１２５を不揮発性メモリ１２に作成し、ブロック管理テーブル１２４において、該当ブロックのメッシュ管理テーブルは不揮発性メモリ１２上にある旨を設定する。プログラムは、ブロック管理テーブル１２４を参照することにより、メッシュ管理テーブルが、記録媒体２上にあるのか不揮発性メモリ１２上にあるのかを判断することができる。
【００４４】
符号１２６は、ナビゲーション装置のメモリ１５内にあるメモリであり、メッシュ管理テーブルを格納する領域である。以下メモリ１２６と言う。プログラムは、メッシュ管理テーブルが記録媒体２上にあるのか不揮発性メモリ１２上にあるのかを判断した後、該当メディアからメッシュ管理テーブルを読み出し、メモリ１２６に格納する。メモリ１２６に読み込まれたメッシュ管理テーブル１２７は、図５で説明したメッシュ情報を有する。
【００４５】
リムーバブルメモリ３から、あるメッシュにおいて、初めてのリンク列単位の更新データを受け取ると、該当メッシュの地図データは不揮発性メモリ１２に読み込まれ、地図データ１３３として格納される。そして、不揮発性メモリ１２上でリンク列単位のデータ更新がなされる。このとき、不揮発性メモリ１２上のメッシュ管理テーブルの該当メッシュ情報の格納場所の領域に、本メッシュのメッシュデータは不揮発性メモリ１２に格納されている旨とそのアドレスを書きこむ。その後、この内容に基づき、不揮発性メモリ１２へアクセスすることができる。すなわち、一度もリンク列単位の更新がされていないメッシュの地図データは記録媒体２へアクセスし、１回でもリンク列単位で更新されたことのあるメッシュの地図データは不揮発性メモリ１２へアクセスする。
【００４６】
−リンク列単位の更新−
次に、図７のリンクテーブル２３２において、リンク列３０２単位にデータを更新する場合について説明する。図１１は、リンク列単位のデータ更新の制御のフローチャートを示す図である。図１１の制御は、制御装置１１において実行される。また、図１１の制御は、更新対象のリンク列の該当メッシュはすでに不揮発性メモリ１２に読み込まれていることを前提とする。さらに、制御装置１１は、リムーバブルメモリ３の装填を確認し、リンク列の更新データを受け取り、更新対象リンク列の該当メッシュのメッシュデータは不揮発性メモリ１２に存在することを確認済みであるところからスタートする。
【００４７】
ステップＳ１では、不揮発性メモリ１２にある該当メッシュのメッシュデータ２３１のリンクテーブル２３２に、読み込まれたリンク列の更新データをテーブルの最後に追加し、リンク列本数３０１をプラス１する。リンク列の更新データは、図７のリンク列全体のデータを含み、それ自体が正規のリンク列データである。更新データの削除フラグ３１３にはＯＦＦが設定されている。ステップＳ２において、更新リンク列データに対応する旧リンク列データの削除フラグ３１３をＯＮに設定する。この削除フラグは、リンク列データ全体を有効にするか無効にするかを識別するための識別情報である。ＯＮの場合は無効、ＯＦＦの場合は有効である。
【００４８】
ステップＳ３では、リンクテーブル２３２の更新に応じて、メッシュデータ２３１の、リンクテーブルへのオフセット２３５、リンクテーブルのサイズ２３６、リンク属性テーブルへのオフセット２３７、リンク属性テーブルのサイズ２３８、リンク間情報テーブルへのオフセット２３９、リンク間情報テーブルのサイズ２４０を更新する。ステップＳ４では、メッシュ管理テーブルの該当メッシュのメッシュ情報２１２〜２１４を更新する。例えば、不揮発性メモリ１２上の格納先やデータサイズに変更があった場合、格納場所２２３、２２６に格納されたそのアドレスやデータサイズを更新する。
【００４９】
なお、リンク属性単位、リンク間情報単位での地図データの更新も、上記と同様に行われる。リンク属性テーブルのリンク属性の数４０１、リンク間情報テーブルのリンク間情報の数５０１も同様に更新される。
【００５０】
−地図表示の制御フローチャート−
図１２は、制御装置１１が地図データ（道路・誘導データ）を読み込んで地図表示を行う制御のフローチャートを示す図である。ステップＳ１１では、現在地検出装置１３を使用して、車両の現在地を検出する。ステップＳ１２では、車両の現在地周辺の必要なメッシュのメッシュデータを読み込む。ステップＳ１３では、必要なメッシュのメッシュデータをすべて読み込んだか否かを判断する。ステップＳ１３で、まだ全てを読み込んでいないと判断すると、ステップＳ１２に戻り、さらに必要なメッシュのメッシュデータを読み込む。ステップＳ１３で、全ての必要な全てのメッシュのメッシュデータを読み込んだと判断するとステップＳ１４に進み、地図表示処理を実行する。なお、地図表示処理において、削除フラグがＯＮされているリンク列データや、リンク属性データや、リンク間情報データは無視される。
【００５１】
図１３は、図１２のステップＳ１２の処理の詳細なフローチャートを示す図である。ステップＳ２１で、前述したように、不揮発性メモリ１２にあるブロック管理テーブルにアクセスする。この場合、ブロック管理テーブルはすでに不揮発性メモリ１２に読みこまれた状態であることを前提とする。ステップＳ２２で、ブロック管理テーブルの内容に基づき、該当ブロックのメッシュ管理テーブルが記録媒体２上にあるか不揮発性メモリ１２上にあるかを判断する。ステップＳ２２で、記録媒体２にあると判断するとステップＳ２３に進む。ステップＳ２３では、記録媒体２から該当ブロックのメッシュ管理テーブルをメモリ１２６に読みこむ。
【００５２】
一方、ステップＳ２２で、記録媒体２上にない、すなわち、不揮発性メモリ１２上にあると判断すると、ステップＳ２４に進む。ステップＳ２４では、不揮発性メモリ１２から該当ブロックのメッシュ管理テーブルをメモリ１２６に読みこむ。ステップＳ２５では、メモリ１２６に読みこまれたメッシュ管理テーブルの内容に基づき、該当メッシュの格納先アドレスを取得する。ステップＳ２６で、取得された格納先からメッシュデータを読みこむ。この場合、メッシュデータが一度でもリンク列単位の更新がされていない場合は、記録媒体２からメッシュデータが読み込まれる。また、メッシュデータが一度でもリンク列単位で更新されている場合は、不揮発性メモリ１２からデータが読み込まれる。
【００５３】
以上のようにして、メッシュデータのリンクテーブルが、リンク列単位で更新され、リンク列単位で更新された地図データを使用して、地図表示処理がなされる。
【００５４】
−背景・名称データ−
次に、地図データのうち背景・名称データについて説明する。背景・名称データについても、道路・誘導データと同様に、レベル、ブロック、メッシュという概念で管理される。従って、図５と同様に管理され、図５のメッシュデータ２３１を、図１４のメッシュデータ６０１に置き換えて理解すればよい。図１４は、背景・名称データのメッシュデータの内容を示す。メッシュデータ６０１は、基本的に、背景テーブル６０２、名称テーブル６０３から構成される。各テーブルへのアクセスが可能なように、メッシュデータ６０１の最初に、背景テーブルへのオフセット６０４、背景テーブルのサイズ６０５、名称テーブルへのオフセット６０６、名称テーブルのサイズ６０７が格納されている。例えば、背景テーブルのオフセット６０４より、メッシュデータ６０１における背景テーブル６０２の先頭アドレスを取得し、背景テーブルのサイズ６０５に格納された値（例えばバイト数）分のデータを読み取る。名称テーブルも同様である。
【００５５】
図１５は、図１４の背景テーブル６０２の内容について説明する図である。背景とは、道路地図を表示するにあたり、道路以外の山や海や鉄道などの背景を言い、背景データとは、それぞれの背景要素を表示するためのポリゴン（面）データ、ポリライン（線）データ、点データである。背景テーブル６０２は、１つのメッシュの中に存在する背景データの総数が格納された背景データの数７０１と、背景データ１〜ｓが格納された背景データ７０２を有する。各背景データ７０２は、背景情報７１１、履歴情報７１２、削除フラグ７１３、要素点数７１４、始点X座標７１５、始点Y座標７１６、オフセット座標１（△Ｘ，△Ｙ）７１７、オフセット座標２（△Ｘ，△Ｙ）７１８、オフセット座標ｔ（△Ｘ，△Ｙ）７１９、インフォメーションポインタ７２０から構成される。
【００５６】
背景情報７１１は、サイズ７２１、形状分類（面、線、点）７２２、描画順位７２３、背景属性７２４、名称オフセット７２５とから構成される。背景属性７２４は、ズーム許可フラグ７３１と背景種別コード７３２とから構成される。
【００５７】
次に、図１４の名称テーブル６０３について説明する。図１６は、名称テーブル６０３の内容について説明する図である。名称とは、道路地図を表示する等において、地名や建物の名称やその他のあらゆる名称を言う。名称テーブル６０３は、名称データの数８０１と、名称データ８０２とから構成される。名称テーブル６０３は、１つのメッシュの中に存在するすべての名称データが格納されており、名称データの数８０１にはその総数が格納される。各名称データ８０２は、名称情報８１１、履歴情報８１２、削除フラグ８１３、文字数８１４、Ｘ座標８１５、Ｙ座標８１６、文字列コード１：８１７、文字列コード２：８１８、文字列コードｖ：８１９、インフォメーションポインタ８２０とから構成される。
【００５８】
名称情報８１１は、サイズ８２１、描画順位８２２、名称属性８２３とから構成される。名称属性８２３は、ズーム許可フラグ８３１と名称種別コード８３２とから構成される。
【００５９】
以上のようにして構成される背景・名称データにおいて、本実施の形態では、背景データ単位、名称データ単位でデータの更新が可能である。更新管理については、リンク列単位での更新管理と同様であり、上述したリンク列を背景データあるいは名称データに置き換えて理解すればよい。背景テーブルの背景データの数７０１、名称テーブルの名称データの数８０１も同様に更新される。なお、背景データあるいは名称データは、更新前では最初に設定された描画順位に応じてデータが並べられている。更新により、背景データあるいは名称データが、変更、追加、削除等された場合は、各データに設定されている描画順位に応じて再度データを並べ変えることができる。
【００６０】
−経路計算データ−
次に、地図データのうち経路計算データについて説明する。経路計算データについても、道路・誘導データと同様に、レベル、ブロック、メッシュという概念で管理される。従って、図５と同様に管理され、図５のメッシュデータ２３１を、図１７のメッシュデータ９０１に置き換えて理解すればよい。図１７は、経路計算データのメッシュデータの内容を示す。メッシュデータ９０１は、基本的に、接続部テーブル９０２、レベル間対応テーブル９０３から構成される。各テーブルへのアクセスが可能なように、メッシュデータ９０１の最初に、接続部テーブルへのオフセット９０４、接続部テーブルのサイズ９０５、レベル間対応テーブルへのオフセット９０６、レベル間対応テーブルのサイズ９０７が格納されている。例えば、接続部テーブルのオフセット９０４より、メッシュデータ９０１における接続部テーブル９０２の先頭アドレスを取得し、接続部テーブルのサイズ９０５に格納された値（例えばバイト数）分のデータを読み取る。レベル間対応テーブルも同様である。
【００６１】
図１８は、図１７の接続部テーブル９０２の内容について説明する図である。経路計算データは、前述したように、道路形状とは直接関係しない分岐情報などから成るネットワークデータであり、ノードの接続情報からなる。接続部テーブル９０２は、１つのメッシュの中に存在するノードの総数が格納されたノード総数１００１と、リンクの総数が格納されたリンク総数１００２と、ノード情報１〜ｗが格納されたノード情報１００３を有する。各ノード情報１００３は、ノード情報のサイズ１０１１、履歴情報１０１２、削除フラグ１０１３、自ノード情報１０１４、隣接ノード＃１〜＃ｅ情報１０１５とから構成される。
【００６２】
自ノード情報１０１４は、隣接ノード数＋Ｘ座標１０２１、上位レベル存在フラグ１０２２、自ノード道路種別コード＋Ｙ座標１０２３、下位レベルの正規化座標（Ｘ，Ｙ）１０２４、下位レベルのＩＤ番号（Ｋ）１０２５とから構成される。本実施の形態では、Ｘ座標１０２１、Ｙ座標１０２３の正規化座標に加えて、下位レベルの正規化座標（Ｘ，Ｙ）１０２４と下位レベルのＩＤ番号（Ｋ）１０２５を格納する。この、Ｘ座標１０２１、Ｙ座標１０２３と下位レベルの正規化座標（Ｘ，Ｙ）１０２４と下位レベルのＩＤ番号（Ｋ）１０２５とを組み合わせることにより、自ノードＩＤ番号であるレベル間対応キーを構成する。レベル間対応キーは、道路・誘導データにおいて説明した通りである。
【００６３】
各隣接ノード情報１０１５は、リンク種別コード＋Ｘ座標１０３１、上位レベル存在フラグ＋Ｙ座標１０３２、下位レベルの正規化座標（Ｘ，Ｙ）１０３３、下位レベルのＩＤ番号（Ｋ）１０３４、交通規制（通行コード）有無フラグ１０３５、図郭外フラグ＋図郭方向１０３６、隣接ノード道路種別コード１０３７、リンク道路種別コード １０３８、道路幅員＋バイパスフラグ１０３９、規制速度＋リンク長＋平均旅行時間１０４０、通行コード（１ワード〜４ワード）１０４１とから構成される。隣接ノードにおいても、Ｘ座標１０３１、Ｙ座標１０３２、下位レベルの正規化座標（Ｘ，Ｙ）１０３３、下位レベルのＩＤ番号（Ｋ）１０３４とにより、隣接ノードＩＤ番号であるレベル間対応キーを構成する。
【００６４】
上記した自ノードＩＤ番号と隣接ノードＩＤ番号とにより、その間のリンクＩＤ番号が規定される。これにより、経路計算データにおいても、あるレベルのノードやリンクが確実に特定でき、レベル間の対応も確実に取れる。図１９は、隣接するノード１とノード２において、ノードＩＤ番号ととリンクＩＤ番号との関係を概念的に示す図である。ノードＩＤ番号は、自ノード情報でもあり、隣接するノードにおいては隣接ノード情報に使用される。リンクＩＤ番号において、ノードＩＤ番号の並びを逆にすることにより、順方向と逆方向のリンクＩＤ番号を規定している。
【００６５】
例えば、ノードＩＤ番号とリンクＩＤ番号を使用して、経路表示をする場合について説明する。経路計算データを使用してある経路が計算された場合、その経路上のノードのノードＩＤ番号を取得できる。取得されたノードＩＤ番号に基づき、道路・誘導データにアクセスし、経路表示のためのデータを取得することができる。この場合、ノードの並び順により、ノードに接続する方向情報を有するリンクＩＤ番号が特定できる。特定された方向情報を有するリンクＩＤ番号を使用して、経路表示のためのデータを取得することができる。例えば、進行方向によって異なる交差点名称を有する交差点などを適切に表示することができる。
【００６６】
次に、図１７のレベル間対応テーブル９０３について説明する。図２０は、レベル間対応テーブル９０３の内容について説明する図である。レベル間対応テーブル９０３は、当該レベルのノードが下位レベルのどのメッシュのどのノードに対応するかの情報を格納したテーブルである。
【００６７】
レベル間対応テーブル９０３は、１つのメッシュの中において、レベル間対応情報が設けられたノードの総数が格納されたレベル間対応ノード総数１１０１と、リンクの総数が格納されたリンク総数１１０２と、対応情報１〜ｆが格納された対応情報１１０３を有する。各対応情報１１０３は、対応情報のサイズ１１１１、履歴情報１１１２、削除フラグ１１１３、自ノード対応情報１１１４、隣接ノード＃１〜＃ｇ情報１１１５とから構成される。
【００６８】
自ノード対応情報１１１４は、隣接ノード数１１２１、自レベル情報１１２２、下位レベル情報１１２３とから構成される。自レベル情報１１２２は、Ｘ座標１１３１、Ｙ座標１１３２、下位レベルの正規化座標（Ｘ，Ｙ）１１３３、下位レベルのＩＤ番号（Ｋ）１１３４とから構成される。これらを組み合わせは前述のレベル間対応キーを構成し、自レベルの自ノードＩＤ番号となる。下位レベル情報１１２３は、下位レベルの存在領域１１４１、Ｘ座標１１４２、Ｙ座標１１４３、下位レベルの正規化座標（Ｘ，Ｙ）１１４４、下位レベルのＩＤ番号（Ｋ）１１４５とから構成される。Ｘ座標１１４２、Ｙ座標１１４３、下位レベルの正規化座標（Ｘ，Ｙ）１１４４、下位レベルのＩＤ番号（Ｋ）１１４５の組み合わせは、同様にレベル間対応キーを構成し、下位レベルの自ノードＩＤ番号となる。
【００６９】
各隣接ノード対応情報１１１５は、自レベル隣接情報１１５１、下位レベル情報１１５２とから構成される。自レベル隣接情報１１５１は、Ｘ座標１１６１、Ｙ座標１１６２、下位レベルの正規化座標（Ｘ，Ｙ）１１６３、下位レベルのＩＤ番号（Ｋ）１１６４とから構成される。これらを組み合わせは、同様にレベル間対応キーを構成し、自レベルの隣接ノードＩＤ番号となる。下位レベル隣接情報１１５２は、下位レベルの存在領域１１７１、Ｘ座標１１７２、Ｙ座標１１７３、下位レベルの正規化座標（Ｘ，Ｙ）１１７４、下位レベルのＩＤ番号（Ｋ）１１７５とから構成される。Ｘ座標１１７２、Ｙ座標１１７３、下位レベルの正規化座標（Ｘ，Ｙ）１１７４、下位レベルのＩＤ番号（Ｋ）１１７５の組み合わせは、同様にレベル間対応キーを構成し、下位レベルの隣接ノードＩＤ番号となる。
【００７０】
以上のようにして構成される経路計算データにおいて、本実施の形態では、ノード情報単位、リンク間情報単位でデータの更新が可能である。更新管理については、リンク列単位での更新管理と同様であり、上述したリンク列をノード情報あるいはリンク間情報に置き換えて理解すればよい。接続部テーブルのノード総数１００１、リンク総数１００２、レベル間対応テーブルのレベル間対応総数１１０１、リンク総数１１０２も同様に更新される。
【００７１】
以上説明したような本実施の形態の地図データの構造や、そのデータ構造を利用するナビゲーション装置は、次のような効果を奏する。
（１）道路・誘導データでは、リンク列単位、リンク属性単位、リンク間情報単位で更新可能であり、背景・名称データでは、ポリゴン、ポリライン、点等の背景表示管理単位、名称単位で更新可能であり、経路計算データでは、ノード情報単位、レベル間対応情報単位で更新可能である。すなわち、地図に関する情報を構成する情報要素単位で更新可能である。従って、地図データの一部のみ更新する場合、地図データが格納されたＤＶＤ−ＲＯＭなどの記録媒体全体を新しいものにする必要がない。また、最小単位でデータ更新がなされるので、データ更新に掛かる通信量(コスト)も低減することができる。また、更新時間も削減できる。ここで、地図に関する情報を構成する情報要素とは、情報あるいはデータの機能、用途等別に分類される要素であり、情報やデータの機能、用途別の種類とも言える。
（２）リンク列等の各情報要素には、削除フラグを設けるようにしたので、旧データを一々削除したり入れ替えたりしなくてもよい。なお、削除フラグを設けず、旧データを削除して、新しい更新データで置き換えるようにしてもよい。
（３）地図データを管理する管理テーブルを不揮発性メモリに格納し、リンク列等の情報要素の更新ごとに、管理テーブルの内容を更新できるようにした。これにより、リンク列等の情報要素単位の更新が可能になるとともに、後に更新されたデータのアクセスが可能となる。
（４）リンク列等の更新対象情報要素が含まれるメッシュデータを不揮発性メモリに格納するようにしたので、更新データの追加、あるいは書き換え、それらに伴う管理情報の更新が可能となる。また、装置の電源が落とされても、更新データが保持される。
（５）ノードの位置情報を、自レベルの位置情報のみならず下位レベルの位置情報も組み合わせたレベル間対応キーで表すようにしたので、ノードの特定が確実にでき、さらにレベル間の対応関係も容易に取ることができる。
（６）レベル間対応キー（ノードＩＤ番号）を使用して、各レベルの各リンクにおけるリンクＩＤ番号を規定するようにしたので、リンクの特定が確実にでき、さらにレベル間の対応関係も容易に取ることができる。また、レベル間対応キーの並びの順序を変えることにより、順方向あるいは逆方向のリンクＩＤ番号を規定するようにしたので、順方向あるいは逆方向のリンクＩＤ番号を容易に確実に特定することができる。上記のように規定されるリンクＩＤ番号は、例えば、経路計算結果に基づく経路表示や経路誘導において、リンクの方向を特定する必要があるときに有効に使用される。
（７）背景データや名称データに、描画順序の情報を設けるようにしたので、情報要素単位の更新時に、描画順序に応じてデータの並び替えをすることもできる。これにより、データが更新されても描画スピードの低下を招かない。
（８）更新データをインターネット経由の通信によっても提供するので、迅速にかつ安い費用で最新の更新データを提供することができる。
（９）ノード位置情報に、緯度経度に対応する２次元座標値を使用するようにしているので、データ更新の方式が機種に依存したり、規格に依存したりすることを防止することができる。すなわち、緯度経度に対応する２次元座標は普遍的なデータと言えるので、これらのデータを使用することにより、データ更新の方式を標準化できる。
（１０）レベル間対応キーにおいて、２次元座標値以外のパラメータを使用しているので、ノード間の特定をより確実に行うことができる。例えば、高さデータを使用する場合、道路が高架して交差する接続点であっても、確実に区別することができる。
【００７２】
上記の実施の形態では、ナビゲーション装置の制御装置１１が実行する制御プログラムはＲＯＭに格納されている例で説明をしたが、この内容に限定する必要はない。制御プログラムやそのインストールプログラムをＤＶＤなどの記録媒体で提供してもよい。なお、記録媒体はＤＶＤに限定する必要はなく、ＣＤ−ＲＯＭ、磁気テープやその他のあらゆる記録媒体を使用するようにしてもよい。
【００７３】
さらに、それらのプログラムをインターネットなどに代表される通信回線などの伝送媒体を介して提供することも可能である。すなわち、プログラムを、伝送媒体を搬送する搬送波上の信号に変換して送信することも可能である。プログラムを記録媒体やインターネットで提供する場合は、図１と同じような構成で提供すればよい。例えば、記録媒体２をプログラム提供の記録媒体にし、地図サーバ６をアプリケーションプログラムを提供するサーバーとすればよい。
【００７４】
また、上述の制御プログラムをパソコン上で実行させてカーナビゲーション装置を実現するようにしてもよい。その場合、現在地検出装置１３や入力装置１９などは、パソコンの所定のＩ／Ｏポートなどに接続するようにすればよい。
【００７５】
上記の実施の形態では、リムーバブルメモリ３から更新データを提供する例を説明したが、この内容に限定する必要はない。更新用データをＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどに書きこんで、記録媒体２を一時的に入れ替えて提供するようにしてもよい。
【００７６】
上記の実施の形態では、記録媒体２から初期の地図データを読み込む例を説明したが、この内容に限定する必要はない。初期の地図データをインターネット５を介して受け取って不揮発性メモリ１２に格納し、その後前述した手法で更新管理するようにしてもよい。また、インターネット５を介して必要な地図データをその都度受け取り、その都度不揮発性メモリ１２に格納し、その後更新がある場合は、前述した手法で更新管理をしてもよい。
【００７７】
上記の実施の形態では、不揮発性メモリ１２はナビゲーション装置１の内部に設けられる例を説明したが、この内容に限定する必要はない。ケーブルなどによって接続される外部記憶装置であってもよい。
【００７８】
上記の実施の形態では、複数のレベルに対応して地図データを有し、当該レベルにおけるノードの正規化座標と下位レベルの正規化座標とを組み合わせたレベル間対応キーを使用する例を説明したが、この内容に限定する必要はない。すべてのノード座標を、最も詳細なレベルで使用できる解像度の緯度経度に関する位置情報で表すようにしてもよい。例えば、所定の解像度の絶対緯度経度そのもので表してもよい。また、所定の解像度の緯度経度に関する位置情報と前述したノードの高さデータや更新時間データなどのＩＤ番号（Ｋ）との組み合わせで表すようにしてもよい。
【００７９】
上記の実施の形態では、道路・誘導データや経路計算データにおいて、リンク列単位やノード情報単位など、それぞれの情報要素の更新データを使用してそれぞれのデータを更新する例を説明したが、この内容に限定する必要はない。例えば、道路・誘導データのリンク列単位の更新データを使用して、リンクテーブルをリンク列単位で更新するとともに、経路計算データの接続部テーブルをノード情報単位で更新するようにしてもよい。リンク列単位の更新データには、ノードの位置情報や規制情報などが含まれ、経路計算データの更新データを生成することも可能であるからである。また、道路・誘導データや背景・名称データや経路計算データなどの情報要素単位の更新に共通に使用できる、所定のフォーマットの統合された更新データを提供し、各データを更新するようにしてもよい。この場合、ナビゲーション装置１側で、所定のフォーマットの統合された更新データから各データの情報要素単位の更新データを生成するプログラムを備えておく。このようにすることにより、通信データをコンパクト化でき、更新を迅速に行うことができるようになる。
【００８０】
上記では、種々の実施の形態および変形例を説明したが、本発明はこれらの内容に限定されるものではない。本発明の技術的思想の範囲内で考えられるその他の態様も本発明の範囲内に含まれる。
【図面の簡単な説明】
【００８１】
【図１】地図データの授受について説明する図である。
【図２】車載用ナビゲーション装置のブロック図である。
【図３】地図データのレベル、ブロック、メッシュの関係を説明する概念図である。
【図４】ブロック管理テーブルとメッシュ管理テーブルとデータであるメッシュデータとの関係を概略的に示す図である。
【図５】ブロック管理テーブルとメッシュ管理テーブルとメッシュデータとの関係をさらに詳細に説明する図である。
【図６】リンク列とリンクの構成の一例を示す図である。
【図７】リンクテーブルの内容について説明する図である。
【図８】リンク属性テーブルの内容について説明する図である。
【図９】リンク間情報テーブルの内容について説明する図である。
【図１０】ナビゲーション装置での地図データの更新管理の様子を説明する図である。
【図１１】リンク列単位のデータ更新の制御のフローチャートを示す図である。
【図１２】制御装置が地図データ（道路・誘導データ）を読み込んで地図表示を行う制御のフローチャートを示す図である。
【図１３】図１２のステップＳ１２の処理の詳細なフローチャートを示す図である。
【図１４】背景・名称データのメッシュデータの内容を示す図である。
【図１５】背景テーブルの内容について説明する図である。
【図１６】名称テーブルの内容について説明する図である。
【図１７】経路計算データのメッシュデータの内容を示す図である。
【図１８】接続部テーブルの内容について説明する図である。
【図１９】ノードＩＤ番号とリンクＩＤ番号との関係を概念的に示す図である。
【図２０】レベル間対応テーブルの内容について説明する図である。
【符号の説明】
【００８２】
１  ナビゲーション装置
２  記録媒体
３  リムーバブルメモリ
４  通信装置
５  インタネット
６  地図サーバ
７  地図データベース
８  案内検索データベース
１１  制御装置
１２  不揮発性メモリ
１３  現在地検出装置
１４  ＤＶＤ駆動装置
１５  メモリ
１６  通信インターフェース
１７  リムーバブルメモリ読込装置
１８  モニタ
１９  入力装置
【図１】
2008233918.tif 000003
【図２】
2008233918.tif 000004
【図３】
2008233918.tif 000005
【図４】
2008233918.tif 000006
【図５】
2008233918.tif 000007
【図６】
2008233918.tif 000008
【図７】
2008233918.tif 000009
【図８】
2008233918.tif 000010
【図９】
2008233918.tif 000011
【図１０】
2008233918.tif 000012
【図１１】
2008233918.tif 000013
【図１２】
2008233918.tif 000014
【図１３】
2008233918.tif 000015
【図１４】
2008233918.tif 000016
【図１５】
2008233918.tif 000017
【図１６】
2008233918.tif 000018
【図１７】
2008233918.tif 000019
【図１８】
2008233918.tif 000020
【図１９】
2008233918.tif 000021
【図２０】
2008233918.tif 000022
【手続補正書】
【提出日】平成20年4月23日(2008.4.23)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
地図データ処理装置であって、
道路上の点をノードとし、隣接するノード間の道路をリンクとして表し、前記ノードを特定する情報は緯度経度に関する位置情報で構成され、前記リンクを特定する情報は対象リンク両端のノードの前記緯度経度に関する位置情報の組み合わせで構成される地図に関する情報を有する地図データを取得する地図データ取得手段と、
前記地図データ取得手段により取得された前記地図データを使用して地図データの処理を行う処理手段とを備え、
前記処理手段は、前記対象リンク両端のノードの前記緯度経度に関する位置情報の組み合わせで構成される前記リンクを特定する情報を使用して、前記地図データの処理を行うことを特徴とする地図データ処理装置。
【請求項２】
請求項１記載の地図データ処理装置において、
前記リンクを特定する情報は、前記対象リンク両端のノードの緯度経度に関する位置情報の組み合わせの順序により、該対象リンクの方向を特定することを特徴とする地図データ処理装置。
【請求項３】
請求項１〜２のいずれか１項に記載の地図データ処理装置において、
前記地図の複数の異なる縮尺率に対応する複数のレベルを定義し、
より広域な地図を表すより小さい値の縮尺率のレベルを上位側レベルとし、
前記地図に関する情報は、前記複数のレベルに対応して複数セット設けられ、
所定レベルの前記ノードの位置情報は、前記所定レベルにおけるノードの位置情報とともに、前記所定レベルの下位側レベルの対応するノードの位置情報も含むことを特徴とする地図データ処理装置。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００１
【補正方法】変更
【補正の内容】
【０００１】
本発明は、地図データ処理装置に関する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００５
【補正方法】変更
【補正の内容】
【０００５】
本発明は、地図データを効率よく使用する地図データ処理装置を提供する。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
請求項１の発明は、地図データ処理装置に適用され、道路上の点をノードとし、隣接するノード間の道路をリンクとして表し、ノードを特定する情報は緯度経度に関する位置情報で構成され、リンクを特定する情報は対象リンク両端のノードの緯度経度に関する位置情報の組み合わせで構成される地図に関する情報を有する地図データを取得する地図データ取得手段と、地図データ取得手段により取得された地図データを使用して地図データの処理を行う処理手段とを備え、処理手段は、対象リンク両端のノードの緯度経度に関する位置情報の組み合わせで構成されるリンクを特定する情報を使用して、地図データの処理を行うことを特徴とするものである。
請求項２の発明は、請求項１記載の地図データ処理装置において、リンクを特定する情報は、対象リンク両端のノードの緯度経度に関する位置情報の組み合わせの順序により、該対象リンクの方向を特定することを特徴とするものである。
請求項３の発明は、請求項１〜２のいずれか１項に記載の地図データ処理装置において、地図の複数の異なる縮尺率に対応する複数のレベルを定義し、より広域な地図を表すより小さい値の縮尺率のレベルを上位側レベルとし、地図に関する情報は、複数のレベルに対応して複数セット設けられ、所定レベルのノードの位置情報は、所定レベルにおけるノードの位置情報とともに、所定レベルの下位側レベルの対応するノードの位置情報も含むことを特徴とするものである。