(57)【特許請求の範囲】
【請求項１】
ナビゲーション装置であって、
地図表示用データおよび経路探索用データを格納する地図データベース手段と、
前記経路探索用データを使用して出発地から目的地までの経路を探索する経路探索手段と、
前記地図表示用データを使用して道路地図を表示手段に表示するとともに、前記探索された経路を前記道路地図に表示するよう制御する道路地図表示制御手段とを備え、
始端と終端にノードを有するリンクを複数接続したリンク列として道路を表し、
前記地図表示用データは、縮尺率の異なる地図に対応した複数のレベルごとに別々に設けられた前記リンク列に対応したリンク列データを有し、
前記リンク列データは、縮尺率の小さい上位レベルに含まれるリンクと共通する縮尺率の大きい下位レベルのリンク列を表すデータとして、前記上位レベルのレベル番号および共通する上位レベルのリンクのリンク番号を含むレベル間統合リンク番号を有し、
前記経路探索用データは、前記地図表示用データの複数のレベルに対応してノードの接続関係を表すノード接続データを有し、
前記ノード接続データは、前記レベル間統合リンク番号を有し、
前記道路地図表示制御手段は、前記経路探索手段により前記接続データを使用して探索された経路のデータに含まれるレベル間統合リンク番号を使用して前記地図表示用データを参照し、前記探索された経路を前記道路地図に表示するよう制御することを特徴とするナビゲーション装置。
【請求項２】
請求項１に記載のナビゲーション装置において、
前記経路探索手段は、所定のレベルに対応するノード接続データを使用して経路を探索し、
前記道路地図表示制御手段は、前記探索された経路のデータに含まれるレベル間統合リンク番号を使用して、前記所定のレベルと同等あるいは下位レベルのリンク列データを参照して、前記探索された経路を前記道路地図に表示するよう制御することを特徴とするナビゲーション装置。
【請求項３】
ナビゲーション装置であって、
地図表示用データを格納する地図データベース手段と、
前記地図表示用データを使用して道路地図を表示手段に表示するよう制御する道路地図表示制御手段とを備え、
始端と終端にノードを有するリンクを複数接続したリンク列として道路を表し、
前記地図表示用データは、縮尺率の異なる地図に対応した複数のレベルごとに別々に設けられた前記リンク列に対応したリンク列データを有し、
前記リンク列データは、縮尺率の小さい上位レベルに含まれるリンクと共通する縮尺率の大きい下位レベルのリンク列を表すデータとして、前記上位レベルのレベル番号および共通する上位レベルのリンクのリンク番号を含むレベル間統合リンク番号を有し、
前記道路地図表示制御手段は、前記レベル間統合リンク番号を使用して異なるレベル間のリンク列の対応づけを行うことを特徴とするナビゲーション装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ナビゲーション装置に関する。
【０００２】
【従来技術】
車両位置周辺の道路地図を表示する機能や、マップマッチングを行って車両位置を正確に検出する機能や、出発地から目的地までの推奨ルートを演算する機能等を兼ね備えた車載用ナビゲーション装置が知られている。これら従来の車載用ナビゲーション装置では、既存のソフトウェアとの互換性を維持し、かつ処理速度を上げるために、道路地図表示用のデータ、マップマッチング用のデータおよびルート探索用のデータを１枚のＣＤ−ＲＯＭにそれぞれ別々に格納している。
【０００３】
道路地図表示用データは、縮尺率が最も小さく広い地域を表示するための最広域地図データと、縮尺率が最も大きく狭い地域を詳細に表示する最詳細地図データと、最広域地図データと最詳細地図データとの間の異なる縮尺率の複数の地図データとを備えている。たとえば最広域地図データをレベル４のデータ、最詳細地図データをレベル１のデータ、レベル４とレベル１との間のデータをそれぞれレベル３および２のデータと呼ぶ。この場合、ルート探索用データは道路地図データのレベル４とレベル２に対応する２つのデータを備え、ルート探索にあたっては出発地近傍と目的地近傍をレベル２で探索し、それ以外の領域をレベル４で探索するようにして、ルート探索時間を短縮化している。
【０００４】
【発明が解決しようとする課題】
図２４は上記レベル４および３として記憶する道路地図表示用データの道路地図を説明する図であり、ＣＤ−ＲＯＭにはレベル４の道路地図表示用データとレベル３の道路地図表示用データが別々に記憶される。図２４（ａ）はレベル４の１つのメッシュＭ４の道路地図を示し、このメッシュＭ４には１本の道路Ｄ１と、道路Ｄ１の両端の交差点Ｃ１，Ｃ２に接続される２本の道路Ｄ２，Ｄ３が存在している。レベル４の１つのメッシュＭ４を１６等分したハッチングで示す小領域ｍ３がレベル３の１つのメッシュＭ３となり、図２４（ｂ）に示すように、メッシュＭ３には道路Ｄ１の一部分の道路Ｄ４だけが存在する。
【０００５】
たとえば、レベル４のメッシュＭ４の道路地図がモニタに表示されているとき詳細ボタンが操作されるとレベル３のメッシュＭ３の道路地図がモニタに表示されるが、道路Ｄ１と道路Ｄ４とが同一の道路であることを示す識別データは使用されていないので、各レベル間での同一道路の対応づけが難しい。あるいは、経路探索データについても同様な問題があり、経路探索結果である推奨ルートデータのうちレベル２で探索したデータとレベル４で探索したデータの対応づけが難しい。また、道路地図表示用データと経路探索データ間でも同一の道路であることを示す識別データは使用していないので、推奨ルートデータを道路地図表示用データに重ねて表示する際の同一道路の対応づけが難しい。
【０００６】
本発明の目的は、各レベル間での同一道路に関するデータの対応づけや異種データ間での同一道路に関するデータの対応づけを簡単にしたナビゲーション装置を提供することにある。
【０００７】
【課題を解決するための手段】
請求項１の発明は、ナビゲーション装置に適用され、地図表示用データおよび経路探索用データを格納する地図データベース手段と、経路探索用データを使用して出発地から目的地までの経路を探索する経路探索手段と、地図表示用データを使用して道路地図を表示手段に表示するとともに、探索された経路を道路地図に表示するよう制御する道路地図表示制御手段とを備え、始端と終端にノードを有するリンクを複数接続したリンク列として道路を表し、地図表示用データは、縮尺率の異なる地図に対応した複数のレベルごとに別々に設けられたリンク列に対応したリンク列データを有し、リンク列データは、縮尺率の小さい上位レベルに含まれるリンクと共通する縮尺率の大きい下位レベルのリンク列を表すデータとして、上位レベルのレベル番号および共通する上位レベルのリンクのリンク番号を含むレベル間統合リンク番号を有し、経路探索用データは、地図表示用データの複数のレベルに対応してノードの接続関係を表すノード接続データを有し、ノード接続データは、レベル間統合リンク番号を有し、道路地図表示制御手段は、経路探索手段により接続データを使用して探索された経路のデータに含まれるレベル間統合リンク番号を使用して地図表示用データを参照し、探索された経路を道路地図に表示するよう制御することを特徴とするものである。
請求項２の発明は、請求項１に記載のナビゲーション装置において、経路探索手段は、所定のレベルに対応するノード接続データを使用して経路を探索し、道路地図表示制御手段は、探索された経路のデータに含まれるレベル間統合リンク番号を使用して、所定のレベルと同等あるいは下位レベルのリンク列データを参照して、探索された経路を道路地図に表示するよう制御することを特徴とするものである。
請求項３の発明は、ナビゲーション装置に適用され、地図表示用データを格納する地図データベース手段と、地図表示用データを使用して道路地図を表示手段に表示するよう制御する道路地図表示制御手段とを備え、始端と終端にノードを有するリンクを複数接続したリンク列として道路を表し、地図表示用データは、縮尺率の異なる地図に対応した複数のレベルごとに別々に設けられたリンク列に対応したリンク列データを有し、リンク列データは、縮尺率の小さい上位レベルに含まれるリンクと共通する縮尺率の大きい下位レベルのリンク列を表すデータとして、上位レベルのレベル番号および共通する上位レベルのリンクのリンク番号を含むレベル間統合リンク番号を有し、道路地図表示制御手段は、レベル間統合リンク番号を使用して異なるレベル間のリンク列の対応づけを行うことを特徴とするものである。
【０００８】
【発明の実施の形態】
図１は本発明の地図データベース装置を内部に有する車載用ナビゲーション装置の一実施の形態のブロック図である。図１において、１は車両の現在地を検出する現在地検出装置であり、例えば車両の進行方位を検出する方位センサや車速を検出する車速センサやＧＰＳ（Global Positioning System）衛星からのＧＰＳ信号を検出するＧＰＳセンサ等から成る。
【０００９】
２は装置全体を制御する制御回路であり、マイクロプロセッサおよびその周辺回路から成る。３は車両の目的地等を入力する入力装置、４は現在地検出装置１によって検出された車両位置情報等を格納するＤＲＡＭ、５は表示装置６に表示するための画像データを格納する画像メモリであり、画像メモリ５に格納された画像データは適宜読み出されて表示装置６に表示される。７は制御回路２が演算した推奨ルート上のノード情報やリンク情報等を格納するＳＲＡＭである。
【００１０】
８は、道路地図表示、経路探索（ルート探索）およびマップマッチング等を行うための種々のデータを格納する地図データベース装置であり、例えばＣＤ−ＲＯＭ装置や磁気記録装置等で構成される。地図データベース装置８には、道路形状や道路種別に関する情報などから成る地図表示用データと、道路形状とは直接関係しない分岐点情報や交差点情報などから成るルート探索用データとが格納されている。地図表示用データは主に表示装置６に道路地図を表示する際に用いられ、ルート探索用データは主に推奨経路（推奨ルート）を演算する際に用いられる。
【００１１】
次に、地図データベース装置８に格納されている地図表示用データとルート探索用データのデータ構成について詳述する。
【００１２】
［１］地図表示用データ
(1)リンク列データの概要
本実施の形態の地図表示用データは、道路地図を所定範囲ごとに区分けしたメッシュ領域ごとにデータを管理しており、メッシュ領域内に存在する各道路をそれぞれ別々のリンク列とする。例えば、図２に示すように、１つのメッシュ領域内で２本の道路Ｄ１，Ｄ２が交差している場合には、各道路をそれぞれ別々のリンク列１，２で表すものとし、リンク列１はリンク１１，１２で構成され、リンク列２はリンク２１〜２３で構成されるものとする。この場合、リンク列１の各リンク、リンク列２の各リンクは同一種別の道路である。リンクは道路を表す最小単位であり、図２では交差点間を一つのリンクの単位とし、各リンクに固有の番号（以下、リンク番号と呼ぶ）をつけて区別する。図２の交差点、すなわち各リンクの接続点をノードＮ０〜Ｎ４で表している。ノードは各リンクの始点と終点でもあり、後述するように、ノード間をさらに細かく区分する補間点を設ける場合もある。
【００１３】
また、本実施の形態では、橋やトンネル等のように道路上に特徴的な構造物がある場合には、その前後の道路を別のリンク列データとする。例えば、図３に示すように、国道２４６号上に橋およびトンネルがある場合には、橋およびトンネルの手前、橋およびトンネルの区間、橋およびトンネルの先をそれぞれ別々のリンク列とする。図３では、これらをリンク列１０１〜１０５として表している。このように、道路上の特徴的な構造物を境にしてその前後を別々のリンク列とすることで、道路地図上の橋やトンネル等を容易に検索できるようになる。
【００１４】
地図表示用データは、縮尺率の異なる複数のデータを有する。本実施の形態では、各縮尺率のデータをレベルｎ（ｎは例えば１〜４）のデータと呼ぶ。レベル１が最も詳細な道路地図であり、レベルが上がるほど小縮尺率で広域な道路地図となる。さらに、本実施の形態では、後述するように、各レベルにおいて共通のリンク列は共通のレベル間統合リンク番号で管理され、異なるレベル間でのデータの対応づけを容易にしている。
【００１５】
(2)リンク列データのデータ構成
図２の道路について説明すると、地図表示用データは、図４に示すとおり、リンク列１，２〜ｎに関する各種情報を記述したリンク列データをリンク列ごとに設けて構成され、各リンク列のデータはリンク列情報とノードリンク情報とを有し、リンク列情報は図４にも示す通りの次のデータから構成される。
▲１▼リンク列サイズ
▲２▼要素点数
▲３▼リンク属性
▲４▼道路名称オフセット
▲５▼路線番号
▲６▼レベル間統合リンク番号
【００１６】
またノードリンク情報は図４にも示す通りの次のデータから構成される。
▲１▼属性１＋Ｘ座標
▲２▼属性２＋Ｙ座標
▲３▼同一ノードオフセット
▲４▼誘導オフセット
▲５▼リンク番号
▲６▼高さ情報
【００１７】
(3)リンク列情報について
図５はリンク列サイズの具体的なデータ構成を示す図であり、図５（ａ）に示すように、第１５ビット〜第１３ビットにはレベル間統合リンク番号の収容サイズであるワード数が格納されている。レベル間統合リンク番号については後述する。図５（ｂ）に示すように本実施の形態では、統合リンク番号無しの場合は「０，０，０」で表され、７ワード分で表す統合リンク番号の場合は「１，１，１」で表されるように、８種類のワード数が割当てられている。第１２ビット〜第０ビットにはリンク列の収容サイズであるワード数が格納されている。リンク列収容サイズを記憶するのは、次のリンク列データをすぐにアクセスするためである。
【００１８】
図４において、要素点数はノード点数と補間点数の合計を表すデータ、リンク属性は国道、県道、高速道路などの道路の種別を表すデータ、路線番号は国道や県道の番号である。道路名称オフセットはこの実施の形態では関係がないので説明を省略する。補間点は後述する。
【００１９】
(4)ノードリンク情報について
図６は図２に示すリンク列１および２の詳細を示す。例えば、図６の太線で示すリンク列２のノードリンク情報は図７のようになる。図示のように、リンク列２のデータは、リンク列上のノードＮ１，Ｎ０２，Ｎ３（図６の黒丸）に関するノード情報と補間点（図６の白丸）に関する補間点情報とを含む。ノード情報は、ノードの位置座標Ｘ，Ｙと、ノードに接続されるリンクの属性と、リンク番号とを有し、補間点情報は補間点の位置座標Ｘ，Ｙを有する。これらの位置座標が後述する推奨ルート表示用の形状データあるいはマップマッチング用の形状データとして用いられる。図６の太線のリンク列２は、ノードＮ１とＮ０２の間のリンク番号２１のリンクと、ノードＮ０２とＮ３との間のリンク番号２２のリンクと、ノードＮ３に接続されたリンク番号２３のリンクとを有する。図７からわかるように、ノードＮ０２のノード情報はリンク番号２１のリンクとリンク番号２２のリンクとで共有している。これらノード情報および補間点情報は、リンクの接続順にデータ配置されている。このため、リンク列データを先頭アドレスから順に読み出すことで、リンク列全体の道路形状や道路種別等を検出できる。
【００２０】
このように、本実施の形態では、１つのメッシュ領域内において、リンク列を単位としてデータを管理して、隣接するリンク間のノードは互に共有するため、図２５に示す従来例のように、リンクを単位としてデータを管理する場合に比べてデータの総容量を減らせる。図２５では、リンクＬ０〜Ｌ３はそれぞれ始点と終点にノードＮ０ｂ，Ｎ１ａ，Ｎ１ｂ……Ｎ３ａを有し、各ノードには接続情報として同一ノードであること示す同一ノード情報Ｃ０１，Ｃ１０……が設けられている。
【００２１】
(5)同一ノードを表すオフセット
図６において、リンク列１とリンク列２が交差する地点のノードの符号を、リンク列１のノードをＮ０１とし、リンク列２のノードをＮ０２とし、さらに、リンク列３のノードをＮ０３とする。その場合、これら交差点Ｎ０１〜Ｎ０３のノード情報はそれぞれ同一ノードオフセットというデータ項目を有している。
【００２２】
図８により同一ノードオフセットを詳細に説明する。例えば、リンク列２のノードＮ０２の同一ノードオフセットとしては、リンク列１のノードＮ０１のノード情報が記憶されたアドレス値が格納され、同様に、リンク列１のノードＮ０１の同一ノードオフセットとしては、リンク列３のノード情報が記憶されたアドレス値が格納され、リンク列３のノードＮ０３の同一ノードオフセットとしては、リンク列２のノードＮ０２のノード情報が記憶されたアドレス値が格納される。
【００２３】
一方、図６の交差点Ｎ０１〜Ｎ０３で表された交差点以外のノードは他の道路と交差していないため、これらノードのノード情報の同一ノードオフセット記憶領域には、同一ノードに関する他のノードが存在しないことを示す特定の値、例えばＦＦＦＦｈが格納される。
【００２４】
このように、同一ノードオフセットを設けることで、交差点のように同一ノードに対して複数のノード情報が存在する場合でも、各ノード情報の対応関係を容易に把握できるようになる。また、従来の装置では、図２６に示すように、３本の道路が交差する交差点に対応するノードを５つ（Ｎ０ａ〜Ｎ０ｄ）必要としていたのに対し、本実施の形態では図６に示すように３つ（Ｎ０１〜Ｎ０３）で足りるため、データ量を削減できる。
【００２５】
(6)属性１
ノードのＸ座標とともに格納される属性１はリンク列データを逆方向に読み出すためのオフセット情報である。前述したように、リンク列データには、実際に接続されている順序に従ってノード情報や補間点情報などがデータ配置されている。このため、リンク列データを記憶部の先頭アドレスから順に読み出せば、先頭位置からの道路形状を正確に把握できる。
【００２６】
一方、場合によっては、リンク列データを最後尾から読み出して、最後尾からの道路形状を把握する必要が生じる場合もある。この場合、最後尾のノード情報や補間点情報を読み出した後に、その直前にデータ配置されているノード情報等のヘッダ位置を検出する必要がある。例えば、図６の太線で示すリンクのリンク列データ（図７）を最後尾から読み出す場合を考えると、図９に矢印で示すように、ノードＮ３のノード情報を読み出した後にその直前にデータ配置されている補間点情報のヘッダ位置を検出し、このヘッダ位置から補間点情報を読み出す必要がある。ところが、ノード情報や補間点情報のデータ量は以下に説明するようにノードや補間点によって異なっており、ノード情報や補間点情報のヘッダ位置を一律に決めることはできない。
【００２７】
図１０（ａ）〜（ｄ）はノード情報や補間点情報のデータ量が異なる場合を説明する図であり、図１０（ａ）はノード情報等がＸ，Ｙ位置座標の２ワードで構成される場合、図１０（ｂ）は図１０（ａ）に同一ノードオフセットを加えた３ワードで構成される場合、図１０（ｃ）は図１０（ｂ）に誘導オフセット情報を加えた４ワードで構成される場合、図１０（ｄ）は図１０（ｃ）にリンク番号を加えた５ワードで構成される場合をそれぞれ示す。
【００２８】
図１０（ａ）〜（ｄ）に示すように、ノード情報や補間点情報のデータ量は各リンクによって異なるため、本実施の形態では、ノード情報や補間点情報のヘッダ位置を示す情報を属性１のデータとして予めリンク列データに付加している。この実施の形態では、各ノードや補間点のＸ位置座標とともに付加している。
【００２９】
たとえば、図１１（ａ）は、属性１＋Ｘ座標データを構成する２バイトデータの下位１１ビットにＸ位置座標を格納し、上位２ビットに各ノード情報等のヘッダ位置を示す情報を格納する例を示す図である。この上位２ビットには、各ノード情報等のヘッダ位置まで何ワードであるかを示す情報が格納される。
【００３０】
このように、本実施の形態では、直前のノード情報等のヘッダ位置を示す情報をリンク列データに付加するため、リンク列データを逆方向に読み出す場合でも、すべてのノード情報等を漏れなく読み出すことができる。
【００３１】
(7)属性２
ノードのＹ座標とともに格納される属性２は交通規制情報、道路幅情報、車線数情報を含む。リンク列データを構成するノードリンク情報の各データのデータ長は１６ビット（２バイト＝１ワード）である。属性２＋Ｙ座標を表すデータの下位１１ビットには、図１２（ａ）に示すように、下位１１ビットにＹ位置座標を格納し、上位５ビットに交通規制情報、道路幅情報および車線数情報が格納される。上位５ビットのビットの組み合わせによって図１２（ｂ）の▲１▼〜▲８▼のいずれかの情報が選択される。
【００３２】
このように、ノードの位置座標等を格納するための２バイトデータの空きビットを利用して道路幅情報と交通規制情報と車線数情報を格納するようにしたため、データ量を増やすことなく道路幅情報や交通規制情報等をリンク列データに付加できる。
【００３３】
(8)高さ情報
道路地図を３次元表示する場合には、道路地図上の複数の地点について標高差に関するデータが必要となる。そこで、本実施の形態では、リンク列を構成する各リンクの高さ情報をまとめてリンク列データの最後尾に付加している。なお、高さ情報を有するリンク列データと高さ情報を持たないリンク列データとが混在するので、高さ情報は複数のノードおよび複数の補間点にそれぞれ付加することができる。
【００３４】
リンク列データに高さ情報を付加することで、道路地図を立体的に表示できるようになる。また、高さ情報をリンク列データの最後尾にまとめて付加するため、必要なときだけ高さ情報を読み出せばよく、例えば通常の平面地図を表示する場合のように高さ情報が不要の場合には、高さ情報の直前までのデータを読み出せばよい。
【００３５】
(9)レベル間統合リンク番号
図１３はレベル間統合リンク番号を説明する図である。レベル間統合リンク番号は、図１３（ａ）に示す第１５ビット〜第１３ビットに格納されるレベル番号と、第１１ビット〜第０ビットに格納されるリンク番号とで構成される。下位１２ビットに格納されるリンク番号は、上位３ビットに格納されるレベル番号に対応するレベルに付与されたリンク番号である。たとえば、道路地図表示用データがレベル４〜レベル１の４階層に設定され、経路探索用データがレベル４とレベル２の２階層である場合、レベル２の道路地図表示用データのレベル間統合リンク番号の上位３ビットのレベル番号として、レベル４を表す「０，０，１」が格納され、下位１１ビットにはレベル４のデータに付与されるリンク番号が格納される。
【００３６】
レベル間統合リンク番号を図１４を一例としてさらに説明する。なお、理解を容易にするため、レベル６〜０までの７レベルのデータのうちレベル６，レベル４，レベル２，レベル０について説明する。レベル６のリンク列１のリンク番号１に対応するリンクは、レベル４ではリンク列１を構成するリンク番号１，２の２本のリンクで構成されている。レベル４のリンク番号１に対応するリンクは、レベル２ではリンク列１を構成するリンク番号１，２の２本のリンクで構成され、レベル４のリンク番号２に対応するリンクは、レベル２ではリンク列２を構成するリンク番号３のリンクで構成されている。レベル２のリンク番号１に対応するリンクは、レベル０ではリンク列１を構成するリンク番号１のリンクで構成され、レベル２のリンク番号２に対応するリンクは、レベル０ではリンク列２を構成するリンク番号２のリンクで構成され、レベル２のリンク番号３に対応するリンクは、レベル０ではリンク列３を構成するリンク番号３，４の２本のリンクで構成される。
【００３７】
図１５は図１４に示した各リンク列の先頭ノード（黒丸）に格納されるレベル間統合リンク番号を説明する図である。図１５の▲１▼〜▲６▼は図１４の各リンク列の先頭ノードに格納されるレベル間統合リンク番号▲１▼〜▲６▼に対応して付している。レベル６ではレベル間統合リンク番号は格納されない。レベル４のレベル間統合リンク番号は、「６−１」の１ワード長である。ここで、「６」はレベル４から見て上位のレベル６を意味し、「１」はレベル４のリンク列１に対応する上位レベル６のリンクのリンク番号である。以下の「４−１」，「２−１」なども同様な意味を持つ。
【００３８】
レベル２のレベル間統合リンク番号は、リンク列１については、「６−１」＋「４−１」の２ワード長、リンク列２については、「６−１」＋「４−２」の２ワード長である。
【００３９】
レベル０のレベル間統合リンク番号は、リンク列１については、「６−１」＋「４−１」＋「２−１」の３ワード長、リンク列２については、「６−１」＋「４−１」＋「２−２」の３ワード長、リンク列３については、「６−１」＋「４−２」＋「２−３」の３ワード長である。
【００４０】
レベル間統合リンク番号を使用することにより、異なるレベル間での同一のリンク列の対応づけ、あるいは地図表示用データと経路探索データとの間での同一リンク列の対応づけが容易となり、処理時間の短縮化が図れる。
【００４１】
［２］ルート探索用データ
ルート探索用データは縮尺率の異なる複数の道路地図表示用データに対応する複数のデータを有し、各縮尺率のデータをレベルｍ（ｍは例えば２，４）のデータと呼ぶ。また、本実施の形態では、各レベルにおいて共通のリンク列は共通のレベル間統合リンク番号で管理され、異なるレベル間でのデータの対応づけと道路地図表示用データとのデータの対応づけを容易にしている。
【００４２】
図１６はルート探索用データのデータ構成を示す図である。ルート探索用データには、図示のように、道路を表現する最小単位であるリンクの接続点（ノード）ごとに、他のノードとの接続関係を示すノード情報が格納されている。各ノード情報はそれぞれ、自ノード情報と隣接ノード情報とからなり、自ノード情報の中にはノードの位置座標が格納されている。一方、隣接ノード情報には、図示のように、隣接ノード番号と、自ノードから隣接ノードに至るまでのリンクのリンク番号と、そのリンクのリンクコストと、そのリンクの交通規制情報とが格納されている。また、各ノード情報は、リンクの接続順に格納されており、格納される順番によって自ノードのノード番号を把握できるようにしている。このため、自ノード情報として自ノードのノード番号を格納しなくても自ノードのノード番号を把握でき、メモリ容量を削減できる。
【００４３】
［3］推奨ルートデータ
図１７は、経路探索データに基づいて探索された出発地から目的地までの推奨ルートを表わす推奨ルートデータのデータ構成の概要を示す図である。推奨ルートデータには、推奨ルート上のノード情報とリンク情報とがメッシュ領域単位で分類して格納されている。なお、メッシュ領域とは、道路地図を所定範囲ごとに区分けしたときの区分けされた各領域をいう。
【００４４】
図１７に示すように、推奨ルートデータは、メッシュコード、ノード数、ノード情報、リンク種別数、リンク情報、フェリー情報およびトンネル情報で構成される。このうち、メッシュコードの記憶領域には、メッシュ領域を識別する番号が格納され、ノード数の記憶領域には、メッシュ領域内に存在するノード数が格納され、ノード情報の記憶領域には、図１８（ａ）に詳細を示すように、メッシュ領域内の各ノードのノード番号、位置座標、距離コスト等が格納される。また、リンク種別数の記憶領域には、メッシュ領域内に存在するリンクの種別数が格納され、リンク情報の記憶領域には、図１８（ｂ）に詳細を示すように、メッシュ領域内の各リンクのリンク種別、レベル間統合リンク番号、リンク数、リンク番号等が格納される。図１８（ａ），（ｂ）は同一メッシュコードで示される領域内に２本のリンク列１，２がある場合を示す。
【００４５】
なお、上述したように、推奨ルートデータはレベルごとに作成され、本実施の形態の場合には、推奨ルート上の開始点および終了点付近についてはレベル２の推奨ルートデータが、開始点と終了点の中間についてはレベル４の推奨ルートデータが作成される。
【００４６】
以下、フローチャートを参照して本実施の形態の動作を説明するが、この実施の形態では、次のようにして推奨ルートを表示装置６に表示する。レベル４とレベル２のルート探索用データを使用して推奨ルートを探索してレベル４と２の推奨ルートデータを作成しさらに、これらレベル４と２の推奨データとレベル２と１の道路地図表示用データに基づいて、表示装置６に表示されているレベル２またはレベル１の道路地図上に推奨ルートを重ね合わせて描画して推奨ルートをたとえば赤い太い線で表示する。
【００４７】
図１９，図２０は制御回路２が行うメイン処理の概要を示すフローチャートである。図１９のステップＳ１では、現在地検出装置１を用いて車両位置を検出する。ステップＳ２では、入力装置３によって入力された目的地を読み込む。ステップＳ３では、地図データベース装置８に格納されている地図表示用データに基づいて、経路探索の可能な道路上に経路探索の開始点および終了点を設定する。たとえば、車両の開始点は車両の現在位置（車両位置）、終了点が目的地である。
【００４８】
ステップＳ４では、レベル２のルート探索用データを用いて経路探索の開始点付近の経路探索を行う。そして、開始点付近における推奨ルートの候補を複数選択する。ステップＳ５では、レベル２のルート探索用データを用いて経路探索の終了点付近の経路探索を行う。そして、終了点付近における推奨ルートの候補を複数選択する。
【００４９】
ステップＳ６では、ステップＳ４，Ｓ５で選択した推奨ルートの候補の間の経路についてレベル４のルート探索用データを用いて経路探索を行い、開始点から終了点までの推奨ルートを演算する。
【００５０】
このように、開始点および終了点付近と、開始点および終了点の中間付近とで異なるレベルのルート探索用データを用いる理由は、すべての経路についてレベル２のルート探索用データを用いて経路探索を行うと、データ量が膨大なために経路探索に要する演算時間が長くなるからである。ステップＳ７では、ステップＳ６で演算した推奨ルートに関する情報を推奨ルートデータとしてＳＲＡＭ７に記憶する。
【００５１】
図１９のステップＳ７の処理が終了すると図２０のステップＳ８に進み、図２１に詳細を示す背景地図描画処理を行い、表示装置６に表示するための推奨ルート周辺の道路地図に関するデータを画像メモリ５に描画（格納）する。まず、図２１のステップＳ１１では、車両位置周辺の地図表示用データを地図データベース装置８から読み込む。次に、ステップＳ１２では、読み込んだ地図表示用データの一部を画像メモリ５に描画（格納）する。
【００５２】
図２１のステップＳ１２の処理が終了すると図２０のステップＳ９に進み、ステップＳ３で演算した推奨ルートを表示するのに必要なデータを画像メモリ５に重ねて描画（格納）する。このステップＳ９の推奨ルート描画処理の詳細については後述する。ステップＳ１０では、画像メモリ５に格納されているデータを読み出し、表示装置６に推奨ルートおよびその周辺の道路地図を表示する。
【００５３】
図２２は図２０のステップＳ９の推奨ルート描画処理の詳細フローチャートである。図２２のステップＳ５１では、道路地図の表示縮尺率が（１／１万または１／２万）か、あるいは（１／４万または１／８万）のいずれであるかを判定する。（１／１万または１／２万）であればステップＳ５２に進み、レベル４および２の推奨ルートデータとレベル１の地図表示用データに基づいて、推奨ルートを画像メモリ５に重ねて描画する。
【００５４】
一方、ステップＳ５１によって（１／４万または１／８万）と判定されるとステップＳ５３に進み、レベル４および２の推奨ルートデータとレベル２の地図表示用データに基づいて、推奨ルートを画像メモリ５に重ねて描画する。
【００５５】
図１６に示すように、本実施の形態のルート探索用データおよび推奨ルートデータは、リンクの接続情報だけを保持しており、道路形状に関する情報は保持していない。したがって、モニタ上の道路地図に推奨ルートを重ねて描画するには、推奨ルートデータに基づいて道路地図データから形状データを抽出する必要がある。図２３は、推奨ルートデータに基づいて推奨ルートをモニタ表示するための手順を説明する図である。
【００５６】
図２３（ａ）はレベル４の推奨ルートデータを示す図であり、先頭ノードＮ０と最終ノードＮ１との間にリンク列１を構成するリンク１が存在する。図２３（ｂ）はレベル２の推奨ルートデータと、レベル２の推奨ルートデータに基づいてレベル２の道路地図表示用データから形状データを抽出して画像メモリ５にレベル２として描画した推奨ルート表示データを説明する図である。図２３（ｂ）において、リンク列１はノードＮ０とＮａ間のリンク１と、ノードＮａとＮ１間のリンク２とで構成される。図２０（ｃ）はレベル４もしくはレベル２の推奨ルートデータに基づいてレベル１の道路地図表示用データから形状データを抽出して画像メモリ５にレベル１として描画する手順を詳細に説明する図である。
【００５７】
図２２のステップＳ５１からステップＳ５３に進む場合、すなわち、レベル４および２の推奨ルートデータによりレベル２の道路地図上に推奨ルートを描画するには、図２３（ｂ）に示す推奨ルートデータのレベル間統合リンク番号「４−１」（リンク列１の先頭ノードの情報として格納される）を手がかりにして、レベル２の道路地図表示データを参照して、図２３（ｂ）に示すような、リンク列１を構成するノードＮ０、補間点Ｈｂ、ノードＮａ、補間点Ｈｃ、ノードＮ１の座標値を読み出す。そして、画像メモリ５に描画されているレベル２の道路地図上に推奨ルートデータのリンク１およびリンク２に該当するリンク列を描画する。
【００５８】
図２２のステップＳ５１からステップＳ５２に進む場合、すなわち、レベル４および２の推奨ルートデータによりレベル１の道路地図上に推奨ルートを描画するには、図２３（ｂ）に示す推奨ルートデータのレベル間統合リンク番号「４−１」を手がかりにして、レベル１の道路地図表示データを参照して、図２３（ｃ）に示すように、リンク列１を構成するノードＮ０、補間点Ｈｄ、補間点Ｈｅ、ノードＮｂ、補間点Ｈｆ、ノードＮｃの座標値、および、リンク列２を構成するノードＮｃ、補間点Ｈｇ、補間点Ｈｈ、補間点Ｈｉ、ノードＮ１の座標値を読み出す。そして、画像メモリ５に描画されているレベル１の道路地図上に推奨ルートデータのリンク１およびリンク２に該当するリンク列を描画する。
【００５９】
これに対して、従来の地図データベース装置のルート探索用データは、本発明のレベル間統合リンク番号の代りに、図２７に示すようにルート表示用データへのアドレスオフセット情報を保持し、形状データを持たない推奨ルートデータに形状データを付加してルート表示データを作成し、このルート表示データを画像メモリ上の同一レベルの道路地図上に重ねて描画するようにしていた。例えば、自ノードと隣接ノードＮ１とを接続する経路について、経路探索データは、同一管理レベルの地図示用データへのアドレスオフセット情報Ｏ１と、下位のレベルの地図表示用データへのアドレスオフセット情報Ｏ２とを保持していた。このため、ルート探索用データのデータ量が大きくなるという問題があった。アドレスオフセット情報Ｏ１とは、自ノードＮ０の位置座標が記憶されている、同一のレベル４の道路地図表示データ中のアドレスであり、アドレスオフセット情報Ｏ２〜Ｏ５とは、自ノードＮ０の位置座標が記憶されている、下位のレベル２の道路地図表示データ中のアドレスである。
【００６０】
このように、本実施の形態では、ルート推奨データ中のレベル間統合リンク番号を手がかりにして道路地図表示データの中から道路形状を検出するため、ルート探索用データ内部にルート表示用データのアドレスオフセット情報を備える必要がなく、かつルート表示専用の道路データを備える必要がなく、従来のルート探索用データに比べてルート探索用データのデータ量を少なくできる。
【００６１】
【発明の効果】
本発明によれば、地図データを縮尺率の異なる複数のレベルに対して設け、上位レベルのリンクに対応する下位レベルのリンク列の情報として、上位レベルのレベル番号とその上位レベルの対応リンク番号を含むレベル間統合リンク番号を付与するようにしたので、同一種類のデータの各レベル間あるいは異種の地図データ間で同一のリンクの対応が容易となる。
【図面の簡単な説明】
【図１】本発明による地図データベース装置を搭載した車載用ナビゲーション装置の一実施の形態のブロック図である
【図２】メッシュ領域内で２本の道路が交差する例を示す図
【図３】リンク列データを説明する図
【図４】道路地図表示用データの構成を示す図
【図５】図４のリンク列サイズを説明する図
【図６】複数のノードおよび補間点を有する道路地図の例を示す図
【図７】図６の太線道路のリンク列データを示す図
【図８】リンク列データに付加される、同一ノードオフセット情報を説明する図
【図９】リンク列データを最後尾から読み出す場合の読み出し方法を示す図
【図１０】ノード情報や補間点情報のデータ長の種類を示す図
【図１１】属性１＋Ｘ座標データの一例を示す図
【図１２】属性２＋Ｙ座標データの一例を示す図
【図１３】レベル間統合リンク番号を説明する図
【図１４】各レベルで共通のリンク列とそのリンク列を構成するリンクを説明する図
【図１５】図１４の場合のレベル間統合リンク番号を説明する図
【図１６】ルート探索用データのデータ構成を示す図
【図１７】推奨ルートデータのデータ構成の概要を示す図
【図１８】推奨ルートデータのノード情報とリンク情報のデータ構成の詳細図
【図１９】制御回路が行うメイン処理の概要を示すフローチャート
【図２０】図１９に続くフローチャート
【図２１】図２０のステップＳ８の背景地図描画処理の詳細フローチャート
【図２２】図２０のステップＳ９の推奨ルート描画処理の詳細フローチャート
【図２３】本実施の形態におけるルート推奨データから推奨ルートを画像メモリに描画する手順を説明する図
【図２４】異なるレベルのリンク列とリンクを説明する図
【図２５】リンクデータとノードデータの従来例を示す図
【図２６】交差点を境にして各道路をそれぞれ別リンクにする従来例を説明する図
【図２７】従来のルート探索用データとルート表示用データの関係を示す図
【符号の説明】
１  現在地検出装置
２  制御回路
３  入力装置
４  ＤＲＡＭ
５  画像メモリ
６  表示装置
７  ＳＲＡＭ
８  地図データベース装置
【図１】
0003665436.tif 000002
【図２】
0003665436.tif 000003
【図３】
0003665436.tif 000004
【図４】
0003665436.tif 000005
【図５】
0003665436.tif 000006
【図６】
0003665436.tif 000007
【図７】
0003665436.tif 000008
【図８】
0003665436.tif 000009
【図９】
0003665436.tif 000010
【図１０】
0003665436.tif 000011
【図１１】
0003665436.tif 000012
【図１２】
0003665436.tif 000013
【図１３】
0003665436.tif 000014
【図１４】
0003665436.tif 000015
【図１５】
0003665436.tif 000016
【図１６】
0003665436.tif 000017
【図１７】
0003665436.tif 000018
【図１８】
0003665436.tif 000019
【図１９】
0003665436.tif 000020
【図２０】
0003665436.tif 000021
【図２１】
0003665436.tif 000022
【図２２】
0003665436.tif 000023
【図２３】
0003665436.tif 000024
【図２４】
0003665436.tif 000025
【図２５】
0003665436.tif 000026
【図２６】
0003665436.tif 000027
【図２７】
0003665436.tif 000028