(57)【要約】  この発明に係る地図描画装置は、入力された縮尺率を内部で使用される値に変換する入力値変換部１０１と、縮尺率が異なる複数種類の地図データを保存する地図データ保存部１０２と、地図データ保存部に保存されていない中間的な縮尺率の地図を作成する地図データを、地図データ保存部に保存されている地図データの中から選択する地図データ選択部１０３と、地図データ選択部で選択された地図データおよび入力値変換部で変換することにより得られた値を用いて、中間的な縮尺率の地図データを生成する加工処理部１０４を備えている。
2011010340.tif 000002
【特許請求の範囲】
【請求項１】
入力された縮尺率を内部で使用される値に変換する入力値変換部と、
縮尺率が異なる複数種類の地図データを保存する地図データ保存部と、
前記地図データ保存部に保存されていない中間的な縮尺率の地図を作成する地図データを、前記地図データ保存部に保存されている地図データの中から選択する地図データ選択部と、
前記地図データ選択部で選択された地図データおよび前記入力値変換部で変換することにより得られた値を用いて、中間的な縮尺率の地図データを生成する加工処理部
とを備えた地図描画装置。
【請求項２】
地図データ選択部は、地図データ保存部に保存されている複数種類の地図データの中から、入力された縮尺率の前後の縮尺率を持つ少なくとも２種類の地図データを選択する
ことを特徴とする請求項１記載の地図描画装置。
【請求項３】
加工処理部は、入力された縮尺率に応じたデータ量の地図データを生成する
ことを特徴とする請求項１記載の地図描画装置。
【請求項４】
加工処理部は、広域地図の特徴点と詳細地図の特徴点を合わせたデータを、描画頂点として抽出し、中間的な縮尺率を持つ地図データを作成する
ことを特徴とする請求項１記載の地図描画装置。
【請求項５】
加工処理部は、仮想的に作成した中間的な縮尺率を持つ中間地図、広域地図および詳細地図の各地図データから階層グラフを作成し、入力値変換部で変換することにより得られた値に基づき算出した閾値を元に前記階層グラフのエッジの中から閾値以上のエッジを辿ることによって、辿った頂点を描画頂点として抽出し、中間的な縮尺率を持つ地図データを作成する
ことを特徴とする請求項１記載の地図描画装置。
【請求項６】
加工処理部は、仮想的に作成する中間地図の地図データを、交差点および座標が広域地図と一致する点を含む地図の特徴点となる頂点から抽出する
ことを特徴とする請求項５記載の地図描画装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、地図を描画する地図描画装置に関し、特に縮尺率が異なる複数種類の地図データに基づき、中間的な縮尺率を持つ地図データを作成して描画に使用する技術に関する。
【背景技術】
【０００２】
カーナビゲーションシステムまたはＰＮＤ（Personal Navigation Device）などにおいて用いられる地図描画装置は、利用者の目的に応じて、地図を任意の縮尺率で表示することが可能である。例えば、目的地までの全ルートを確認するためには広域地図が使用され、渋滞の情報などといった現在地周辺の道路状況を確認するためには、詳細地図が使用されている。このように、利用者の目的に応じた縮尺率で地図を描画するために、地図描画装置の内部の記憶装置には、異なる縮尺率を持つ地図を描画するために、複数種類の独立した地図データが予め用意されている。地図描画装置は、利用者から要求された縮尺率に応じて、描画に用いる地図データを使い分けている。しかしながら、記憶容量にも限界があるため、無限に存在する縮尺率の各々に対応する地図データを保存しておくことは現実的には不可能である。【０００３】
そこで、用意されている縮尺率の地図データを用いて、用意されていない縮尺率の地図データを補間することが考えられている。例えば、１万分の１と２万分の１の縮尺率の地図データがあらかじめ用意されているとき、従来の地図描画装置においては、１．５万分の１の縮尺率の地図を描画するために、１万分の１の縮尺率の地図を縮小し、または、２万分の１の縮尺率の地図を拡大することにより、中間的な縮尺率を持つ地図を描画している。【０００４】
しかしながら、この方法で中間的な縮尺率を持つ地図を作成した場合は、以下の問題が生じる。すなわち、実際の単位面積におけるデータ量を広域地図と詳細地図とで比較した場合、詳細地図は、広域地図に比べてデータ量が多い。そのため、広域地図を拡大して中間的な縮尺率を持つ地図を描画すると、中間的な縮尺率の地図としての最適なデータ量よりも、データ量が少なくなり、中間的な縮尺率において描画すべき地図要素を描画することができない。逆に、詳細地図を縮小して中間的な縮尺率を持つ地図を描画すると、中間的な縮尺率の地図としての最適なデータ量よりも、データ量が多くなり、中間的な縮尺率において描画する必要がない地図要素まで描画することになる。【０００５】
以上の問題を解消するために、特許文献１は、複数の縮尺率の地図データを使って少ないデータ量で中間的な縮尺率の地図を適切な地図情報で表示できるようにした無段階縮尺地図表示装置を開示している。この無段階縮尺地図表示装置では、中間的な縮尺率を持つ地図を描画するために、画面のデータ量に応じて、描画に使用する地図データが適切に切り替えられる。詳しくは、中間的な縮尺率を持つ地図データを作成するための地図データ選択手段および地図データの縮尺率を決定する選択条件を設定する設定手段などを備え、選択条件に基づき記憶手段から選択して読み出す地図データの縮尺率を決定する。選択条件は、画面に描画される文字の数や道路の数などの地図情報を基準として、該地図情報の量に応じて縮尺率の大きい方の地図データと縮尺率の小さいほうの地図データの何れかを選択するものであり、設定手段は地図拡大操作と縮小操作のそれぞれで選択条件を有し、縮尺率の範囲毎に、地域環境毎に選択条件を有する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平１１−２７２１６３号公報  第１０頁、第２図
【０００７】
しかしながら、上述した特許文献１に開示された無段階縮尺地図表示装置では、中間的な縮尺率を持つ地図を描画する場合、記憶装置に記憶されている広域地図または詳細地図の地図データを加工せずに拡大または縮小が行われるため、ある縮尺率において急激に描画の変化が起こり、また、描画の縮尺率にとって最適なデータだけで描画できないという問題がある。【０００８】
このような問題のうち、まず、急激な描画の変化が起こる理由について説明する。例えば、１万分の１の縮尺率の地図データと、２万分の１の縮尺率の地図データが記憶装置に保存されており、保存されていない中間的な縮尺率の地図を描画する場合を例に挙げて説明する。１．５万分の１の縮尺率の地図を描画するために、詳細地図である１万分の１の縮尺率の地図データを用いる場合、徐々にズームアウト(縮小)していくと、２万分の１の縮尺率に切り替わった瞬間に地図のデータ量が急激に少なくなる。同様に、中間的な地図を描画するために広域地図である２万分の１の縮尺率の地図データを用いる場合、徐々にズームイン(拡大)していくと、１万分の１の縮尺率に切り替わった瞬間に地図のデータ量が急激に多くなる。そのため、従来の地図描画装置は、中間的な縮尺率の地図で描画するべき地図要素を含む地図を適切なデータ量で描画することができない。【０００９】
次に、適切なデータ量で描画できない理由について説明する。従来の地図描画装置は、中間的な縮尺率の地図を描画するために詳細地図を縮小すると冗長な地図要素を描画してしまうために処理負荷が大きくなり、また、広域地図を拡大すると必要な地図要素を描画できない。例えば、詳細地図では異なる座標の頂点列からなる道路を、中間的な縮尺率の地図を描画するために縮小すると、複数の頂点の座標が一致する場合が発生する。この場合、同一座標の間で直線または曲線を引くことになり、冗長である。一方、広域地図を拡大して中間的な縮尺率の地図を描画すると、中間的な縮尺率の地図として最適なデータよりも少ないデータ量となり、必要なデータが不足する。【００１０】
この問題は、例えば１．５万分の１〜１万分の１の縮尺率では１万分の１の地図を用い、２万分の１〜１．５万分の１の縮尺率では２万分の１を用いるなど、要求される縮尺率、利用者の操作状況、および、その他のルールにおいて、使用する地図データをどんなに適切に選択したとしても解消することができない。【００１１】
上述した適切なデータ量で地図を描画できないという問題は、一方の縮尺率の地図データを用いているために避けることができなかった。また、不連続に地図描画が切り替わることにより、利用者が地図内の目的物を見失う可能性もある。【００１２】
この発明は、上述した課題を解決するためになされたものであり、その課題は、縮尺率変更時に不連続な画面切り替えが行われることがなく、しかも、過不足の無いデータで迅速に地図を描画できる地図描画装置を提供することある。
【発明の概要】
【００１３】
この発明に係る地図描画装置は、入力された縮尺率を内部で使用される値に変換する入力値変換部と、縮尺率が異なる複数種類の地図データを保存する地図データ保存部と、地図データ保存部に保存されていない中間的な縮尺率の地図を作成する地図データを、地図データ保存部に保存されている地図データの中から選択する地図データ選択部と、地図データ選択部で選択された地図データおよび入力値変換部で変換することにより得られた値を用いて、中間的な縮尺率の地図データを生成する加工処理部を備えている。
【００１４】
この発明によれば、縮尺率変更時に、不連続な画面切り替えが行われなくなる。また、データ量の調節を行うことができるため、過不足の無いデータで迅速に地図描画を行うことが可能となる。
【図面の簡単な説明】
【００１５】
【図１】この発明の実施の形態１に係る地図描画装置の構成を示すブロック図である。
【図２】この発明の実施の形態１に係る地図描画装置の動作を、中間的な縮尺率の地図を描画するための地図データを作成する処理を中心に示すフローチャートである。
【図３】図２に示すフローチャートのステップＳＴ２０８からステップＳＴ２１０までの処理を説明するための図である。
【図４】この発明の実施の形態１に係る地図描画装置で実行される、各リンクのエッジの値を計算する処理の流れを示すフローチャートである。
【図５】図４に示すフローチャートのステップＳＴ４０３で計算される広域地図、中間地図および詳細地図の各エッジの値を示す図である。
【図６】この発明の実施の形態１に係る地図描画装置で実行される、詳細地図の各頂点に階層付けを行う処理の流れを示すフローチャートである。
【図７】この発明の実施の形態１に係る地図描画装置で実行される、階層グラフを作成する処理（自身の階層が高のとき）の流れを示すフローチャートである。
【図８】この発明の実施の形態１に係る地図描画装置で実行される、階層グラフを作成する処理（自身の階層が中のとき）の流れを示すフローチャートである。
【図９】この発明の実施の形態１に係る地図描画装置で実行される、階層グラフを作成する処理（自身の階層が低のとき）の流れを示すフローチャートである。
【図１０】この発明の実施の形態１に係る地図描画装置の加工処理部で作成された階層グラフを示す図である。
【図１１】この発明の実施の形態１に係る地図描画装置で実行される、階層グラフを走査して描画する頂点を抽出する処理の流れを示すフローチャートである。
【図１２】この発明の実施の形態１に係る地図描画装置の加工処理部で作成された中間的な縮尺率を持つ地図データの例を示す図である。
【発明を実施するための形態】
【００１６】
以下、この発明の実施の形態を、図面を参照しながら詳細に説明する。
実施の形態１．
図１は、この発明の実施の形態１に係る地図描画装置の構成を示すブロック図である。この地図描画装置は、入力値変換部１０１、地図データ保存部１０２、地図データ選択部１０３、加工処理部１０４およびメモリ１０５を備えている。
【００１７】
入力値変換部１０１は、図示しない入力装置などを用いて入力された縮尺率などの情報を、地図描画装置の内部処理において使用される値（例えば、距離または曲率など）に変換する。この入力値変換部１０１における変換によって得られた値は、地図データ選択部１０３に送られる。
【００１８】
地図データ保存部１０２は、例えば、地図などのデータおよびプログラムなどを記憶した外部記憶装置、例えばＲＯＭ（Read Only Memory）またはＲＡＭ（Random Access Memory）などから構成されている。この地図データ保存部１０２は、例えば、１万分の１の地図、２万分の１の地図、４万分の１の地図、・・・といった固有の縮尺率を持つ地図を描画するための複数種類の地図データを保存している。この地図データ保存部１０２に保存されている地図データは、地図データ選択部１０３によって読み出される。
【００１９】
地図データ選択部１０３は、地図データ保存部１０２に保存されている複数種類の地図データの中から、中間的な縮尺率を持つ地図を作成するために必要な地図データを選択する。例えば、１．３万分の１といった中間的な縮尺率の地図を新たに作成するときは、地図データ保存部１０２に保存されている複数種類の地図データ、つまり１万分の１、２万分の１、４万分の１、・・・の地図データの中から、１．３万分の１の縮尺率に近い縮尺率の地図データを、１．３万分の１の縮尺率より大きい縮尺率の地図データと、１．３万分の１の縮尺率より小さい縮尺率の地図データとから１つずつ選択する。この例では、１万分の１と２万分の１の縮尺率を持つ地図データが選択される。この地図データ選択部１０３で選択された地図データは、加工処理部１０４およびメモリ１０５に送られる。
【００２０】
加工処理部１０４は、地図データ選択部１０３から送られてきた地図データを加工し、中間的な縮尺率を持つ地図データを作成する。この加工処理部１０４で作成された地図データは、外部に送られて地図の描画に供される。
【００２１】
メモリ１０５は、例えば、高速で読み出しおよび書き込みが可能なキャッシュメモリから構成されており、地図データ選択部１０３で選択された地図データを一時的に記憶するととともに、加工処理部１０４において作成された中間的な縮尺率を持つ地図データを抽出するときの元データを記憶する。このメモリ１０５の内容は、加工処理部１０４によって読み出される。
【００２２】
次に、上記のように構成される、この発明の実施の形態１に係る地図描画装置の動作を、中間的な縮尺率の地図を描画するための地図データを作成する処理を中心に、図２に示すフローチャートを参照しながら説明する。
【００２３】
中間的な縮尺率の地図を描画するための地図データを作成する処理では、まず、縮尺率が入力される（ステップＳＴ２０１）。すなわち、利用者は、描画したい地図の縮尺率を入力する。なお、縮尺率は、地図描画装置の利用者によって入力される他に、全ルート表示などといった内部処理からの描画要求によっても入力される。
【００２４】
次いで、既存縮尺であるかどうかが調べられる（ステップＳＴ２０２）。すなわち、入力値変換部１０１は、ステップＳＴ２０１で入力された縮尺率（以下、「要求縮尺率」という）が、既存の縮尺率、つまり地図データ保存部１０２に保存されている地図データが持つ縮尺率であるかどうかを調べる。このステップＳＴ２０２において、既存縮尺であることが判断されると、換言すれば、要求縮尺率の地図データが地図データ保存部１０２に存在することが判断されると、複数種類の地図データの中から１つが抜き出される（ステップＳＴ２０３）。すなわち、地図データ選択部１０３は、ステップＳＴ２０１で入力された要求縮尺率を持つ地図データを地図データ保存部１０２から選択し、加工処理部１０４を介して、描画用データとして外部に送る。
【００２５】
上記ステップＳＴ２０２において、既存縮尺でないことが判断されると、換言すれば、要求縮尺率の地図データが地図データ保存部１０２に存在しないことが判断されると、次いで、要求縮尺率が各パラメータの閾値に変換される（ステップＳＴ２０４）。すなわち、入力値変換部１０１は、要求縮尺率を距離および曲率の閾値に変換し、地図データ選択部１０３に送る。
【００２６】
次いで、階層グラフが作成済みであるかどうかが調べられる（ステップＳＴ２０５）。すなわち、地図データ選択部１０３は、階層グラフが既に存在するかどうかを調べる。階層グラフとは、中間的な縮尺率を持つ地図データを生成するために使用される。この階層グラフの詳細については後述する。
【００２７】
このステップＳＴ２０５において、階層グラフが作成済みでないことが判断されると、抜き出す地図データが１つ以上選択される（ステップＳＴ２０６）。すなわち、地図データ選択部１０３は、地図データ保存部１０２に保存されている地図データのうち、どの縮尺率の地図データを階層グラフの作成に用いるかを判断し、この地図データ保存部１０２から１種類以上の地図データを選択する。例えば、ステップＳＴ２０６において、地図データ選択部１０３は、要求縮尺率が１．５万分の１の中間的な縮尺率である場合、地図データ保存部１０２から、１万分の１の縮尺率の地図データと、２万分の１の縮尺率の地図データを選択するなど、縮尺率または地図描画装置内部の遷移状態に応じて柔軟に地図データを選択する。
【００２８】
次いで、地図データが抜き出される（ステップＳＴ２０７）。すなわち、地図データ選択部１０３は、ステップＳＴ２０６で選択された地図データを地図データ保存部１０２から抜き出し、加工処理部１０４に送る。
【００２９】
次いで、階層グラフが作成される（ステップＳＴ２０８）。すなわち、加工処理部１０４は、ステップＳＴ２０７で抜き出された地図データに基づき階層グラフを作成する。次いで、階層グラフが保存される（ステップＳＴ２０９）。すなわち、加工処理部１０４は、作成した階層グラフのデータをメモリ１０５に格納する。その後、シーケンスはステップＳＴ２１０に進む。
【００３０】
ステップＳＴ２１０においては、階層グラフの中から描画するノードが選択される。すなわち、加工処理部１０４は、ステップＳＴ２０４で求めた閾値に基づき、ステップＳＴ２０９で保存した階層グラフの中から描画する頂点を選択する。以上により、中間的な縮尺率の地図を描画するための地図データを作成する処理は終了する。
【００３１】
上記ステップＳＴ２０５において、階層グラフが作成済みであることが判断されると、地図データ選択部１０３は、階層グラフが既に保存済みであるので階層グラフを修正または作成しなおす必要が無いと判断した場合、既に作成されている階層グラフを再利用することが可能であるため、ステップＳＴ２０６からステップＳＴ２０９までの階層グラフを作成する処理はスキップされ、シーケンスはステップＳＴ２１０に進む。
【００３２】
例えば、１万分の１と２万分の１の縮尺率を持つ地図データが地図データ保存部１０２に存在し、１万分の１の地図から２万分の１の縮尺率に向けて徐々にズームアウトしていく場合、加工処理部１０４が階層グラフを作成するタイミングは、以下の通りである。１万分の１の縮尺率を持つ地図データを描画する際、１万分の１の縮尺率は、中間的な縮尺率ではないので、加工処理部１０４は、階層グラフを作成する必要はない。
【００３３】
しかしながら、１万分の１を超えた縮尺率、例えば１．０１万分の１の縮尺率で地図を描画する時点で、加工処理部１０４は、階層グラフを作成する必要がある。その後、縮尺率の変更を継続して、２万分の１の縮尺率に至るまで、加工処理部１０４は、階層グラフを作成する必要はない。つまり、例えば、１．３万分の１、１．５万分の１または１．９９万分の１などといった中間的な縮尺率を持つ地図データの作成において、加工処理部１０４は、１．０１万分の１の縮尺率を持つ地図データ描画時に作成した階層グラフを再利用して描画データを作成することができる。ズームインの際も同様である。つまり、加工処理部１０４は、ステップＳＴ２０６からステップＳＴ２０９までの処理を省略することができる。これにより、この地図描画装置は、利用者の要求に対して迅速に中間的な縮尺率を持つ地図を描画することができる。
【００３４】
また、ステップＳＴ２０４において、要求縮尺率を閾値に変換するという処理は、ステップＳＴ２０２において、要求縮尺率が地図データ保存部１０２に存在しない縮尺率であると判断された直後から、ステップＳＴ２１０において階層グラフの中から描画する頂点を選択する処理を実行するまでの間の任意のタイミングで行うことができる。
【００３５】
さらに、図２に示すフローチャートでは、地図データ保存部１０２に存在する地図データの縮尺率に合致する縮尺率を持つ地図データを描画する場合は階層グラフを作成しなかったが、この地図描画装置は、地図データ保存部１０２に存在する地図データの縮尺率に合致する縮尺率を持つ地図データを描画する場合であっても階層グラフを作成し、この階層グラフから描画頂点を抽出するように構成することもできる。
【００３６】
図３は、ステップＳＴ２０８からステップＳＴ２１０までの処理を説明するための図である。図３は、仮想的に作成した中間地図を用いて階層グラフを作成し、中間的な縮尺率を持つ地図データを作成する様子を表している。図３（Ａ）はステップＳＴ２０８における処理、図３（Ｂ）はステップＳＴ２０９における処理、および、図３（Ｃ）はステップＳＴ２１０における処理を説明するための図である。
【００３７】
まず、図３（Ａ）に示すように、加工処理部１０４は、地図データ選択部１０３で選択された２万分の１の広域地図と１万分の１の詳細地図との間に、中間的な地図を仮想的に定義する。定義する中間地図の数は、必要に応じて決めることができる。つまり、加工処理部１０４は、中間的な地図を必要に応じて複数個定義することができるし、必要ない場合は１つも定義しなくてもよい。図３（Ａ）では、加工処理部１０４は、中間地図を１つ定義している例を示している。また、中間地図の地図データは、交差点および座標が広域地図と一致する点を含む地図の特徴点となる頂点から抽出して作成することができる。
【００３８】
次に、図３（Ｂ）に示すように、加工処理部１０４は、広域地図、中間地図および詳細地図といった３種類の地図に基づき、階層グラフを作成する。この階層グラフでは、階層の高い頂点を辿らない限り、階層の低い頂点に到達できないことを示している。ただし、１つの頂点から他の頂点に至るエッジを辿った先に中間地図の頂点が存在しなかった場合は、その限りではない。また、仮想的な中間地図を１つも作成しない場合、加工処理部１０４は、広域地図と詳細地図の２つのレベルの地図から、階層グラフを作成する。また、加工処理部１０４は、図３（Ｃ）の処理を行う前に、具体的には、図３（Ａ）または図３（Ｂ）のいずれかにおいて、各エッジへの重み付けを行っておく。
【００３９】
次に、図３（Ｃ）に示すように、加工処理部１０４は、階層グラフの走査を行い、描画頂点を抽出する。すなわち、加工処理部１０４は、縮尺率によって一意に決まる閾値と、エッジ毎の重みを比較し、閾値以上の値を持つエッジを順に辿る。そして、加工処理部１０４は、この処理をエッジの始点から終点まで繰り返し、辿ったエッジの頂点を描画頂点として抽出する。
【００４０】
以上のように、この地図描画装置では、地図データ選択部１０３で選択された地図データから必要な頂点が適宜抽出されるため、縮尺率に応じて適切なデータ量で地図を描画することが可能である。例えば、この地図描画装置を用いて作成した１．５万分の１の中間的な縮尺率を持つ地図データの量は、１万分の１の縮尺率を持つ地図を縮小して作成された１．５万分の１の縮尺率を持つ地図のデータ量よりは少ないが、２万分の１の縮尺率を拡大して作成された地図のデータ量より多い。このように、この地図描画装置は、縮尺率に応じてデータ量を調節することが可能である。
【００４１】
以下、ステップＳＴ２０８とステップＳＴ２１０において実行される処理の詳細を、図４〜図１０を参照しながら、具体例を用いて説明する。
【００４２】
図４は、図２に示すフローチャートのステップＳＴ２０８において実行される、各リンクのエッジの値を計算する処理の流れを示すフローチャートである。この処理では、まず、広域地図および詳細地図が入力される（ステップＳＴ４０１）。すなわち、加工処理部１０４は、地図データ選択部１０３で選択された広域地図および詳細地図を入力する。
【００４３】
次いで、中間地図が作成される（ステップＳＴ４０２）。すなわち、加工処理部１０４は、ステップＳＴ４０１で入力した地図に基づき、中間地図を仮想的に作成する。次いで、広域地図、詳細地図および中間地図の各エッジの値が計算される（ステップＳＴ４０３）。すなわち、加工処理部１０４は、広域地図、中間地図および詳細地図といった３つの地図の各エッジの値を計算する。
【００４４】
図５は、図４に示すフローチャートのステップＳＴ４０３において、加工処理部１０４によって計算された広域地図、中間地図および詳細地図の各エッジの値を示す図である。図５に示す例では、頂点間距離をエッジの値としている。各頂点間の距離は、Ａ−Ｂ間：２、Ｂ−Ｃ間：３、Ｃ−Ｄ間：３、Ｄ−Ｅ間：２、Ｅ−Ｆ間：２、Ｆ−Ｇ間：１、Ｇ−Ｈ間：５、Ｈ−Ｉ間：６、Ｉ−Ｊ間：５、Ｊ−Ｋ間：３、Ｋ−Ｌ間：２、Ａ−Ｃ間：４、Ｃ−Ｅ間：４、Ｇ−Ｉ間：９、Ｉ−Ｊ間：５、Ｊ−Ｌ間：４、Ａ−Ｅ間：７、Ｅ−Ｇ間：３、Ｉ−Ｌ間：８である。
【００４５】
図６は、図２に示すフローチャートのステップＳＴ２０８において、加工処理部１０４が、詳細地図の各頂点に階層付けを行う処理（図３（Ａ）参照）の流れを示すフローチャートである。この処理では、頂点数だけのループが開始されると（ステップＳＴ６０１）、まず、詳細地図にのみ存在する頂点であるかどうかが調べられる（ステップＳＴ６０２）。すなわち、加工処理部１０４は、広域地図、中間地図および詳細地図の各頂点の座標を比較して、頂点の座標が、詳細地図にのみ存在する座標であるかどうかを調べる。
【００４６】
このステップＳＴ６０２において、詳細地図にのみ存在する頂点である、つまり、頂点座標が詳細地図にのみ存在する座標であることが判断されると、階層が低に決定される（ステップＳＴ６０３）。すなわち、加工処理部１０４は、その頂点の階層を「低」に設定する。一方、ステップＳＴ６０２において、詳細地図にのみ存在する頂点でない、つまり、頂点座標と同じ座標を持つ頂点が詳細地図以外にも存在することが判断されると、次いで、中間地図にのみ存在する頂点であるかどうかが調べられる（ステップＳＴ６０４）。すなわち、加工処理部１０４は、広域地図と中間地図の頂点座標を比較し、中間地図にのみに存在する頂点座標かどうかを調べる。
【００４７】
このステップＳＴ６０４において、中間地図にのみ存在する頂点座標であることが判断されると、階層が中に設定される（ステップＳＴ６０５）。すなわち、加工処理部１０４は、該当する詳細地図の頂点の階層を「中」に設定する。一方、ステップＳＴ６０４において、中間地図にのみ存在する頂点座標でない、つまり、広域地図にも存在する頂点座標であることが判断されると、階層が高に設定される（ステップＳＴ６０６）。すなわち、加工処理部１０４は、該当する詳細地図の頂点の階層を「高」に設定する。
【００４８】
次いで、頂点数だけのループが終了したかどうかが調べられ（ステップＳＴ６０７）、終了していない場合は、シーケンスはステップＳＴ６０２に戻り、上述した処理が繰り返される。そして、ステップＳＴ６０７において、頂点数だけのループが終了したことが判断されると、処理は終了する。これにより、全ての頂点に対し、「高」、「中」または「低」の重みが付される。
【００４９】
次に、加工処理部１０４が、図３（Ｂ）に示すような階層グラフを作成する処理の詳細を説明する。以下において、Ａ−Ｂ−Ｃ−Ｄ−Ｅ−Ｆ−Ｇ−Ｈ−Ｉ−Ｊ−Ｋ−Ｌを元の頂点の並びと呼ぶ。詳細地図のスケールが決まると、詳細地図を構成する頂点を元に階層グラフが作成される。階層グラフは、複数の頂点をエッジで繋ぐことにより作成される。この場合、繋がれる対象となる頂点は、詳細地図の頂点の並びにおいて、自身より後ろに存在する頂点とする。複数の頂点をエッジで繋ぐ処理を、図７〜図９に示すフローチャートを参照しながら説明する。エッジの繋ぎ方は自身の階層によって異なる。以下においては、自身の階層が「高」の場合、「中」の場合および「低」の場合に分けて説明する。
【００５０】
図７は、自身の階層が「高」の場合の階層グラフを作成する処理を示すフローチャートである。この処理では、終点になるまでのループが開始されると（ステップＳＴ７０１）、まず、隣の頂点とエッジで繋がれる（ステップＳＴ７０２）。すなわち、加工処理部１０４は、詳細地図の元の頂点の並びで、後ろ隣に存在する頂点へ向かうエッジを追加する。
【００５１】
次いで、隣の頂点の階層が高であるかどうかが調べられる（ステップＳＴ７０３）。すなわち、加工処理部１０４は、図６のフローチャートに示す処理によって割り振った後ろ隣の頂点の階層が「高」であるかどうかを調べる。このステップＳＴ７０３において、頂点の階層が「高」でないことが判断されると、頂点数だけのループが終了したかどうかが調べられ（ステップＳ７０４）、終了していない場合は、シーケンスはステップＳＴ７０２に戻り、上述した処理が繰り返される。そして、ステップＳＴ７０４において、頂点数だけのループが終了したことが判断されると、処理は終了する。
【００５２】
一方、ステップＳＴ７０３において、隣の頂点の階層が「高」であることが判断されると、処理は終了する。以上の処理により、後ろ隣の頂点が「高」になるまで、階層を調べる対象の頂点を後ろにずらしながら探索が繰り返され、隣の頂点の階層が「高」であることが判断されると、その頂点へのエッジが１本追加されて、処理は終了する。
【００５３】
図８は、自身の階層が「中」の場合の階層グラフを作成する処理を示すフローチャートである。この処理では、終点になるまでのループが開始されると（ステップＳＴ８０１）、まず、隣の階層が調べられる（ステップＳＴ８０２）。すなわち、加工処理部１０４は、詳細地図の元の頂点の並びで、後ろ隣に存在する頂点の階層が「高」、「中」または「低」のいずれであるかを調べる。
【００５４】
このステップＳＴ８０２において、後ろ隣に存在する頂点の階層が「高」であることが判断されると、隣の頂点とエッジで繋がれる（ステップＳＴ８０３）。すなわち、加工処理部１０４は、詳細地図の元の頂点の並びで、後ろ隣に存在する頂点へ向かうエッジを追加する。その後、処理は終了する。
【００５５】
上記ステップＳＴ８０２において、後ろ隣に存在する頂点の階層が「中」であることが判断されると、次いで、階層が中の頂点へ向かうエッジが存在するかどうかが調べられる（ステップＳＴ８０４）。このステップＳＴ８０４において、階層が中の頂点へ向かうエッジが存在しないことが判断されると、隣の頂点とエッジで繋がれる（ステップＳＴ８０５）。すなわち、加工処理部１０４は、詳細地図の元の頂点の並びで、後ろ隣に存在する頂点へ向かうエッジを追加する。その後、シーケンスはステップＳＴ８０８に進む。上記ステップＳＴ８０４において、階層が中の頂点へ向かうエッジが存在することが判断された場合も、シーケンスはステップＳＴ８０８に進む。
【００５６】
上記ステップＳＴ８０２において、後ろ隣に存在する頂点の階層が「低」であることが判断されると、次いで、階層が中の頂点へ繋がるエッジが存在するかどうかが調べられる（ステップＳＴ８０６）。このステップＳＴ８０６において、階層が中の頂点へ向かうエッジが存在しないことが判断されると、隣の頂点とエッジで繋がれる（ステップＳＴ８０７）。すなわち、加工処理部１０４は、詳細地図の元の頂点の並びで、後ろ隣に存在する頂点へ向かうエッジを追加する。その後、シーケンスはステップＳＴ８０８に進む。上記ステップＳＴ８０４において、階層が中の頂点へ向かうエッジが存在することが判断された場合も、シーケンスはステップＳＴ８０８に進む。
【００５７】
ステップＳＴ８０８においては、頂点数だけのループが終了したか否かが調べられ、終了していない場合は、シーケンスはステップＳＴ８０２に戻り、上述した処理が繰り返される。すなわち、後ろ隣の頂点が「高」になるまで、階層を調べる対象の頂点を後ろにずらして探索が繰り返される。そして、ステップＳＴ８０８において、頂点数だけのループが終了したことが判断されると、処理は終了する。以上の処理により、後ろ隣の頂点の階層が「高」である場合は、その頂点へ向かうエッジが追加され、後ろ隣の頂点の階層が「中」または「低」である場合は、階層が「中」または「低」の頂点へ向かうエッジが１つも存在しない場合にのみエッジが追加され、後ろ隣の頂点の階層が「高」になるまで、上述した処理が繰り返される。
【００５８】
図９は、自身の階層が「低」の場合の階層グラフを作成する処理を示すフローチャートである。この処理では、終点になるまでのループが開始されると（ステップＳＴ９０１）、まず、真隣の階層が低であるかどうかが調べられる（ステップＳＴ９０２）。すなわち、加工処理部１０４は、詳細地図の元の頂点の並びで、真隣に存在する頂点の階層が「低」であるか否かを調べる。このステップＳＴ９０２において、真隣の階層が低でないことが判断されると、シーケンスはステップＳＴ９０４に進む。
【００５９】
一方、ステップＳＴ９０２において、真隣の階層が低であることが判断されると、次いで、階層が低の頂点へ向かうエッジが存在するかどうかが調べられる（ステップＳＴ９０３）。このステップＳＴ９０３において、階層が低の頂点へ向かうエッジが存在しないことが判断されると、真隣の頂点とエッジで繋がれる（ステップＳＴ９０４）。すなわち、加工処理部１０４は、詳細地図の元の頂点の並びで、真隣に存在する頂点へ向かうエッジを追加する。その後、シーケンスはステップＳＴ９０９に進む。上記ステップＳＴ９０３において、階層が低の頂点へ向かうエッジが存在することが判断された場合も、シーケンスはステップＳＴ９０９に進む。
【００６０】
また、上記ステップＳＴ９０１とステップＳＴ９０９との間のループにおいて、隣の階層が中または高であるかどうかが調べられる（ステップＳＴ９０５）。すなわち、加工処理部１０４は、詳細地図の元の頂点の並びで、隣に存在する頂点の階層が「中」または「高」であるか否かを調べる。このステップＳＴ９０５において、隣の階層が中または高でないことが判断されると、シーケンスはステップＳＴ９０９に進む。
【００６１】
一方、ステップＳＴ９０５において、隣の階層が中または高であることが判断されると、次いで、階層が中の頂点へ向かうエッジが存在するかどうかが調べられる（ステップＳＴ９０６）。このステップＳＴ９０６において、階層が中の頂点へ向かうエッジが存在することが判断されると、処理は終了する。一方、ステップＳＴ９０６において、階層が中の頂点へ向かうエッジが存在しないことが判断されると、次いで、階層が高の頂点へ向かうエッジが存在するかどうかが調べられる（ステップＳＴ９０７）。このステップＳＴ９０７において、階層が高の頂点へ向かうエッジが存在することが判断されると、処理は終了する。一方、ステップＳＴ９０７において、階層が高の頂点へ向かうエッジが存在しないことが判断されると、隣の頂点とエッジで繋がれる（ステップＳＴ９０８）。すなわち、加工処理部１０４は、詳細地図の元の頂点の並びで、後ろ隣に存在する頂点へ向かうエッジを追加する。その後、シーケンスはステップＳＴ９０９に進む。
【００６２】
ステップＳＴ９０９においては、頂点数だけのループが終了したか否かが調べられ、終了していない場合は、シーケンスはステップＳＴ９０２およびステップＳＴ９０５に戻り、上述した処理が繰り返される。そして、ステップＳＴ９０９において、頂点数だけのループが終了したことが判断されると、処理は終了する。以上の処理により、まず、自身の後ろ隣の階層が「低」の場合のみ、階層が「低」の頂点へのエッジが追加される。階層が「中」または「高」の頂点へ向かうエッジが追加されるまで、ステップＳＴ９０２およびステップＳＴ９０５とステップＳＴ９０９との間のループが繰り返され、自身の階層よりも大きい階層を持つ頂点へ向かうエッジが１本追加されると、処理は終了する。
【００６３】
上述した図７〜図９に示した処理により、エッジを追加して頂点を繋ぐことで、階層グループの全てのパスは、高位の階層を持つすべての点および頂点を通るようになる。つまり、階層グラフ中のどのパスを選んだとしても、高位の頂点を漏れなく抽出することができるようになる。
【００６４】
以上の処理により、階層グラフが作成される。図１０は、加工処理部１０４で作成された階層グラフを示す図である。加工処理部１０４は、各エッジに、図５に示したエッジの値を割り振り、階層グラフを表すデータとしてメモリ１０５に格納する。
【００６５】
図１１は、図３（Ｃ）に示すように、加工処理部１０４が作成した階層グラフを走査して描画する頂点を抽出する処理の流れを示すフローチャートである。なお、図１１のフローチャートに示す処理を実行する前に、図２に示すフローチャートのステップＳＴ２０４において、入力値変換部１０１は、要求縮尺率をパラメータとする評価関数によって、閾値を決定しておかなければならない。
【００６６】
この処理では、まず、低の階層に繋がるエッジが存在するかどうかが調べられる（ステップＳＴ１１０１）。すなわち、加工処理部１０４は、頂点から「低」の階層を持つ頂点へ向かうエッジが存在するかどうかを調べる。このステップＳＴ１１０１において、低の階層に繋がるエッジが存在しない、つまり頂点から「低」の階層を持つ頂点へ向かうエッジが存在しないことが判断されると、シーケンスはステップＳＴ１１０４に進む。
【００６７】
一方、ステップＳＴ１１０１において、低の階層に繋がるエッジが存在する、つまり頂点から「低」の階層を持つ頂点へ向かうエッジが存在することが判断されると、次いで、エッジの値が閾値以上であるかどうかが調べられる（ステップＳＴ１１０２）。すなわち、加工処理部１０４は、エッジの値が閾値以上であるかどうかを調べる。このステップＳＴ１１０２において、エッジの値が閾値以上でないことが判断されると、シーケンスはステップＳＴ１１０４に進む。一方、ステップＳＴ１１０２において、エッジの値が閾値以上であることが判断されると、階層が低のエッジに繋がる頂点が描画頂点として選択される（ステップＳＴ１１０３）。すなわち、加工処理部１０４は、閾値以上であるエッジに繋がっている頂点を描画頂点として選択する。その後、処理は終了する。
【００６８】
ステップＳＴ１１０４においては、中の階層に繋がるエッジが存在するかどうかが調べられる。すなわち、加工処理部１０４は、頂点から「中」の階層を持つ頂点へ向かうエッジが存在するかどうかを調べる。このステップＳＴ１１０４において、中の階層に繋がるエッジが存在しない、つまり頂点から「中」の階層を持つ頂点へ向かうエッジが存在しないことが判断されると、シーケンスはステップＳＴ１１０７に進む。
【００６９】
一方、ステップＳＴ１１０４において、中の階層に繋がるエッジが存在する、つまり頂点から「中」の階層を持つ頂点へ向かうエッジが存在することが判断されると、次いで、エッジの値が閾値以上であるかどうかが調べられる（ステップＳＴ１１０５）。すなわち、加工処理部１０４は、エッジの値が閾値以上であるかどうかを調べる。このステップＳＴ１１０５において、エッジの値が閾値以上でないことが判断されると、シーケンスはステップＳＴ１１０７に進む。一方、ステップＳＴ１１０５において、エッジの値が閾値以上であることが判断されると、階層が中のエッジに繋がる頂点が描画頂点として選択される（ステップＳＴ１１０６）。すなわち、加工処理部１０４は、閾値以上であるエッジに繋がっている頂点を描画頂点として選択する。その後、処理は終了する。
【００７０】
ステップＳＴ１１０７においては、階層が高のエッジに繋がる頂点が描画頂点として選択される。すなわち、加工処理部１０４は、「高」の階層を持つ頂点を描画頂点として選択する。なお、図１１に示すフローチャートでは記載を省略しているが、加工処理部１０４は、ステップＳＴ１１０１からステップＳＴ１１０７の処理を、始点Ａから終点Ｌに到達するまで繰り返す。
【００７１】
図１２は、加工処理部１０４が作成した中間的な縮尺率を持つ地図データの例を示す図である。図１２では、要求縮尺率をパラメータの閾値に変換した値を「４」としている。図１２（ａ）は、階層グラフ上での描画頂点列であり、図１２（ｂ）は、抽出した描画頂点を用いて描画された中間的な縮尺率を持つ地図を示す図である。加工処理部１０４は、エッジが持つ値と閾値の大小関係を比較して描画頂点を抽出し、閾値「４」以上のエッジに繋がる頂点のみを描画頂点として抽出する。
【００７２】
上述した例では、１リンク内の頂点の並びから中間的な縮尺率を持つ頂点を抽出する流れを示したが、一般的には、道路は複数のリンクで構成されており、リンクの集結により交差点などを形成することが可能である。どの道がどの道とつながっているかという情報を得るために、加工処理部１０４は、地図データ選択部１０３で選択された地図データの各リンクを関連付けることが必要となる。リンク間を関連付けるために、上述した方法と同様に、頂点に重みを付けたグラフで表現することが可能である。
【００７３】
また、上述した実施の形態１に係る地図描画装置では、階層グラフの走査に用いる閾値には、距離をパラメータとして用いたが、加工処理部１０４は、曲率、密度、位置情報、１リンク内に存在する点の数などといった、頂点の重み付けに重要と思われる情報を用いることもできる。頂点の密度は、別々のリンクの頂点間の距離を調査するときに、特に有効である。
【００７４】
なお、上述した実施の形態１に係る地図描画装置では、図２に示すフローチャートのステップＳＴ２０６において、地図データ選択部１０３は、地図データを選択する際に、地図データ保存部１０２に保存されている地図データの中から所望の縮尺率に最も近い縮尺率の地図データを広域地図および詳細地図のうちから１つずつ合計２つを選んだ。しかしながら、このステップＳＴ２０６においては、地図データ選択部１０３は、地図データ保存部１０２に保存されている地図データを１つ以上選べばよく、その数は任意である。１種類の地図データのみ用いて階層グラフを作成する場合、加工処理部１０４は、図３（Ａ）に示す広域地図も仮想的に生成することになる。
【００７５】
また、図２に示すフローチャートのステップＳＴ２０６において、地図データ選択部１０３は、選択する地図データの縮尺率を、前後の２つの縮尺率のみに限定せず、それ以外の縮尺率の地図データを用いることもできる。例えば、地図データ保存部１０２に保存されている地図データの縮尺率が１万分の１、２万分の１、４万分の１、８万分の１および１６万分の１であった場合に、１．５万分の１の中間的な縮尺率を持つ仮想的な地図データを作成するために使用する地図データは、広域地図の縮尺率で最近接の２万分の１の縮尺率を持つ地図データと、詳細地図の縮尺率で最近接の１万分の１の縮尺率を持つ地図データに限定されない。
【００７６】
つまり、このステップＳＴ２０６において、地図データ選択部１０３は、１．５万分の１の地図データを作成する際に、４万分の１の縮尺率を持つ地図データと１６万分の１の縮尺率を持つ地図データとを選択することもできる。すなわち、ステップＳＴ２０６においては、地図データ選択部１０３は、地図データ保存部１０２に保存されている地図データの中から、独立した１種類以上の地図データを選択するという条件を満たすように地図データを選択する。ただし、地図描画装置内で同様の遷移が起こった際の中間的な縮尺率を持つ地図描画には、同じ縮尺率の地図データが選択され、描画する地図データも同様のものとする。例えば、利用者が１万分の１から１６万分の１の縮尺率を持つ地図を描画することを要求している場合、実施の形態１に係る地図描画装置は、利用者が直前にどのような操作を行っているかにかかわらず、常に同一の中間的な縮尺率を持つ地図を描画する。
【００７７】
また、例えば、画面に１万分の１の縮尺率の地図を描画しているときに、利用者が１６万分の１の縮尺率を描画したいという急激な縮尺率変更を要求した場合の処理を以下に説明する。１万分の１から２万分の１の縮尺率を持つ地図へズームアウトする場合に描画される地図と、１万分の１から１６万分の１の縮尺率を持つ地図へズームアウトする場合に描画される地図において、各々の場合に地図描画装置が描画する１．５万分の１の縮尺率を持つ地図は、異なった地図になっていてもよい。地図描画装置は、急激な縮尺変更時も、１万分の１、１．５万分の１、２万分の１、２．５万分の１・・・等のように、順に縮尺率変更を行う。１．５万分の１と２．５万分の１の中間的な縮尺率を持つ地図データを描画する際、地図描画装置は、例えば１万分の１と２万分の１、２万分の１と５万分の１の縮尺率を持つ地図データで作成した階層グラフを各々で作成するよりも、１万分の１と１６万分の１の縮尺率を持つ地図データを用いて階層グラフを作成する方が、中間的な縮尺率を持つ地図作成にかかる時間を短縮できる。地図描画装置は、階層グラフ作成回数を減らすことにより、利用者が所望する縮尺率までの応答時間を短縮できる。
【００７８】
このように、地図データ選択部１０３は、階層グラフを作成する際に、前後の２種類の縮尺率以外の地図データを選択することもできる。地図データ選択部１０３は、場合によっては数段広域または数段詳細の地図データを使用できる。この方法よって、加工処理部１０４が作成する階層グラフの数が減るため、高速描画が可能となり、利用者の要求に迅速に対応できる。
【００７９】
以上説明したように、この発明の実施の形態１に係る地図描画装置は、中間的な縮尺率を持つ地図データを作成することにより、地図データ選択部１０３で選択された地図データの断続的な縮尺率間を補完することができるので、徐々に縮尺率変更を行う際の急激な画面の切り替わりを防ぐことができ、不自然さを解消できる。
【００８０】
また、実施の形態１に係る地図描画装置は、縮尺率に応じてデータ量を調節できるため、どの縮尺率でも描画に要する時間を一定時間以内に抑えることができる。つまり、描画処理負荷を削減できる。
【００８１】
また、実施の形態１に係る地図描画装置は、一定縮尺率の範囲内であれば、一度作成した階層グラフを再利用することにより、階層グラフ作成に要する時間を省略することができ、描画に要する時間を短縮できるため、利用者への情報供給を迅速に行うことができる。
【００８２】
また、実施の形態１に係る地図描画装置は、所望の縮尺率に応じた最適なデータ量で地図を描画できるため、詳細地図を縮小して中間的な地図を描画する場合と比較して、描画するデータ量が減り、描画時間を短縮できる。
【００８３】
さらに、実施の形態１に係る地図描画装置は、地図の広域的な特徴点と局所的に見た時の特徴点を考慮して描画頂点を抽出しているため、地図形状を維持したまま描画頂点数を削減することができる。
【産業上の利用可能性】
【００８４】
この発明は、ユーザが所望する縮尺率で地図を高速に表示するナビゲーションシステムに利用できる。
【図１】
2011010340.tif 000003
【図２】
2011010340.tif 000004
【図３】
2011010340.tif 000005
【図４】
2011010340.tif 000006
【図５】
2011010340.tif 000007
【図６】
2011010340.tif 000008
【図７】
2011010340.tif 000009
【図８】
2011010340.tif 000010
【図９】
2011010340.tif 000011
【図１０】
2011010340.tif 000012
【図１１】
2011010340.tif 000013
【図１２】
2011010340.tif 000014
【国際調査報告】
2011010340.tif 000015
2011010340.tif 000016
2011010340.tif 000017