JP4580209B2

JP4580209B2 - 要約地図作成装置

Info

Publication number: JP4580209B2
Application number: JP2004302958A
Authority: JP
Inventors: 紹男住沢; 学森田; 敦廣池; 貴志子丸山; 彰規淺原
Original assignee: Clarion Co Ltd
Current assignee: Faurecia Clarion Electronics Co Ltd
Priority date: 2004-10-18
Filing date: 2004-10-18
Publication date: 2010-11-10
Anticipated expiration: 2024-10-18
Also published as: US7493212B2; JP2006113457A; DE102005049829A1; DE102005049829B4; US20060085122A1

Description

本発明は、道路地図を簡略化した要約地図を作成する装置に関する。

地図を表すための地図データに基づいて、道路形状を簡略化する方法が知られている。たとえば、特許文献１に開示される装置では、地図データにおいて道路形状を表している各リンクに対して直線化や直交化などの処理を行い、さらに、マスクで規定した範囲内のランドマーク情報のみを表示することにより、道路形状を簡略化する。このようにして簡略化された道路形状を用いて地図を表示することで、見やすい地図を提供する。

特開平１１−２０２７６２号公報

特許文献１に開示される装置では、各リンクに対して直線化や直交化などの処理を行うことによって道路形状を簡略化している。このうち直交化処理を行うとリンクの端点の位置が移動してしまうため、隣接するリンクの位置に影響が及ぶことになる。したがって、長い距離に渡って道路形状を簡略化すると、元の位置より大幅に道路の位置がずれてしまう場合がある。

請求項１の発明による要約地図作成装置は、所定の道路区間ごとに設定されたリンクの形状によって道路の形状を表す道路地図データのうち、両端点の間に１以上の形状補間点が設定されている要約対象リンクの道路地図データを読み出す読み出し手段と、読み出し手段により読み出された道路地図データに基づいて、要約対象リンクにおいて形状補間点のいずれかを選択する点選択手段と、点選択手段により選択された形状補間点と要約対象リンクの各端点とを順に結ぶ２つの線分を設定する線分設定手段と、線分設定手段により設定された各線分が予め決められた所定の方向に対してなす角度が、予め設定された所定の単位角度の整数倍となるように、要約対象リンクの各端点を中心にして各線分の方向を補正する方向補正手段と、方向補正手段により方向を補正された各線分を延長したときの交点を求める交点検出手段と、交点検出手段により求められた交点と要約対象リンクの各端点とを結ぶように、各線分の長さを補正する長さ補正手段と、長さ補正手段により長さを補正された各線分を用いて要約対象リンクの形状を簡略化することにより、道路の形状を簡略化した要約地図を作成する要約地図作成手段とを備えるものである。
請求項２の発明は、請求項１の要約地図作成装置において、要約対象リンクの両端点の間に複数の形状補間点が設定されており、点選択手段は、複数の形状補間点のうち、要約対象リンクの両端点の間を結ぶ線分から最も遠くにある形状補間点を選択するものである。
請求項３の発明による要約地図作成装置は、所定の道路区間ごとに設定されたリンクの形状によって道路の形状を表す道路地図データのうち、両端点の間に少なくとも３以上の複数の形状補間点が設定されている要約対象リンクの道路地図データを読み出す読み出し手段と、読み出し手段により読み出された道路地図データに基づいて、要約対象リンクにおいて複数の形状補間点のうち３以上の形状補間点を選択する点選択手段と、点選択手段により選択された形状補間点の各々と要約対象リンクの各端点とを順に結ぶ複数の線分を設定する線分設定手段と、点選択手段により選択された形状補間点のうちいずれか少なくとも１つを保存点として設定する保存点設定手段と、線分設定手段により設定された各線分が予め決められた所定の方向に対してなす角度が、予め設定された所定の単位角度の整数倍となるように、要約対象リンクの各端点および保存点をそれぞれ中心にして各線分の方向を補正する方向補正手段と、互いに隣接する２つの線分同士を一組として、方向補正手段により方向を補正された各線分の交点を各組について求める交点検出手段と、交点検出手段により求められた各交点と要約対象リンクの各端点および保存点とをそれぞれ結ぶように、各線分の長さを補正する長さ補正手段と、長さ補正手段により長さを補正された各線分を用いて要約対象リンクの形状を簡略化することにより、道路の形状を簡略化した要約地図を作成する要約地図作成手段とを備えるものである。
請求項４の発明は、請求項３の要約地図作成装置において、点選択手段は、複数の形状補間点のうち、要約対象リンクの両端点の間を結ぶ線分から最も遠くにある形状補間点を選択する第１の選択工程と、既に選択した形状補間点の各々と要約対象リンクの各端点とを順に結ぶ複数の線分からそれぞれ最も遠くにある複数の形状補間点を選択する第２の選択工程とを行うものである。
請求項５の発明は、請求項４の要約地図作成装置において、点選択手段は、第２の選択工程を所定の回数だけ繰り返し行うものである。
請求項６の発明は、請求項４または５の要約地図作成装置において、保存点設定手段は、少なくとも第１の選択工程で選択された形状補間点を保存点として設定するものである。

本発明によれば、要約地図を作成するときに隣接するリンクの位置に影響を及ぼさずに、各リンクの形状を簡略化できる。その結果、長い距離に渡って道路形状を簡略化するときでも、元の位置より大幅に道路の位置がずれてしまうことなく、道路形状を簡略化できる。

本発明の一実施形態によるナビゲーション装置の構成を図１に示す。このナビゲーション装置は車両に搭載されており、設定された目的地までの経路を複数探索して、各経路の全体について通常の地図を基に道路形状などを簡略化することにより、通常の地図を要約した地図（以下、要約地図という）を作成して表示する。そして、表示した複数の経路のうち１つをユーザに選択させ、その経路を推奨経路として自車両を目的地まで案内する。図１に示すナビゲーション装置１は、制御回路１１、ＲＯＭ１２、ＲＡＭ１３、現在地検出装置１４、画像メモリ１５、表示モニタ１６、入力装置１７、およびディスクドライブ１８を有している。ディスクドライブ１８には、地図データが記録されたＤＶＤ−ＲＯＭ１９が装填される。

制御回路１１は、マイクロプロセッサおよびその周辺回路からなり、ＲＡＭ１３を作業エリアとしてＲＯＭ１２に格納された制御プログラムを実行することにより、各種の処理や制御を行う。この制御回路１１において後で説明するような処理を実行することによって、設定された目的地に対してＤＶＤ−ＲＯＭ１９に記録された地図データに基づいて複数の経路が探索され、各経路の全体について要約地図が作成されて、それぞれ表示モニタ１６に表示される。

現在地検出装置１４は、自車両の現在地を検出する装置であり、たとえば、自車両の進行方位を検出する振動ジャイロ１４ａ、車速を検出する車速センサ１４ｂ、ＧＰＳ衛星からのＧＰＳ信号を検出するＧＰＳセンサ１４ｃ等からなる。ナビゲーション装置１は、この現在地検出装置１４により検出された自車両の現在地に基づいて、推奨経路を探索するときの経路探索開始点を決定することができる。

画像メモリ１５は、表示モニタ１６に表示するための画像データを一時的に格納する。この画像データは、要約地図を画像表示するための道路地図描画用データや各種の図形データ等からなり、制御回路１１において、ＤＶＤ−ＲＯＭ１９に記録されている地図データに基づいて作成される。この画像メモリ１５に格納された画像データを用いて、各経路の全体の要約地図が表示モニタ１６に表示される。

入力装置１７は、ユーザが目的地の設定などを行うための各種入力スイッチを有し、これは操作パネルやリモコンなどによって実現される。ユーザは、表示モニタ１６に表示される画面指示に従って入力装置１７を操作することにより、地名や地図上の位置を指定して目的地を設定し、その目的地までの経路探索をナビゲーション装置１に開始させることができる。

ディスクドライブ１８は、要約地図を作成するために用いられる地図データを、装填されたＤＶＤ−ＲＯＭ１９より読み出す。なお、ここではＤＶＤ−ＲＯＭを用いた例について説明しているが、ＤＶＤ−ＲＯＭ以外の他の記録メディア、たとえばＣＤ−ＲＯＭやハードディスクなどより、地図データを読み出すこととしてもよい。この地図データには、複数の経路を演算するために用いられる経路計算データや、交差点名称、道路名称など、ユーザに選択された推奨経路に従って自車両を目的地まで案内するために用いられる経路誘導データ、道路を表す道路データ、さらには海岸線や河川、鉄道、地図上の各種施設（ランドマーク）など、道路以外の地図形状を表す背景データなどが含まれている。

道路データにおいて、道路区間を表す最小単位はリンクと呼ばれている。すなわち、各道路は所定の道路区間ごとに設定された複数のリンクによって構成されている。なお、リンクによって設定される道路区間の長さは異なっており、リンクの長さは一定ではない。リンク同士を接続している点はノードと呼ばれ、このノードはそれぞれに位置情報（座標情報）を有している。また、リンク内にはノードとノードの間に形状補間点と呼ばれる点が設定されていることもある。形状補間点もノードと同じく、それぞれに位置情報（座標情報）を有している。このノードと形状補間点の位置情報によって、リンク形状、すなわち道路の形状が決定される。経路計算データには、上記の各リンクに対応して、自車両の通過所要時間を表すためのリンクコストと呼ばれる値が設定されている。

前述のように入力装置１７におけるユーザの操作によって目的地が設定されると、制御回路１１において図２に示すフローチャートが実行される。これにより、現在地検出装置１４により検出された現在地を経路探索開始点として、設定された目的地までの経路演算が経路計算データに基づいて所定のアルゴリズムにより行われ、目的地までの複数の経路が求められる。そして、こうして求められた各経路の全体の要約地図が道路データに基づいて作成され、表示モニタ１６に表示される。

図２のフローチャートについて以下に説明する。ステップＳ１００では、ユーザに入力された目的地により、経路探索の目的地を設定する。ステップＳ２００では、経路探索開始点である自車両の現在地から、ステップＳ１００において設定された目的地まで、複数の経路を探索する。このとき、前述したように経路計算データに基づいて所定のアルゴリズムにより経路演算が行われる。なお、自車両の現在地は現在地検出装置１４によって一定時間ごとに求められる。

なお、ステップＳ２００では複数の経路を探索するために、様々な経路探索条件によって経路探索を行う。たとえば、有料道路優先や一般道路優先、距離優先などの経路探索条件によって経路探索を行い、それぞれの条件で最適な経路を求めることにより、複数の経路を探索する。あるいは、１つの経路探索条件によって最適経路以外の経路も探索することで、複数の経路を探索するようにしてもよい。たとえば、目的地までのリンクコストの合計が最も小さいものを最適経路とし、さらにその最適経路とリンクコストの合計の差が所定値以内である経路も含めて経路探索結果を求めることにより、１つの経路探索条件で複数の経路を探索することができる。

ステップＳ３００では、海岸線抽出処理を実行する。ここでは、ステップＳ８００の海岸線描画処理を実行するために必要な前処理として、ステップＳ２００で探索された各経路から所定の範囲内にある海岸線の形状を抽出する。なお、この海岸線抽出処理は必要に応じて実行すればよく、実行しなくても構わない。本発明では、ここでの処理内容は直接関係がないため、詳しい説明を省略する。

ステップＳ４００では、リンク簡潔化処理を実行する。ここでは、ステップＳ５００の要約地図作成処理において正しく処理を実行できるようにするための前処理として、ステップＳ２００で探索された各経路のリンクを簡潔化する処理を行う。具体的には、複数のリンクの近接している部分同士を統合して１つのリンクで表す処理（近接リンク統合処理）と、微小なリンクを除去する処理（微小リンク除去処理）と、隣の点との間隔が微小な形状補間点を除去する処理（微小間隔中間点除去処理）とを、各経路に対して実行する。なお、このリンク簡潔化処理は必要に応じて実行すればよく、実行しなくても構わない。本発明では、ここでの処理内容は直接関係がないため、詳しい説明を省略する。

ステップＳ５００では、ステップＳ２００で探索され、さらに必要に応じてステップＳ４００のリンク簡潔化処理が行われた各経路に対して、要約地図作成処理を実行する。このときの処理内容については、後で詳しく説明する。この要約地図作成処理によって、各経路の全体、すなわち現在地から目的地までを表す要約地図が作成される。

ステップＳ６００では、縮尺変更処理を実行する。ここでは、ステップＳ５００で作成された要約地図の縮尺を部分的に変更する処理を行う。たとえば、出発地や目的地周辺の縮尺を他の部分よりも大きくして、出発地や目的地周辺が拡大されて見やすくなるようにする。なお、この縮尺変更処理は必要に応じて実行すればよく、実行しなくても構わない。本発明では、ここでの処理内容は直接関係がないため、詳しい説明を省略する。

ステップＳ７００では、重複部分描画処理を実行する。ここでは、ステップＳ５００で作成された要約地図に対して、２つ以上の経路が重なっている部分をそれぞれの経路が判別できるような表示形態で描画する処理を行う。たとえば、各経路を互いに少しずつずらして描画する。なお、この重複部分描画処理は必要に応じて実行すればよく、実行しなくても構わない。本発明では、ここでの処理内容は直接関係がないため、詳しい説明を省略する。

ステップＳ８００では、海岸線描画処理を実行する。ここでは、ステップＳ３００で抽出された海岸線の形状に基づいて、経路から所定の範囲内にある海岸線を描画する処理を行う。なお、この海岸線描画処理は必要に応じて実行すればよく、実行しなくても構わない。本発明では、ここでの処理内容は直接関係がないため、詳しい説明を省略する。

ステップＳ９００では、ステップＳ５００において作成され、さらに必要に応じてステップＳ６００〜Ｓ８００の処理が行われた各経路の要約地図を、表示モニタ１６に表示する。このとき、出発地と目的地にはそれぞれ出発地マークと目的地マークを表示する。ステップＳ９００を実行した後は、図２のフローチャートを終了する。以上説明したようにして、目的地までの複数の経路が探索されて、各経路の全体の要約地図が表示モニタ１６に表示される。

図２のフローチャートの処理を実行して各経路の全体の要約地図を表示モニタ１６に表示したら、その後ナビゲーション装置１は、各経路のうち１つをユーザに選択するように指示する。ユーザが入力装置１７を操作することによっていずれかの経路を選択すると、選択された経路を推奨経路に設定して、現在地の周辺の道路地図上を表示してその上に推奨経路を示す。そして、この推奨経路に従って自車両を誘導し、目的地まで案内する。なお、このとき現在地周辺の道路地図として、通常の地図と要約地図のどちらを表示してもよい。このときの要約地図も、図２のフローチャートと同様の処理によって作成することができる。

図３は、通常の要約前の地図と、図２のフローチャートの処理を実行することによって表示された要約地図とを示したものである。（ａ）に示す要約前の地図には、現在地６１から目的地６２までをつなぐ３つの経路６３、６４および６５が示されている。この経路６３〜６５に対して図２のフローチャートの処理を実行することにより、（ｂ）の要約地図が表示される。この要約地図では、経路６３〜６５の道路形状がそれぞれ簡略化されていることが分かる。こうして各経路の要約地図を表示した後、いずれか選択された経路を推奨経路として、現在地６１から目的地６２まで自車両を案内する。

次に、ステップＳ５００において実行される要約地図作成処理の内容について説明する。要約地図作成処理では、方向量子化処理と呼ばれる処理を実行することによって各経路の道路形状を簡略化することにより、各経路の要約地図を作成する。この方向量子化処理について、以下に説明する。

方向量子化処理では、各経路のリンクをそれぞれ所定の分割数で分割した上で、道路形状の簡略化を行う。図４および図５は、いずれもこの方向量子化処理の内容を説明するための詳細説明図であり、図４ではリンク分割数が２（２分割）の場合について、また図５ではリンク分割数が４（４分割）の場合について、それぞれの方向量子化処理の内容を図示している。以下、図４に示す２分割の場合より先に説明を行う。

図４（ａ）の符号３０は、探索された経路に含まれているリンクの１つを例示している。このリンク３０に対して、（ｂ）に示すように、その両端点の間を結ぶ線分３１から最も遠くにあるリンク３０上の点３２を選択する。なお、ここで選択される点３２は前述の形状補間点に相当し、両端点はノードに相当する。

上記のような点３２が求められたら、次に（ｃ）に示すように、リンク３０の両端点のそれぞれと点３２とを結ぶ線分３３および３４を設定する。この線分３３と３４がそれぞれの基準線に対してなす角度をθ_１およびθ_２と表す。なお、ここでいう基準線とは、リンク３０の両端点から予め決められた所定の方向（たとえば、真北方向）に向かって、それぞれ延びている線のことである。（ｃ）に示すように、一方の端点からの基準線と線分３３によって挟まれている部分の角度が、θ_１と表される。また、もう一方の端点からの基準線と線分３４によって挟まれている部分の角度が、θ_２と表される。

上記のようにして点３２とリンク３０の両端点とをそれぞれ結ぶ線分３３、３４が設定されたら、次に（ｄ）に示すように、この線分３３と３４の方向をそれぞれ量子化する。ここでいう方向の量子化とは、前述の角度θ_１およびθ_２が予め設定された単位角度の整数倍にそれぞれなるように、線分３３と３４を各端点を中心にしてそれぞれ回転させることをいう。すなわち、θ_１＝ｍ・Δθ、θ_２＝ｎ・Δθ（ｎ、ｍは整数）となるように、線分３３と３４をそれぞれ回転させてθ_１とθ_２の値を補正する。上記の式においてｍとｎの値は、この式によって計算される補正後のθ_１とθ_２がそれぞれ元の値に最も近くなるように設定される。

以上説明したように線分３３と３４の方向をそれぞれ量子化すると、線分３３と３４が基準線となす角度θ_１およびθ_２が、単位角度Δθ刻みで補正される。なお図４（ｄ）では、Δθ＝１５°としている。そして、θ_１についてはｍ＝６と設定して補正後の角度を９０°にし、θ_２についてはｎ＝０と設定して補正後の角度を０°にした例を図示している。

こうして線分３３と３４の方向をそれぞれ量子化したら、次に線分３３と３４をそれぞれ延長したときの交点を求める。そして、その交点と各端点とを結ぶようにして、（ｄ）に示すように、線分３３と３４の長さをそれぞれ補正する。

以上説明したようにして、線分３３と３４を求め、これらの方向を量子化すると共に長さを補正することによって、リンク３０に対する２分割の場合の方向量子化処理が行われる。この線分３３と３４をリンク３０の代わりに用いることで、リンク３０の形状を簡略化して表すことができる。このとき、リンク３０の両端点の位置が固定された状態でリンク３０の形状が簡略化されるため、隣接するリンクの位置には影響を及ぼさない。したがって、方向量子化処理を用いて経路の各リンク形状をそれぞれ簡略化することにより、経路の全体的な位置関係を保ちつつ、その道路形状を容易に簡略化することができる。

次に、４分割の場合の方向量子化処理について説明する。図５（ａ）の符号４０は、図４（ａ）と同様に、探索された経路に含まれているリンクの１つを例示している。このリンク４０に対して、（ｂ）に示すように、まずその両端点の間を結ぶ線分４１ａから最も遠くにあるリンク４０上の点４２ａを選択する。次に、その点４２ａとリンク４０の各端点とをそれぞれ結ぶ線分４１ｂおよび４１ｃを設定し、この線分４１ｂと４１ｃからそれぞれ最も遠く離れた位置にあるリンク４０上の点４２ｂおよび４２ｃを選択する。なお、ここで選択される点４２ａ〜４２ｃは、いずれも２分割の場合と同様に前述のノードまたは形状補間点に相当する。

上記のような点４２ａ〜４２ｃが求められたら、次に（ｃ）に示すように、２分割の場合と同様にして、リンク４０の各端点と点４２ａ〜４２ｃとをそれぞれ順に結ぶ線分４３、４４、４５および４６を設定する。この線分４３〜４６がそれぞれの基準線に対してなす角度を、θ_３、θ_４、θ_５およびθ_６と表す。なお、このときの基準線はリンク４０の両端点に対して定められるだけでなく、点４２ａ〜４２ｃのうち真ん中に位置する最初に選択された点４２ａに対しても定められる。

上記のようにして線分４３〜４６が設定されたら、次に（ｄ）に示すように、各線分の方向をそれぞれ量子化する。このとき、点４２ａを保存点として、線分４４と４５はこの保存点４２ａを中心にそれぞれ回転させる。なお、線分４３と４６については、２分割の場合と同様に各端点を中心にそれぞれ回転させる。ここでは、Δθ＝１５°と予め設定し、θ_３〜θ_６の補正後の角度をそれぞれ６０°、４５°、１８０°および６０°とした例を図示している。

こうして線分４３〜４６の方向をそれぞれ量子化したら、次に線分４３と４４をそれぞれ延長したときの交点と、線分４５と４６をそれぞれ延長したときの交点とを求める。そして、各交点と各端点または保存点４２ａとを結ぶようにして、（ｄ）に示すように、線分４３〜４６の長さをそれぞれ補正する。

以上説明したようにして、線分４３〜４６を求め、これらの方向を量子化すると共に長さを補正することによって、リンク４０に対する４分割の場合の方向量子化処理が行われる。この線分４３〜４６をリンク４０の代わりに用いることで、リンク４０の形状を簡略化して表すことができる。このとき、リンク４０の両端点の位置に加えて、さらに保存点４２ａの位置も固定された状態で、リンク４０の形状が簡略化される。したがって、複雑な形状のリンクによって構成されている経路に対しても、その全体的な位置関係を保ちつつ適切に道路形状を簡略化することができる。

なお、上記では２分割と４分割の場合の方向量子化処理について説明したが、これ以外の分割数についても同様にして方向量子化処理を実行することができる。たとえば８分割の場合には、まず４分割の場合と同様に、リンクの両端点の間を結ぶ線分から最も遠い１点と、その点と両端点とを結ぶ２つの線分からそれぞれ最も遠い２点を選択する。その後、さらにこれらの３点に両端点を加えた各点間を結ぶ４つの線分からそれぞれ最も遠い４点を選択する。こうして選択された合計７点と両端点とを順に結ぶ８つの線分を求め、これらの線分に対して前述したような方向の量子化と長さの補正を行うことによって、８分割の方向量子化処理を行うことができる。

方向量子化処理の分割数をいくつにするかは、予め設定しておいてもよいし、あるいはリンクの形状によって判断してもよい。たとえば、上記のようにして両端点またはそれまでに選択された点の間を結ぶ各線分から最も遠い点を順次選択していくとき、すなわち図４および５の（ｂ）で説明した処理を繰り返していくときに、各線分から最も遠い点までの距離が所定値以下となるまで処理を繰り返して、その処理回数に応じた数の点を順次選択していく。このようにすれば、リンクの形状によって方向量子化処理の分割数を決めることができる。

図４で説明した２分割の方向量子化処理において、方向を量子化した後に線分３３と３４をそれぞれ延長しても、適切な交点がない場合がある。すなわち、方向を量子化した後の線分３３と３４が平行となっている場合には、これらの線分を延長すると両者が一体化してリンク３３の両端点を結ぶ１つの線分となるため、交点が存在しないこととなる。このような場合には、その両端点を直接結ぶ線分、すなわち線分３１を用いて、リンク３０の形状を簡略化して表すようにすればよい。また、図５で説明した４分割の方向量子化処理や、それ以上の分割数の方向量子化処理において、同様に方向を量子化した後に各線分を延長すると適切な交点がない場合には、それよりも分割数が少ない方向量子化処理を行うようにすればよい。

以上説明したような方向量子化処理を各経路の全てのリンクに対して順次実行していくことにより、各経路の道路形状を簡略化して要約地図を作成することができる。なお、リンク単位ではなく、リンクを複数連ねて構成されるリンク列ごとに上記のような方向量子化処理を実行するようにしてもよい。この場合、図４の点３２や図５の点４２ａ〜４２ｃとして選択される点には、形状補間点だけでなくノードも含まれることになる。

または、ステップＳ５００の要約地図作成処理において、上記の方向量子化処理を実行せずに各経路の道路形状を簡略化することもできる。ここでは、各リンク形状を曲線で近似することによって各経路の道路形状を簡略化する方法を、図６を参照して説明する。

図６（ａ）には、探索された経路に含まれるリンクの一部として、リンク５０、５１および５２を例示している。これらのリンク５０〜５２に対して、まず（ｂ）に示すように各リンクの両端点において量子化したリンク方向を求める。ここでは、前述の方向量子化処理において各線分の方向の量子化を行ったのと同様にして、元の角度に最も近くて単位角度の整数倍となるようなリンク方向を求める。その結果、（ｂ）において矢印で示されているようなリンク方向が各端点に対して求められる。

次に、（ｃ）に示すように各端点の間を結ぶ曲線５３、５４および５５を求めることにより、各リンクの形状を曲線近似する。このとき、各曲線の端点付近における接線の方向が上記の量子化したリンク方向と一致するように、曲線５３〜５５の形状がそれぞれ決定される。なお、このような曲線を求める方法としては、たとえばスプライン関数を用いたスプライン近似などがあるが、ここでは詳細な説明は省略する。

以上説明したような処理を各経路の全てのリンクに対して順次実行していき、求められた曲線を用いて道路形状を表すことにより、各経路の道路形状を簡略化して要約地図を作成することができる。このときも方向量子化処理の場合と同様に、各リンクの両端点の位置が固定された状態で各リンクの形状が簡略化される。したがってこの場合にも、経路の全体的な位置関係を保ちつつ、その道路形状を容易に簡略化することができる。

以上説明した実施の形態によれば、次の作用効果が得られる。
（１）リンクまたはリンク列の両端点の位置を固定して、そのリンクまたはリンク列の形状を簡略化することとしたので、隣接するリンクまたはリンク列の位置に影響を及ぼさずに、各リンクまたはリンク列の形状を簡略化できる。その結果、道路の全体的な位置関係を保ちつつ容易に道路形状を簡略化できるため、長い距離に渡って道路形状を簡略化しても、元の位置より大幅に道路の位置がずれてしまうことがない。

（２）４分割の場合の方向量子化処理において、両端点の位置に加えてさらに保存点４２ａの位置も固定した状態で、リンクまたはリンク列の形状を簡略化することとした。このようにしたので、複雑な形状のリンクやリンク列によって構成されている道路に対しても、その全体的な位置関係を保ちつつ適切に道路形状を簡略化できる。さらにこのとき、両端点の間を結ぶ線分４１ａから最も遠くにある点４２ａを保存点として選択することとしたので、適切な保存点を容易に選択してリンクやリンク列の形状を簡略化できる。

（３）方向量子化処理を用いてリンクまたはリンク列の形状を簡略化することとしたので、簡単な処理でリンクまたはリンク列の形状を簡略化できる。

（４）２分割の場合の方向量子化処理において、両端点の間を結ぶ線分３１から最も遠くにある点３２を選択して、方向量子化処理を行うこととした。また、４分割の場合の方向量子化処理において、両端点の間を結ぶ線分４１ａから最も遠くにある点４２ａを選択し、さらに、両端点とその点４２ａとの間をそれぞれ結ぶ線分４１ｂ、４１ｃから最も遠くにある点４２ｂおよび４２ｃを選択して、方向量子化処理を行うこととした。このようにしたので、方向量子化処理を行うときに適切な点を容易に選択して、リンクまたはリンク列の形状を簡略化できる。

上記の実施形態では、ナビゲーション装置において、ＤＶＤ−ＲＯＭなどの記憶メディアより地図データを読み出して要約地図を作成する例について説明しているが、本発明はこの内容には限定されない。たとえば、携帯電話などによる無線通信を用いて、地図データを情報配信センターからダウンロードする通信ナビゲーション装置などにおいても、本発明を適用できる。この場合、上記に説明したような要約地図の作成処理を情報配信センターにおいて行い、その結果を情報配信センターから信号出力してナビゲーション装置へ配信するようにしてもよい。すなわち、情報配信センターは、要約地図を作成する装置と、その要約地図を外部へ信号出力する装置によって構成される。

本発明は、上記実施の形態に限定されるものではない。本発明の技術的思想の範囲内で考えられるその他の態様も、本発明の範囲内に含まれる。

本発明の一実施形態によるナビゲーション装置の構成を示すブロック図である。設定された目的地まで複数の経路を探索して各経路の要約地図を表示するときに実行される処理のフローチャートである。要約前の地図と要約後の地図を示した図である。要約地図を作成するときに利用される２分割の場合の方向量子化処理の内容を説明するための図である。同じく４分割の場合の方向量子化処理の内容を説明するための図である。各リンク形状を曲線で近似することによって各経路の道路形状を簡略化する方法を説明するための図である。

符号の説明

１ナビゲーション装置
１１制御回路
１２ＲＯＭ
１３ＲＡＭ
１４現在地検出装置
１５画像メモリ
１６表示モニタ
１７入力装置
１８ディスクドライブ
１９ＤＶＤ−ＲＯＭ
３０，４０リンク
６１現在地
６２目的地
６３〜６５経路

Claims

所定の道路区間ごとに設定されたリンクの形状によって道路の形状を表す道路地図データのうち、両端点の間に１以上の形状補間点が設定されている要約対象リンクの道路地図データを読み出す読み出し手段と、
前記読み出し手段により読み出された道路地図データに基づいて、前記要約対象リンクにおいて前記形状補間点のいずれかを選択する点選択手段と、
前記点選択手段により選択された形状補間点と前記要約対象リンクの各端点とを順に結ぶ２つの線分を設定する線分設定手段と、
前記線分設定手段により設定された各線分が予め決められた所定の方向に対してなす角度が、予め設定された所定の単位角度の整数倍となるように、前記要約対象リンクの各端点を中心にして前記各線分の方向を補正する方向補正手段と、
前記方向補正手段により方向を補正された各線分を延長したときの交点を求める交点検出手段と、
前記交点検出手段により求められた交点と前記要約対象リンクの各端点とを結ぶように、前記各線分の長さを補正する長さ補正手段と、
前記長さ補正手段により長さを補正された各線分を用いて前記要約対象リンクの形状を簡略化することにより、前記道路の形状を簡略化した要約地図を作成する要約地図作成手段とを備えることを特徴とする要約地図作成装置。
請求項１の要約地図作成装置において、
前記要約対象リンクの両端点の間に複数の形状補間点が設定されており、
前記点選択手段は、前記複数の形状補間点のうち、前記要約対象リンクの両端点の間を結ぶ線分から最も遠くにある形状補間点を選択することを特徴とする要約地図作成装置。
所定の道路区間ごとに設定されたリンクの形状によって道路の形状を表す道路地図データのうち、両端点の間に少なくとも３以上の複数の形状補間点が設定されている要約対象リンクの道路地図データを読み出す読み出し手段と、
前記読み出し手段により読み出された道路地図データに基づいて、前記要約対象リンクにおいて前記複数の形状補間点のうち３以上の形状補間点を選択する点選択手段と、
前記点選択手段により選択された形状補間点の各々と前記要約対象リンクの各端点とを順に結ぶ複数の線分を設定する線分設定手段と、
前記点選択手段により選択された形状補間点のうちいずれか少なくとも１つを保存点として設定する保存点設定手段と、
前記線分設定手段により設定された各線分が予め決められた所定の方向に対してなす角度が、予め設定された所定の単位角度の整数倍となるように、前記要約対象リンクの各端点および前記保存点をそれぞれ中心にして前記各線分の方向を補正する方向補正手段と、
互いに隣接する２つの線分同士を一組として、前記方向補正手段により方向を補正された各線分の交点を各組について求める交点検出手段と、
前記交点検出手段により求められた各交点と前記要約対象リンクの各端点および前記保存点とをそれぞれ結ぶように、前記各線分の長さを補正する長さ補正手段と、
前記長さ補正手段により長さを補正された各線分を用いて前記要約対象リンクの形状を簡略化することにより、前記道路の形状を簡略化した要約地図を作成する要約地図作成手段とを備えることを特徴とする要約地図作成装置。
請求項３の要約地図作成装置において、
前記点選択手段は、前記複数の形状補間点のうち、前記要約対象リンクの両端点の間を結ぶ線分から最も遠くにある形状補間点を選択する第１の選択工程と、既に選択した形状補間点の各々と前記要約対象リンクの各端点とを順に結ぶ複数の線分からそれぞれ最も遠くにある複数の形状補間点を選択する第２の選択工程とを行うことを特徴とする要約地図作成装置。
請求項４の要約地図作成装置において、
前記点選択手段は、前記第２の選択工程を所定の回数だけ繰り返し行うことを特徴とする要約地図作成装置。
請求項４または５の要約地図作成装置において、
前記保存点設定手段は、少なくとも前記第１の選択工程で選択された形状補間点を前記保存点として設定することを特徴とする要約地図作成装置。