要約地図作成装置
【課題】複数の経路の要約地図を作成する場合に、適切に道路形状が簡略化されるように事前に各経路のリンクを簡潔化しておくことができる方法を提供する。
【解決手段】(a)に示す互いに近接するリンク71とリンク72に対して、(b)に示すように新たなリンク75を生成することにより、その近接部分を1つのリンクに統合する。このとき(a)に示す元のリンク71とリンク72を、それぞれ(b)に示すように、リンク75の前後で分割する。リンク71はリンク73、75および76に分割され、リンク72はリンク74、75および77に分割される。このようにして、複数のリンクの近接している部分同士を統合して1つのリンクで表すことにより、要約地図を作成する前に各経路のリンクを簡潔化する。
【解決手段】(a)に示す互いに近接するリンク71とリンク72に対して、(b)に示すように新たなリンク75を生成することにより、その近接部分を1つのリンクに統合する。このとき(a)に示す元のリンク71とリンク72を、それぞれ(b)に示すように、リンク75の前後で分割する。リンク71はリンク73、75および76に分割され、リンク72はリンク74、75および77に分割される。このようにして、複数のリンクの近接している部分同士を統合して1つのリンクで表すことにより、要約地図を作成する前に各経路のリンクを簡潔化する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、道路地図を簡略化した要約地図を作成する装置に関する。
【背景技術】
【0002】
地図を表すための地図データに基づいて、道路形状を簡略化する方法が知られている。たとえば、特許文献1に開示される装置では、地図データにおいて道路形状を表している各リンクに対して直線化や直交化などの処理を行い、さらに、マスクで規定した範囲内のランドマーク情報のみを表示することにより、道路形状を簡略化する。このようにして簡略化された道路形状を用いて作成された要約地図を表示することで、通常の地図よりも見やすい地図を提供する。
【0003】
【特許文献1】特開平11−202762号公報
【発明の開示】
【発明が解決しようとする課題】
【0004】
特許文献1に開示される装置では、各リンクに対して直線化や直交化などの処理を行うことによって道路形状を簡略化することにより、要約地図を作成している。しかし、このような処理方法によって道路形状を簡略化すると、複数の経路の要約地図を作成する場合には、適切に道路形状が簡略化されないことがある。たとえば、互いに近接している複数の経路に対して道路形状を簡略化すると、それぞれの経路が要約地図において重なってしまうことがある。
【課題を解決するための手段】
【0005】
請求項1の発明による要約地図作成装置は、出発地から設定された目的地までの複数の経路を探索する経路探索手段と、所定の道路区間ごとに設定されたリンクの形状によって道路の形状を表した道路地図データに基づいて、経路探索手段により探索された各経路の道路形状を簡略化した要約地図を作成する要約地図作成手段と、要約地図作成手段により要約地図を作成する前に、各経路の相対的な位置関係に基づいて、各経路のリンクを簡潔化するリンク簡潔化手段とを備えるものである。
請求項2の発明は、請求項1の要約地図作成装置において、リンク簡潔化手段は、各経路のうちいずれか2つ以上の経路がその経路間の距離が所定値以下である近接部分をそれぞれ有している場合、その近接部分を1つのリンクに統合することにより、各経路のリンクを簡潔化するものである。
請求項3の発明は、請求項2の要約地図作成装置において、リンク簡潔化手段は、各々が複数の経路のいずれかの一部分を表し、各々の間の距離が所定値以下であるリンクAとリンクBのいずれかの上に、第1の近接点Pおよび第2の近接点Qを求め、第1の近接点Pと第2の近接点Qの間をつないで1つのリンクCとして表し、リンクAとリンクBを、それぞれの先頭から第1の近接点PまでのリンクA1およびB1と、リンクCと、第2の近接点Qからそれぞれの末尾までのリンクA2およびB2とに分割するものである。
請求項4の発明は、請求項2または3の要約地図作成装置において、近接部分が統合された1つのリンクに対して、そのリンクには複数の道路が含まれていることを示すフラグ情報を付与することとするものである。
【発明の効果】
【0006】
本発明によれば、探索された複数の経路の要約地図を作成する前に、各経路の相対的な位置関係に基づいて、各経路のリンクを簡潔化することとした。このようにしたので、複数の経路の要約地図を作成する場合に、適切に道路形状が簡略化されるように事前に各経路のリンクを簡潔化しておくことができる。
【発明を実施するための最良の形態】
【0007】
本発明の一実施形態によるナビゲーション装置の構成を図1に示す。このナビゲーション装置は車両に搭載されており、設定された目的地までの経路を複数探索して、各経路の全体について通常の地図を基に道路形状などを簡略化することにより、通常の地図を要約した地図(以下、要約地図という)を作成して表示する。そして、表示した複数の経路のうち1つをユーザに選択させ、その経路を推奨経路として自車両を目的地まで案内する。図1に示すナビゲーション装置1は、制御回路11、ROM12、RAM13、現在地検出装置14、画像メモリ15、表示モニタ16、入力装置17、およびディスクドライブ18を有している。ディスクドライブ18には、地図データが記録されたDVD−ROM19が装填される。
【0008】
制御回路11は、マイクロプロセッサおよびその周辺回路からなり、RAM13を作業エリアとしてROM12に格納された制御プログラムを実行することにより、各種の処理や制御を行う。この制御回路11において後で説明するような処理を実行することによって、設定された目的地に対してDVD−ROM19に記録された地図データに基づいて複数の経路が探索され、各経路の全体について要約地図が作成されて、それぞれ表示モニタ16に表示される。
【0009】
現在地検出装置14は、自車両の現在地を検出する装置であり、たとえば、自車両の進行方位を検出する振動ジャイロ14a、車速を検出する車速センサ14b、GPS衛星からのGPS信号を検出するGPSセンサ14c等からなる。ナビゲーション装置1は、この現在地検出装置14により検出された自車両の現在地に基づいて、推奨経路を探索するときの経路探索開始点を決定することができる。
【0010】
画像メモリ15は、表示モニタ16に表示するための画像データを一時的に格納する。この画像データは、要約地図を画像表示するための道路地図描画用データや各種の図形データ等からなり、制御回路11において、DVD−ROM19に記録されている地図データに基づいて作成される。この画像メモリ15に格納された画像データを用いて、各経路の全体の要約地図が表示モニタ16に表示される。
【0011】
入力装置17は、ユーザが目的地の設定などを行うための各種入力スイッチを有し、これは操作パネルやリモコンなどによって実現される。ユーザは、表示モニタ16に表示される画面指示に従って入力装置17を操作することにより、地名や地図上の位置を指定して目的地を設定し、その目的地までの経路探索をナビゲーション装置1に開始させることができる。
【0012】
ディスクドライブ18は、要約地図を作成するために用いられる地図データを、装填されたDVD−ROM19より読み出す。なお、ここではDVD−ROMを用いた例について説明しているが、DVD−ROM以外の他の記録メディア、たとえばCD−ROMやハードディスクなどより、地図データを読み出すこととしてもよい。この地図データには、複数の経路を演算するために用いられる経路計算データや、交差点名称、道路名称など、ユーザに選択された推奨経路に従って自車両を目的地まで案内するために用いられる経路誘導データ、道路を表す道路データ、さらには海岸線や河川、鉄道、地図上の各種施設(ランドマーク)など、道路以外の地図形状を表す背景データなどが含まれている。
【0013】
道路データにおいて、道路区間を表す最小単位はリンクと呼ばれている。すなわち、各道路は所定の道路区間ごとに設定された複数のリンクによって構成されている。なお、リンクによって設定される道路区間の長さは異なっており、リンクの長さは一定ではない。リンク同士を接続している点はノードと呼ばれ、このノードはそれぞれに位置情報(座標情報)を有している。また、リンク内にはノードとノードの間に形状補間点と呼ばれる点が設定されていることもある。形状補間点もノードと同じく、それぞれに位置情報(座標情報)を有している。このノードと形状補間点の位置情報によって、リンク形状、すなわち道路の形状が決定される。経路計算データには、上記の各リンクに対応して、自車両の通過所要時間を表すためのリンクコストと呼ばれる値が設定されている。
【0014】
前述のように入力装置17におけるユーザの操作によって目的地が設定されると、制御回路11において図2に示すフローチャートが実行される。これにより、現在地検出装置14により検出された現在地を経路探索開始点として、設定された目的地までの経路演算が経路計算データに基づいて所定のアルゴリズムにより行われ、目的地までの複数の経路が求められる。そして、こうして求められた各経路の全体の要約地図が道路データに基づいて作成され、表示モニタ16に表示される。
【0015】
図2のフローチャートについて以下に説明する。ステップS100では、ユーザに入力された目的地により、経路探索の目的地を設定する。ステップS200では、経路探索開始点である自車両の現在地から、ステップS100において設定された目的地まで、複数の経路を探索する。このとき、前述したように経路計算データに基づいて所定のアルゴリズムにより経路演算が行われる。なお、自車両の現在地は現在地検出装置14によって一定時間ごとに求められる。
【0016】
なお、ステップS200では複数の経路を探索するために、様々な経路探索条件によって経路探索を行う。たとえば、有料道路優先や一般道路優先、距離優先などの経路探索条件によって経路探索を行い、それぞれの条件で最適な経路を求めることにより、複数の経路を探索する。あるいは、1つの経路探索条件によって最適経路以外の経路も探索することで、複数の経路を探索するようにしてもよい。たとえば、目的地までのリンクコストの合計が最も小さいものを最適経路とし、さらにその最適経路とリンクコストの合計の差が所定値以内である経路も含めて経路探索結果を求めることにより、1つの経路探索条件で複数の経路を探索することができる。
【0017】
ステップS300では、海岸線抽出処理を実行する。ここでは、ステップS800の海岸線描画処理を実行するために必要な前処理として、ステップS200で探索された各経路から所定の範囲内にある海岸線の形状を抽出する。なお、この海岸線抽出処理は必要に応じて実行すればよく、実行しなくても構わない。本発明では、ここでの処理内容は直接関係がないため、詳しい説明を省略する。
【0018】
ステップS400では、リンク簡潔化処理を実行する。ここでは、ステップS500の要約地図作成処理において正しく処理を実行できるようにするための前処理として、ステップS200で探索された各経路のリンクを簡潔化する処理を行う。具体的には、複数のリンクの近接している部分同士を統合して1つのリンクで表す処理(近接リンク統合処理)と、微小なリンクを除去する処理(微小リンク除去処理)と、隣の点との間隔が微小な形状補間点を除去する処理(微小間隔中間点除去処理)とを、各経路に対して実行する。このリンク簡潔化処理の内容については、後で説明する。
【0019】
ステップS500では、ステップS200で探索され、さらにステップS400のリンク簡潔化処理が行われた各経路に対して、要約地図作成処理を実行する。このときの処理内容については、後で詳しく説明する。この要約地図作成処理によって、各経路の全体、すなわち現在地から目的地までを表す要約地図が作成される。
【0020】
ステップS600では、縮尺変更処理を実行する。ここでは、ステップS500で作成された要約地図の縮尺を部分的に変更する処理を行う。たとえば、出発地や目的地周辺の縮尺を他の部分よりも大きくして、出発地や目的地周辺が拡大されて見やすくなるようにする。なお、この縮尺変更処理は必要に応じて実行すればよく、実行しなくても構わない。本発明では、ここでの処理内容は直接関係がないため、詳しい説明を省略する。
【0021】
ステップS700では、重複部分描画処理を実行する。ここでは、ステップS500で作成された要約地図に対して、2つ以上の経路が重なっている部分をそれぞれの経路が判別できるような表示形態で描画する処理を行う。たとえば、各経路を互いに少しずつずらして描画する。なお、この重複部分描画処理は必要に応じて実行すればよく、実行しなくても構わない。本発明では、ここでの処理内容は直接関係がないため、詳しい説明を省略する。
【0022】
ステップS800では、海岸線描画処理を実行する。ここでは、ステップS300で抽出された海岸線の形状に基づいて、経路から所定の範囲内にある海岸線を描画する処理を行う。なお、この海岸線描画処理は必要に応じて実行すればよく、実行しなくても構わない。本発明では、ここでの処理内容は直接関係がないため、詳しい説明を省略する。
【0023】
ステップS900では、ステップS500において作成され、さらに必要に応じてステップS600〜S800の処理が行われた各経路の要約地図を、表示モニタ16に表示する。このとき、出発地と目的地にはそれぞれ出発地マークと目的地マークを表示する。ステップS900を実行した後は、図2のフローチャートを終了する。以上説明したようにして、目的地までの複数の経路が探索されて、各経路の全体の要約地図が表示モニタ16に表示される。
【0024】
図2のフローチャートの処理を実行して各経路の全体の要約地図を表示モニタ16に表示したら、その後ナビゲーション装置1は、各経路のうち1つをユーザに選択するように指示する。ユーザが入力装置17を操作することによっていずれかの経路を選択すると、選択された経路を推奨経路に設定して、現在地の周辺の道路地図上を表示してその上に推奨経路を示す。そして、この推奨経路に従って自車両を誘導し、目的地まで案内する。なお、このとき現在地周辺の道路地図として、通常の地図と要約地図のどちらを表示してもよい。このときの要約地図も、図2のフローチャートと同様の処理によって作成することができる。
【0025】
図3は、通常の要約前の地図と、図2のフローチャートの処理を実行することによって表示された要約地図とを示したものである。(a)に示す要約前の地図には、現在地61から目的地62までをつなぐ3つの経路63、64および65が示されている。この経路63〜65に対して図2のフローチャートの処理を実行することにより、(b)の要約地図が表示される。この要約地図では、経路63〜65の道路形状がそれぞれ簡略化されていることが分かる。こうして各経路の要約地図を表示した後、いずれか選択された経路を推奨経路として、現在地61から目的地62まで自車両を案内する。
【0026】
ここで、ステップS400において実行されるリンク簡潔化処理の内容について説明する。リンク簡潔化処理では、図4に示すフローチャートにより、ステップS410において近接リンク統合処理を、次のステップS440において微小リンク除去処理を、その次のステップS470において微小間隔中間点除去処理を、それぞれ順番に実行する。以下、これら各処理の内容について説明する。
【0027】
図5は、近接リンク統合処理の内容を説明するための図であり、(a)には複数のリンクが互いに近接している部分を有している様子を示している。なお、複数のリンクが互いに近接している部分を有しているとは、そのリンク間の距離が所定値以下の部分が存在することを意味する。(a)のリンク71とリンク72は、それぞれ別の経路に含まれているリンクであり、互いに近接している部分を有している。すなわち、リンク71を含む経路と、リンク72を含む経路とは、その経路間の距離が所定値以下である部分(近接部分)をそれぞれ有している。
【0028】
近接リンク統合処理では、このように複数の経路が互いに近接部分を有している場合、(b)に示すように新たなリンク75を生成することにより、その近接部分を1つのリンクに統合する。このとき(a)に示す元のリンク71とリンク72は、それぞれ(b)に示すように、リンク75の前後で分割される。リンク71はリンク73、75および76に分割され、リンク72はリンク74、75および77に分割される。このようにして、複数のリンクの近接している部分同士を統合して1つのリンクで表す。
【0029】
統合されたリンク75には、2つの道路が含まれていることを示すフラグ情報が付与される。このフラグ情報を用いることにより、図2のステップS700の重複部分描画処理において要約後のリンク75を要約地図中に描画するときに、そこに含まれる複数の経路をそれぞれ判別できるような表示形態で描画することができる。なお、この近接リンク統合処理については、後でその内容を詳細に説明する。
【0030】
図6は、微小リンク除去処理の内容を説明するための図である。(a)に図示するリンク81〜85のうち、リンク81は微小なリンクであるものとする。なお、リンクの長さが予め設定された所定の値よりも短いときに、そのリンクは微小であるものとされる。ノード80aと80bは、リンク81の両端点を表している。なお、これらのノードはリンク81の端点である以外に、リンク82〜85の端点の一方でもある。
【0031】
微小リンク除去処理では、上記のような微小リンク81を除去し、さらに(b)に示すように、除去された微小リンク81の両端点であるノード80aと80bの中間の位置に、新たにノード80cを生成する。その後は(c)に示すように、ノード80aと80bを除去する。このとき、除去されたノード80aと80bのどちらか一方に接続されていたリンク82〜85は、新たに生成されたノード80cへ接続される。このようにして、微小なリンクを除去する。
【0032】
図7は、微小間隔中間点除去処理の内容を説明するための図である。(a)に図示する点86a〜86dは、いずれもリンク内に設定されている形状補間点である。これらの形状補間点は、中間点とも呼ばれている。線分87、88および89は、形状補間点(中間点)86aと86b、86bと86c、および86cと86dの間をそれぞれつなぐリンクの一部分を表している。このうち線分88は微小な線分であり、その両端にある形状補間点86bと86cの間隔は微小であるものとする。なお、形状補間点同士をつなぐ線分の長さが予め設定された所定の値よりも短いときに、その線分は微小であるものとされ、その形状補間点の間隔が微小であるものとされる。
【0033】
微小間隔中間点除去処理では、上記のように間隔が微小な形状補間点86bと86cののうち一方を除去する。このとき、微小な線分88の反対側につながっている線分の長さが短いほうの形状補間点を除去する。ここで、形状補間点86bにつながっている線分87と、形状補間点86cにつながっている線分89では、(a)に図示されるように線分89の方が短い。したがって、(b)のように形状補間点86cを除去する。形状補間点86cを除去したら、その両隣の形状補間点86bと86dの間をつなぐ線分90を、線分88と89の代わりに生成する。このようにして、隣の点との間隔が微小な形状補間点を除去する。なお、形状補間点とリンク端点(ノード)の間隔が微小であるときには、形状補間点のほうを除去してノードは除去しないようにする。
【0034】
次に、近接リンク統合処理の内容を詳細に説明する。図8には、近接リンク統合処理で実行される処理のフローチャートを示している。なお、このフローチャートを実行するときには、変数i,j,k、sおよびLが用いられる。このうちLの初期値には、図2のステップS200で探索された全ての経路に含まれる全リンクの合計数が設定される。また、その全リンクのそれぞれをV[t](t=0,1,2,・・・)と表す。このときtが取りうる最大値は、(全リンクの合計数−1)である。すなわち、(tの最大値+1)=(Lの初期値)である。以下に図8のフローチャートについて説明する。
【0035】
ステップS411では、変数iの初期値としてi=0を設定する。ステップS412では、その時点における変数Lと変数iの値に基づいて、i<L−1であるか否かを判定する。i<L−1である場合は次のステップS413へ進む。i<L−1でない場合、すなわちi≧(L−1)である場合は、図8のフローチャートを終了する。この場合、図4のステップS410の近接リンク統合処理を終了して、次のステップS440の微小リンク除去処理を実行する。
【0036】
ステップS413では、A=V[i]として、その時点における変数iの値に基づいてリンクAとしていずれかのリンクを選択する。ステップS414では、ステップS413で選択したリンクAの長さが所定値εよりも大きいか否かを判定する。(Aの長さ)>εの場合はステップS415へ進み、そうでない場合、すなわち(Aの長さ)≦εの場合には、後で説明するステップS428へ進む。なお、このときの所定値εの値は予め設定されている。ステップS415では、j=i+1として、変数iに1を加えた値を変数jに代入する。
【0037】
ステップS416では、B=V[j]として、その時点における変数jの値に基づいてリンクBとしていずれかのリンクを選択する。ステップS417では、ステップS416で選択されたリンクBの長さが前述の所定値εよりも大きいか否かを判定する。(Bの長さ)>εの場合は、ステップS418へ進み、そうでない場合、すなわち(Bの長さ)≦εの場合は、後で説明するステップS426へ進む。ステップS418では、変数kに対してk=0とする。ステップS419では、変数sに対してs=0とする。
【0038】
ステップS420では、リンクAまたはリンクB上に近接点Pを求める。このステップS420において近接点Pを求める方法については、後で詳しく説明する。ステップS421では、ステップS420において近接点Pが求められたか否かを判定する。ステップS420において近接点Pが求められた場合には、次のステップS422へ進む。一方、ステップS420において近接点Pが求められなかった場合は、ステップS429へ進む。以下、ステップS422へ進んだ場合から先に説明する。
【0039】
ステップS422では、リンクAまたはリンクB上に近接点Qを求める。この近接点Qの求め方については、前述の近接点Pと同様に後で説明する。ステップS423では、ステップS420で求められた近接点PとステップS422で求められた近接点Qにより、リンクAを次のように新たな3つのリンクに分割する。1つ目のリンクは、元のリンクAの一方の端点と近接点Pとをつなぐリンク(リンクA1とする)である。2つ目のリンクは、近接点Pと近接点Qをつなぐリンク(リンクCとする)である。3つ目のリンクは、近接点Qと元のリンクAのもう一方の端点とをつなぐリンク(リンクA2とする)である。この内容については、後で詳しく説明する。
【0040】
ステップS424では、ステップS423と同様にして、リンクBを3つのリンクに分割する。すなわち、元のリンクBの一方の端点と近接点Pとをつなぐリンク(リンクB1とする)と、近接点Pと近接点Qをつなぐリンク(リンクC)と、近接点Qと元のリンクBのもう一方の端点とをつなぐリンク(リンクB2とする)とに、リンクBを分割する。なお、近接点Pと近接点QをつなぐリンクCは、ステップS423においてリンクAが分割されることによって生成されたものと共通である。このリンクCには、前述したように2つの道路が含まれていることを示すフラグ情報が付与される。
【0041】
ステップS425では、ステップS423およびS424の結果に基づいて、変数Lの値を更新する。すなわち、ステップS423とS424において分割する前にはリンクA,Bの2個のリンクであったところが、分割した後には上記のようにリンクA1,A2,B1,B2およびCと合計5個のリンクとなって、リンクが3個増えている。そのため、ここでは変数Lの値に3を加えることで、Lの値を更新する。
【0042】
ステップS426では、変数jの値に1を加える。ステップS427では、その時点における変数Lと変数jの値に基づいて、変数jが変数Lよりも小さいか否かを判定する。j<Lである場合はステップS416へ戻る。変数jが変数Lより小さくない場合、すなわちj≧Lである場合は、次のステップS428へ進む。ステップS428では、変数iの値に1を加える。ステップS428を実行した後は、ステップS412へ戻る。
【0043】
一方、ステップS421において近接点Pが求められなかったと判定されてステップS429へ進んだ場合は、ステップS429で変数sの値に1を加える。ステップS430では、変数sがNより小さいか否か判定する。ここで、NはリンクBに含まれる点の総数である。s<Nである場合はステップS420へ戻り、s≧Nである場合は次のステップS431へ進む。
【0044】
ステップS431では、変数kの値に1を加える。ステップS432では、変数kがMより小さいか否か判定する。ここで、MはリンクAに含まれる点の総数である。k<Mである場合はステップS419へ戻り、k≧Mである場合はステップS426へ進む。以上説明したようにして、近接リンク統合処理が実行される。
【0045】
ここで図9を用いて、前述のステップS420において近接点Pを求め、さらにステップS422において近接点Qを求めて、この近接点Pと近接点QによりステップS423とS424においてリンクAとリンクBを分割する方法について、詳しく説明する。図9(a)には、リンクAとリンクBの一部分がそれぞれ図示されている。なお、このリンクAとリンクBは、ステップS413とステップS416においてそれぞれ選択されるものであり、探索された複数の経路のいずれかの一部分を表している。
【0046】
図9(a)の点A[k]と点B[s]は、その時点で設定されている変数kと変数sの値に基づいて、リンクA上とリンクB上に存在する点の中からそれぞれ選択された点である。ここでは、リンクAの先頭から数えてk番目にある点をA[k]と表し、リンクBの先頭から数えてs番目にある点をB[s]と表している。なお、ここでいうリンク上の点とは、前述のノードまたは形状補間点に相当する。
【0047】
近接点Pは、点A[k]と点A[k+1]とをつなぐ線分(線分Akと表す)に対して点B[s]から下ろした垂線の長さが所定の長さ以下であり、かつその垂線と線分Akが交差するときに、その垂線と線分Akとの交点として求められる。あるいは、リンクAとリンクBの関係を逆にして、点B[s]と点B[s+1]とをつなぐ線分(線分Bsと表す)に対して点A[k]から下ろした垂線の長さが所定の長さ以下であり、かつその垂線と線分Bsが交差するときに、その垂線と線分Bsとの交点として求められる。このような条件のいずれかを満たす近接点Pが、ステップS420において線分Ak上または線分Bs上に設定される。図9(a)には、点B[s]から下ろした垂線と線分Akとの交点が近接点Pとして線分Ak上に設定されている様子を図示している。
【0048】
なお、上記の条件のいずれも満たさない場合、たとえば点A[k]から線分Bsへ下ろした垂線の長さと、点B[s]から線分Akへ下ろした垂線の長さが、いずれも所定の長さより大きい場合などは、ステップS420において近接点Pが設定されない。その場合には、次のステップS421において近接点Pが求められなかったと判定される。
【0049】
上記のようにして近接点Pが求められると、次に近接点Qが求められる。近接点Qは、線分AkおよびBsから順に並んだ線分上に近接点Pと同様にして次々に近接点を設定していき、設定された近接点のうち近接点Pからのリンク上の長さが最大となる近接点として求められる。この近接点Qを求める具体的な方法を、図9(a)により説明する。
【0050】
前述のようにして図9(a)の近接点Pが求められたら、次に、点A[k+1]または点B[s+1]から下ろした垂線に対しても、同じようにして近接点を求める。この近接点をQ1と表す。すなわち近接点Q1は、線分Akに対して点B[s+1]から下ろした垂線の長さが所定の長さ以下であり、かつその垂線と線分Akが交差するときに、その垂線と線分Akとの交点として求められる。あるいは、線分Bsに対して点A[k+1]から下ろした垂線の長さが所定の長さ以下であり、かつその垂線と線分Bsが交差するときに、その垂線と線分Bsとの交点として求められる。図9(a)では、点B[s+1]から下ろした垂線と線分Akとの交点が、近接点Q1として線分Ak上に設定されている様子を図示している。
【0051】
上記のようにして近接点Q1が求められたら、この近接点Q1が設定されていない方のリンクについて次の(隣の)点と線分を対象として、同様の方法により次の近接点Q2を求める。すなわち図9(a)の例では、線分Akに対して点B[s+2]から下ろした垂線の長さが所定の長さ以下であり、かつその垂線と線分Akが交差するときに、その垂線と線分Akとの交点として求められる。あるいは、線分Bs+1に対して点A[k+1]から下ろした垂線の長さが所定の長さ以下であり、かつその垂線と線分Bs+1が交差するときに、その垂線と線分Bs+1との交点として求められる。図9(a)では、点A[k+1]から下ろした垂線と線分Bs+1との交点が、近接点Q2として線分Bs+1上に設定されている。
【0052】
以上説明したのと同様にして、上記のような近接点の設定条件を満たさなくなるまで、リンクAまたはリンクBの線分上に近接点Q3、Q4、・・・が順番に設定されていく。そして、最後に設定された近接点Qnが、最終的な近接点Qとされる。図9(a)の例では、線分Ak+1上に設定された近接点Q3が近接点Qとされている様子を表している。このようにして、ステップS422において近接点Qが求められる。
【0053】
上記のように近接点PおよびQが求められると、次にリンクAとリンクBをそれぞれ分割する。リンクAは(b)に示すように、先頭から近接点PまでのリンクA1と、近接点Pから近接点QまでのリンクCと、近接点Qから末尾までのリンクA2に分割する。またリンクBも同様に、先頭から近接点PまでのリンクB1と、近接点Pから近接点QまでのリンクCと、近接点Qから末尾までのリンクB2に分割する。このとき、近接点Pと近接点Qの間にある点、すなわち近接点Pおよび前述の近接点Q1,Q2,・・・にそれぞれ対応する点(各近接点を設定したときにそこから垂線を下ろした点)が削除される。図9(b)では、点B[s]、B[s+1]、A[k+1]およびB[s+2]が削除される。これにより、リンクB1については点B[s−1]と近接点Pが接続され、リンクB2については近接点Qと点B[s+3]が接続される。このようにして、ステップS423とS424においてリンクAとリンクBがそれぞれ分割され、近接部分が1つのリンクCに統合される。
【0054】
なお、近接点Qが求められない場合、すなわち近接点Pと近接点Qが一致してしまうような場合には、分割後のリンクCの長さを0として設定する。また、近接点PがリンクAやリンクBの先頭部分と一致してしまう場合は、分割後のリンクA1やリンクB1の長さを0として設定する。同様に、近接点QがリンクAやリンクBの末尾部分と一致してしまう場合は、分割後のリンクA2やリンクB2の長さを0として設定する。このように長さを0として設定される分割後のリンクは、ダミーリンクと呼ばれている。こうして設定されるダミーリンクがステップS413やS416においてリンクAやリンクBとして選択された場合、ステップS414またはステップS417が否定判定されることにより、そのダミーリンクに対しては上記のような近接点を求める処理が行われない。
【0055】
次に、図2のステップS500において実行される要約地図作成処理の内容について説明する。要約地図作成処理では、方向量子化処理と呼ばれる処理を実行することによって各経路の道路形状を簡略化することにより、各経路の要約地図を作成する。この方向量子化処理について、以下に説明する。
【0056】
方向量子化処理では、各経路のリンクをそれぞれ所定の分割数で分割した上で、道路形状の簡略化を行う。図10および図11は、いずれもこの方向量子化処理の内容を説明するための詳細説明図であり、図10ではリンク分割数が2(2分割)の場合について、また図11ではリンク分割数が4(4分割)の場合について、それぞれの方向量子化処理の内容を図示している。以下、図10に示す2分割の場合より先に説明を行う。
【0057】
図10(a)の符号30は、探索された経路に含まれているリンクの1つを例示している。このリンク30に対して、(b)に示すように、その両端点の間を結ぶ線分31から最も遠くにあるリンク30上の点32を選択する。なお、ここで選択される点32は前述の形状補間点に相当し、両端点はノードに相当する。
【0058】
上記のような点32が求められたら、次に(c)に示すように、リンク30の両端点のそれぞれと点32とを結ぶ線分33および34を設定する。この線分33と34がそれぞれの基準線に対してなす角度をθ1およびθ2と表す。なお、ここでいう基準線とは、リンク30の両端点から予め決められた所定の方向(たとえば、真北方向)に向かって、それぞれ延びている線のことである。(c)に示すように、一方の端点からの基準線と線分33によって挟まれている部分の角度が、θ1と表される。また、もう一方の端点からの基準線と線分34によって挟まれている部分の角度が、θ2と表される。
【0059】
上記のようにして点32とリンク30の両端点とをそれぞれ結ぶ線分33、34が設定されたら、次に(d)に示すように、この線分33と34の方向をそれぞれ量子化する。ここでいう方向の量子化とは、前述の角度θ1およびθ2が予め設定された単位角度の整数倍にそれぞれなるように、線分33と34を各端点を中心にしてそれぞれ回転させることをいう。すなわち、θ1=m・Δθ、θ2=n・Δθ(n、mは整数)となるように、線分33と34をそれぞれ回転させてθ1とθ2の値を補正する。上記の式においてmとnの値は、この式によって計算される補正後のθ1とθ2がそれぞれ元の値に最も近くなるように設定される。
【0060】
以上説明したように線分33と34の方向をそれぞれ量子化すると、線分33と34が基準線となす角度θ1およびθ2が、単位角度Δθ刻みで補正される。なお図10(d)では、Δθ=15°としている。そして、θ1についてはm=6と設定して補正後の角度を90°にし、θ2についてはn=0と設定して補正後の角度を0°にした例を図示している。
【0061】
こうして線分33と34の方向をそれぞれ量子化したら、次に線分33と34をそれぞれ延長したときの交点を求める。そして、その交点と各端点とを結ぶようにして、(d)に示すように、線分33と34の長さをそれぞれ補正する。
【0062】
以上説明したようにして、線分33と34を求め、これらの方向を量子化すると共に長さを補正することによって、リンク30に対する2分割の場合の方向量子化処理が行われる。この線分33と34をリンク30の代わりに用いることで、リンク30の形状を簡略化して表すことができる。このとき、リンク30の両端点の位置が固定された状態でリンク30の形状が簡略化されるため、隣接するリンクの位置には影響を及ぼさない。したがって、方向量子化処理を用いて経路の各リンク形状をそれぞれ簡略化することにより、経路の全体的な位置関係を保ちつつ、その道路形状を容易に簡略化することができる。
【0063】
次に、4分割の場合の方向量子化処理について説明する。図11(a)の符号40は、図10(a)と同様に、探索された経路に含まれているリンクの1つを例示している。このリンク40に対して、(b)に示すように、まずその両端点の間を結ぶ線分41aから最も遠くにあるリンク40上の点42aを選択する。次に、その点42aとリンク40の各端点とをそれぞれ結ぶ線分41bおよび41cを設定し、この線分41bと41cからそれぞれ最も遠く離れた位置にあるリンク40上の点42bおよび42cを選択する。なお、ここで選択される点42a〜42cは、いずれも2分割の場合と同様に前述のノードまたは形状補間点に相当する。
【0064】
上記のような点42a〜42cが求められたら、次に(c)に示すように、2分割の場合と同様にして、リンク40の各端点と点42a〜42cとをそれぞれ順に結ぶ線分43、44、45および46を設定する。この線分43〜46がそれぞれの基準線に対してなす角度を、θ3、θ4、θ5およびθ6と表す。なお、このときの基準線はリンク40の両端点に対して定められるだけでなく、点42a〜42cのうち真ん中に位置する最初に選択された点42aに対しても定められる。
【0065】
上記のようにして線分43〜46が設定されたら、次に(d)に示すように、各線分の方向をそれぞれ量子化する。このとき、点42aを保存点として、線分44と45はこの保存点42aを中心にそれぞれ回転させる。なお、線分43と46については、2分割の場合と同様に各端点を中心にそれぞれ回転させる。ここでは、Δθ=15°と予め設定し、θ3〜θ6の補正後の角度をそれぞれ60°、45°、180°および60°とした例を図示している。
【0066】
こうして線分43〜46の方向をそれぞれ量子化したら、次に線分43と44をそれぞれ延長したときの交点と、線分45と46をそれぞれ延長したときの交点とを求める。そして、各交点と各端点または保存点42aとを結ぶようにして、(d)に示すように、線分43〜46の長さをそれぞれ補正する。
【0067】
以上説明したようにして、線分43〜46を求め、これらの方向を量子化すると共に長さを補正することによって、リンク40に対する4分割の場合の方向量子化処理が行われる。この線分43〜46をリンク40の代わりに用いることで、リンク40の形状を簡略化して表すことができる。このとき、リンク40の両端点の位置に加えて、さらに保存点42aの位置も固定された状態で、リンク40の形状が簡略化される。したがって、複雑な形状のリンクによって構成されている経路に対しても、その全体的な位置関係を保ちつつ適切に道路形状を簡略化することができる。
【0068】
なお、上記では2分割と4分割の場合の方向量子化処理について説明したが、これ以外の分割数についても同様にして方向量子化処理を実行することができる。たとえば8分割の場合には、まず4分割の場合と同様に、リンクの両端点の間を結ぶ線分から最も遠い1点と、その点と両端点とを結ぶ2つの線分からそれぞれ最も遠い2点を選択する。その後、さらにこれらの3点に両端点を加えた各点間を結ぶ4つの線分からそれぞれ最も遠い4点を選択する。こうして選択された合計7点と両端点とを順に結ぶ8つの線分を求め、これらの線分に対して前述したような方向の量子化と長さの補正を行うことによって、8分割の方向量子化処理を行うことができる。
【0069】
方向量子化処理の分割数をいくつにするかは、予め設定しておいてもよいし、あるいはリンクの形状によって判断してもよい。たとえば、上記のようにして両端点またはそれまでに選択された点の間を結ぶ各線分から最も遠い点を順次選択していくとき、すなわち図10および11の(b)で説明した処理を繰り返していくときに、各線分から最も遠い点までの距離が所定値以下となるまで処理を繰り返して、その処理回数に応じた数の点を順次選択していく。このようにすれば、リンクの形状によって方向量子化処理の分割数を決めることができる。
【0070】
図10で説明した2分割の方向量子化処理において、方向を量子化した後に線分33と34をそれぞれ延長しても、適切な交点がない場合がある。すなわち、方向を量子化した後の線分33と34が平行となっている場合には、これらの線分を延長すると両者が一体化してリンク33の両端点を結ぶ1つの線分となるため、交点が存在しないこととなる。このような場合には、その両端点を直接結ぶ線分、すなわち線分31を用いて、リンク30の形状を簡略化して表すようにすればよい。また、図11で説明した4分割の方向量子化処理や、それ以上の分割数の方向量子化処理において、同様に方向を量子化した後に各線分を延長すると適切な交点がない場合には、それよりも分割数が少ない方向量子化処理を行うようにすればよい。
【0071】
以上説明したような方向量子化処理を各経路の全てのリンクに対して順次実行していくことにより、各経路の道路形状を簡略化して要約地図を作成することができる。なお、リンク単位ではなく、リンクを複数連ねて構成されるリンク列ごとに上記のような方向量子化処理を実行するようにしてもよい。この場合、図10の点32や図11の点42a〜42cとして選択される点には、形状補間点だけでなくノードも含まれることになる。
【0072】
または、ステップS500の要約地図作成処理において、上記の方向量子化処理を実行せずに各経路の道路形状を簡略化することもできる。ここでは、各リンク形状を曲線で近似することによって各経路の道路形状を簡略化する方法を、図12を参照して説明する。
【0073】
図12(a)には、探索された経路に含まれるリンクの一部として、リンク50、51および52を例示している。これらのリンク50〜52に対して、まず(b)に示すように各リンクの両端点において量子化したリンク方向を求める。ここでは、前述の方向量子化処理において各線分の方向の量子化を行ったのと同様にして、元の角度に最も近くて単位角度の整数倍となるようなリンク方向を求める。その結果、(b)において矢印で示されているようなリンク方向が各端点に対して求められる。
【0074】
次に、(c)に示すように各端点の間を結ぶ曲線53、54および55を求めることにより、各リンクの形状を曲線近似する。このとき、各曲線の端点付近における接線の方向が上記の量子化したリンク方向と一致するように、曲線53〜55の形状がそれぞれ決定される。なお、このような曲線を求める方法としては、たとえばスプライン関数を用いたスプライン近似などがあるが、ここでは詳細な説明は省略する。
【0075】
以上説明したような処理を各経路の全てのリンクに対して順次実行していき、求められた曲線を用いて道路形状を表すことにより、各経路の道路形状を簡略化して要約地図を作成することができる。このときも方向量子化処理の場合と同様に、各リンクの両端点の位置が固定された状態で各リンクの形状が簡略化される。したがってこの場合にも、経路の全体的な位置関係を保ちつつ、その道路形状を容易に簡略化することができる。
【0076】
以上説明した実施の形態によれば、次の作用効果が得られる。
(1)探索された複数の経路の要約地図を作成する前に、各経路の相対的な位置関係に基づいて、各経路のリンクを簡潔化することとした(ステップS400)。このようにしたので、複数の経路の要約地図を作成する場合に、適切に道路形状が簡略化されるように事前に各経路のリンクを簡潔化しておくことができる。
【0077】
(2)リンク簡潔化処理において近接リンク統合処理を行う(ステップS410)ことにより、各経路のうちいずれか2つ以上の経路が近接部分を有している場合には、その近接部分を1つのリンクに統合することとした。このようにしたので、互いに近接している複数の経路に対して適切に道路形状が簡略化されるように、各経路のリンクを簡潔化しておくことができる。
【0078】
(3)リンクAとリンクBのいずれかの上に近接点Pを求め(ステップS420)、さらに近接点Qを求める(ステップS422)。そして、近接点Pと近接点Qをつないで1つのリンクCとして表し、リンクAとリンクBを、それぞれの先頭から近接点PまでのリンクA1およびB1と、リンクCと、近接点Qからそれぞれの末尾までのリンクA2およびB2とに分割することとした(ステップS423,424)。このようにしたので、複数経路の近接部分を簡単に1つのリンクに統合することができる。
【0079】
(4)近接部分が統合された1つのリンクに対して、そのリンクには複数の道路が含まれていることを示すフラグ情報が付与されることとしたので、そのリンクを要約した後に要約地図中に描画するときに、このフラグ情報に基づいて複数の経路をそれぞれ判別できるような表示形態で描画することができる。
【0080】
なお、上記の実施の形態において、近接リンク統合処理を行う前に、探索された各経路がどこで交差しているのかを予め把握しておくようにしてもよい。さらにこのとき、立体交差のように同じ位置を通るが直接は交わらない経路同士の接続関係も予め把握しておくようにしてもよい。このように経路同士の接続関係を予め把握した上で近接リンク統合処理を実行するようにすれば、接続点付近に対して重点的に処理を行うことで、効率的に処理することができる。
【0081】
上記の実施形態では、ナビゲーション装置において、DVD−ROMなどの記憶メディアより地図データを読み出して要約地図を作成する例について説明しているが、本発明はこの内容には限定されない。たとえば、携帯電話などによる無線通信を用いて、地図データを情報配信センターからダウンロードする通信ナビゲーション装置などにおいても、本発明を適用できる。この場合、上記に説明したような要約地図の作成処理を情報配信センターにおいて行い、その結果を情報配信センターから信号出力してナビゲーション装置へ配信するようにしてもよい。すなわち、情報配信センターは、要約地図を作成する装置と、その要約地図を外部へ信号出力する装置によって構成される。
【0082】
本発明は、上記実施の形態に限定されるものではない。本発明の技術的思想の範囲内で考えられるその他の態様も、本発明の範囲内に含まれる。
【図面の簡単な説明】
【0083】
【図1】本発明の一実施形態によるナビゲーション装置の構成を示すブロック図である。
【図2】設定された目的地まで複数の経路を探索して各経路の要約地図を表示するときに実行される処理のフローチャートである。
【図3】要約前の地図と要約後の地図を示した図である。
【図4】リンク簡潔化処理の内容を示すフローチャートである。
【図5】リンク簡潔化処理において実行される近接リンク統合処理の内容を説明するための図である。
【図6】同じくリンク簡潔化処理において実行される微小リンク除去処理の内容を説明するための図である。
【図7】同じくリンク簡潔化処理において実行される微小間隔中間点除去処理の内容を説明するための図である。
【図8】近接リンク統合処理の内容を示すフローチャートである。
【図9】近接リンク統合処理において近接点Pと近接点Qを求め、この近接点Pと近接点QによりリンクAとリンクBを分割する方法について、詳しく説明するための図である。
【図10】要約地図を作成するときに利用される2分割の場合の方向量子化処理の内容を説明するための図である。
【図11】同じく4分割の場合の方向量子化処理の内容を説明するための図である。
【図12】各リンク形状を曲線で近似することによって各経路の道路形状を簡略化する方法を説明するための図である。
【符号の説明】
【0084】
1 ナビゲーション装置
11 制御回路
12 ROM
13 RAM
14 現在地検出装置
15 画像メモリ
16 表示モニタ
17 入力装置
18 ディスクドライブ
19 DVD−ROM
30,40 リンク
61 現在地
62 目的地
63〜65 経路
【技術分野】
【0001】
本発明は、道路地図を簡略化した要約地図を作成する装置に関する。
【背景技術】
【0002】
地図を表すための地図データに基づいて、道路形状を簡略化する方法が知られている。たとえば、特許文献1に開示される装置では、地図データにおいて道路形状を表している各リンクに対して直線化や直交化などの処理を行い、さらに、マスクで規定した範囲内のランドマーク情報のみを表示することにより、道路形状を簡略化する。このようにして簡略化された道路形状を用いて作成された要約地図を表示することで、通常の地図よりも見やすい地図を提供する。
【0003】
【特許文献1】特開平11−202762号公報
【発明の開示】
【発明が解決しようとする課題】
【0004】
特許文献1に開示される装置では、各リンクに対して直線化や直交化などの処理を行うことによって道路形状を簡略化することにより、要約地図を作成している。しかし、このような処理方法によって道路形状を簡略化すると、複数の経路の要約地図を作成する場合には、適切に道路形状が簡略化されないことがある。たとえば、互いに近接している複数の経路に対して道路形状を簡略化すると、それぞれの経路が要約地図において重なってしまうことがある。
【課題を解決するための手段】
【0005】
請求項1の発明による要約地図作成装置は、出発地から設定された目的地までの複数の経路を探索する経路探索手段と、所定の道路区間ごとに設定されたリンクの形状によって道路の形状を表した道路地図データに基づいて、経路探索手段により探索された各経路の道路形状を簡略化した要約地図を作成する要約地図作成手段と、要約地図作成手段により要約地図を作成する前に、各経路の相対的な位置関係に基づいて、各経路のリンクを簡潔化するリンク簡潔化手段とを備えるものである。
請求項2の発明は、請求項1の要約地図作成装置において、リンク簡潔化手段は、各経路のうちいずれか2つ以上の経路がその経路間の距離が所定値以下である近接部分をそれぞれ有している場合、その近接部分を1つのリンクに統合することにより、各経路のリンクを簡潔化するものである。
請求項3の発明は、請求項2の要約地図作成装置において、リンク簡潔化手段は、各々が複数の経路のいずれかの一部分を表し、各々の間の距離が所定値以下であるリンクAとリンクBのいずれかの上に、第1の近接点Pおよび第2の近接点Qを求め、第1の近接点Pと第2の近接点Qの間をつないで1つのリンクCとして表し、リンクAとリンクBを、それぞれの先頭から第1の近接点PまでのリンクA1およびB1と、リンクCと、第2の近接点Qからそれぞれの末尾までのリンクA2およびB2とに分割するものである。
請求項4の発明は、請求項2または3の要約地図作成装置において、近接部分が統合された1つのリンクに対して、そのリンクには複数の道路が含まれていることを示すフラグ情報を付与することとするものである。
【発明の効果】
【0006】
本発明によれば、探索された複数の経路の要約地図を作成する前に、各経路の相対的な位置関係に基づいて、各経路のリンクを簡潔化することとした。このようにしたので、複数の経路の要約地図を作成する場合に、適切に道路形状が簡略化されるように事前に各経路のリンクを簡潔化しておくことができる。
【発明を実施するための最良の形態】
【0007】
本発明の一実施形態によるナビゲーション装置の構成を図1に示す。このナビゲーション装置は車両に搭載されており、設定された目的地までの経路を複数探索して、各経路の全体について通常の地図を基に道路形状などを簡略化することにより、通常の地図を要約した地図(以下、要約地図という)を作成して表示する。そして、表示した複数の経路のうち1つをユーザに選択させ、その経路を推奨経路として自車両を目的地まで案内する。図1に示すナビゲーション装置1は、制御回路11、ROM12、RAM13、現在地検出装置14、画像メモリ15、表示モニタ16、入力装置17、およびディスクドライブ18を有している。ディスクドライブ18には、地図データが記録されたDVD−ROM19が装填される。
【0008】
制御回路11は、マイクロプロセッサおよびその周辺回路からなり、RAM13を作業エリアとしてROM12に格納された制御プログラムを実行することにより、各種の処理や制御を行う。この制御回路11において後で説明するような処理を実行することによって、設定された目的地に対してDVD−ROM19に記録された地図データに基づいて複数の経路が探索され、各経路の全体について要約地図が作成されて、それぞれ表示モニタ16に表示される。
【0009】
現在地検出装置14は、自車両の現在地を検出する装置であり、たとえば、自車両の進行方位を検出する振動ジャイロ14a、車速を検出する車速センサ14b、GPS衛星からのGPS信号を検出するGPSセンサ14c等からなる。ナビゲーション装置1は、この現在地検出装置14により検出された自車両の現在地に基づいて、推奨経路を探索するときの経路探索開始点を決定することができる。
【0010】
画像メモリ15は、表示モニタ16に表示するための画像データを一時的に格納する。この画像データは、要約地図を画像表示するための道路地図描画用データや各種の図形データ等からなり、制御回路11において、DVD−ROM19に記録されている地図データに基づいて作成される。この画像メモリ15に格納された画像データを用いて、各経路の全体の要約地図が表示モニタ16に表示される。
【0011】
入力装置17は、ユーザが目的地の設定などを行うための各種入力スイッチを有し、これは操作パネルやリモコンなどによって実現される。ユーザは、表示モニタ16に表示される画面指示に従って入力装置17を操作することにより、地名や地図上の位置を指定して目的地を設定し、その目的地までの経路探索をナビゲーション装置1に開始させることができる。
【0012】
ディスクドライブ18は、要約地図を作成するために用いられる地図データを、装填されたDVD−ROM19より読み出す。なお、ここではDVD−ROMを用いた例について説明しているが、DVD−ROM以外の他の記録メディア、たとえばCD−ROMやハードディスクなどより、地図データを読み出すこととしてもよい。この地図データには、複数の経路を演算するために用いられる経路計算データや、交差点名称、道路名称など、ユーザに選択された推奨経路に従って自車両を目的地まで案内するために用いられる経路誘導データ、道路を表す道路データ、さらには海岸線や河川、鉄道、地図上の各種施設(ランドマーク)など、道路以外の地図形状を表す背景データなどが含まれている。
【0013】
道路データにおいて、道路区間を表す最小単位はリンクと呼ばれている。すなわち、各道路は所定の道路区間ごとに設定された複数のリンクによって構成されている。なお、リンクによって設定される道路区間の長さは異なっており、リンクの長さは一定ではない。リンク同士を接続している点はノードと呼ばれ、このノードはそれぞれに位置情報(座標情報)を有している。また、リンク内にはノードとノードの間に形状補間点と呼ばれる点が設定されていることもある。形状補間点もノードと同じく、それぞれに位置情報(座標情報)を有している。このノードと形状補間点の位置情報によって、リンク形状、すなわち道路の形状が決定される。経路計算データには、上記の各リンクに対応して、自車両の通過所要時間を表すためのリンクコストと呼ばれる値が設定されている。
【0014】
前述のように入力装置17におけるユーザの操作によって目的地が設定されると、制御回路11において図2に示すフローチャートが実行される。これにより、現在地検出装置14により検出された現在地を経路探索開始点として、設定された目的地までの経路演算が経路計算データに基づいて所定のアルゴリズムにより行われ、目的地までの複数の経路が求められる。そして、こうして求められた各経路の全体の要約地図が道路データに基づいて作成され、表示モニタ16に表示される。
【0015】
図2のフローチャートについて以下に説明する。ステップS100では、ユーザに入力された目的地により、経路探索の目的地を設定する。ステップS200では、経路探索開始点である自車両の現在地から、ステップS100において設定された目的地まで、複数の経路を探索する。このとき、前述したように経路計算データに基づいて所定のアルゴリズムにより経路演算が行われる。なお、自車両の現在地は現在地検出装置14によって一定時間ごとに求められる。
【0016】
なお、ステップS200では複数の経路を探索するために、様々な経路探索条件によって経路探索を行う。たとえば、有料道路優先や一般道路優先、距離優先などの経路探索条件によって経路探索を行い、それぞれの条件で最適な経路を求めることにより、複数の経路を探索する。あるいは、1つの経路探索条件によって最適経路以外の経路も探索することで、複数の経路を探索するようにしてもよい。たとえば、目的地までのリンクコストの合計が最も小さいものを最適経路とし、さらにその最適経路とリンクコストの合計の差が所定値以内である経路も含めて経路探索結果を求めることにより、1つの経路探索条件で複数の経路を探索することができる。
【0017】
ステップS300では、海岸線抽出処理を実行する。ここでは、ステップS800の海岸線描画処理を実行するために必要な前処理として、ステップS200で探索された各経路から所定の範囲内にある海岸線の形状を抽出する。なお、この海岸線抽出処理は必要に応じて実行すればよく、実行しなくても構わない。本発明では、ここでの処理内容は直接関係がないため、詳しい説明を省略する。
【0018】
ステップS400では、リンク簡潔化処理を実行する。ここでは、ステップS500の要約地図作成処理において正しく処理を実行できるようにするための前処理として、ステップS200で探索された各経路のリンクを簡潔化する処理を行う。具体的には、複数のリンクの近接している部分同士を統合して1つのリンクで表す処理(近接リンク統合処理)と、微小なリンクを除去する処理(微小リンク除去処理)と、隣の点との間隔が微小な形状補間点を除去する処理(微小間隔中間点除去処理)とを、各経路に対して実行する。このリンク簡潔化処理の内容については、後で説明する。
【0019】
ステップS500では、ステップS200で探索され、さらにステップS400のリンク簡潔化処理が行われた各経路に対して、要約地図作成処理を実行する。このときの処理内容については、後で詳しく説明する。この要約地図作成処理によって、各経路の全体、すなわち現在地から目的地までを表す要約地図が作成される。
【0020】
ステップS600では、縮尺変更処理を実行する。ここでは、ステップS500で作成された要約地図の縮尺を部分的に変更する処理を行う。たとえば、出発地や目的地周辺の縮尺を他の部分よりも大きくして、出発地や目的地周辺が拡大されて見やすくなるようにする。なお、この縮尺変更処理は必要に応じて実行すればよく、実行しなくても構わない。本発明では、ここでの処理内容は直接関係がないため、詳しい説明を省略する。
【0021】
ステップS700では、重複部分描画処理を実行する。ここでは、ステップS500で作成された要約地図に対して、2つ以上の経路が重なっている部分をそれぞれの経路が判別できるような表示形態で描画する処理を行う。たとえば、各経路を互いに少しずつずらして描画する。なお、この重複部分描画処理は必要に応じて実行すればよく、実行しなくても構わない。本発明では、ここでの処理内容は直接関係がないため、詳しい説明を省略する。
【0022】
ステップS800では、海岸線描画処理を実行する。ここでは、ステップS300で抽出された海岸線の形状に基づいて、経路から所定の範囲内にある海岸線を描画する処理を行う。なお、この海岸線描画処理は必要に応じて実行すればよく、実行しなくても構わない。本発明では、ここでの処理内容は直接関係がないため、詳しい説明を省略する。
【0023】
ステップS900では、ステップS500において作成され、さらに必要に応じてステップS600〜S800の処理が行われた各経路の要約地図を、表示モニタ16に表示する。このとき、出発地と目的地にはそれぞれ出発地マークと目的地マークを表示する。ステップS900を実行した後は、図2のフローチャートを終了する。以上説明したようにして、目的地までの複数の経路が探索されて、各経路の全体の要約地図が表示モニタ16に表示される。
【0024】
図2のフローチャートの処理を実行して各経路の全体の要約地図を表示モニタ16に表示したら、その後ナビゲーション装置1は、各経路のうち1つをユーザに選択するように指示する。ユーザが入力装置17を操作することによっていずれかの経路を選択すると、選択された経路を推奨経路に設定して、現在地の周辺の道路地図上を表示してその上に推奨経路を示す。そして、この推奨経路に従って自車両を誘導し、目的地まで案内する。なお、このとき現在地周辺の道路地図として、通常の地図と要約地図のどちらを表示してもよい。このときの要約地図も、図2のフローチャートと同様の処理によって作成することができる。
【0025】
図3は、通常の要約前の地図と、図2のフローチャートの処理を実行することによって表示された要約地図とを示したものである。(a)に示す要約前の地図には、現在地61から目的地62までをつなぐ3つの経路63、64および65が示されている。この経路63〜65に対して図2のフローチャートの処理を実行することにより、(b)の要約地図が表示される。この要約地図では、経路63〜65の道路形状がそれぞれ簡略化されていることが分かる。こうして各経路の要約地図を表示した後、いずれか選択された経路を推奨経路として、現在地61から目的地62まで自車両を案内する。
【0026】
ここで、ステップS400において実行されるリンク簡潔化処理の内容について説明する。リンク簡潔化処理では、図4に示すフローチャートにより、ステップS410において近接リンク統合処理を、次のステップS440において微小リンク除去処理を、その次のステップS470において微小間隔中間点除去処理を、それぞれ順番に実行する。以下、これら各処理の内容について説明する。
【0027】
図5は、近接リンク統合処理の内容を説明するための図であり、(a)には複数のリンクが互いに近接している部分を有している様子を示している。なお、複数のリンクが互いに近接している部分を有しているとは、そのリンク間の距離が所定値以下の部分が存在することを意味する。(a)のリンク71とリンク72は、それぞれ別の経路に含まれているリンクであり、互いに近接している部分を有している。すなわち、リンク71を含む経路と、リンク72を含む経路とは、その経路間の距離が所定値以下である部分(近接部分)をそれぞれ有している。
【0028】
近接リンク統合処理では、このように複数の経路が互いに近接部分を有している場合、(b)に示すように新たなリンク75を生成することにより、その近接部分を1つのリンクに統合する。このとき(a)に示す元のリンク71とリンク72は、それぞれ(b)に示すように、リンク75の前後で分割される。リンク71はリンク73、75および76に分割され、リンク72はリンク74、75および77に分割される。このようにして、複数のリンクの近接している部分同士を統合して1つのリンクで表す。
【0029】
統合されたリンク75には、2つの道路が含まれていることを示すフラグ情報が付与される。このフラグ情報を用いることにより、図2のステップS700の重複部分描画処理において要約後のリンク75を要約地図中に描画するときに、そこに含まれる複数の経路をそれぞれ判別できるような表示形態で描画することができる。なお、この近接リンク統合処理については、後でその内容を詳細に説明する。
【0030】
図6は、微小リンク除去処理の内容を説明するための図である。(a)に図示するリンク81〜85のうち、リンク81は微小なリンクであるものとする。なお、リンクの長さが予め設定された所定の値よりも短いときに、そのリンクは微小であるものとされる。ノード80aと80bは、リンク81の両端点を表している。なお、これらのノードはリンク81の端点である以外に、リンク82〜85の端点の一方でもある。
【0031】
微小リンク除去処理では、上記のような微小リンク81を除去し、さらに(b)に示すように、除去された微小リンク81の両端点であるノード80aと80bの中間の位置に、新たにノード80cを生成する。その後は(c)に示すように、ノード80aと80bを除去する。このとき、除去されたノード80aと80bのどちらか一方に接続されていたリンク82〜85は、新たに生成されたノード80cへ接続される。このようにして、微小なリンクを除去する。
【0032】
図7は、微小間隔中間点除去処理の内容を説明するための図である。(a)に図示する点86a〜86dは、いずれもリンク内に設定されている形状補間点である。これらの形状補間点は、中間点とも呼ばれている。線分87、88および89は、形状補間点(中間点)86aと86b、86bと86c、および86cと86dの間をそれぞれつなぐリンクの一部分を表している。このうち線分88は微小な線分であり、その両端にある形状補間点86bと86cの間隔は微小であるものとする。なお、形状補間点同士をつなぐ線分の長さが予め設定された所定の値よりも短いときに、その線分は微小であるものとされ、その形状補間点の間隔が微小であるものとされる。
【0033】
微小間隔中間点除去処理では、上記のように間隔が微小な形状補間点86bと86cののうち一方を除去する。このとき、微小な線分88の反対側につながっている線分の長さが短いほうの形状補間点を除去する。ここで、形状補間点86bにつながっている線分87と、形状補間点86cにつながっている線分89では、(a)に図示されるように線分89の方が短い。したがって、(b)のように形状補間点86cを除去する。形状補間点86cを除去したら、その両隣の形状補間点86bと86dの間をつなぐ線分90を、線分88と89の代わりに生成する。このようにして、隣の点との間隔が微小な形状補間点を除去する。なお、形状補間点とリンク端点(ノード)の間隔が微小であるときには、形状補間点のほうを除去してノードは除去しないようにする。
【0034】
次に、近接リンク統合処理の内容を詳細に説明する。図8には、近接リンク統合処理で実行される処理のフローチャートを示している。なお、このフローチャートを実行するときには、変数i,j,k、sおよびLが用いられる。このうちLの初期値には、図2のステップS200で探索された全ての経路に含まれる全リンクの合計数が設定される。また、その全リンクのそれぞれをV[t](t=0,1,2,・・・)と表す。このときtが取りうる最大値は、(全リンクの合計数−1)である。すなわち、(tの最大値+1)=(Lの初期値)である。以下に図8のフローチャートについて説明する。
【0035】
ステップS411では、変数iの初期値としてi=0を設定する。ステップS412では、その時点における変数Lと変数iの値に基づいて、i<L−1であるか否かを判定する。i<L−1である場合は次のステップS413へ進む。i<L−1でない場合、すなわちi≧(L−1)である場合は、図8のフローチャートを終了する。この場合、図4のステップS410の近接リンク統合処理を終了して、次のステップS440の微小リンク除去処理を実行する。
【0036】
ステップS413では、A=V[i]として、その時点における変数iの値に基づいてリンクAとしていずれかのリンクを選択する。ステップS414では、ステップS413で選択したリンクAの長さが所定値εよりも大きいか否かを判定する。(Aの長さ)>εの場合はステップS415へ進み、そうでない場合、すなわち(Aの長さ)≦εの場合には、後で説明するステップS428へ進む。なお、このときの所定値εの値は予め設定されている。ステップS415では、j=i+1として、変数iに1を加えた値を変数jに代入する。
【0037】
ステップS416では、B=V[j]として、その時点における変数jの値に基づいてリンクBとしていずれかのリンクを選択する。ステップS417では、ステップS416で選択されたリンクBの長さが前述の所定値εよりも大きいか否かを判定する。(Bの長さ)>εの場合は、ステップS418へ進み、そうでない場合、すなわち(Bの長さ)≦εの場合は、後で説明するステップS426へ進む。ステップS418では、変数kに対してk=0とする。ステップS419では、変数sに対してs=0とする。
【0038】
ステップS420では、リンクAまたはリンクB上に近接点Pを求める。このステップS420において近接点Pを求める方法については、後で詳しく説明する。ステップS421では、ステップS420において近接点Pが求められたか否かを判定する。ステップS420において近接点Pが求められた場合には、次のステップS422へ進む。一方、ステップS420において近接点Pが求められなかった場合は、ステップS429へ進む。以下、ステップS422へ進んだ場合から先に説明する。
【0039】
ステップS422では、リンクAまたはリンクB上に近接点Qを求める。この近接点Qの求め方については、前述の近接点Pと同様に後で説明する。ステップS423では、ステップS420で求められた近接点PとステップS422で求められた近接点Qにより、リンクAを次のように新たな3つのリンクに分割する。1つ目のリンクは、元のリンクAの一方の端点と近接点Pとをつなぐリンク(リンクA1とする)である。2つ目のリンクは、近接点Pと近接点Qをつなぐリンク(リンクCとする)である。3つ目のリンクは、近接点Qと元のリンクAのもう一方の端点とをつなぐリンク(リンクA2とする)である。この内容については、後で詳しく説明する。
【0040】
ステップS424では、ステップS423と同様にして、リンクBを3つのリンクに分割する。すなわち、元のリンクBの一方の端点と近接点Pとをつなぐリンク(リンクB1とする)と、近接点Pと近接点Qをつなぐリンク(リンクC)と、近接点Qと元のリンクBのもう一方の端点とをつなぐリンク(リンクB2とする)とに、リンクBを分割する。なお、近接点Pと近接点QをつなぐリンクCは、ステップS423においてリンクAが分割されることによって生成されたものと共通である。このリンクCには、前述したように2つの道路が含まれていることを示すフラグ情報が付与される。
【0041】
ステップS425では、ステップS423およびS424の結果に基づいて、変数Lの値を更新する。すなわち、ステップS423とS424において分割する前にはリンクA,Bの2個のリンクであったところが、分割した後には上記のようにリンクA1,A2,B1,B2およびCと合計5個のリンクとなって、リンクが3個増えている。そのため、ここでは変数Lの値に3を加えることで、Lの値を更新する。
【0042】
ステップS426では、変数jの値に1を加える。ステップS427では、その時点における変数Lと変数jの値に基づいて、変数jが変数Lよりも小さいか否かを判定する。j<Lである場合はステップS416へ戻る。変数jが変数Lより小さくない場合、すなわちj≧Lである場合は、次のステップS428へ進む。ステップS428では、変数iの値に1を加える。ステップS428を実行した後は、ステップS412へ戻る。
【0043】
一方、ステップS421において近接点Pが求められなかったと判定されてステップS429へ進んだ場合は、ステップS429で変数sの値に1を加える。ステップS430では、変数sがNより小さいか否か判定する。ここで、NはリンクBに含まれる点の総数である。s<Nである場合はステップS420へ戻り、s≧Nである場合は次のステップS431へ進む。
【0044】
ステップS431では、変数kの値に1を加える。ステップS432では、変数kがMより小さいか否か判定する。ここで、MはリンクAに含まれる点の総数である。k<Mである場合はステップS419へ戻り、k≧Mである場合はステップS426へ進む。以上説明したようにして、近接リンク統合処理が実行される。
【0045】
ここで図9を用いて、前述のステップS420において近接点Pを求め、さらにステップS422において近接点Qを求めて、この近接点Pと近接点QによりステップS423とS424においてリンクAとリンクBを分割する方法について、詳しく説明する。図9(a)には、リンクAとリンクBの一部分がそれぞれ図示されている。なお、このリンクAとリンクBは、ステップS413とステップS416においてそれぞれ選択されるものであり、探索された複数の経路のいずれかの一部分を表している。
【0046】
図9(a)の点A[k]と点B[s]は、その時点で設定されている変数kと変数sの値に基づいて、リンクA上とリンクB上に存在する点の中からそれぞれ選択された点である。ここでは、リンクAの先頭から数えてk番目にある点をA[k]と表し、リンクBの先頭から数えてs番目にある点をB[s]と表している。なお、ここでいうリンク上の点とは、前述のノードまたは形状補間点に相当する。
【0047】
近接点Pは、点A[k]と点A[k+1]とをつなぐ線分(線分Akと表す)に対して点B[s]から下ろした垂線の長さが所定の長さ以下であり、かつその垂線と線分Akが交差するときに、その垂線と線分Akとの交点として求められる。あるいは、リンクAとリンクBの関係を逆にして、点B[s]と点B[s+1]とをつなぐ線分(線分Bsと表す)に対して点A[k]から下ろした垂線の長さが所定の長さ以下であり、かつその垂線と線分Bsが交差するときに、その垂線と線分Bsとの交点として求められる。このような条件のいずれかを満たす近接点Pが、ステップS420において線分Ak上または線分Bs上に設定される。図9(a)には、点B[s]から下ろした垂線と線分Akとの交点が近接点Pとして線分Ak上に設定されている様子を図示している。
【0048】
なお、上記の条件のいずれも満たさない場合、たとえば点A[k]から線分Bsへ下ろした垂線の長さと、点B[s]から線分Akへ下ろした垂線の長さが、いずれも所定の長さより大きい場合などは、ステップS420において近接点Pが設定されない。その場合には、次のステップS421において近接点Pが求められなかったと判定される。
【0049】
上記のようにして近接点Pが求められると、次に近接点Qが求められる。近接点Qは、線分AkおよびBsから順に並んだ線分上に近接点Pと同様にして次々に近接点を設定していき、設定された近接点のうち近接点Pからのリンク上の長さが最大となる近接点として求められる。この近接点Qを求める具体的な方法を、図9(a)により説明する。
【0050】
前述のようにして図9(a)の近接点Pが求められたら、次に、点A[k+1]または点B[s+1]から下ろした垂線に対しても、同じようにして近接点を求める。この近接点をQ1と表す。すなわち近接点Q1は、線分Akに対して点B[s+1]から下ろした垂線の長さが所定の長さ以下であり、かつその垂線と線分Akが交差するときに、その垂線と線分Akとの交点として求められる。あるいは、線分Bsに対して点A[k+1]から下ろした垂線の長さが所定の長さ以下であり、かつその垂線と線分Bsが交差するときに、その垂線と線分Bsとの交点として求められる。図9(a)では、点B[s+1]から下ろした垂線と線分Akとの交点が、近接点Q1として線分Ak上に設定されている様子を図示している。
【0051】
上記のようにして近接点Q1が求められたら、この近接点Q1が設定されていない方のリンクについて次の(隣の)点と線分を対象として、同様の方法により次の近接点Q2を求める。すなわち図9(a)の例では、線分Akに対して点B[s+2]から下ろした垂線の長さが所定の長さ以下であり、かつその垂線と線分Akが交差するときに、その垂線と線分Akとの交点として求められる。あるいは、線分Bs+1に対して点A[k+1]から下ろした垂線の長さが所定の長さ以下であり、かつその垂線と線分Bs+1が交差するときに、その垂線と線分Bs+1との交点として求められる。図9(a)では、点A[k+1]から下ろした垂線と線分Bs+1との交点が、近接点Q2として線分Bs+1上に設定されている。
【0052】
以上説明したのと同様にして、上記のような近接点の設定条件を満たさなくなるまで、リンクAまたはリンクBの線分上に近接点Q3、Q4、・・・が順番に設定されていく。そして、最後に設定された近接点Qnが、最終的な近接点Qとされる。図9(a)の例では、線分Ak+1上に設定された近接点Q3が近接点Qとされている様子を表している。このようにして、ステップS422において近接点Qが求められる。
【0053】
上記のように近接点PおよびQが求められると、次にリンクAとリンクBをそれぞれ分割する。リンクAは(b)に示すように、先頭から近接点PまでのリンクA1と、近接点Pから近接点QまでのリンクCと、近接点Qから末尾までのリンクA2に分割する。またリンクBも同様に、先頭から近接点PまでのリンクB1と、近接点Pから近接点QまでのリンクCと、近接点Qから末尾までのリンクB2に分割する。このとき、近接点Pと近接点Qの間にある点、すなわち近接点Pおよび前述の近接点Q1,Q2,・・・にそれぞれ対応する点(各近接点を設定したときにそこから垂線を下ろした点)が削除される。図9(b)では、点B[s]、B[s+1]、A[k+1]およびB[s+2]が削除される。これにより、リンクB1については点B[s−1]と近接点Pが接続され、リンクB2については近接点Qと点B[s+3]が接続される。このようにして、ステップS423とS424においてリンクAとリンクBがそれぞれ分割され、近接部分が1つのリンクCに統合される。
【0054】
なお、近接点Qが求められない場合、すなわち近接点Pと近接点Qが一致してしまうような場合には、分割後のリンクCの長さを0として設定する。また、近接点PがリンクAやリンクBの先頭部分と一致してしまう場合は、分割後のリンクA1やリンクB1の長さを0として設定する。同様に、近接点QがリンクAやリンクBの末尾部分と一致してしまう場合は、分割後のリンクA2やリンクB2の長さを0として設定する。このように長さを0として設定される分割後のリンクは、ダミーリンクと呼ばれている。こうして設定されるダミーリンクがステップS413やS416においてリンクAやリンクBとして選択された場合、ステップS414またはステップS417が否定判定されることにより、そのダミーリンクに対しては上記のような近接点を求める処理が行われない。
【0055】
次に、図2のステップS500において実行される要約地図作成処理の内容について説明する。要約地図作成処理では、方向量子化処理と呼ばれる処理を実行することによって各経路の道路形状を簡略化することにより、各経路の要約地図を作成する。この方向量子化処理について、以下に説明する。
【0056】
方向量子化処理では、各経路のリンクをそれぞれ所定の分割数で分割した上で、道路形状の簡略化を行う。図10および図11は、いずれもこの方向量子化処理の内容を説明するための詳細説明図であり、図10ではリンク分割数が2(2分割)の場合について、また図11ではリンク分割数が4(4分割)の場合について、それぞれの方向量子化処理の内容を図示している。以下、図10に示す2分割の場合より先に説明を行う。
【0057】
図10(a)の符号30は、探索された経路に含まれているリンクの1つを例示している。このリンク30に対して、(b)に示すように、その両端点の間を結ぶ線分31から最も遠くにあるリンク30上の点32を選択する。なお、ここで選択される点32は前述の形状補間点に相当し、両端点はノードに相当する。
【0058】
上記のような点32が求められたら、次に(c)に示すように、リンク30の両端点のそれぞれと点32とを結ぶ線分33および34を設定する。この線分33と34がそれぞれの基準線に対してなす角度をθ1およびθ2と表す。なお、ここでいう基準線とは、リンク30の両端点から予め決められた所定の方向(たとえば、真北方向)に向かって、それぞれ延びている線のことである。(c)に示すように、一方の端点からの基準線と線分33によって挟まれている部分の角度が、θ1と表される。また、もう一方の端点からの基準線と線分34によって挟まれている部分の角度が、θ2と表される。
【0059】
上記のようにして点32とリンク30の両端点とをそれぞれ結ぶ線分33、34が設定されたら、次に(d)に示すように、この線分33と34の方向をそれぞれ量子化する。ここでいう方向の量子化とは、前述の角度θ1およびθ2が予め設定された単位角度の整数倍にそれぞれなるように、線分33と34を各端点を中心にしてそれぞれ回転させることをいう。すなわち、θ1=m・Δθ、θ2=n・Δθ(n、mは整数)となるように、線分33と34をそれぞれ回転させてθ1とθ2の値を補正する。上記の式においてmとnの値は、この式によって計算される補正後のθ1とθ2がそれぞれ元の値に最も近くなるように設定される。
【0060】
以上説明したように線分33と34の方向をそれぞれ量子化すると、線分33と34が基準線となす角度θ1およびθ2が、単位角度Δθ刻みで補正される。なお図10(d)では、Δθ=15°としている。そして、θ1についてはm=6と設定して補正後の角度を90°にし、θ2についてはn=0と設定して補正後の角度を0°にした例を図示している。
【0061】
こうして線分33と34の方向をそれぞれ量子化したら、次に線分33と34をそれぞれ延長したときの交点を求める。そして、その交点と各端点とを結ぶようにして、(d)に示すように、線分33と34の長さをそれぞれ補正する。
【0062】
以上説明したようにして、線分33と34を求め、これらの方向を量子化すると共に長さを補正することによって、リンク30に対する2分割の場合の方向量子化処理が行われる。この線分33と34をリンク30の代わりに用いることで、リンク30の形状を簡略化して表すことができる。このとき、リンク30の両端点の位置が固定された状態でリンク30の形状が簡略化されるため、隣接するリンクの位置には影響を及ぼさない。したがって、方向量子化処理を用いて経路の各リンク形状をそれぞれ簡略化することにより、経路の全体的な位置関係を保ちつつ、その道路形状を容易に簡略化することができる。
【0063】
次に、4分割の場合の方向量子化処理について説明する。図11(a)の符号40は、図10(a)と同様に、探索された経路に含まれているリンクの1つを例示している。このリンク40に対して、(b)に示すように、まずその両端点の間を結ぶ線分41aから最も遠くにあるリンク40上の点42aを選択する。次に、その点42aとリンク40の各端点とをそれぞれ結ぶ線分41bおよび41cを設定し、この線分41bと41cからそれぞれ最も遠く離れた位置にあるリンク40上の点42bおよび42cを選択する。なお、ここで選択される点42a〜42cは、いずれも2分割の場合と同様に前述のノードまたは形状補間点に相当する。
【0064】
上記のような点42a〜42cが求められたら、次に(c)に示すように、2分割の場合と同様にして、リンク40の各端点と点42a〜42cとをそれぞれ順に結ぶ線分43、44、45および46を設定する。この線分43〜46がそれぞれの基準線に対してなす角度を、θ3、θ4、θ5およびθ6と表す。なお、このときの基準線はリンク40の両端点に対して定められるだけでなく、点42a〜42cのうち真ん中に位置する最初に選択された点42aに対しても定められる。
【0065】
上記のようにして線分43〜46が設定されたら、次に(d)に示すように、各線分の方向をそれぞれ量子化する。このとき、点42aを保存点として、線分44と45はこの保存点42aを中心にそれぞれ回転させる。なお、線分43と46については、2分割の場合と同様に各端点を中心にそれぞれ回転させる。ここでは、Δθ=15°と予め設定し、θ3〜θ6の補正後の角度をそれぞれ60°、45°、180°および60°とした例を図示している。
【0066】
こうして線分43〜46の方向をそれぞれ量子化したら、次に線分43と44をそれぞれ延長したときの交点と、線分45と46をそれぞれ延長したときの交点とを求める。そして、各交点と各端点または保存点42aとを結ぶようにして、(d)に示すように、線分43〜46の長さをそれぞれ補正する。
【0067】
以上説明したようにして、線分43〜46を求め、これらの方向を量子化すると共に長さを補正することによって、リンク40に対する4分割の場合の方向量子化処理が行われる。この線分43〜46をリンク40の代わりに用いることで、リンク40の形状を簡略化して表すことができる。このとき、リンク40の両端点の位置に加えて、さらに保存点42aの位置も固定された状態で、リンク40の形状が簡略化される。したがって、複雑な形状のリンクによって構成されている経路に対しても、その全体的な位置関係を保ちつつ適切に道路形状を簡略化することができる。
【0068】
なお、上記では2分割と4分割の場合の方向量子化処理について説明したが、これ以外の分割数についても同様にして方向量子化処理を実行することができる。たとえば8分割の場合には、まず4分割の場合と同様に、リンクの両端点の間を結ぶ線分から最も遠い1点と、その点と両端点とを結ぶ2つの線分からそれぞれ最も遠い2点を選択する。その後、さらにこれらの3点に両端点を加えた各点間を結ぶ4つの線分からそれぞれ最も遠い4点を選択する。こうして選択された合計7点と両端点とを順に結ぶ8つの線分を求め、これらの線分に対して前述したような方向の量子化と長さの補正を行うことによって、8分割の方向量子化処理を行うことができる。
【0069】
方向量子化処理の分割数をいくつにするかは、予め設定しておいてもよいし、あるいはリンクの形状によって判断してもよい。たとえば、上記のようにして両端点またはそれまでに選択された点の間を結ぶ各線分から最も遠い点を順次選択していくとき、すなわち図10および11の(b)で説明した処理を繰り返していくときに、各線分から最も遠い点までの距離が所定値以下となるまで処理を繰り返して、その処理回数に応じた数の点を順次選択していく。このようにすれば、リンクの形状によって方向量子化処理の分割数を決めることができる。
【0070】
図10で説明した2分割の方向量子化処理において、方向を量子化した後に線分33と34をそれぞれ延長しても、適切な交点がない場合がある。すなわち、方向を量子化した後の線分33と34が平行となっている場合には、これらの線分を延長すると両者が一体化してリンク33の両端点を結ぶ1つの線分となるため、交点が存在しないこととなる。このような場合には、その両端点を直接結ぶ線分、すなわち線分31を用いて、リンク30の形状を簡略化して表すようにすればよい。また、図11で説明した4分割の方向量子化処理や、それ以上の分割数の方向量子化処理において、同様に方向を量子化した後に各線分を延長すると適切な交点がない場合には、それよりも分割数が少ない方向量子化処理を行うようにすればよい。
【0071】
以上説明したような方向量子化処理を各経路の全てのリンクに対して順次実行していくことにより、各経路の道路形状を簡略化して要約地図を作成することができる。なお、リンク単位ではなく、リンクを複数連ねて構成されるリンク列ごとに上記のような方向量子化処理を実行するようにしてもよい。この場合、図10の点32や図11の点42a〜42cとして選択される点には、形状補間点だけでなくノードも含まれることになる。
【0072】
または、ステップS500の要約地図作成処理において、上記の方向量子化処理を実行せずに各経路の道路形状を簡略化することもできる。ここでは、各リンク形状を曲線で近似することによって各経路の道路形状を簡略化する方法を、図12を参照して説明する。
【0073】
図12(a)には、探索された経路に含まれるリンクの一部として、リンク50、51および52を例示している。これらのリンク50〜52に対して、まず(b)に示すように各リンクの両端点において量子化したリンク方向を求める。ここでは、前述の方向量子化処理において各線分の方向の量子化を行ったのと同様にして、元の角度に最も近くて単位角度の整数倍となるようなリンク方向を求める。その結果、(b)において矢印で示されているようなリンク方向が各端点に対して求められる。
【0074】
次に、(c)に示すように各端点の間を結ぶ曲線53、54および55を求めることにより、各リンクの形状を曲線近似する。このとき、各曲線の端点付近における接線の方向が上記の量子化したリンク方向と一致するように、曲線53〜55の形状がそれぞれ決定される。なお、このような曲線を求める方法としては、たとえばスプライン関数を用いたスプライン近似などがあるが、ここでは詳細な説明は省略する。
【0075】
以上説明したような処理を各経路の全てのリンクに対して順次実行していき、求められた曲線を用いて道路形状を表すことにより、各経路の道路形状を簡略化して要約地図を作成することができる。このときも方向量子化処理の場合と同様に、各リンクの両端点の位置が固定された状態で各リンクの形状が簡略化される。したがってこの場合にも、経路の全体的な位置関係を保ちつつ、その道路形状を容易に簡略化することができる。
【0076】
以上説明した実施の形態によれば、次の作用効果が得られる。
(1)探索された複数の経路の要約地図を作成する前に、各経路の相対的な位置関係に基づいて、各経路のリンクを簡潔化することとした(ステップS400)。このようにしたので、複数の経路の要約地図を作成する場合に、適切に道路形状が簡略化されるように事前に各経路のリンクを簡潔化しておくことができる。
【0077】
(2)リンク簡潔化処理において近接リンク統合処理を行う(ステップS410)ことにより、各経路のうちいずれか2つ以上の経路が近接部分を有している場合には、その近接部分を1つのリンクに統合することとした。このようにしたので、互いに近接している複数の経路に対して適切に道路形状が簡略化されるように、各経路のリンクを簡潔化しておくことができる。
【0078】
(3)リンクAとリンクBのいずれかの上に近接点Pを求め(ステップS420)、さらに近接点Qを求める(ステップS422)。そして、近接点Pと近接点Qをつないで1つのリンクCとして表し、リンクAとリンクBを、それぞれの先頭から近接点PまでのリンクA1およびB1と、リンクCと、近接点Qからそれぞれの末尾までのリンクA2およびB2とに分割することとした(ステップS423,424)。このようにしたので、複数経路の近接部分を簡単に1つのリンクに統合することができる。
【0079】
(4)近接部分が統合された1つのリンクに対して、そのリンクには複数の道路が含まれていることを示すフラグ情報が付与されることとしたので、そのリンクを要約した後に要約地図中に描画するときに、このフラグ情報に基づいて複数の経路をそれぞれ判別できるような表示形態で描画することができる。
【0080】
なお、上記の実施の形態において、近接リンク統合処理を行う前に、探索された各経路がどこで交差しているのかを予め把握しておくようにしてもよい。さらにこのとき、立体交差のように同じ位置を通るが直接は交わらない経路同士の接続関係も予め把握しておくようにしてもよい。このように経路同士の接続関係を予め把握した上で近接リンク統合処理を実行するようにすれば、接続点付近に対して重点的に処理を行うことで、効率的に処理することができる。
【0081】
上記の実施形態では、ナビゲーション装置において、DVD−ROMなどの記憶メディアより地図データを読み出して要約地図を作成する例について説明しているが、本発明はこの内容には限定されない。たとえば、携帯電話などによる無線通信を用いて、地図データを情報配信センターからダウンロードする通信ナビゲーション装置などにおいても、本発明を適用できる。この場合、上記に説明したような要約地図の作成処理を情報配信センターにおいて行い、その結果を情報配信センターから信号出力してナビゲーション装置へ配信するようにしてもよい。すなわち、情報配信センターは、要約地図を作成する装置と、その要約地図を外部へ信号出力する装置によって構成される。
【0082】
本発明は、上記実施の形態に限定されるものではない。本発明の技術的思想の範囲内で考えられるその他の態様も、本発明の範囲内に含まれる。
【図面の簡単な説明】
【0083】
【図1】本発明の一実施形態によるナビゲーション装置の構成を示すブロック図である。
【図2】設定された目的地まで複数の経路を探索して各経路の要約地図を表示するときに実行される処理のフローチャートである。
【図3】要約前の地図と要約後の地図を示した図である。
【図4】リンク簡潔化処理の内容を示すフローチャートである。
【図5】リンク簡潔化処理において実行される近接リンク統合処理の内容を説明するための図である。
【図6】同じくリンク簡潔化処理において実行される微小リンク除去処理の内容を説明するための図である。
【図7】同じくリンク簡潔化処理において実行される微小間隔中間点除去処理の内容を説明するための図である。
【図8】近接リンク統合処理の内容を示すフローチャートである。
【図9】近接リンク統合処理において近接点Pと近接点Qを求め、この近接点Pと近接点QによりリンクAとリンクBを分割する方法について、詳しく説明するための図である。
【図10】要約地図を作成するときに利用される2分割の場合の方向量子化処理の内容を説明するための図である。
【図11】同じく4分割の場合の方向量子化処理の内容を説明するための図である。
【図12】各リンク形状を曲線で近似することによって各経路の道路形状を簡略化する方法を説明するための図である。
【符号の説明】
【0084】
1 ナビゲーション装置
11 制御回路
12 ROM
13 RAM
14 現在地検出装置
15 画像メモリ
16 表示モニタ
17 入力装置
18 ディスクドライブ
19 DVD−ROM
30,40 リンク
61 現在地
62 目的地
63〜65 経路
【特許請求の範囲】
【請求項1】
出発地から設定された目的地までの複数の経路を探索する経路探索手段と、
所定の道路区間ごとに設定されたリンクの形状によって道路の形状を表した道路地図データに基づいて、前記経路探索手段により探索された各経路の道路形状を簡略化した要約地図を作成する要約地図作成手段と、
前記要約地図作成手段により前記要約地図を作成する前に、前記各経路の相対的な位置関係に基づいて、前記各経路のリンクを簡潔化するリンク簡潔化手段とを備えることを特徴とする要約地図作成装置。
【請求項2】
請求項1の要約地図作成装置において、
前記リンク簡潔化手段は、前記各経路のうちいずれか2つ以上の経路がその経路間の距離が所定値以下である近接部分をそれぞれ有している場合、その近接部分を1つのリンクに統合することにより、前記各経路のリンクを簡潔化することを特徴とする要約地図作成装置。
【請求項3】
請求項2の要約地図作成装置において、
前記リンク簡潔化手段は、各々が前記複数の経路のいずれかの一部分を表し、各々の間の距離が前記所定値以下であるリンクAとリンクBのいずれかの上に、第1の近接点Pおよび第2の近接点Qを求め、
前記第1の近接点Pと第2の近接点Qの間をつないで1つのリンクCとして表し、
前記リンクAとリンクBを、それぞれの先頭から前記第1の近接点PまでのリンクA1およびB1と、前記リンクCと、前記第2の近接点Qからそれぞれの末尾までのリンクA2およびB2とに分割することを特徴とする要約地図作成装置。
【請求項4】
請求項2または3の要約地図作成装置において、
前記近接部分が統合された1つのリンクに対して、そのリンクには複数の道路が含まれていることを示すフラグ情報を付与することを特徴とする要約地図作成装置。
【請求項1】
出発地から設定された目的地までの複数の経路を探索する経路探索手段と、
所定の道路区間ごとに設定されたリンクの形状によって道路の形状を表した道路地図データに基づいて、前記経路探索手段により探索された各経路の道路形状を簡略化した要約地図を作成する要約地図作成手段と、
前記要約地図作成手段により前記要約地図を作成する前に、前記各経路の相対的な位置関係に基づいて、前記各経路のリンクを簡潔化するリンク簡潔化手段とを備えることを特徴とする要約地図作成装置。
【請求項2】
請求項1の要約地図作成装置において、
前記リンク簡潔化手段は、前記各経路のうちいずれか2つ以上の経路がその経路間の距離が所定値以下である近接部分をそれぞれ有している場合、その近接部分を1つのリンクに統合することにより、前記各経路のリンクを簡潔化することを特徴とする要約地図作成装置。
【請求項3】
請求項2の要約地図作成装置において、
前記リンク簡潔化手段は、各々が前記複数の経路のいずれかの一部分を表し、各々の間の距離が前記所定値以下であるリンクAとリンクBのいずれかの上に、第1の近接点Pおよび第2の近接点Qを求め、
前記第1の近接点Pと第2の近接点Qの間をつないで1つのリンクCとして表し、
前記リンクAとリンクBを、それぞれの先頭から前記第1の近接点PまでのリンクA1およびB1と、前記リンクCと、前記第2の近接点Qからそれぞれの末尾までのリンクA2およびB2とに分割することを特徴とする要約地図作成装置。
【請求項4】
請求項2または3の要約地図作成装置において、
前記近接部分が統合された1つのリンクに対して、そのリンクには複数の道路が含まれていることを示すフラグ情報を付与することを特徴とする要約地図作成装置。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【公開番号】特開2006−113458(P2006−113458A)
【公開日】平成18年4月27日(2006.4.27)
【国際特許分類】
【出願番号】特願2004−302965(P2004−302965)
【出願日】平成16年10月18日(2004.10.18)
【出願人】(591132335)株式会社ザナヴィ・インフォマティクス (745)
【Fターム(参考)】
【公開日】平成18年4月27日(2006.4.27)
【国際特許分類】
【出願日】平成16年10月18日(2004.10.18)
【出願人】(591132335)株式会社ザナヴィ・インフォマティクス (745)
【Fターム(参考)】
[ Back to top ]