(57)【要約】    【課題】要約地図において道路形状が簡略化された複数の互いに重複している経路について、その重複部分で各経路が判別できるように表示できるナビゲーション装置を提供する。    【解決手段】現在地６１から目的地６２までの複数の経路Ｒ１、Ｒ２およびＲ３を探索し、各経路の道路形状を簡略化して表示する。このとき、（ａ）のように２以上の経路が同一の道路を重複して通っている場合には、経路シフト処理を実行することにより、各経路の全体を所定のシフト幅ずつずらす。こうして重複部分をずらし、（ｂ）のような要約地図を表示する。【選択図】図１２
2006113460.tif 000002
【特許請求の範囲】
【請求項１】
出発地から目的地まで複数の経路を探索する経路探索手段と、
前記経路探索手段により探索された複数の経路の地図を表示モニタに表示する地図表示制御手段とを備え、
前記地図表示制御手段は、前記複数の経路のうちいずれか２以上の経路が同一の道路を重複して通っている場合、その重複部分をずらして表示することを特徴とするナビゲーション装置。
【請求項２】
請求項１のナビゲーション装置において、
前記地図表示制御手段は、前記重複部分をずらして表示するとき、元の形状を維持したままで、前記重複している各経路の全体をずらすことを特徴とするナビゲーション装置。
【請求項３】
請求項２のナビゲーション装置において、
前記地図表示制御手段は、前記重複している各経路の重心座標に基づいて、その各経路に対するずらし幅をそれぞれ設定することを特徴とするナビゲーション装置。
【請求項４】
請求項１のナビゲーション装置において、
前記地図表示制御手段は、前記重複部分をずらして表示するとき、その重複部分以外をずらさないで、前記重複している各経路の一部分のみをずらすことを特徴とするナビゲーション装置。
【請求項５】
請求項４のナビゲーション装置において、
前記地図表示制御手段は、前記重複している各経路における前記重複部分からの流出角度または前記重複部分への流入角度に基づいて、その各経路に対するずらし幅をそれぞれ設定することを特徴とするナビゲーション装置。
【請求項６】
請求項１〜５のいずれかのナビゲーション装置において、
前記地図表示制御手段は、前記重複部分をずらして表示するとき、予め定められた所定幅単位で各経路をずらすことを特徴とするナビゲーション装置。
【請求項７】
出発地から目的地まで複数の経路を探索する経路探索手段と、
前記経路探索手段により探索された複数の経路の地図を表示するための表示用データを作成するデータ作成手段と、
前記データ作成手段により作成された表示用データを外部へ配信するデータ配信手段とを備え、
前記データ作成手段は、前記複数の経路のうちいずれか２以上の経路が同一の道路を重複して通っている場合、その重複部分をずらして前記表示用データを作成することを特徴とする地図データ配信装置。
【請求項８】
請求項７の地図データ配信装置において、
前記データ作成手段は、前記重複部分をずらして前記表示用データを作成するとき、元の形状を維持したままで、前記重複している各経路の全体をずらすことを特徴とする地図データ配信装置。
【請求項９】
請求項８の地図データ配信装置において、
前記データ作成手段は、前記重複している各経路の重心座標に基づいて、その各経路に対するずらし幅をそれぞれ設定することを特徴とする地図データ配信装置。
【請求項１０】
請求項７の地図データ配信装置において、
前記データ作成手段は、前記重複部分をずらして前記表示用データを作成するとき、その重複部分以外をずらさないで、前記重複している各経路の一部分のみをずらすことを特徴とする地図データ配信装置。
【請求項１１】
請求項１０の地図データ配信装置において、
前記データ作成手段は、前記重複している各経路における前記重複部分からの流出角度または前記重複部分への流入角度に基づいて、その各経路に対するずらし幅をそれぞれ設定することを特徴とする地図データ配信装置。
【請求項１２】
請求項７〜１１のいずれかの地図データ配信装置において、
前記データ作成手段は、前記重複部分をずらして表示するとき、予め定められた所定幅単位で各経路をずらすことを特徴とする地図データ配信装置。
【請求項１３】
請求項７〜１２のいずれかの地図データ配信装置と、
前記表示用データを受信して前記複数の経路の地図を表示する地図表示装置とを有する地図データ配信システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、出発地から目的地までの複数の経路の地図を表示する技術に関する。
【背景技術】
【０００２】
地図を表すための地図データに基づいて、道路形状を簡略化する方法が知られている。たとえば、特許文献１に開示される装置では、地図データにおいて道路形状を表している各リンクに対して直線化や直交化などの処理を行い、さらに、マスクで規定した範囲内のランドマーク情報のみを表示することにより、道路形状を簡略化する。このようにして簡略化された道路形状を用いて地図を表示することで、見やすい地図を提供する。
【０００３】
【特許文献１】特開平１１−２０２７６２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
特許文献１に開示される装置により、複数の経路の道路形状をそれぞれ簡略化して同時に表示すると、経路同士が重なっている場合にはその重複部分が見えづらい場合がある。そのため、要約地図において道路形状が簡略化され複数の互いに重複している経路について、その重複部分で各経路が判別できるように表示できる装置が求められている。
【課題を解決するための手段】
【０００５】
請求項１の発明によるナビゲーション装置は、出発地から目的地まで複数の経路を探索する経路探索手段と、経路探索手段により探索された複数の経路の地図を表示モニタに表示する地図表示制御手段とを備え、地図表示制御手段は、複数の経路のうちいずれか２以上の経路が同一の道路を重複して通っている場合、その重複部分をずらして表示するものである。
請求項２の発明は、請求項１のナビゲーション装置において、地図表示制御手段は、重複部分をずらして表示するとき、元の形状を維持したままで、重複している各経路の全体をずらすものである。
請求項３の発明は、請求項２のナビゲーション装置において、地図表示制御手段は、重複している各経路の重心座標に基づいて、その各経路に対するずらし幅をそれぞれ設定するものである。
請求項４の発明は、請求項１のナビゲーション装置において、地図表示制御手段は、重複部分をずらして表示するとき、その重複部分以外をずらさないで、重複している各経路の一部分のみをずらすものである。
請求項５の発明は、請求項４のナビゲーション装置において、地図表示制御手段は、重複している各経路における重複部分からの流出角度または重複部分への流入角度に基づいて、その各経路に対するずらし幅をそれぞれ設定するものである。
請求項６の発明は、請求項１〜５のいずれかのナビゲーション装置において、地図表示制御手段は、重複部分をずらして表示するとき、予め定められた所定幅単位で各経路をずらすものである。
請求項７の発明による地図データ配信装置は、出発地から目的地まで複数の経路を探索する経路探索手段と、経路探索手段により探索された複数の経路の地図を表示するための表示用データを作成するデータ作成手段と、データ作成手段により作成された表示用データを外部へ配信するデータ配信手段とを備え、データ作成手段は、複数の経路のうちいずれか２以上の経路が同一の道路を重複して通っている場合、その重複部分をずらして表示用データを作成するものである。
請求項８の発明は、請求項７の地図データ配信装置において、データ作成手段は、重複部分をずらして表示用データを作成するとき、元の形状を維持したままで、重複している各経路の全体をずらすものである。
請求項９の発明は、請求項８の地図データ配信装置において、データ作成手段は、重複している各経路の重心座標に基づいて、その各経路に対するずらし幅をそれぞれ設定するものである。
請求項１０の発明は、請求項７の地図データ配信装置において、データ作成手段は、重複部分をずらして表示用データを作成するとき、その重複部分以外をずらさないで、重複している各経路の一部分のみをずらすものである。
請求項１１の発明は、請求項１０の地図データ配信装置において、データ作成手段は、重複している各経路における重複部分からの流出角度または重複部分への流入角度に基づいて、その各経路に対するずらし幅をそれぞれ設定するものである。
請求項１２の発明は、請求項７〜１１のいずれかの地図データ配信装置において、データ作成手段は、重複部分をずらして表示するとき、予め定められた所定幅単位で各経路をずらすものである。
請求項１３の発明による地図データ配信システムは、請求項７〜１２のいずれかの地図データ配信装置と、表示用データを受信して複数の経路の地図を表示する地図表示装置とを有するものである。
【発明の効果】
【０００６】
本発明によれば、探索された複数の経路のうちいずれか２以上の経路が同一の道路を重複して通っている場合、その重複部分をずらして表示することとした。このようにしたので、要約地図において道路形状が簡略化された複数の互いに重複している経路について、その重複部分で各経路が判別できるように表示することができる。
【発明を実施するための最良の形態】
【０００７】
−第１の実施形態−
本発明の一実施形態によるナビゲーション装置の構成を図１に示す。このナビゲーション装置は車両に搭載されており、設定された目的地までの経路を複数探索して、各経路の全体について通常の地図を基に道路形状などを簡略化することにより、通常の地図を要約した地図（以下、要約地図という）を作成して表示する。そして、表示した複数の経路のうち１つをユーザに選択させ、その経路を推奨経路として自車両を目的地まで案内する。図１に示すナビゲーション装置１は、制御回路１１、ＲＯＭ１２、ＲＡＭ１３、現在地検出装置１４、画像メモリ１５、表示モニタ１６、入力装置１７、およびディスクドライブ１８を有している。ディスクドライブ１８には、地図データが記録されたＤＶＤ−ＲＯＭ１９が装填される。
【０００８】
制御回路１１は、マイクロプロセッサおよびその周辺回路からなり、ＲＡＭ１３を作業エリアとしてＲＯＭ１２に格納された制御プログラムを実行することにより、各種の処理や制御を行う。この制御回路１１において後で説明するような処理を実行することによって、設定された目的地に対してＤＶＤ−ＲＯＭ１９に記録された地図データに基づいて複数の経路が探索され、各経路の全体について要約地図が作成されて、それぞれ表示モニタ１６に表示される。
【０００９】
現在地検出装置１４は、自車両の現在地を検出する装置であり、たとえば、自車両の進行方位を検出する振動ジャイロ１４ａ、車速を検出する車速センサ１４ｂ、ＧＰＳ衛星からのＧＰＳ信号を検出するＧＰＳセンサ１４ｃ等からなる。ナビゲーション装置１は、この現在地検出装置１４により検出された自車両の現在地に基づいて、推奨経路を探索するときの経路探索開始点を決定することができる。
【００１０】
画像メモリ１５は、表示モニタ１６に表示するための画像データを一時的に格納する。この画像データは、要約地図を画像表示するための道路地図描画用データや各種の図形データ等からなり、制御回路１１において、ＤＶＤ−ＲＯＭ１９に記録されている地図データに基づいて作成される。この画像メモリ１５に格納された画像データを用いて、各経路の全体の要約地図が表示モニタ１６に表示される。
【００１１】
入力装置１７は、ユーザが目的地の設定などを行うための各種入力スイッチを有し、これは操作パネルやリモコンなどによって実現される。ユーザは、表示モニタ１６に表示される画面指示に従って入力装置１７を操作することにより、地名や地図上の位置を指定して目的地を設定し、その目的地までの経路探索をナビゲーション装置１に開始させることができる。
【００１２】
ディスクドライブ１８は、要約地図を作成するために用いられる地図データを、装填されたＤＶＤ−ＲＯＭ１９より読み出す。なお、ここではＤＶＤ−ＲＯＭを用いた例について説明しているが、ＤＶＤ−ＲＯＭ以外の他の記録メディア、たとえばＣＤ−ＲＯＭやハードディスクなどより、地図データを読み出すこととしてもよい。この地図データには、複数の経路を演算するために用いられる経路計算データや、交差点名称、道路名称など、ユーザに選択された推奨経路に従って自車両を目的地まで案内するために用いられる経路誘導データ、道路を表す道路データ、さらには海岸線や河川、鉄道、地図上の各種施設（ランドマーク）など、道路以外の地図形状を表す背景データなどが含まれている。
【００１３】
道路データにおいて、道路区間を表す最小単位はリンクと呼ばれている。すなわち、各道路は所定の道路区間ごとに設定された複数のリンクによって構成されている。なお、リンクによって設定される道路区間の長さは異なっており、リンクの長さは一定ではない。リンク同士を接続している点はノードと呼ばれ、このノードはそれぞれに位置情報（座標情報）を有している。また、リンク内にはノードとノードの間に形状補間点と呼ばれる点が設定されていることもある。形状補間点もノードと同じく、それぞれに位置情報（座標情報）を有している。このノードと形状補間点の位置情報によって、リンク形状、すなわち道路の形状が決定される。経路計算データには、上記の各リンクに対応して、自車両の通過所要時間を表すためのリンクコストと呼ばれる値が設定されている。
【００１４】
前述のように入力装置１７におけるユーザの操作によって目的地が設定されると、制御回路１１において図２に示すフローチャートが実行される。これにより、現在地検出装置１４により検出された現在地を経路探索開始点として、設定された目的地までの経路演算が経路計算データに基づいて所定のアルゴリズムにより行われ、目的地までの複数の経路が求められる。そして、こうして求められた各経路の全体の要約地図が道路データに基づいて作成され、表示モニタ１６に表示される。
【００１５】
図２のフローチャートについて以下に説明する。ステップＳ１００では、ユーザに入力された目的地により、経路探索の目的地を設定する。ステップＳ２００では、経路探索開始点である自車両の現在地から、ステップＳ１００において設定された目的地まで、複数の経路を探索する。このとき、前述したように経路計算データに基づいて所定のアルゴリズムにより経路演算が行われる。なお、自車両の現在地は現在地検出装置１４によって一定時間ごとに求められる。
【００１６】
なお、ステップＳ２００では複数の経路を探索するために、様々な経路探索条件によって経路探索を行う。たとえば、有料道路優先や一般道路優先、距離優先などの経路探索条件によって経路探索を行い、それぞれの条件で最適な経路を求めることにより、複数の経路を探索する。あるいは、１つの経路探索条件によって最適経路以外の経路も探索することで、複数の経路を探索するようにしてもよい。たとえば、目的地までのリンクコストの合計が最も小さいものを最適経路とし、さらにその最適経路とリンクコストの合計の差が所定値以内である経路も含めて経路探索結果を求めることにより、１つの経路探索条件で複数の経路を探索することができる。
【００１７】
ステップＳ３００では、ステップＳ２００で探索された各経路に対して、要約地図作成処理を実行する。このときの処理内容については、後で詳しく説明する。この要約地図作成処理によって、各経路の全体、すなわち現在地から目的地までを表す要約地図が作成される。
【００１８】
ステップＳ４００では、経路シフト処理を実行する。ここでは、ステップＳ３００で作成された要約地図において、探索された複数の経路のうちいずれか２以上の経路が同一の道路を重複して通っている場合に、その重複部分をそれぞれの経路が判別できるような表示形態で描画する処理を行う。具体的には、その重複部分の描画位置をずらす（シフトする）ことにより、各経路を判別できるようにする。なお、この経路シフト処理の具体的な内容は後で詳しく説明する。
【００１９】
ステップＳ５００では、ステップＳ３００において作成され、さらにステップＳ４００において重複部分の描画位置がずらされた各経路の要約地図を、表示モニタ１６に表示する。このとき、出発地と目的地にはそれぞれ出発地マークと目的地マークを表示する。ステップＳ５００を実行した後は、図２のフローチャートを終了する。以上説明したようにして、目的地までの複数の経路が探索され、各経路の全体の要約地図が表示モニタ１６に重複部分をずらして表示される。
【００２０】
図２のフローチャートの処理を実行して各経路の全体の要約地図を表示モニタ１６に表示したら、その後ナビゲーション装置１は、各経路のうち１つをユーザに選択するように指示する。ユーザが入力装置１７を操作することによっていずれかの経路を選択すると、選択された経路を推奨経路に設定して、現在地の周辺の道路地図上を表示してその上に推奨経路を示す。そして、この推奨経路に従って自車両を誘導し、目的地まで案内する。なお、このとき現在地周辺の道路地図として、通常の地図と要約地図のどちらを表示してもよい。このときの要約地図も、図２のフローチャートと同様の処理によって作成することができる。
【００２１】
図３は、通常の要約前の地図と、図２のフローチャートの処理を実行することによって表示された要約地図とを示したものである。（ａ）に示す要約前の地図には、現在地６１から目的地６２までをつなぐ３つの経路Ｒ１、Ｒ２およびＲ３が示されている。この経路Ｒ１〜Ｒ３に対して図２のフローチャートの処理を実行することにより、（ｂ）の要約地図が表示される。この要約地図では、経路Ｒ１〜Ｒ３の道路形状がそれぞれ簡略化されていることが分かる。こうして各経路の要約地図を表示した後、いずれか選択された経路を推奨経路として、現在地６１から目的地６２まで自車両を案内する。
【００２２】
次に、ステップＳ３００において実行される要約地図作成処理の内容について説明する。要約地図作成処理では、方向量子化処理と呼ばれる処理を実行することによって各経路の道路形状を簡略化することにより、各経路の要約地図を作成する。この方向量子化処理について、以下に説明する。
【００２３】
方向量子化処理では、各経路のリンクをそれぞれ所定の分割数で分割した上で、道路形状の簡略化を行う。図４および図５は、いずれもこの方向量子化処理の内容を説明するための詳細説明図であり、図４ではリンク分割数が２（２分割）の場合について、また図５ではリンク分割数が４（４分割）の場合について、それぞれの方向量子化処理の内容を図示している。以下、図４に示す２分割の場合より先に説明を行う。
【００２４】
図４（ａ）の符号３０は、探索された経路に含まれているリンクの１つを例示している。このリンク３０に対して、（ｂ）に示すように、その両端点の間を結ぶ線分３１から最も遠くにあるリンク３０上の点３２を選択する。なお、ここで選択される点３２は前述の形状補間点に相当し、両端点はノードに相当する。
【００２５】
上記のような点３２が求められたら、次に（ｃ）に示すように、リンク３０の両端点のそれぞれと点３２とを結ぶ線分３３および３４を設定する。この線分３３と３４がそれぞれの基準線に対してなす角度をθ１およびθ２と表す。なお、ここでいう基準線とは、リンク３０の両端点から予め決められた所定の方向（たとえば、真北方向）に向かって、それぞれ延びている線のことである。（ｃ）に示すように、一方の端点からの基準線と線分３３によって挟まれている部分の角度が、θ１と表される。また、もう一方の端点からの基準線と線分３４によって挟まれている部分の角度が、θ２と表される。
【００２６】
上記のようにして点３２とリンク３０の両端点とをそれぞれ結ぶ線分３３、３４が設定されたら、次に（ｄ）に示すように、この線分３３と３４の方向をそれぞれ量子化する。ここでいう方向の量子化とは、前述の角度θ１およびθ２が予め設定された単位角度の整数倍にそれぞれなるように、線分３３と３４を各端点を中心にしてそれぞれ回転させることをいう。すなわち、θ１＝ｍ・Δθ、θ２＝ｎ・Δθ（ｎ、ｍは整数）となるように、線分３３と３４をそれぞれ回転させてθ１とθ２の値を補正する。上記の式においてｍとｎの値は、この式によって計算される補正後のθ１とθ２がそれぞれ元の値に最も近くなるように設定される。
【００２７】
以上説明したように線分３３と３４の方向をそれぞれ量子化すると、線分３３と３４が基準線となす角度θ１およびθ２が、単位角度Δθ刻みで補正される。なお図４（ｄ）では、Δθ＝１５°としている。そして、θ１についてはｍ＝６と設定して補正後の角度を９０°にし、θ２についてはｎ＝０と設定して補正後の角度を０°にした例を図示している。
【００２８】
こうして線分３３と３４の方向をそれぞれ量子化したら、次に線分３３と３４をそれぞれ延長したときの交点を求める。そして、その交点と各端点とを結ぶようにして、（ｄ）に示すように、線分３３と３４の長さをそれぞれ補正する。
【００２９】
以上説明したようにして、線分３３と３４を求め、これらの方向を量子化すると共に長さを補正することによって、リンク３０に対する２分割の場合の方向量子化処理が行われる。この線分３３と３４をリンク３０の代わりに用いることで、リンク３０の形状を簡略化して表すことができる。このとき、リンク３０の両端点の位置が固定された状態でリンク３０の形状が簡略化されるため、隣接するリンクの位置には影響を及ぼさない。したがって、方向量子化処理を用いて経路の各リンク形状をそれぞれ簡略化することにより、経路の全体的な位置関係を保ちつつ、その道路形状を容易に簡略化することができる。
【００３０】
次に、４分割の場合の方向量子化処理について説明する。図５（ａ）の符号４０は、図４（ａ）と同様に、探索された経路に含まれているリンクの１つを例示している。このリンク４０に対して、（ｂ）に示すように、まずその両端点の間を結ぶ線分４１ａから最も遠くにあるリンク４０上の点４２ａを選択する。次に、その点４２ａとリンク４０の各端点とをそれぞれ結ぶ線分４１ｂおよび４１ｃを設定し、この線分４１ｂと４１ｃからそれぞれ最も遠く離れた位置にあるリンク４０上の点４２ｂおよび４２ｃを選択する。なお、ここで選択される点４２ａ〜４２ｃは、いずれも２分割の場合と同様に前述のノードまたは形状補間点に相当する。
【００３１】
上記のような点４２ａ〜４２ｃが求められたら、次に（ｃ）に示すように、２分割の場合と同様にして、リンク４０の各端点と点４２ａ〜４２ｃとをそれぞれ順に結ぶ線分４３、４４、４５および４６を設定する。この線分４３〜４６がそれぞれの基準線に対してなす角度を、θ３、θ４、θ５およびθ６と表す。なお、このときの基準線はリンク４０の両端点に対して定められるだけでなく、点４２ａ〜４２ｃのうち真ん中に位置する最初に選択された点４２ａに対しても定められる。
【００３２】
上記のようにして線分４３〜４６が設定されたら、次に（ｄ）に示すように、各線分の方向をそれぞれ量子化する。このとき、点４２ａを保存点として、線分４４と４５はこの保存点４２ａを中心にそれぞれ回転させる。なお、線分４３と４６については、２分割の場合と同様に各端点を中心にそれぞれ回転させる。ここでは、Δθ＝１５°と予め設定し、θ３〜θ６の補正後の角度をそれぞれ６０°、４５°、１８０°および６０°とした例を図示している。
【００３３】
こうして線分４３〜４６の方向をそれぞれ量子化したら、次に線分４３と４４をそれぞれ延長したときの交点と、線分４５と４６をそれぞれ延長したときの交点とを求める。そして、各交点と各端点または保存点４２ａとを結ぶようにして、（ｄ）に示すように、線分４３〜４６の長さをそれぞれ補正する。
【００３４】
以上説明したようにして、線分４３〜４６を求め、これらの方向を量子化すると共に長さを補正することによって、リンク４０に対する４分割の場合の方向量子化処理が行われる。この線分４３〜４６をリンク４０の代わりに用いることで、リンク４０の形状を簡略化して表すことができる。このとき、リンク４０の両端点の位置に加えて、さらに保存点４２ａの位置も固定された状態で、リンク４０の形状が簡略化される。したがって、複雑な形状のリンクによって構成されている経路に対しても、その全体的な位置関係を保ちつつ適切に道路形状を簡略化することができる。
【００３５】
なお、上記では２分割と４分割の場合の方向量子化処理について説明したが、これ以外の分割数についても同様にして方向量子化処理を実行することができる。たとえば８分割の場合には、まず４分割の場合と同様に、リンクの両端点の間を結ぶ線分から最も遠い１点と、その点と両端点とを結ぶ２つの線分からそれぞれ最も遠い２点を選択する。その後、さらにこれらの３点に両端点を加えた各点間を結ぶ４つの線分からそれぞれ最も遠い４点を選択する。こうして選択された合計７点と両端点とを順に結ぶ８つの線分を求め、これらの線分に対して前述したような方向の量子化と長さの補正を行うことによって、８分割の方向量子化処理を行うことができる。
【００３６】
方向量子化処理の分割数をいくつにするかは、予め設定しておいてもよいし、あるいはリンクの形状によって判断してもよい。たとえば、上記のようにして両端点またはそれまでに選択された点の間を結ぶ各線分から最も遠い点を順次選択していくとき、すなわち図４および５の（ｂ）で説明した処理を繰り返していくときに、各線分から最も遠い点までの距離が所定値以下となるまで処理を繰り返して、その処理回数に応じた数の点を順次選択していく。このようにすれば、リンクの形状によって方向量子化処理の分割数を決めることができる。
【００３７】
図４で説明した２分割の方向量子化処理において、方向を量子化した後に線分３３と３４をそれぞれ延長しても、適切な交点がない場合がある。すなわち、方向を量子化した後の線分３３と３４が平行となっている場合には、これらの線分を延長すると両者が一体化してリンク３３の両端点を結ぶ１つの線分となるため、交点が存在しないこととなる。このような場合には、その両端点を直接結ぶ線分、すなわち線分３１を用いて、リンク３０の形状を簡略化して表すようにすればよい。また、図５で説明した４分割の方向量子化処理や、それ以上の分割数の方向量子化処理において、同様に方向を量子化した後に各線分を延長すると適切な交点がない場合には、それよりも分割数が少ない方向量子化処理を行うようにすればよい。
【００３８】
以上説明したような方向量子化処理を各経路の全てのリンクに対して順次実行していくことにより、各経路の道路形状を簡略化して要約地図を作成することができる。なお、リンク単位ではなく、リンクを複数連ねて構成されるリンク列ごとに上記のような方向量子化処理を実行するようにしてもよい。この場合、図４の点３２や図５の点４２ａ〜４２ｃとして選択される点には、形状補間点だけでなくノードも含まれることになる。
【００３９】
または、ステップＳ３００の要約地図作成処理において、上記の方向量子化処理を実行せずに各経路の道路形状を簡略化することもできる。ここでは、各リンク形状を曲線で近似することによって各経路の道路形状を簡略化する方法を、図６を参照して説明する。
【００４０】
図６（ａ）には、探索された経路に含まれるリンクの一部として、リンク５０、５１および５２を例示している。これらのリンク５０〜５２に対して、まず（ｂ）に示すように各リンクの両端点において量子化したリンク方向を求める。ここでは、前述の方向量子化処理において各線分の方向の量子化を行ったのと同様にして、元の角度に最も近くて単位角度の整数倍となるようなリンク方向を求める。その結果、（ｂ）において矢印で示されているようなリンク方向が各端点に対して求められる。
【００４１】
次に、（ｃ）に示すように各端点の間を結ぶ曲線５３、５４および５５を求めることにより、各リンクの形状を曲線近似する。このとき、各曲線の端点付近における接線の方向が上記の量子化したリンク方向と一致するように、曲線５３〜５５の形状がそれぞれ決定される。なお、このような曲線を求める方法としては、たとえばスプライン関数を用いたスプライン近似などがあるが、ここでは詳細な説明は省略する。
【００４２】
以上説明したような処理を各経路の全てのリンクに対して順次実行していき、求められた曲線を用いて道路形状を表すことにより、各経路の道路形状を簡略化して要約地図を作成することができる。このときも方向量子化処理の場合と同様に、各リンクの両端点の位置が固定された状態で各リンクの形状が簡略化される。したがってこの場合にも、経路の全体的な位置関係を保ちつつ、その道路形状を容易に簡略化することができる。
【００４３】
上記の方向量子化処理によって経路ネットワークデータを変更する様子を図７に示す。ここでいう経路ネットワークデータとは、図２のステップＳ２００で探索された経路を表すために、地図データに基づいて作成されるデータである。方向量子化処理では、この経路ネットワークデータの内容を変更することによって、道路形状を簡略化する。
【００４４】
図７（ａ）は入力データ、すなわち要約前の経路ネットワークデータにより表される経路Ｒ１、Ｒ２およびＲ３を示している。図中の四角形はノードを、黒丸は補間点（形状補間点）を、実線はリンクをそれぞれ表している。また、矢印は経路の進行方向を表している。なお、破線は非経路リンクを表しており、これは方向量子化処理において入力対象とされない。このような入力データに基づいて、要約前にまず（ｂ）に示すような内部データを設定する。この内部データを設定する際には、各経路のリンクを統合して分岐点をノードとする。すなわち、分岐点以外にあるノード（始点と終点を除く）を補間点に置き換える。
【００４５】
（ｂ）の内部データに対して上記の方向量子化処理を実行することにより、（ｃ）に示すような出力データが要約地図として得られる。この出力データでは、ノードの位置は変化せず、補間点の位置のみが変化している。なお、リンク形状が変化しない部分にある余分な補間点は間引きされている。このようにして、方向量子化処理によって経路ネットワークデータが変更される。
【００４６】
図８は、経路ネットワークデータの表現形式の例を示している。経路ネットワークデータでは、ノードデータ、リンクデータ、および経路データによって各経路を表している。（ａ）は、経路中の各ノードに対してそれぞれ設定されているノードデータの表現形式の例である。このノードデータには、ノードＩＤと座標が含まれている。ノードＩＤは、各ノードに固有に割り振られており、これによってそのノードが特定される。座標は、そのノードの地図上の位置を示している。（ａ）には例として、ノードＩＤがＮ１であり、座標値が（Ｘ１，Ｙ１）であるノードデータを示している。
【００４７】
（ｂ）は、経路中の各リンクに対してそれぞれ設定されているリンクデータの表現形式の例である。このリンクデータには、リンクＩＤ、始点ノードＩＤ、終点ノードＩＤ、補間点数および補間点情報が含まれている。リンクＩＤは、各リンクに固有に割り振られており、これによってそのリンクが特定される。始点ノードＩＤと終点ノードＩＤは、そのリンクの始点と終点のノードＩＤを表しており、前述のノードデータにおいて同じノードＩＤのものを参照することで、始点と終点の座標を特定することができる。補間点数は、そのリンクに含まれる補間点の合計数を表しており、補間点情報は、そのリンクに含まれる各補間点の座標を表している。（ｂ）には例として、リンクＩＤがＬ１、始点ノードＩＤがＮ１、終点ノードＩＤがＮ２、補間点数がｐであり、合計ｐ個の補間点に対して、その補間点情報として座標値（ｘ１，ｙ１）から（ｘｐ，ｙｐ）までが設定されたリンクデータを示している。なお、補間点数と補間点情報は、上記の方向量子化処理の結果によってその内容が変更される。
【００４８】
（ｃ）は、各経路に対してそれぞれ設定されている経路データの表現形式の例である。この経路データには、経路ＩＤ、経路リンク数および経路リンク情報が含まれている。経路ＩＤは、各経路に固有に割り振られており、これによってその経路が特定される。経路リンク数は、その経路に含まれるリンクの合計数を表しており、経路リンク情報は、その経路に含まれる各リンクのリンクＩＤを表している。前述のリンクデータから同じリンクＩＤのものを参照することで、経路中のリンクの位置や形状を特定することができる。なお、経路リンク情報には、各リンクＩＤに対して経路の進行方向との関係を示すための方向フラグも設定される。この方向フラグは、リンクＩＤの登録順序を経路の進行方向に一致させることで省略してもよい。（ｃ）には例として、経路ＩＤがＲ１、経路リンク数がｎであり、合計ｎ個の経路リンクに対する経路リンク情報として、リンクＩＤがＬ１からＬｎまで設定された経路データを示している。
【００４９】
次に、ステップＳ４００において実行される経路シフト処理について説明する。ここでは、ステップＳ３００の要約地図作成処理によって道路形状が簡略化された各経路について、図９に示すフローチャートを実行することで、元の形状を維持したままで重複している各経路の全体をずらす。以下、図９のフローチャートについて説明する。
【００５０】
ステップＳ４０１では、ステップＳ３００で作成された要約地図の各経路について、それぞれの重心の座標を求める。たとえば、いずれかの経路の重心座標を（ｘg，ｙg）と表すこととすると、その座標値は以下の式（１）によって算出することができる。
【００５１】
【数１】
2006113460.tif 000003
【００５２】
式（１）において、（ｘi，ｙi）はその経路を構成する各点の座標値を表しており、ｎはその点の数を表している。ｉは１からｎまでの整数値のいずれかである。すなわち、式（１）によって経路を構成する各点の座標値の平均値が計算され、その平均値によって経路の重心座標（ｘg，ｙg）が表される。このように、各点の位置に応じて重み付けを行って、経路の重心の座標値を求める。
【００５３】
式（１）により経路の重心座標を求める様子を、図１０に示す例を用いて説明する。経路Ｒ１は、始点（ｘ1，ｙ1）から終点（ｘ10，ｙ10）までの間に計８個の補間点を有している。これらの補間点の座標値を、始点に近いほうから順に（ｘ2，ｙ2）、（ｘ3，ｙ3）、・・・、（ｘ9，ｙ9）とすると、重心Ｇ１の座標値（ｘg，ｙg）は式（１）を用いて次のように計算される。
ｘg＝（ｘ1＋ｘ2＋ｘ3＋ｘ4＋ｘ5＋ｘ6＋ｘ7＋ｘ8＋ｘ9＋ｘ10）／１０
ｙg＝（ｙ1＋ｙ2＋ｙ3＋ｙ4＋ｙ5＋ｙ6＋ｙ7＋ｙ8＋ｙ9＋ｙ10）／１０
【００５４】
あるいは、上記の式（１）に替えて、以下の式（２）により経路の重心の座標値を求めてもよい。
【００５５】
【数２】
2006113460.tif 000004
【００５６】
式（２）において、ｌiはその経路を構成する各点間をそれぞれ結ぶ線分の長さを表しており、Ｌは経路全体の長さを表している。すなわち、式（２）によって経路を構成する各線分の中点の座標値がそれぞれ計算され、その中点の座標値に対して当該線分の経路全体に対する長さの割合を乗じたものを合計した値によって、経路の重心座標（ｘg，ｙg）が表される。このように、各線分の長さに応じて重み付けを行って、経路の重心の座標値を求める。
【００５７】
図１０の例において、経路Ｒ１の各点（始点、終点および補間点）の間をそれぞれ結ぶ線分の長さを、始点に近いほうから順にｌ1、ｌ2、・・・ｌ9とすると、このときの重心Ｇ１の座標値（ｘg，ｙg）は式（２）を用いて次のように計算される。なお、Ｌ＝ｌ1＋ｌ2＋ｌ3＋ｌ4＋ｌ5＋ｌ6＋ｌ7＋ｌ8＋ｌ9＋ｌ10である。
ｘg＝｛ｌ1（ｘ1＋ｘ2）＋ｌ2（ｘ2＋ｘ3）＋・・・＋ｌ9（ｘ9＋ｘ10）｝／２Ｌ
ｙg＝｛ｌ1（ｙ1＋ｙ2）＋ｌ2（ｙ2＋ｙ3）＋・・・＋ｌ9（ｙ9＋ｙ10）｝／２Ｌ
【００５８】
以上説明したのと同様にして、全ての経路について、その重心の座標値をステップＳ４０１において算出する。
【００５９】
次のステップＳ４０２では、ステップＳ４０１で求められた各経路の重心のｘ座標値とｙ座標値を、その大きさの順にそれぞれ並べる。ステップＳ４０３では、ステップＳ４０２で並べられた大きさの順にしたがって、重心のｘ座標値の小さい経路から順に、その経路に対するｘ座標のシフト量を設定する。重心のｘ座標値が最も小さい経路に対しては、ｘ座標のシフト量を０とし、次に小さい経路に対しては、ｘ座標のシフト量を所定値ｄｘとし、その次に小さい経路に対しては、ｘ座標のシフト量を２ｄｘとする。ここでｄｘの大きさは予め定められており、たとえば経路の表示線幅をｗとすると、ｄｘ＝ｗ／２と定めることができる。同様にして全ての経路に対して、その重心のｘ座標値が小さい経路から順に、ｄｘずつ大きなｘ座標のシフト量を設定していく。
【００６０】
ステップＳ４０４では、ステップＳ４０３と同様の処理をｙ座標のシフト量に対して行う。すなわち、ステップＳ４０２で並べられた大きさの順にしたがって、重心のｙ座標値の小さい経路から順に、その経路に対するｙ座標のシフト量を０、ｄｙ、２ｄｙ、・・・と順に、所定値ｄｙずつ大きな値で設定する。なお、ｄｙの大きさは予め定められており、前述のｄｘと同様に、たとえば経路の表示線幅をｗとすると、ｄｙ＝ｗ／２と定めることができる。以上説明したようにして、重複している各経路の重心座標に基づいて、各経路に対するずらし幅をそれぞれ設定する。
【００６１】
ステップＳ４０５では、ステップＳ４０３およびＳ４０４において設定されたｘ座標とｙ座標のシフト量に従って、各経路をそれぞれ構成する各点の位置を移動する。これにより、元の形状を維持したままで、各経路の全体の描画位置をシフトする。
【００６２】
図１１は、設定されたシフト量に従って各経路の描画位置を画面上でシフトする様子を示した図である。たとえば図１１の例に示すように、経路Ｒ３の重心Ｇ３よりも、経路Ｒ２の重心Ｇ２の方がそのｘ座標値とｙ座標値がともに大きく、さらにこれらの重心よりも、経路Ｒ１の重心Ｇ１の方がそのｘ座標値とｙ座標値がともに大きいとする。この場合、重心のｘ座標値およびｙ座標値がともに最も小さい経路Ｒ３に対しては、ステップＳ４０３およびＳ４０４において、ｘ座標とｙ座標のシフト量にともに０が設定される。したがって、ステップＳ４０５において経路Ｒ３の描画位置は移動されない。
【００６３】
重心のｘ座標値およびｙ座標値が経路Ｒ３の次に小さい経路Ｒ２に対しては、ステップＳ４０３およびＳ４０４において、ｘ座標のシフト量ｄｘとｙ座標のシフト量ｄｙがそれぞれ設定される。また、重心のｘ座標値およびｙ座標値が最も大きい経路Ｒ１に対しては、ステップＳ４０３およびＳ４０４において、ｘ座標のシフト量２ｄｘとｙ座標のシフト量２ｄｙがそれぞれ設定される。そしてステップＳ４０５において、これらのシフト量の分だけ、経路Ｒ１とＲ２の描画位置がｘ方向すなわち画面横方向と、ｙ方向すなわち画面縦方向とにそれぞれ移動される。こうして各経路の重心位置に応じてシフト量を設定することで、元々ずれている経路が近づく方向にはシフトしないようにすることができる。
【００６４】
以上説明したようにしてステップＳ４０５を実行したら、図９の処理フローを終了する。これにより、図２のステップＳ４００の経路シフト処理が完了する。
【００６５】
図１２は、経路シフト処理の前後における各経路の描画位置の変化の様子を表した図である。（ａ）は経路シフト処理前、すなわちステップＳ３００の要約地図作成処理後の各経路を表しており、（ｂ）は経路シフト処理後の各経路を表している。（ａ）に対して（ｂ）では、経路Ｒ１と経路Ｒ２が前述の経路シフト処理によって設定されたシフト量に応じて、それぞれ描画位置がシフトされている。経路の表示線幅ｗに対してｄｘ＝ｄｙ＝ｗ／２と定められており、経路Ｒ２は、ｄｘすなわち経路の表示線幅の半分だけｘ方向とｙ方向にそれぞれシフトされ、経路Ｒ１は、２ｄｘすなわち経路の表示線幅分だけｘ方向とｙ方向にそれぞれシフトされている。このようにして、予め定められた所定幅単位で各経路をずらす。なお、経路Ｒ３についてはシフト量が０に設定されているため、描画位置がシフトされていない。
【００６６】
以上説明した第１の実施の形態によれば、次の作用効果が得られる。
（１）探索された複数の経路のうちいずれか２以上の経路が同一の道路を重複して通っている場合、その重複部分をずらして表示することとした。このようにしたので、複数の経路を地図上に同時に表示する際に、重複している部分を見やすく表示することができる。特に、要約地図において道路形状が簡略化された複数の互いに重複している経路について、その重複部分で各経路が判別できるように表示することができる。
【００６７】
（２）重複部分をずらして表示するとき、元の形状を維持したままで各経路の全体をずらすこととした。このようにしたので、簡単な処理により重複部分をずらして表示することができる。
【００６８】
（３）重複している各経路の重心座標に基づいて、その各経路に対するずらし幅をそれぞれ設定することとした。このようにしたので、簡単な処理により、重複部分をずらして表示するときのずらし幅を設定することができる。
【００６９】
（４）予め定められた所定幅単位で各経路をずらすこととしたので、三つ以上の経路が重複している場合でも、各経路をそれぞれ見やすく表示することができる。
【００７０】
−第２の実施形態−
本発明の第２の実施の形態について説明する。本実施形態によるナビゲーション装置では、上記の第１の実施形態で説明したのとは異なる方法で経路シフト処理を行い、各経路の描画位置をシフトする。これにより、作成された要約地図に対して、２つ以上の経路が重なっている部分をそれぞれの経路が判別できるような表示形態で描画する。なお、本実施形態によるナビゲーション装置の構成は、図１に示す第１の実施の形態のものと同じである。また、本実施形態によるナビゲーション装置において目的地設定の際に実行される処理のフローチャートは、図２に示す第１の実施の形態のものと同じである。
【００７１】
図１３は、第１の実施形態における経路シフト処理の方法を用いたときの問題点を説明するための図である。たとえば、経路シフト処理前の各経路が（ａ）に示すような状態であったとすると、上述した第１の実施形態における経路シフト処理方法によって、（ｂ）に示すように各経路の描画位置が画面上でシフトされる。このとき、異なる経路の符号６６に示す部分と符号６７に示す部分は、（ａ）では互いに離れていたものが（ｂ）では近づいている。したがってこの部分については、実際は互いに離れた別の道路を通っているにも関わらず、元々は重なっていたのが経路シフト処理によってシフトされたものであるように見えてしまう。第１の実施形態における経路シフト処理方法では、このような問題が生じる可能性がある。
【００７２】
以上説明したような問題を回避するため、本実施形態における経路シフト処理では、図２のステップＳ４００において、既に第１の実施の形態で説明した図９のフローチャートに替えて、図１４に示すフローチャートを実行する。これにより、ステップＳ３００の要約地図作成処理によって道路形状が簡略化された各経路について、その重複部分以外をずらさないで、重複している各経路の一部分のみをずらすようにする。以下、図１４のフローチャートについて説明する。
【００７３】
ステップＳ４１０では、経路ネットワークデータの初期化を行う。ここで初期化する経路ネットワークデータは、要約地図作成処理によって道路形状が簡略化された後のものである。この要約後の経路ネットワークデータについて、ステップＳ４１０では各経路上の補間点を全てノードとして扱う。そして、その各ノード間をつなぐリンクのそれぞれに対して、いくつの経路が重なっているかをあらわすリンク重複度を設定する。このようにして、経路ネットワークデータの初期化を行う。
【００７４】
ステップＳ４１０における経路ネットワークデータの初期化の様子を、図１８に示す例を用いて説明する。（ａ）には入力データ、すなわちステップＳ３００の要約地図作成処理において作成された経路ネットワークデータにより表される経路Ｒ１、Ｒ２およびＲ３を示している。この入力データでは、各経路の図示する位置にノードｎ１〜ｎ６と補間点ｓ１〜ｓ６がそれぞれ配置されているものとする。ノードｎ１は出発地（現在地）に該当し、ここからノードｎ２を経由して、ノードｎ３、ｎ５またはｎ６まで各経路が続いている。ノードｎ１とｎ２の間をつなぐリンクは、経路Ｒ１、Ｒ２およびＲ３に共通に用いられている。また、ノードｎ２とｎ４の間をつなぐリンクは、経路Ｒ２とＲ３に共通に用いられている。
【００７５】
（ｂ）は、（ａ）の入力データにおける補間点をノードへ置換した様子を示している。これにより、補間点ｓ１〜ｓ６がノードｎ１１〜ｎ１６にそれぞれ置換される。（ｃ）は、（ｂ）における各ノード、すなわち元のノードｎ１〜ｎ６に、補間点から置換されたノードｎ１１〜ｎ１６を加えた各ノードの間を互いにつなぐリンクのそれぞれに対して、リンク重複度を設定した様子を示している。たとえばノードｎ１とｎ１１の間のリンクに対しては、経路Ｒ１、Ｒ２およびＲ３が重複しているため、リンク重複度に３を設定する。このようにして各リンクに対してリンク重複度を設定することで、経路ネットワークデータの初期化を行う。
【００７６】
上記のようにして経路ネットワークデータの初期化を行った後には、初期化前とは異なる表現形式が用いられる。図１９は、初期化した後の経路ネットワークデータの表現形式の例を示している。（ａ）のノードデータと（ｃ）の経路データについては、図８に示す初期化前の表現形式と同じである。
【００７７】
（ｂ）のリンクデータには、初期化前と同じリンクＩＤ、始点ノードＩＤおよび終点ノードＩＤに加えて、リンクＩＤの初期値と、重複度が含まれている。リンクＩＤの初期値は、初期化した直後のリンクＩＤを表している。これは、後で説明するように、ステップＳ４４０のリンクシフト処理において新たにコピーリンクが生成された場合、その元になったリンクを判別できるようにするために設定されている。なお、新たに生成されたコピーリンクに対しては、新たなリンクＩＤが設定されるとともに、元となったリンクのリンクＩＤが初期値として設定される。重複度は、前述したリンク重複度を表している。
【００７８】
なお、図１８で説明したように、初期化後の経路ネットワークデータでは補間点が全てノードに置き換えられている。そのため（ｂ）のリンクデータには、図８に示す初期化前の表現形式とは異なり、補間点数と補間点情報が含まれていない。その代わりに、経路リンク参照情報が含まれている。これは、そのリンクが含まれている経路の経路ＩＤと、その経路において当該リンクが始点から何番目のリンクに当たるかを示す経路リンク番号とを表している。重複度がｍであれば、経路リンク参照情報にはｍ組の経路ＩＤと経路リンク番号が含まれている。
【００７９】
図１４のステップＳ４２０では、ステップＳ４１０で初期化した経路ネットワークデータに対して、先頭のリンク、すなわち出発地に近い側のリンクから順に選択する。図１８の例では、ノードｎ１とｎ１１の間のリンクから順に選択する。ステップＳ４３０では、ステップＳ４２０で選択したリンクについて、設定されているリンク重複度の値が１より大きいか否かを判定する。１より大きい場合はステップＳ４４０へ進む。１より大きくない場合、すなわちリンク重複度の値が１である場合は、ステップＳ４６０へ進む。
【００８０】
ステップＳ４４０では、ステップＳ４３０においてリンク重複度が１より大きいと判定したリンクについて、図１５のフローチャートに示すリンクシフト処理を実行する。このリンクシフト処理により、当該リンクにおいて互いに重なっている複数の経路について、その重複部分の描画位置がそれぞれ画面上でシフトされる。なお、リンクシフト処理の内容の詳細については後で説明する。
【００８１】
ステップＳ４５０では、ステップＳ４４０でリンクシフト処理を行った結果を反映して経路ネットワークデータの再構成を行う。すなわち、描画位置がシフトされた重複部分をそれぞれ別個のリンクとして表す。ステップＳ４５０を実行したらステップＳ４２０へ戻り、再構成後の経路ネットワークデータにおいて再び先頭のリンクから順に選択して、上記に説明したような処理を繰り返す。
【００８２】
一方、ステップＳ４３０においてリンク重複度の値が１より大きくないと判定されてステップＳ４６０へ進んだ場合は、ステップＳ４６０において、現在選択しているリンクの次のリンクがあるか否かを判定する。次のリンクがある場合はステップＳ４２０へ戻り、そのリンクを選択して上記のような処理を繰り返す。次のリンクがない場合、すなわちステップＳ４２０において全てのリンクを選択済みである場合は、図１４のフローチャートを終了する。以上説明したようにして、本実施形態における経路シフト処理を実行し、各経路の描画位置を画面上でシフトする。
【００８３】
次に、ステップＳ４４０において実行されるリンクシフト処理について、図１５に示すフローチャートにより説明する。ステップＳ４４１では、現在選択しているリンクが最後尾、すなわち目的地へと至るリンクであるか否かを判定する。最後尾のリンクであればステップＳ４４５へ進み、そうでなければステップＳ４４２へ進む。以下、ステップＳ４４２へ進んだ場合から先に説明する。
【００８４】
ステップＳ４４２では、選択しているリンクに対する流出リンク数が１より大きいか否かを判定する。ここでいう流出リンクとは、出発地から目的地へ向かって経路を進むときに、対象とするリンクから先につながっているリンクの数を表している。すなわち、流出リンク数が１であれば、２つのリンクが一対一につながっていることになり、流出リンク数が２以上であれば、１つのリンクから複数のリンクが分岐していることになる。流出リンク数が１より大きい場合はステップＳ４４３へ進み、１より大きくない場合、すなわち流出リンク数が１である場合は、ステップＳ４４４へ進む。
【００８５】
ステップＳ４４３では、選択しているリンクに対して、図１６に示す分岐リンクシフト処理を実行する。この内容については後で説明する。ステップＳ４４３を実行したら図１５のフローチャートを終了する。これにより、図１４のステップＳ４４０においてリンクシフト処理が実行される。
【００８６】
一方、ステップＳ４４４では、次の流出リンクを選択する。このとき、直前のステップＳ４４２で流出リンク数が１であると判定されているため、その１つの流出リンクが選択される。ステップＳ４４４において次の流出リンクを選択したら、ステップＳ４４１へ戻り、その流出リンクに対して前述したような処理を繰り返す。
【００８７】
次に、ステップＳ４４２からステップＳ４４５へ進んだ場合について説明する。ステップＳ４４５では、選択しているリンクに対する流入リンク数が１より大きいか否かを判定する。ここでいう流入リンクとは、出発地から目的地へ向かって経路を進むときに、対象とするリンクの前につながっているリンクの数を表している。すなわち、流入リンク数が１であれば、２つのリンクが一対一につながっていることになり、流入リンク数が２以上であれば、複数のリンクから１つのリンクに合流していることになる。流入リンク数が１より大きい場合はステップＳ４４６へ進み、１より大きくない場合、すなわち流入リンク数が１である場合は、ステップＳ４４７へ進む。
【００８８】
ステップＳ４４６では、選択しているリンクに対して、図１７に示す合流リンクシフト処理を実行する。この内容については後で説明する。ステップＳ４４６を実行したら図１５のフローチャートを終了する。これにより、図１４のステップＳ４４０のリンクシフト処理が実行される。
【００８９】
一方、ステップＳ４４７では、前の流入リンクを選択する。このとき、直前のステップＳ４４５で流入リンク数が１であると判定されているため、その１つの流入リンクが選択される。ステップＳ４４７において前の流入リンクを選択したら、次のステップＳ４４８ではその流入リンクが先頭のリンクであるか否かを判定する。先頭のリンクであればステップＳ４４９へ進み、そうでなければステップＳ４４５へ戻って、そのリンクに対して前述したような処理を繰り返す。
【００９０】
ステップＳ４４９へ進んだ場合は、先頭から最後尾まで全てのリンクについて、流入リンク数および流出リンク数が１であることになる。言い換えると、複数の経路が出発地から目的地まで完全に重複していることになる。このような場合は、ステップＳ４４９において単純シフト処理を実行する。ここでいう単純シフト処理とは、第１の実施の形態において説明したような経路シフト処理の方法である。なお、ステップＳ４４９は省略してもよい。この場合には、出発地から目的地まで完全に重複している複数の経路は、要約地図において重複したまま表示されることになる。
【００９１】
次に、ステップＳ４４３の分岐リンクシフト処理について、図１６のフローチャートを用いて説明する。ステップＳ４４３１では、そのとき選択しているリンクの直進方向が各流出リンクとなす角度をそれぞれ求める。ステップＳ４４３２では、選択しているリンクの直進方向に最も近い経路、すなわち、ステップＳ４４３１で算出した角度が最も小さい流出リンクに対応する経路を、基準経路に設定する。
【００９２】
ステップＳ４４３３では、選択しているリンクの進行方向に対して右折方向につながっている各流出リンクを、ステップＳ４４３１で算出した角度が小さい順に並べる。そして、後のステップＳ４４３５において各流出リンクに対応してそれぞれ生成される各コピーリンクのシフト幅を、ｄｗ、２ｄｗ・・・のようにｄｗ刻みで設定する。なお、ｄｗの大きさは予め定められており、たとえば経路の表示線幅をｗとすると、ｄｗ＝ｗ／２と定めることができる。
【００９３】
ステップＳ４４３４では、選択しているリンクの進行方向に対して左折方向につながっている各流出リンクについて、ステップＳ４４３３と同様の処理を行う。すなわち、各流出リンクをステップＳ４４３１で算出した角度が小さい順に並べ、ステップＳ４４３５において各流出リンクに対応してそれぞれ生成される各コピーリンクのシフト幅を、ｄｗ、２ｄｗ・・・のようにｄｗ刻みで設定する。このようにして、ステップＳ４４３３およびＳ４４３４の処理により、重複している各経路における重複部分からの流出角度に基づいて、その各経路に対するずらし幅をそれぞれ設定する。
【００９４】
ステップＳ４４３５では、選択しているリンクについて、流出リンクの数に応じて各流出リンクにそれぞれ対応するノード・リンクのコピーを生成する。このとき、流出リンク数よりも１つ少ない数だけコピーを生成する。これにより、選択しているリンクと同一のコピーリンクが、重複する経路の数に応じた分だけ生成される。そして、生成されたコピーリンクを各流出リンクにそれぞれ１つずつ対応付ける。この対応付けの情報は経路ネットワークデータに反映され、リンク同士の参照関係が更新される。
【００９５】
ステップＳ４４３６では、ステップＳ４４３５において各流出リンクに対応付けられたコピーリンクのそれぞれの描画位置を、ステップＳ４４３３およびＳ４４３４で設定されたシフト幅に従って画面上でシフトする。ステップＳ４４３６を実行したら、図１６のフローチャートを終了する。これにより、図１５のステップＳ４４３において分岐リンクシフト処理が実行される。
【００９６】
以上説明した分岐リンクシフト処理について、図２０に具体例を示す。たとえば（ａ）に示すようなリンクＬ０、Ｌ１、Ｌ２およびＬ３が存在しているとする。リンクＬ０にはリンク重複度に３が設定されており、リンクＬ１〜Ｌ３にはリンク重複度に１が設定されている。各リンクの矢印は進行方向を表しており、リンクＬ１〜Ｌ３は、リンクＬ０の流出リンクに該当している。このときリンクＬ０が、分岐リンクシフト処理の対象として選択されたとする。
【００９７】
初めに、図１６のステップＳ４４３１において、リンクＬ０に対する流出リンクＬ１〜Ｌ３について角度計算を行う。このときリンクＬ０の矢印に示す進行方向を角度基準位置として、そこからの角度θ１、θ２およびθ３を（ｂ）に示すように求める。するとθ２が一番小さいため、ステップＳ４４３２においてリンクＬ２に対応する経路が基準とされる。
【００９８】
次に、ステップＳ４４３３において、リンクＬ３に対応付けられるコピーリンク、すなわち後述のコピーリンクＬ０’に対して、シフト幅ｄｗを設定する。その次のステップＳ４４３４において、リンクＬ１に対応付けられるコピーリンク、すなわち後述のコピーリンクＬ０’’に対して、シフト幅ｄｗを設定する。そしてステップＳ４４３５において、リンクＬ０のコピーリンクＬ０’とＬ０’’を生成する。そして、コピーリンクＬ０’をリンクＬ３へ、コピーリンクＬ０’’をリンクＬ１へそれぞれ対応付ける。
【００９９】
次に、ステップＳ４４３６において、コピーリンクＬ０’とＬ０’’を、（ｃ）に示すように設定されたシフト幅ｄｗだけ左右にそれぞれシフトする。そして、シフト後の接続位置において、コピーリンクＬ０’とリンクＬ３を接続し、コピーリンクＬ０’’とリンクＬ１を接続する。なお、リンクＬ０はリンクＬ２に接続されている。このようにして、分岐リンクシフト処理を実行する。
【０１００】
図１５のステップＳ４４６の合流リンクシフト処理について説明する。図１７に示すフローチャートは、合流リンクシフト処理において実行される処理内容を表すものである。このフローチャートに示すように合流リンクシフト処理では、図１６の分岐リンクシフト処理と同様の内容を各流入リンクに対して実行する。そのため、図１７のフローチャートについての具体的な説明は省略する。このフローチャートのステップＳ４４６３およびＳ４４６４の処理により、図１６のステップＳ４４３３およびＳ４４３４の場合と同様に、重複している各経路における重複部分への流入角度に基づいて、その各経路に対するずらし幅をそれぞれ設定する。
【０１０１】
以上説明したような経路シフト処理を実行したときの具体例を図２１に示す。各経路を構成するリンクが（ａ）のような状態であったとすると、上記の処理により、最初の分岐点の手前にあるリンクＬ０が最初に選択される。このリンクＬ０に対して図１６の分岐リンクシフト処理が実行され、（ｂ）のように３つに分割される。
【０１０２】
次に（ｂ）の状態において、最初の分岐点の手前にあるリンクＬ１が選択される。このリンクＬ１について分割リンクシフト処理が実行されることで、リンクＬ１が分割されて（ｃ）のように変化する。同様に、（ｃ）ではリンクＬ２が選択され、これが分割リンクシフト処理によって分割されることで、（ｄ）のように変化する。さらに（ｄ）ではリンクＬ３が選択され、これが分割リンクシフト処理によって分割されることで、（ｅ）のように変化する。このようにして全ての重複部分が分割され、重なり合った経路がそれぞれ位置をずらして表示される。
【０１０３】
図２２は、経路シフト処理の前後における各経路の描画位置の変化の様子を表した図である。（ａ）は経路シフト処理前、すなわちステップＳ３００の要約地図作成処理後の各経路を表しており、（ｂ）は経路シフト処理後の各経路を表している。（ａ）に対して（ｂ）では、各経路の重複部分の描画位置がそれぞれリンク単位でシフトされているため、図１１のように離れた位置にある符号６６に示す部分と符号６７に示す部分が近づくようなことはない。
【０１０４】
以上説明した第２の実施の形態によれば、次の作用効果が得られる。
（１）重複部分をずらして表示するとき、その重複部分以外をずらさないで、重複している各経路の一部分のみをずらすこととした。このようにしたので、互いに離れている経路が近づいて表示されてしまって重複部分との見分けがつかなくなることを回避し、より適切に重複部分をずらして表示することができる。
【０１０５】
（２）重複している各経路における重複部分からの流出角度または重複部分への流入角度に基づいて、その各経路に対するずらし幅をそれぞれ設定することとした。このようにしたので、経路の形状に合わせてより適切なずらし幅を設定することができる。
【０１０６】
なお、上記の各実施形態では、探索された複数の経路を要約地図において表示する例を説明しているが、要約しない通常の地図上に探索された複数の経路を表示するナビゲーション装置に本発明を適用してもよい。
【０１０７】
上記の各実施形態では、ナビゲーション装置において、ＤＶＤ−ＲＯＭなどの記憶メディアより地図データを読み出して探索された要約地図を作成する例について説明しているが、本発明はこの内容には限定されない。たとえば、携帯電話などによる無線通信を用いて、地図データを情報配信センターからダウンロードする通信ナビゲーション装置などにおいても、本発明を適用できる。この場合、上記に説明したような要約地図の作成処理を情報配信センターにおいて行い、その結果を情報配信センターから信号出力してナビゲーション装置へ配信するようにしてもよい。
【０１０８】
すなわち、情報配信センターは、出発地から目的地まで複数の経路を探索する装置と、その複数の経路の地図を表示するための表示用データを作成する装置と、その表示用データを外部へ配信する装置によって構成される。そして、ナビゲーション装置においてこの情報配信センターから配信される表示用データを受信して、出発地から目的地までの複数の経路の地図を表示する。このような地図データ配信システムにおいて、上記に説明したような様々な処理を実行することにより、各経路の重複部分をずらして見やすく表示することができる。
【０１０９】
本発明は、上記各実施の形態に限定されるものではない。本発明の技術的思想の範囲内で考えられるその他の態様も、本発明の範囲内に含まれる。
【図面の簡単な説明】
【０１１０】
【図１】本発明の一実施形態によるナビゲーション装置の構成を示すブロック図である。
【図２】設定された目的地まで複数の経路を探索して各経路の要約地図を表示するときに実行される処理のフローチャートである。
【図３】要約前の地図と要約後の地図を示した図である。
【図４】要約地図を作成するときに利用される２分割の場合の方向量子化処理の内容を説明するための図である。
【図５】同じく４分割の場合の方向量子化処理の内容を説明するための図である。
【図６】各リンク形状を曲線で近似することによって各経路の道路形状を簡略化する方法を説明するための図である。
【図７】方向量子化処理によって経路ネットワークデータを変更する様子を示す図である。
【図８】経路ネットワークデータの表現形式の例を示す図である。
【図９】第１の実施の形態において実行される経路シフト処理のフローチャートである。
【図１０】経路の重心座標を求める様子を説明するための図である。
【図１１】設定されたシフト量に従って各経路の描画位置をシフトする様子を示した図である。
【図１２】第１の実施の形態において経路シフト処理の前後における各経路の描画位置の変化の様子を表した図である。
【図１３】第１の実施形態における経路シフト処理の方法を用いたときの問題点を説明するための図である。
【図１４】第２の実施の形態において実行される経路シフト処理のフローチャートである。
【図１５】経路シフト処理において実行されるリンクシフト処理のフローチャートである。
【図１６】リンクシフト処理において実行される分岐リンクシフト処理のフローチャートである。
【図１７】リンクシフト処理において実行される合流リンクシフト処理のフローチャートである。
【図１８】経路ネットワークデータの初期化の様子を説明するための図である。
【図１９】初期化後の経路ネットワークデータの表現形式の例を示す図である。
【図２０】分岐リンクシフト処理の具体例を示す図である。
【図２１】経路シフト処理を各経路に対して実行したときの具体例を示す図である。
【図２２】第２の実施の形態において経路シフト処理の前後における各経路の描画位置の変化の様子を表した図である。
【符号の説明】
【０１１１】
１  ナビゲーション装置
１１  制御回路
１２  ＲＯＭ
１３  ＲＡＭ
１４  現在地検出装置
１５  画像メモリ
１６  表示モニタ
１７  入力装置
１８  ディスクドライブ
１９  ＤＶＤ−ＲＯＭ
３０，４０  リンク
６１  現在地
６２  目的地
【図１】
2006113460.tif 000005
【図２】
2006113460.tif 000006
【図３】
2006113460.tif 000007
【図４】
2006113460.tif 000008
【図５】
2006113460.tif 000009
【図６】
2006113460.tif 000010
【図７】
2006113460.tif 000011
【図８】
2006113460.tif 000012
【図９】
2006113460.tif 000013
【図１０】
2006113460.tif 000014
【図１１】
2006113460.tif 000015
【図１２】
2006113460.tif 000016
【図１３】
2006113460.tif 000017
【図１４】
2006113460.tif 000018
【図１５】
2006113460.tif 000019
【図１６】
2006113460.tif 000020
【図１７】
2006113460.tif 000021
【図１８】
2006113460.tif 000022
【図１９】
2006113460.tif 000023
【図２０】
2006113460.tif 000024
【図２１】
2006113460.tif 000025
【図２２】
2006113460.tif 000026