JP4579640B2 - 要約地図作成装置 - Google Patents

Description

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

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

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

特許文献１に開示される装置では、各リンクに対して直線化や直交化などの処理を行うことによって道路形状を簡略化することにより、要約地図を作成している。しかし、このような処理方法によって道路形状を簡略化すると、複数の経路の要約地図を作成する場合には、適切に道路形状が簡略化されないことがある。たとえば、互いに近接している複数の経路に対して道路形状を簡略化すると、それぞれの経路が要約地図において重なってしまうことがある。

請求項１の発明による要約地図作成装置は、出発地から設定された目的地までの複数の経路を探索する経路探索手段と、所定の道路区間ごとに設定されたリンクの形状によって道路の形状を表した道路地図データのうち、経路探索手段により探索された各経路にそれぞれ対応しており、両端点の間に１以上の形状補間点がそれぞれ設定されている複数のリンクの道路地図データを読み出す読み出し手段と、読み出し手段により読み出された道路地図データに基づいて、複数のリンクのうちいずれか２つのリンクを、第１のリンクおよび第２のリンクとして選択するリンク選択手段と、第１のリンクの各端点および形状補間点のうちいずれかの点を、第１のリンクの先頭から順次、第１の選択点として選択する第１点選択手段と、第２のリンクの各端点および形状補間点のうちいずれかの点を、第２のリンクの先頭から順次、第２の選択点として選択する第２点選択手段と、第１のリンクの各端点および形状補間点のうち第１の選択点とそれに隣接する点とをつなぐ線分に対して、第２の選択点から下ろした垂線の長さが所定値以下であり、かつ当該垂線と当該線分とが交差するとき、当該垂線と当該線分との交点を第１の近接点として求める第１近接点決定手段と、第１のリンクの各端点および形状補間点のうち第１のリンクにおいて第１の選択点よりも末尾側に存在するいずれかの点、または第２のリンクの各端点および形状補間点のうち第２のリンクにおいて第２の選択点よりも末尾側に存在するいずれかの点を、第１の選択点または第２の選択点から順次、第３の選択点として選択する第３点選択手段と、第１のリンクまたは第２のリンクのいずれか一方であって第３の選択点を含まない方の各端点および形状補間点のうち互いに隣接する２点をつなぐ各線分のいずれかに対して、第３の選択点から下ろした垂線の長さが所定値以下であり、かつ当該垂線と当該線分とが交差するときに、当該垂線と当該線分との交点を第２の近接点として求める第２近接点決定手段と、第１のリンクおよび第２のリンクのうち第１の近接点から第２の近接点までの各部分を統合して表す第３のリンクを求める第３リンク決定手段と、第１のリンクおよび第２のリンクを、第１のリンクの先頭から第１の近接点までの第４のリンクと、第２のリンクの先頭から第１の近接点までの第５のリンクと、第３のリンクと、第２の近接点から第１のリンクの末尾までの第６のリンクと、第２の近接点から第２のリンクの末尾までの第７のリンクとに分割するリンク分割手段とを備えるものである。
請求項２の発明は、請求項１の要約地図作成装置において、第３の選択点として選択された複数の点について第２近接点決定手段により第２の近接点がそれぞれ求められた場合、第３リンク決定手段は、当該複数の第２の近接点のうち第１の近接点から最も離れたものについて第３のリンクを求めるものである。
請求項３の発明は、請求項１または２の要約地図作成装置において、第３のリンクに対して、そのリンクには複数の道路が含まれていることを示すフラグ情報を付与することとするものである。

本発明によれば、複数の経路の要約地図を作成する場合に、適切に道路形状が簡略化されるように事前に各経路のリンクを簡潔化しておくことができる。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ここで、ステップＳ４００において実行されるリンク簡潔化処理の内容について説明する。リンク簡潔化処理では、図４に示すフローチャートにより、ステップＳ４１０において近接リンク統合処理を、次のステップＳ４４０において微小リンク除去処理を、その次のステップＳ４７０において微小間隔中間点除去処理を、それぞれ順番に実行する。以下、これら各処理の内容について説明する。

図５は、近接リンク統合処理の内容を説明するための図であり、（ａ）には複数のリンクが互いに近接している部分を有している様子を示している。なお、複数のリンクが互いに近接している部分を有しているとは、そのリンク間の距離が所定値以下の部分が存在することを意味する。（ａ）のリンク７１とリンク７２は、それぞれ別の経路に含まれているリンクであり、互いに近接している部分を有している。すなわち、リンク７１を含む経路と、リンク７２を含む経路とは、その経路間の距離が所定値以下である部分（近接部分）をそれぞれ有している。

近接リンク統合処理では、このように複数の経路が互いに近接部分を有している場合、（ｂ）に示すように新たなリンク７５を生成することにより、その近接部分を１つのリンクに統合する。このとき（ａ）に示す元のリンク７１とリンク７２は、それぞれ（ｂ）に示すように、リンク７５の前後で分割される。リンク７１はリンク７３、７５および７６に分割され、リンク７２はリンク７４、７５および７７に分割される。このようにして、複数のリンクの近接している部分同士を統合して１つのリンクで表す。

統合されたリンク７５には、２つの道路が含まれていることを示すフラグ情報が付与される。このフラグ情報を用いることにより、図２のステップＳ７００の重複部分描画処理において要約後のリンク７５を要約地図中に描画するときに、そこに含まれる複数の経路をそれぞれ判別できるような表示形態で描画することができる。なお、この近接リンク統合処理については、後でその内容を詳細に説明する。

図６は、微小リンク除去処理の内容を説明するための図である。（ａ）に図示するリンク８１〜８５のうち、リンク８１は微小なリンクであるものとする。なお、リンクの長さが予め設定された所定の値よりも短いときに、そのリンクは微小であるものとされる。ノード８０ａと８０ｂは、リンク８１の両端点を表している。なお、これらのノードはリンク８１の端点である以外に、リンク８２〜８５の端点の一方でもある。

微小リンク除去処理では、上記のような微小リンク８１を除去し、さらに（ｂ）に示すように、除去された微小リンク８１の両端点であるノード８０ａと８０ｂの中間の位置に、新たにノード８０ｃを生成する。その後は（ｃ）に示すように、ノード８０ａと８０ｂを除去する。このとき、除去されたノード８０ａと８０ｂのどちらか一方に接続されていたリンク８２〜８５は、新たに生成されたノード８０ｃへ接続される。このようにして、微小なリンクを除去する。

図７は、微小間隔中間点除去処理の内容を説明するための図である。（ａ）に図示する点８６ａ〜８６ｄは、いずれもリンク内に設定されている形状補間点である。これらの形状補間点は、中間点とも呼ばれている。線分８７、８８および８９は、形状補間点（中間点）８６ａと８６ｂ、８６ｂと８６ｃ、および８６ｃと８６ｄの間をそれぞれつなぐリンクの一部分を表している。このうち線分８８は微小な線分であり、その両端にある形状補間点８６ｂと８６ｃの間隔は微小であるものとする。なお、形状補間点同士をつなぐ線分の長さが予め設定された所定の値よりも短いときに、その線分は微小であるものとされ、その形状補間点の間隔が微小であるものとされる。

微小間隔中間点除去処理では、上記のように間隔が微小な形状補間点８６ｂと８６ｃののうち一方を除去する。このとき、微小な線分８８の反対側につながっている線分の長さが短いほうの形状補間点を除去する。ここで、形状補間点８６ｂにつながっている線分８７と、形状補間点８６ｃにつながっている線分８９では、（ａ）に図示されるように線分８９の方が短い。したがって、（ｂ）のように形状補間点８６ｃを除去する。形状補間点８６ｃを除去したら、その両隣の形状補間点８６ｂと８６ｄの間をつなぐ線分９０を、線分８８と８９の代わりに生成する。このようにして、隣の点との間隔が微小な形状補間点を除去する。なお、形状補間点とリンク端点（ノード）の間隔が微小であるときには、形状補間点のほうを除去してノードは除去しないようにする。

次に、近接リンク統合処理の内容を詳細に説明する。図８には、近接リンク統合処理で実行される処理のフローチャートを示している。なお、このフローチャートを実行するときには、変数ｉ，ｊ，ｋ、ｓおよびＬが用いられる。このうちＬの初期値には、図２のステップＳ２００で探索された全ての経路に含まれる全リンクの合計数が設定される。また、その全リンクのそれぞれをＶ［ｔ］（ｔ＝０，１，２，・・・）と表す。このときｔが取りうる最大値は、（全リンクの合計数−１）である。すなわち、（ｔの最大値＋１）＝（Ｌの初期値）である。以下に図８のフローチャートについて説明する。

ステップＳ４１１では、変数ｉの初期値としてｉ＝０を設定する。ステップＳ４１２では、その時点における変数Ｌと変数ｉの値に基づいて、ｉ＜Ｌ−１であるか否かを判定する。ｉ＜Ｌ−１である場合は次のステップＳ４１３へ進む。ｉ<Ｌ−１でない場合、すなわちｉ≧（Ｌ−１）である場合は、図８のフローチャートを終了する。この場合、図４のステップＳ４１０の近接リンク統合処理を終了して、次のステップＳ４４０の微小リンク除去処理を実行する。

ステップＳ４１３では、Ａ＝Ｖ［ｉ］として、その時点における変数ｉの値に基づいてリンクＡとしていずれかのリンクを選択する。ステップＳ４１４では、ステップＳ４１３で選択したリンクＡの長さが所定値εよりも大きいか否かを判定する。（Ａの長さ）＞εの場合はステップＳ４１５へ進み、そうでない場合、すなわち（Ａの長さ）≦εの場合には、後で説明するステップＳ４２８へ進む。なお、このときの所定値εの値は予め設定されている。ステップＳ４１５では、ｊ＝ｉ＋１として、変数ｉに１を加えた値を変数ｊに代入する。

ステップＳ４１６では、Ｂ＝Ｖ［ｊ］として、その時点における変数ｊの値に基づいてリンクＢとしていずれかのリンクを選択する。ステップＳ４１７では、ステップＳ４１６で選択されたリンクＢの長さが前述の所定値εよりも大きいか否かを判定する。（Ｂの長さ）＞εの場合は、ステップＳ４１８へ進み、そうでない場合、すなわち（Ｂの長さ）≦εの場合は、後で説明するステップＳ４２６へ進む。ステップＳ４１８では、変数ｋに対してｋ＝０とする。ステップＳ４１９では、変数ｓに対してｓ＝０とする。

ステップＳ４２０では、リンクＡまたはリンクＢ上に近接点Ｐを求める。このステップＳ４２０において近接点Ｐを求める方法については、後で詳しく説明する。ステップＳ４２１では、ステップＳ４２０において近接点Ｐが求められたか否かを判定する。ステップＳ４２０において近接点Ｐが求められた場合には、次のステップＳ４２２へ進む。一方、ステップＳ４２０において近接点Ｐが求められなかった場合は、ステップＳ４２９へ進む。以下、ステップＳ４２２へ進んだ場合から先に説明する。

ステップＳ４２２では、リンクＡまたはリンクＢ上に近接点Ｑを求める。この近接点Ｑの求め方については、前述の近接点Ｐと同様に後で説明する。ステップＳ４２３では、ステップＳ４２０で求められた近接点ＰとステップＳ４２２で求められた近接点Ｑにより、リンクＡを次のように新たな３つのリンクに分割する。１つ目のリンクは、元のリンクＡの一方の端点と近接点Ｐとをつなぐリンク（リンクＡ１とする）である。２つ目のリンクは、近接点Ｐと近接点Ｑをつなぐリンク（リンクＣとする）である。３つ目のリンクは、近接点Ｑと元のリンクＡのもう一方の端点とをつなぐリンク（リンクＡ２とする）である。この内容については、後で詳しく説明する。

ステップＳ４２４では、ステップＳ４２３と同様にして、リンクＢを３つのリンクに分割する。すなわち、元のリンクＢの一方の端点と近接点Ｐとをつなぐリンク（リンクＢ１とする）と、近接点Ｐと近接点Ｑをつなぐリンク（リンクＣ）と、近接点Ｑと元のリンクＢのもう一方の端点とをつなぐリンク（リンクＢ２とする）とに、リンクＢを分割する。なお、近接点Ｐと近接点ＱをつなぐリンクＣは、ステップＳ４２３においてリンクＡが分割されることによって生成されたものと共通である。このリンクＣには、前述したように２つの道路が含まれていることを示すフラグ情報が付与される。

ステップＳ４２５では、ステップＳ４２３およびＳ４２４の結果に基づいて、変数Ｌの値を更新する。すなわち、ステップＳ４２３とＳ４２４において分割する前にはリンクＡ，Ｂの２個のリンクであったところが、分割した後には上記のようにリンクＡ１，Ａ２，Ｂ１，Ｂ２およびＣと合計５個のリンクとなって、リンクが３個増えている。そのため、ここでは変数Ｌの値に３を加えることで、Ｌの値を更新する。

ステップＳ４２６では、変数ｊの値に１を加える。ステップＳ４２７では、その時点における変数Ｌと変数ｊの値に基づいて、変数ｊが変数Ｌよりも小さいか否かを判定する。ｊ＜Ｌである場合はステップＳ４１６へ戻る。変数ｊが変数Ｌより小さくない場合、すなわちｊ≧Ｌである場合は、次のステップＳ４２８へ進む。ステップＳ４２８では、変数ｉの値に１を加える。ステップＳ４２８を実行した後は、ステップＳ４１２へ戻る。

一方、ステップＳ４２１において近接点Ｐが求められなかったと判定されてステップＳ４２９へ進んだ場合は、ステップＳ４２９で変数ｓの値に１を加える。ステップＳ４３０では、変数ｓがＮより小さいか否か判定する。ここで、ＮはリンクＢに含まれる点の総数である。ｓ＜Ｎである場合はステップＳ４２０へ戻り、ｓ≧Ｎである場合は次のステップＳ４３１へ進む。

ステップＳ４３１では、変数ｋの値に１を加える。ステップＳ４３２では、変数ｋがＭより小さいか否か判定する。ここで、ＭはリンクＡに含まれる点の総数である。ｋ＜Ｍである場合はステップＳ４１９へ戻り、ｋ≧Ｍである場合はステップＳ４２６へ進む。以上説明したようにして、近接リンク統合処理が実行される。

ここで図９を用いて、前述のステップＳ４２０において近接点Ｐを求め、さらにステップＳ４２２において近接点Ｑを求めて、この近接点Ｐと近接点ＱによりステップＳ４２３とＳ４２４においてリンクＡとリンクＢを分割する方法について、詳しく説明する。図９（ａ）には、リンクＡとリンクＢの一部分がそれぞれ図示されている。なお、このリンクＡとリンクＢは、ステップＳ４１３とステップＳ４１６においてそれぞれ選択されるものであり、探索された複数の経路のいずれかの一部分を表している。

図９（ａ）の点Ａ［ｋ］と点Ｂ［ｓ］は、その時点で設定されている変数ｋと変数ｓの値に基づいて、リンクＡ上とリンクＢ上に存在する点の中からそれぞれ選択された点である。ここでは、リンクＡの先頭から数えてｋ番目にある点をＡ［ｋ］と表し、リンクＢの先頭から数えてｓ番目にある点をＢ［ｓ］と表している。なお、ここでいうリンク上の点とは、前述のノードまたは形状補間点に相当する。

近接点Ｐは、点Ａ［ｋ］と点Ａ［ｋ＋１］とをつなぐ線分（線分Ａｋと表す）に対して点Ｂ［ｓ］から下ろした垂線の長さが所定の長さ以下であり、かつその垂線と線分Ａｋが交差するときに、その垂線と線分Ａｋとの交点として求められる。あるいは、リンクＡとリンクＢの関係を逆にして、点Ｂ［ｓ］と点Ｂ［ｓ＋１］とをつなぐ線分（線分Ｂｓと表す）に対して点Ａ［ｋ］から下ろした垂線の長さが所定の長さ以下であり、かつその垂線と線分Ｂｓが交差するときに、その垂線と線分Ｂｓとの交点として求められる。このような条件のいずれかを満たす近接点Ｐが、ステップＳ４２０において線分Ａｋ上または線分Ｂｓ上に設定される。図９（ａ）には、点Ｂ［ｓ］から下ろした垂線と線分Ａｋとの交点が近接点Ｐとして線分Ａｋ上に設定されている様子を図示している。

なお、上記の条件のいずれも満たさない場合、たとえば点Ａ［ｋ］から線分Ｂｓへ下ろした垂線の長さと、点Ｂ［ｓ］から線分Ａｋへ下ろした垂線の長さが、いずれも所定の長さより大きい場合などは、ステップＳ４２０において近接点Ｐが設定されない。その場合には、次のステップＳ４２１において近接点Ｐが求められなかったと判定される。

上記のようにして近接点Ｐが求められると、次に近接点Ｑが求められる。近接点Ｑは、線分ＡｋおよびＢｓから順に並んだ線分上に近接点Ｐと同様にして次々に近接点を設定していき、設定された近接点のうち近接点Ｐからのリンク上の長さが最大となる近接点として求められる。この近接点Ｑを求める具体的な方法を、図９（ａ）により説明する。

前述のようにして図９（ａ）の近接点Ｐが求められたら、次に、点Ａ［ｋ＋１］または点Ｂ［ｓ＋１］から下ろした垂線に対しても、同じようにして近接点を求める。この近接点をＱ_１と表す。すなわち近接点Ｑ_１は、線分Ａｋに対して点Ｂ［ｓ＋１］から下ろした垂線の長さが所定の長さ以下であり、かつその垂線と線分Ａｋが交差するときに、その垂線と線分Ａｋとの交点として求められる。あるいは、線分Ｂｓに対して点Ａ［ｋ＋１］から下ろした垂線の長さが所定の長さ以下であり、かつその垂線と線分Ｂｓが交差するときに、その垂線と線分Ｂｓとの交点として求められる。図９（ａ）では、点Ｂ［ｓ＋１］から下ろした垂線と線分Ａｋとの交点が、近接点Ｑ_１として線分Ａｋ上に設定されている様子を図示している。

上記のようにして近接点Ｑ_１が求められたら、この近接点Ｑ_１が設定されていない方のリンクについて次の（隣の）点と線分を対象として、同様の方法により次の近接点Ｑ_２を求める。すなわち図９（ａ）の例では、線分Ａｋに対して点Ｂ［ｓ＋２］から下ろした垂線の長さが所定の長さ以下であり、かつその垂線と線分Ａｋが交差するときに、その垂線と線分Ａｋとの交点として求められる。あるいは、線分Ｂｓ＋１に対して点Ａ［ｋ＋１］から下ろした垂線の長さが所定の長さ以下であり、かつその垂線と線分Ｂｓ＋１が交差するときに、その垂線と線分Ｂｓ＋１との交点として求められる。図９（ａ）では、点Ａ［ｋ＋１］から下ろした垂線と線分Ｂｓ＋１との交点が、近接点Ｑ_２として線分Ｂｓ＋１上に設定されている。

以上説明したのと同様にして、上記のような近接点の設定条件を満たさなくなるまで、リンクＡまたはリンクＢの線分上に近接点Ｑ_３、Ｑ_４、・・・が順番に設定されていく。そして、最後に設定された近接点Ｑ_ｎが、最終的な近接点Ｑとされる。図９（ａ）の例では、線分Ａｋ＋１上に設定された近接点Ｑ_３が近接点Ｑとされている様子を表している。このようにして、ステップＳ４２２において近接点Ｑが求められる。

上記のように近接点ＰおよびＱが求められると、次にリンクＡとリンクＢをそれぞれ分割する。リンクＡは（ｂ）に示すように、先頭から近接点ＰまでのリンクＡ１と、近接点Ｐから近接点ＱまでのリンクＣと、近接点Ｑから末尾までのリンクＡ２に分割する。またリンクＢも同様に、先頭から近接点ＰまでのリンクＢ１と、近接点Ｐから近接点ＱまでのリンクＣと、近接点Ｑから末尾までのリンクＢ２に分割する。このとき、近接点Ｐと近接点Ｑの間にある点、すなわち近接点Ｐおよび前述の近接点Ｑ_１，Ｑ_２，・・・にそれぞれ対応する点（各近接点を設定したときにそこから垂線を下ろした点）が削除される。図９（ｂ）では、点Ｂ［ｓ］、Ｂ［ｓ＋１］、Ａ［ｋ＋１］およびＢ［ｓ＋２］が削除される。これにより、リンクＢ１については点Ｂ［ｓ−１］と近接点Ｐが接続され、リンクＢ２については近接点Ｑと点Ｂ［ｓ＋３］が接続される。このようにして、ステップＳ４２３とＳ４２４においてリンクＡとリンクＢがそれぞれ分割され、近接部分が１つのリンクＣに統合される。

なお、近接点Ｑが求められない場合、すなわち近接点Ｐと近接点Ｑが一致してしまうような場合には、分割後のリンクＣの長さを０として設定する。また、近接点ＰがリンクＡやリンクＢの先頭部分と一致してしまう場合は、分割後のリンクＡ１やリンクＢ１の長さを０として設定する。同様に、近接点ＱがリンクＡやリンクＢの末尾部分と一致してしまう場合は、分割後のリンクＡ２やリンクＢ２の長さを０として設定する。このように長さを０として設定される分割後のリンクは、ダミーリンクと呼ばれている。こうして設定されるダミーリンクがステップＳ４１３やＳ４１６においてリンクＡやリンクＢとして選択された場合、ステップＳ４１４またはステップＳ４１７が否定判定されることにより、そのダミーリンクに対しては上記のような近接点を求める処理が行われない。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

以上説明した実施の形態によれば、次の作用効果が得られる。
（１）探索された複数の経路の要約地図を作成する前に、各経路の相対的な位置関係に基づいて、各経路のリンクを簡潔化することとした（ステップＳ４００）。このようにしたので、複数の経路の要約地図を作成する場合に、適切に道路形状が簡略化されるように事前に各経路のリンクを簡潔化しておくことができる。

（２）リンク簡潔化処理において近接リンク統合処理を行う（ステップＳ４１０）ことにより、各経路のうちいずれか２つ以上の経路が近接部分を有している場合には、その近接部分を１つのリンクに統合することとした。このようにしたので、互いに近接している複数の経路に対して適切に道路形状が簡略化されるように、各経路のリンクを簡潔化しておくことができる。

（３）リンクＡとリンクＢのいずれかの上に近接点Ｐを求め（ステップＳ４２０）、さらに近接点Ｑを求める（ステップＳ４２２）。そして、近接点Ｐと近接点Ｑをつないで１つのリンクＣとして表し、リンクＡとリンクＢを、それぞれの先頭から近接点ＰまでのリンクＡ１およびＢ１と、リンクＣと、近接点Ｑからそれぞれの末尾までのリンクＡ２およびＢ２とに分割することとした（ステップＳ４２３，４２４）。このようにしたので、複数経路の近接部分を簡単に１つのリンクに統合することができる。

（４）近接部分が統合された１つのリンクに対して、そのリンクには複数の道路が含まれていることを示すフラグ情報が付与されることとしたので、そのリンクを要約した後に要約地図中に描画するときに、このフラグ情報に基づいて複数の経路をそれぞれ判別できるような表示形態で描画することができる。

なお、上記の実施の形態において、近接リンク統合処理を行う前に、探索された各経路がどこで交差しているのかを予め把握しておくようにしてもよい。さらにこのとき、立体交差のように同じ位置を通るが直接は交わらない経路同士の接続関係も予め把握しておくようにしてもよい。このように経路同士の接続関係を予め把握した上で近接リンク統合処理を実行するようにすれば、接続点付近に対して重点的に処理を行うことで、効率的に処理することができる。

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

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

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

符号の説明

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

Claims (3)

1. 出発地から設定された目的地までの複数の経路を探索する経路探索手段と、
   所定の道路区間ごとに設定されたリンクの形状によって道路の形状を表した道路地図データのうち、前記経路探索手段により探索された各経路にそれぞれ対応しており、両端点の間に１以上の形状補間点がそれぞれ設定されている複数のリンクの道路地図データを読み出す読み出し手段と、
   前記読み出し手段により読み出された道路地図データに基づいて、前記複数のリンクのうちいずれか２つのリンクを、第１のリンクおよび第２のリンクとして選択するリンク選択手段と、
   前記第１のリンクの各端点および形状補間点のうちいずれかの点を、前記第１のリンクの先頭から順次、第１の選択点として選択する第１点選択手段と、
   前記第２のリンクの各端点および形状補間点のうちいずれかの点を、前記第２のリンクの先頭から順次、第２の選択点として選択する第２点選択手段と、
   前記第１のリンクの各端点および形状補間点のうち前記第１の選択点とそれに隣接する点とをつなぐ線分に対して、前記第２の選択点から下ろした垂線の長さが所定値以下であり、かつ当該垂線と当該線分とが交差するとき、当該垂線と当該線分との交点を第１の近接点として求める第１近接点決定手段と、
   前記第１のリンクの各端点および形状補間点のうち前記第１のリンクにおいて前記第１の選択点よりも末尾側に存在するいずれかの点、または前記第２のリンクの各端点および形状補間点のうち前記第２のリンクにおいて前記第２の選択点よりも末尾側に存在するいずれかの点を、前記第１の選択点または前記第２の選択点から順次、第３の選択点として選択する第３点選択手段と、
   前記第１のリンクまたは前記第２のリンクのいずれか一方であって前記第３の選択点を含まない方の各端点および形状補間点のうち互いに隣接する２点をつなぐ各線分のいずれかに対して、前記第３の選択点から下ろした垂線の長さが所定値以下であり、かつ当該垂線と当該線分とが交差するときに、当該垂線と当該線分との交点を第２の近接点として求める第２近接点決定手段と、
   前記第１のリンクおよび前記第２のリンクのうち前記第１の近接点から前記第２の近接点までの各部分を統合して表す第３のリンクを求める第３リンク決定手段と、
   前記第１のリンクおよび前記第２のリンクを、前記第１のリンクの先頭から前記第１の近接点までの第４のリンクと、前記第２のリンクの先頭から前記第１の近接点までの第５のリンクと、前記第３のリンクと、前記第２の近接点から前記第１のリンクの末尾までの第６のリンクと、前記第２の近接点から前記第２のリンクの末尾までの第７のリンクとに分割するリンク分割手段とを備えることを特徴とする要約地図作成装置。
2. 請求項１の要約地図作成装置において、
   前記第３の選択点として選択された複数の点について前記第２近接点決定手段により前記第２の近接点がそれぞれ求められた場合、前記第３リンク決定手段は、当該複数の第２の近接点のうち前記第１の近接点から最も離れたものについて前記第３のリンクを求めることを特徴とする要約地図作成装置。
3. 請求項１または２の要約地図作成装置において、
   前記第３のリンクに対して、そのリンクには複数の道路が含まれていることを示すフラグ情報を付与することを特徴とする要約地図作成装置。
   

Images