(57)【要約】表示切り替え前後の地図データを互いに同一の位相構造を有するポリゴンに変換する地図ポリゴン化部５と、このポリゴンを表示切り替え前後の地図間で対応する点の接続関係が等しい三角形に三角形分割する三角形分割部６と、地図表示をモーフィングさせて切り替えるにあたり、表示切り替え前後の各地図と位相構造が等しい中間地図の地図データを生成するモーフィング部７とを備える。
2009104218.tif 000002
【特許請求の範囲】
【請求項１】
表示切り替え前後の地図データを互いに同一の位相構造を有するポリゴンに変換するポリゴン化部と、
前記ポリゴン化部で得られたポリゴンにおいて、表示切り替え前後の地図間で対応する点の接続関係が等しい三角形分割を求める三角形分割部と、
地図表示をモーフィングさせて切り替えるにあたり、前記三角形分割部による三角形分割の結果から特定されるポリゴン内の点情報に基づいて、前記表示切り替え前後の各地図と位相構造が等しい中間地図の地図データを生成するモーフィング部とを備えた地図表示装置。
【請求項２】
ポリゴン化部は、表示切り替え前後の地図間で対応する点を探索し、前記地図間の一方にのみ存在する点があると、この点に対応する点を他方の地図上に追加することを特徴とする請求項１記載の地図表示装置。
【請求項３】
ポリゴン化部は、地図全体を囲む同一のバウンディングボックスを各地図データに設定することにより、表示切り替え前後の地図データを前記バウンディングボックスの外形枠で規定されるポリゴンに変換することを特徴とする請求項１記載の地図表示装置。
【請求項４】
モーフィング部は、三角形分割部による三角形分割の結果から特定されるポリゴン内の各点を周辺の点の凸結合で表現し、前記凸結合で表現した点の線形補間によって中間地図の地図データを生成することを特徴とする請求項１記載の地図表示装置。
【請求項５】
モーフィング部は、中間地図において表示切り替え前後の地図間の一方にのみ存在する点を透過率の変化で表現することを特徴とする請求項１記載の地図表示装置。
【請求項６】
モーフィング部は、表示切り替え前後の地図間の一方にのみ存在する点を他方の地図のポリゴン内の三角形にマッピングし、マッピングにより特定された前記点の相対位置における表示を変化させた中間地図の地図データを生成することを特徴とする請求項１記載の地図表示装置。
【請求項７】
モーフィング部は、三角形分割部で得られた表示切り替え前後の地図間で対応する三角形の内部をテクスチャとし、透過率を変化させた前記テクスチャのブレンディングを行いながら中間地図の地図データを生成することを特徴とする請求項１記載の地図表示装置。
【請求項８】
ポリゴン化部は、対応する点を予め指定した各地図データを互いに同一の位相構造を有するポリゴンに変換することを特徴とする請求項１記載の地図表示装置。
【請求項９】
ポリゴン化部は、縮尺の異なる地図データを互いに同一の位相構造を有するポリゴンに変換し、
三角形分割部は、前記ポリゴン化部で得られたポリゴンにおいて、前記縮尺の異なる地図間で対応する点の接続関係が等しい三角形分割を求め、
モーフィング部は、前記縮尺の異なる地図をモーフィングさせて切り替えるにあたり、前記三角形分割部による三角形分割の結果から特定されるポリゴン内の点情報に基づいて、中間地図の地図データを生成することを特徴とする請求項１記載の地図表示装置。
【請求項１０】
表示切り替え前後の地図データを互いに同一の位相構造を有するポリゴンに変換するポリゴン化部と、前記ポリゴン化部で得られたポリゴンにおいて、表示切り替え前後の地図間で対応する点の接続関係が等しい三角形分割を求める三角形分割部と、前記三角形分割部で得られた三角形分割の結果を対応する地図データに関連付けて記憶する記憶部とを有する前処理部と、
地図データを表示する表示部と、前記表示部の地図表示をモーフィングさせて切り替えるにあたり、前記記憶部から読み出した三角形分割の結果から特定されるポリゴン内の点情報に基づいて、前記表示切り替え前後の各地図と位相構造が等しい中間地図の地図データを生成するモーフィング部とを有する後処理部とを備えた地図表示装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、カーナビゲーションシステム等の地図表示に利用される地図表示装置に関するものである。
【背景技術】
【０００２】
カーナビゲーションシステム等において、表示する地図の縮尺を変更するスケールチェンジは、必須の機能となっている。スケールチェンジ機能を実現した従来の地図表示装置としては、縮尺の異なる複数の地図データを保持し、地図データの縮尺毎に地図レベルを段階的に設定しておくことにより、切り替え後の縮尺に対応する地図レベルの地図データを選択して表示するものがある。【０００３】
しかしながら、このような地図表示装置では、地図レベルの切り替えによって地図の表示縮尺が突然変更される。このため、ユーザが、地図レベル切り替え前の縮尺に対応する地図上で認識していた道路や建物を地図レベル切り替え後の地図上で見失う場合がある。【０００４】
上述のような不具合を解消するには、異なる地図データを切り替え表示するにあたり、切り替え前の地図データから切り替え後の地図データへ表示内容を滑らかに変化させていくことが考えられる。このように、あるオブジェクトから他のオブジェクトへオブジェクト内容を滑らかに変化させていくことをモーフィングと呼ぶ。【０００５】
モーフィングは、コンピュータグラフィックスの分野で広く利用されている。例えば、切り替え対象となる２つのポリゴン間で対応点を求め、一方のポリゴンを他方のポリゴンへ切り替える際に対応点間を線形補間することでモーフィングを実現している。なお、線形補間によるモーフィングでは、下記のような不具合が発生する場合がある。【０００６】
（１）自己交差
図１１に示すように、五角形オブジェクトであるポリゴン（ａ）から中間オブジェクト（ｂ）を介して五角形オブジェクトであるポリゴン（ｃ）へモーフィングする場合を考える。この場合、ポリゴン（ａ）及びポリゴン（ｃ）の間における対応点の線形補間の結果によっては、中間オブジェクト（ｂ）において破線で囲んだ部分ように輪郭線の自己交差が生じることがある。このような自己交差は、地図間のモーフィングによる切り替えにおいて不自然な変化を表すこととなり、回避する必要がある。【０００７】
（２）退化
図１２に示すように、複数の三角形の組み合わせからなる四角形オブジェクトであるポリゴン（ａ）から中間オブジェクト（ｂ）を介して四角形オブジェクトであるポリゴン（ｃ）へモーフィングする場合を考える。この場合、ポリゴン（ａ）及びポリゴン（ｃ）の間における対応点の線形補間の結果によっては、中間オブジェクト（ｂ）において破線で囲んだ部分ように、ポリゴン（ａ）内の三角形の３つの頂点が同一直線上に並んだ退化が生じることがある。このような退化は、本来存在するオブジェクトを消失することになるため、回避する必要がある。【０００８】
ポリゴンモデルのモーフィングで自己交差や退化を回避する従来の技術としては、モーフィング対象の２つのポリゴンに対する対応点の接続関係が等しい三角形分割を求め、これを利用してモーフィングする手法がある（非特許文献１参照）。【０００９】
図１３は、ポリゴンの三角形分割を説明するための図である。図１３において、黒塗りの三角形記号、四角形記号、丸形記号、白抜きの三角形記号、四角形記号、丸形記号は、ポリゴンを三角形分割して得られた三角形の頂点を示している。また、ポリゴン（ａ）及びポリゴン（ｂ）において同じ記号で表した点は、ポリゴン（ａ）からポリゴン（ｂ）へモーフィングする際の上記ポリゴン間の対応点である。【００１０】
図１３に示す例は、ポリゴン（ａ）及びポリゴン（ｂ）において、対応点が等しい接続関係で表された三角形分割が得られた場合を示している。これら対応点の接続関係が等しい三角形分割を利用して、各頂点を辺で結ばれた周りの点の凸結合で表現する。ポリゴン（ａ）からポリゴン（ｂ）へ変化させるにあたり、この凸結合で表現した頂点を線形補間することで、自己交差や退化のないモーフィングを実現することができる。【００１１】
なお、図１４は、ポリゴンに対応する対応点の接続関係が等しい三角形分割が得られない場合を示す図である。図１４における各記号は、図１３と同様にポリゴンを三角形分割して得られた三角形の頂点を示している。また、ポリゴン（ａ）及びポリゴン（ｂ）において同じ記号で表した点は、ポリゴン（ａ）からポリゴン（ｂ）へモーフィングする際の対応点である。図１４に示すように、対応点の接続関係が等しい三角形が得られないと、モーフィングの際に対応点間を無理に結ぶ演算を施しても三角形同士が重なり合ったり、三角形にならない場合がある。【００１２】
一方、地図表示の切り替えにおけるモーフィング技術としては、例えば非特許文献２に開示されるものがある。非特許文献２では、地図表示の切り替えにおいて地図上のオブジェクトを構成するポリライン同士をモーフィングする。【００１３】
【非特許文献１】C. Gotsman, V. Surazhsky, “Guaranteed intersection-free polygon morphing”, Computers & Graphics, 25(1), pages.67-75,2001．
【００１４】
【非特許文献２】D. Merrick, M. Nollenburg, A. Wolffand, M. Benkert, “Morphing polygonal lines: A step towards continuous generalization”, Proc. 15th Annu. Geograph. Inform. Sci. Research Conf. UK(GISRUK ’07), pages.390-399, 2007.
【００１５】
しかしながら、実際の地図では、ポリラインで表現される地形等の輪郭線の他、建物や道路を含む全ての描画オブジェクトを考慮してモーフィングする必要がある。このため、非特許文献２に記載されたモーフィング処理は、実用的な地図表示の切り替えに適用できない。【００１６】
また、地図表示のモーフィングによる切り替えを実現するため、対応点間の線形補間を利用することも考えられる。しかしながら、図１５に示すように、縮尺の小さい詳細地図（ａ）から縮尺の大きい広域地図（ｃ）へモーフィングするにあたり、上述したポリゴンと同様に、中間地図（ｂ）上の道路と建物、道路同士等の描画オブジェクトにおいても、自己交差が発生する。モーフィング途中の中間地図（ｂ）における自己交差は、地図の表示切り替えにおいて不自然な変化を与える。【００１７】
さらに、対応点の線形補間を利用した地図表示のモーフィングによる切り替えにおいて、非特許文献１に開示される技術を適用することも考えられる。しかしながら、非特許文献１は、分割された三角形の描画オブジェクトが全て連結されていることが前提であり、地図データのように道路や建物等の描画オブジェクトが点在している場合には、そのまま適用することができない。【００１８】
この発明は、上記のような課題を解決するためになされたもので、モーフィングを適用して視認性を落とさずに地図表示を切り替えることができる地図表示装置を得ることを目的とする。
【発明の開示】
【００１９】
この発明に係る地図表示装置は、表示切り替え前後の地図データを互いに同一の位相構造を有するポリゴンに変換するポリゴン化部と、ポリゴン化部で得られたポリゴンにおいて、表示切り替え前後の地図間で対応する点の接続関係が等しい三角形分割を求める三角形分割部と、地図表示をモーフィングさせて切り替えるにあたり、三角形分割部による三角形分割の結果から特定されるポリゴン内の点情報に基づいて、表示切り替え前後の各地図と位相構造が等しい中間地図の地図データを生成するモーフィング部とを備えるものである。
【００２０】
この発明によれば、表示切り替え前後の各地図と位相構造が等しい中間地図の地図データによりモーフィングが行われるので、視認性を落とさずに地図表示を切り替えることができるという効果がある。
【図面の簡単な説明】
【００２１】
【図１】この発明の実施の形態１による地図表示装置の構成を示すブロック図である。
【図２】図１中の地図表示装置による地図表示の切り替え処理の流れを示すフローチャートである。
【図３】２つの地図Ａ，Ｂ間のマッチング処理を説明するための図である。
【図４】図３中の地図Ａ，Ｂ間でマッチングできなかった点に対応する点を追加する処理を説明するための図である。
【図５】図４中の地図Ａ，Ｂをポリゴン化する処理を説明するための図である。
【図６】図５中の地図Ａ，Ｂを含むポリゴンを対応点の接続関係が等しい三角形に分割した結果を示す図である。
【図７】図５中の地図Ａを含むポリゴン内の点や辺を多角形の退化によるものとみなす場合を説明するための図である。
【図８】対応点のみの三角形分割を説明するための図である。
【図９】対応がとれなかった点のマッピングを説明するための図である。
【図１０】この発明の実施の形態２による地図表示装置の構成を示す図である。
【図１１】自己交差の例を示す図である。
【図１２】退化の例を示す図である。
【図１３】ポリゴンの三角形分割を説明するための図である。
【図１４】ポリゴンに対応する対応点の接続関係が等しい三角形分割が得られない場合を示す図である。
【図１５】地図表示のモーフィングにおける自己交差を説明するための図である。
【発明を実施するための最良の形態】
【００２２】
以下、この発明をより詳細に説明するために、この発明を実施するための最良の形態について、添付の図面に従って説明する。
実施の形態１．
図１は、この発明の実施の形態１による地図表示装置の構成を示すブロック図である。図１において、実施の形態１による地図表示装置１は、入力部２、制御部３、表示部４、地図ポリゴン化部５、三角形分割部６、モーフィング部７及び地図データベース（ＤＢ）部８を備える。入力部２は、ユーザからの情報入力を受け付ける構成要素であり、タッチパネルデバイスやポインティングデバイス、キーボード等のデータ入力用ハードウエア及びその制御ソフトウエアから構成される。【００２３】
制御部３は、地図ポリゴン化部５、三角形分割部６及びモーフィング部７の動作を制御する。表示部４は、地図データ等を表示する構成要素であり、様々なタイプのディスプレイ装置で実現することができる。地図ポリゴン化部５は、地図データをポリゴン化する構成要素である。例えば、地図データで表される地図全体を所定の形状のバウンディングボックスで取り囲むことにより、バウンディングボックスの外形で規定されるポリゴンを生成する。このポリゴンは、バウンディングボックスで外形が規定され、地図上の建物や道路を表す描画オブジェクトを規定する多角形が内部に包含されている。【００２４】
三角形分割部６は、地図ポリゴン化部５で生成された切り替え前後の地図に対応する各ポリゴンにおいて、ポリゴン間における対応点の接続関係が等しい三角形分割を求める。モーフィング部７は、三角形分割部６で求められた三角形データを用いて、切り替え前の地図から切り替え後の地図へ変化する途中の描画オブジェクトからなる中間地図を生成し、地図表示をモーフィングで切り替える。地図ＤＢ部８は、複数の縮尺の地図データを保持するデータベースであり、例えば縮尺毎に設定した地図レベルに関連付けて対応する縮尺の地図データが管理される。【００２５】
なお、入力部２、制御部３、表示部４、地図ポリゴン化部５、三角形分割部６、モーフィング部７及び地図ＤＢ部８は、例えば本発明の趣旨に従う地図表示処理用プログラムをコンピュータに読み込ませてその動作を制御することにより、このコンピュータ上でソフトウエアとハードウエアが協働した具体的な手段として実現することができる。【００２６】
次に動作について説明する。
図２は、図１中の地図表示装置による地図表示の切り替え処理の流れを示すフローチャートであり、この図に沿って地図表示の切り替えの詳細を説明する。以降では、縮尺のみが異なる２つの地図Ａ，Ｂの表示をモーフィングで切り替える場合を例に挙げる。なお、３以上の地図間でモーフィングによる切り替えを行う場合は、切り替え順に２つの地図を逐次取り出して、後述する切り替え処理を繰り返し実行すればよい。【００２７】
例えば、表示部４が、切り替え前の地図Ａを表示画面上に表示すると共に、地図データの縮尺毎に設定した地図レベルの選択用ＧＵＩ（Graphical User Interface）画面も表示画面の一部に表示する。ユーザは、地図レベルの選択用ＧＵＩ画面に基づいて、地図Ｂに対応する地図レベルを選択し、入力部２を介して当該地図レベルの選択情報を入力する。【００２８】
制御部３は、入力部２を介して地図Ｂに対応する地図レベルの選択情報を入力すると、切り替え前の地図Ａに対応する地図レベルと切り替え後の地図Ｂに対応する地図レベルを地図ポリゴン化部５に出力する。地図ポリゴン化部５は、制御部３による動作制御に従って、制御部３から入力した地図レベルを用いて地図ＤＢ部８を検索し、地図Ａ，Ｂの地図データを入力する（ステップＳＴ１）。【００２９】
なお、以降では、実施の形態１による地図表示装置１が、下記のように地図が表現されるベクタ地図データを扱うものと仮定して説明する。
（１）地図が点及び点間を接続する辺によって表現される。
（２）辺は、点列によって表現されることもある。このような辺に関する情報には、点列中の点間の接続関係を示す情報も含まれる。
（３）各点、各辺、及び辺の集合（若しくは、点列）に関する情報は、地図上の位置や互いの接続関係を示す情報のみならず、これらが構成する建物や道路等の描画オブジェクトを表す属性情報、及び各属性に固有な情報（例えば、建物の名称や道路幅など）を含む。【００３０】
地図ポリゴン化部５は、地図Ａ，Ｂの地図データをそれぞれ入力すると、地図Ａ，Ｂ間のマッチングを実行する（ステップＳＴ２）。ここで、マッチングとは、２つの地図の間で同じ地点を表す点の対応関係を求める処理である。図３は、２つの地図間のマッチング処理を説明するための図である。図３において、黒塗りの三角形記号、四角形記号、丸形記号、白抜きの三角形記号、四角形記号、丸形記号は、地図Ａ，Ｂを構成する点を示している。また、地図Ａ，Ｂにおいて同じ記号で表した点は、地図Ａ，Ｂ間で同じ地点を表す対応点である。【００３１】
カーナビゲーションシステムで利用されるＫＩＷＩフォーマットでは、図３に示すような対応点同士の位置座標は一致する。このため、対応点の位置情報を利用すれば、２つの地図間で同じ地点を表す点の対応関係を容易に求めることができる。また、地図間で対応点の位置座標が一致しない場合は、下記の参考文献１に開示されるマッチング処理を利用してもよい。
参考文献１；特開２００２−２７９４３７号公報【００３２】
参考文献１のマッチング処理では、地図を構成するオブジェクトの属性を考慮して、２つの地図間のマッチングを階層的に行ったり、点の接続情報に重みを加えることにより、距離のみで対応点を求める場合よりも高精度に対応点を求めることができる。なお、本発明は、上述したマッチング方法に限定されるものではなく、本発明の趣旨から逸脱しない範囲で他の方法を利用しても構わない。【００３３】
次に、地図ポリゴン化部５は、地図Ａ，Ｂ間でマッチングできなかった点に対応する点を追加する（ステップＳＴ３）。例えば、地図Ｂを縮尺の大きい広域地図とし、地図Ａを縮尺の小さい詳細地図とする。この場合、マッチング処理において、広域地図である地図Ｂは、詳細地図である地図Ａとの間で全ての点の対応がとれる。しかし、地図Ａは、地図Ｂとの間で対応がとれない点が残ることがある。このように対応がとれない点が残る理由としては、下記の場合が考えられる。
（１ａ）地図間で辺の詳細度が異なることに起因して辺を構成する点の対応がとれない。
（２ａ）地図の一方に対応する辺がなく、この対応する辺が接続している辺は双方の地図に存在する場合において、上記対応する辺を構成する点の対応がとれない。
（３ａ）地図の一方で対応するオブジェクト（建物や道路等）自体がないため、このオブジェクトを構成する点の対応がとれない。【００３４】
上述の理由から地図Ａ，Ｂの一方で対応する点がない場合、後述する処理が正確に行えないため、地図Ａ，Ｂの一方でマッチングできなかった点に対応する点をもう一方の地図上に追加する必要がある。
図４は、図３中の地図Ａ，Ｂ間でマッチングできなかった点に対応する点を追加する処理を説明するための図であり、地図Ａ（詳細地図）で対応がとれずに残った点に対応する点を地図Ｂ（広域地図）に追加する場合を示している。図４における黒塗りの三角形記号、正方形記号、菱形記号、五角形記号、丸形記号、十字形記号、白抜きの三角形記号、正方形記号、菱形記号、五角形記号、丸形記号、十字形記号は、地図Ａ，Ｂを構成する点を示している。また、地図Ａ，Ｂにおいて同じ記号で表した点は、地図Ａ，Ｂ間で同じ地点を表す対応点である。図４を用いて、対応点の追加処理を上記（１ａ）〜（３ａ）に示す状況ごとに説明する。【００３５】
（Ａ）（１ａ）の場合
詳細地図（地図Ａ）と広域地図（地図Ｂ）とを比べた場合、広域地図内の全ての辺は、詳細地図に含まれている。このように地図Ａ，Ｂの双方に存在する辺は、ステップＳＴ２で求めた対応点を用いて特定することができる。一方、詳細地図（地図Ａ）上のオブジェクトと広域地図（地図Ｂ）上のオブジェクトとでは、これらオブジェクトを構成する辺の数が異なる。このように辺の詳細度が異なる場合、地図ポリゴン化部５は、広域地図（地図Ｂ）上に詳細地図（地図Ａ）と同一の割合で点を追加する。【００３６】
図４に示す例では、地図Ｂ上の４つの黒塗りの丸形記号の点を接続してなる矩形のオブジェクトは、地図Ａ上に存在する辺の数が異なる八角形のオブジェクトに対応している。具体的に説明すると、地図Ｂ上における上記オブジェクトの一辺（黒塗りの丸形記号の点からなる辺）に対応する辺として、地図Ａには、白抜きの三角形記号の点と黒塗りの三角形記号の点を接続してなる辺と、白抜きの菱形記号の点と黒塗りの菱形記号の点を接続してなる辺とが存在する。【００３７】
ステップＳＴ２のマッチングを行った段階の地図Ｂには、上述した地図Ａ上における白抜きの三角形記号の点と黒塗りの三角形記号の点を接続してなる辺と、白抜きの菱形記号の点と黒塗りの菱形記号の点を接続してなる辺は存在しない。そこで、地図ポリゴン化部５は、図４に示すように、地図Ａにおける白抜きの三角形記号の点、黒塗りの三角形記号の点、白抜きの菱形記号の点、及び黒塗りの菱形記号の点に対応する点を、地図Ｂの対応する辺（黒塗りの丸形記号の点からなる矩形の一辺）上に追加する。【００３８】
（Ｂ）（２ａ）の場合
図４に示すように、地図Ａに存在する白抜きの正方形記号の点と黒塗りの正方形記号の点を接続してなる辺は地図Ｂ上に存在しないが、この辺が接続している２つの黒塗りの丸形記号の点を接続してなる辺は、地図Ａ，Ｂ間で対応する辺が存在する。この場合、地図ポリゴン化部５は、地図Ａに存在する、処理対象の辺を構成する白抜きの正方形記号の点と黒塗りの正方形記号の点を、上記処理対象の辺が接続している辺に対応する地図Ｂ上の辺（黒塗りの丸形記号の点を接続してなる辺）に追加する。【００３９】
なお、対応点を追加する辺上の位置は、上記処理対象の辺が接続していた位置とする。このとき、上記処理対象の辺を構成する全ての点が地図Ｂ上の同じ点に配置されることになり得る。このように複数の点の配置位置が一致した場合には、摂動を与えて別の点とみなす処理を施す。図４の例では、地図Ｂ上で白抜きの正方形記号の点と黒塗りの正方形記号の点が同一位置に配置されるが、摂動を与えることで若干ずれた位置の点として記載されている。【００４０】
（Ｃ）（３ａ）の場合
ステップＳＴ２のマッチングを行った段階の地図Ｂには、図４に示す白抜きの十字形記号の点、白抜きの五角形記号の点、黒塗りの十字形記号の点及び黒塗りの五角形記号の点を接続してなる地図Ａ上の矩形オブジェクトに対応するオブジェクトが存在しない。この場合、地図ポリゴン化部５は、図４に示すように、地図Ｂ上の地図Ａと同一位置座標に白抜きの十字形記号の点、白抜きの五角形記号の点、黒塗りの十字形記号の点、及び黒塗りの五角形記号の点に対応する点を追加する。さらに、追加された点同士を接続する辺も追加する。図４中の破線で示す辺は、追加した対応点によって新たに規定された辺である。【００４１】
ここで、地図精度や詳細地図から広域地図を作成する際に生じた簡略化のずれにより、広域地図に追加した点やオブジェクトが元々存在した他のオブジェクトと重なる場合がある。これについては、下記の参考文献２に記載されるように地図Ｂ上で各オブジェクトとの交差判定を行い、交差しているオブジェクトについては交差している位置まで点をずらすことで、交差を解消できる。
参考文献２；M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, “Computational Geometry-Algorithms and Applications”, Springer-Verlag, 2000.【００４２】
なお、本発明は、（Ａ）〜（Ｃ）で上述した点や辺の追加方法に限定されるものではなく、本発明の趣旨から逸脱しない範囲で他の方法を利用しても構わない。【００４３】
次に、地図ポリゴン化部５は、地図Ａ，Ｂ上の点や辺、オブジェクトの位置に基づいて地図Ａ，Ｂ上の全ての点及び辺を囲むバウンディングボックスを設定する（ステップＳＴ４）。これにより、地図Ａ及び地図Ｂの地図データは、バウンディングボックスで規定される枠内に地図全体を含んだポリゴンとみなすことができる。【００４４】
図５は、図４中の地図Ａ，Ｂをポリゴン化する処理を説明するための図である。図５において、バウンディングボックスを破線で記載している。バウンディングボックスは、図５に示すように、地図Ａ，Ｂで同じ外形状で、かつ同じ大きさとする。例えば、地図Ａ，Ｂをそれぞれ囲む矩形のバウンディングボックスを求め、これらのうちサイズの大きい方を選択する。このとき、バウンディングボックスは、地図上の全ての頂点及び辺を完全に含む矩形でなければならない。【００４５】
地図Ａ及び地図Ｂには、ともにバウンディングボックスとして４点で構成される矩形が追加されるため、２つの地図Ａ，Ｂの間で頂点数及び辺数の違いはない。なお、上述のようにして得られた各ポリゴンは、点の数及び辺の接続関係が等しい、同一の位相構造（トポロジー）を有する。【００４６】
次に、三角形分割部６は、地図ポリゴン化部５で生成されたポリゴンとみなせる２つの地図データに対して、対応点の接続関係が等しい三角形分割を求める（ステップＳＴ５）。対応点の接続関係が等しい三角形分割に２つのポリゴンを分割するアルゴリズムとしては、例えば参考文献３に記載される方法を用いる。【００４７】
なお、参考文献３に記載の方法のみならず、三角形分割を利用するモーフィングでは、同一の位相構造を有するポリゴンが与えられてから、処理が可能となる。ここでは、地図ポリゴン化部５が、同一の位相構造を有するポリゴンとみなせる２つの地図データ（地図Ａ，Ｂ）を生成しているので、三角形分割をそのまま実行することができる。【００４８】
また、参考文献３は、穴のあいた、つまり内部に多角形を有するポリゴンに対するものであり、ポリゴンの内部に存在する多角形まで三角形分割しない。一方、この発明では、ポリゴン化した地図上の点及び辺によって構成される多角形についても三角形分割する必要がある。そこで、ポリゴン化した地図データに対して、例えば非特許文献１に記載される処理を施すことにより、図６に示すように各ポリゴン内の地図Ａ，Ｂを構成する多角形についても、対応点の接続関係が等しい三角形分割が求められる。
参考文献３；M. Babikov, D. L. Souvaine, R. Wenger, “Constructing piecewise linear homeomorphisms of polygons with holes”, Proc. 9th Canadian Conf. Computational Geometry(CCCG ’97), pages6-10, 1997．【００４９】
さらに、ポリゴンの内部にある多角形以外の点や辺については、多角形が退化したものとして参考文献３の三角形分割を適用してもよい。
図７は、図５中の地図Ａを含むポリゴン内の点や辺を多角形の退化によるものとみなす場合を説明するための図である。図７に示すように、地図Ａのポリゴン内には、点と辺の接続により閉じた系となる多角形のオブジェクトと、点と辺の接続により開いた系ａとなる部分がある。【００５０】
そこで、三角形分割部６は、点と辺の接続による開いた系ａが、図７に示す多角形ａ１が退化したものとみなし、多角形ａ１を含む地図Ａ１のポリゴンの三角形分割を求める。このように、ポリゴン内部の点や辺が多角形の退化によるものとみなすことで、ポリゴン内部に辺のみを有する場合、又は、ポリゴン内部に複雑な多角形が存在する場合においても、参考文献３の三角形分割を適用することができる。【００５１】
なお、本発明は、上述した三角形分割方法に限定されるものではなく、本発明の趣旨から逸脱しない範囲で、対応点の接続関係が等しい三角形分割を求めることが可能な他のアルゴリズムも適用することができる。【００５２】
次に、モーフィング部７は、三角形分割部６で得られた三角形分割の結果を用いて、地図Ａ，Ｂ間の表示切り替えのモーフィング処理を実行する（ステップＳＴ６）。具体的には、モーフィング部７が、例えば下記の参考文献４に記載される方法を利用して、地図Ａ，Ｂ間のモーフィングにおける中間地図を求める。
参考文献４；M. S. Floater, C. Gotsman, “How to morph tilings injectively”, Journal of Computational and Applied Mathematics, 101(1-2), pages 117−129, 1999.【００５３】
ステップＳＴ６において、モーフィング部７は、自己交差のない中間地図を求めるために、地図Ａ，Ｂを表す各ポリゴン内の各点を辺で接続された周りの点との凸結合で表現する。ここで、点ｐiの周りの点の集合をｎ（ｐi）とすると、点ｐは、ｎ（ｐ）の凸結合として、下記式（１）で表現できる。但し、ｐjはｎ（ｐ）内の点の位置を示しており、λijは点ｐiに対するｐjの凸結合における係数である。
【数１】
2009104218.tif 000003
【００５４】
ポリゴン内の各点を凸結合で表現したときの係数を行列の形で並べると、下記式（２）に示すような行列Ｍで表現することができる。
【数２】
2009104218.tif 000004
【００５５】
モーフィング部７は、上記式（２）で表現された地図Ａ，Ｂの行列ＭA，ＭBに対して線形補間により、下記式（３）のような中間地図の係数Ｍtを求める。
（数３）Ｍt＝（１−ｔ）ＭA＋ｔＭB      ・・・（３）【００５６】
上記式（３）で求められる係数Ｍtから中間地図の各点の位置を求めることができる。
なお、線形補間のときに与えるパラメータｔは、地図Ａのときにはｔ＝０、地図Ｂのときにはｔ＝１となる（もしくは、その逆になる）。例えば、パラメータｔに０．５を設定することにより、地図Ａ、地図Ｂのちょうど中間の地図を求めることができる。なお、このようにして得られた中間地図は、地図Ａ，Ｂと位相構造が等しく、自己交差がない。【００５７】
縮尺変更に伴って地図表示を切り替える際には、モーフィング部７が、地図表示装置１の演算性能に応じた分解能でパラメータｔに０から１まで間の数値を順に設定してゆく。このようにして得られた地図Ａから中間地図を介して地図Ｂへ至るまでの地図データが、モーフィング部７から表示部４へ出力される。これにより、表示部４の表示画面上には、地図Ａから地図Ｂへの滑らかな地図変化が表示される。【００５８】
なお、本発明は、上述したモーフィング処理に限定されるものではなく、本発明の趣旨から逸脱しない範囲で他のモーフィング処理方法を利用しても構わない。例えば、下記の参考文献５に記載されるように、ポリゴン間の対応点の接続関係が等しい三角形から交差のないモーフィングを求めるアルゴリズムならばよい。
参考文献５；C. Erten, S. G. Kobourov and C. Pitta, “Morphing Planar Graphs”, Proc. 20th Annu. Symp. Comp. Geom. (SoCG ’04), pages451−452, 2004.【００５９】
また、モーフィング部７は、地図Ａから地図Ｂへモーフィングするにあたり、ステップＳＴ３で地図ポリゴン化部５により追加された点への対応として、線形補間により与えるパラメータｔの値をアルファ値として利用する。つまり、アルファ値により対応点の透過率を変化させることで、地図を構成する頂点が徐々に滑らかに表示されていき、ユーザは違和感なく点を認識することができる。【００６０】
辺についても同様に、各端点のアルファブレンド値に応じて透過率を変化させていくことで、地図を構成する辺が徐々に滑らかに現れるように表示することができる。追加された点への対応としては、パラメータｔの値の設定タイミングを制御することにより、地図Ａから地図Ｂへ変化し終わった時点で表示したり、予め表示する等の処理が可能である。このようなモーフィングの内容は、地図表示装置１の演算性能やアプリケーションの要求によって適宜変化させればよい。【００６１】
（１）対応点の追加をしない処理例１
上述の説明では、図２中のステップＳＴ３において、地図Ａ，Ｂ間で対応がとれなかった点を追加する処理を示したが、対応がとれなかった点について下記の処理を行うようにしてもよい。ここで、地図Ａから地図Ｂへ地図を変更するものとし、地図Ａが縮尺の小さい詳細地図、地図Ｂが縮尺の大きい広域地図とする。つまり、地図Ｂを構成する点については地図Ａとの間で全て対応がとれるが、地図Ａを構成する点では地図Ｂとの間で対応がとれない点が余った状態となる。但し、下記処理は地図Ａと地図Ｂとの関係が逆になったとしても成立する。【００６２】
地図ポリゴン化部５が、図２中のステップＳＴ３を省略して対応点の追加を行わず、ステップＳＴ４で地図Ａ，Ｂのポリゴンを作成する。三角形分割部６は、図８に示すように地図Ａのポリゴン及び対応点が追加されていない地図Ｂのポリゴンを入力し、地図Ａのポリゴンと地図Ｂのポリゴンの双方の対応点とこれを繋ぐ辺とを利用して、対応点の接続関係が等しい三角形分割を求める（対応点のみの三角形分割）。【００６３】
このようにして求められた地図Ａのポリゴン内の三角形と地図Ｂのポリゴン内の三角形は、図８に示すように地図Ａ，Ｂ間で対応がとれている。一方、地図Ａ内の地図Ｂと対応がとれずに余った点は、地図Ｂのポリゴンのいずれかの三角形内に含まれる。そこで、三角形分割部６は、図９に示すように地図Ａのポリゴン内の三角形に含まれる上記余った点（対応がとれなかった点）を、地図Ｂのポリゴン内の対応する三角形へマッピングする。マッピングの方法としては、例えば対応する三角形のアフィン変換を利用する。【００６４】
図９に示す例では、地図Ａのポリゴン内で地図Ｂと対応がとれなかった、黒塗りの三角形記号、正方形記号、菱形記号、五角形記号、丸形記号、十字形記号、白抜きの三角形記号、正方形記号、菱形記号、五角形記号、丸形記号、十字形記号で表す点の情報が、地図Ｂのポリゴン内の対応する三角形の情報としてマッピングされている。【００６５】
このような各三角形に対応のとれなかった点の情報がマッピングされた地図データに対して、モーフィング処理部７が、上述と同様のモーフィング処理を実行することにより、地図Ａ，Ｂ間の表示切り替えにおいて交差のないモーフィングを実現することができる。つまり、地図Ａ，Ｂ間で対応がとれた点は、上述したモーフィング処理で自己交差なく、モーフィングすることができ、対応がとれなかった点については、対応がとれた点で構成される三角形内の相対位置として表現され、地図Ａから地図Ｂへの変化の途中にその相対位置に点の表示若しくは非表示を設定すればよい。【００６６】
（２）対応点の追加をしない処理例２
図９で示したような対応点のマッピングを行わず、地図Ａのポリゴンと地図Ｂのポリゴンの間で対応する三角形については、地図Ａと地図Ｂの間での線形補間における上記パラメータｔを用いてブレンディングを行うようにしてもよい。例えば、三角形分割部６により得られた三角形の内部領域をテクスチャとみなし、下記式（４）を用いて対応する三角形間のブレンディングを行う。但し、ＴA、ＴBはそれぞれ地図Ａ、地図Ｂにおける三角形のテクスチャを示し、Ｔtはパラメータｔに対応するテクスチャの情報を示している。
（数４）Ｔt＝（１−ｔ）ＴA＋ｔＴA      ・・・（４）【００６７】
モーフィング部７が、地図Ａのポリゴン及び地図Ｂのポリゴン内の全ての三角形に対し上記式（４）を適用することにより、地図Ａから地図Ｂへ滑らかに変化する表示が可能である。この処理は、地図Ａと地図Ｂの間で対応がとれない余りの点が存在する場合においても適用可能である。しかしながら、自己交差がないことは、対応がとれた点のみで保証される。【００６８】
上述した処理例１，２は、地図内の点の数に依存しない。このため、対応がとれた点のみを対象とするだけでなく、ユーザの指定に合わせて自己交差がないことを保証する点の数を決定するようにしても構わない。このようにすることにより、自己交差なしの保証はできないが、できるだけ自己交差の発生を低減し、かつモーフィングに要する処理量を制御することができる。【００６９】
以上のように、この実施の形態１によれば、表示切り替え前後の地図Ａ，Ｂを互いに同一の位相構造を有するポリゴンに変換する地図ポリゴン化部５と、地図ポリゴン化部５で得られたポリゴンにおいて、表示切り替え前後の地図Ａ，Ｂ間で対応する点の接続関係が等しい三角形分割を求める三角形分割部６と、地図Ａ，Ｂの表示をモーフィングさせて切り替えるにあたり、三角形分割部６による三角形分割の結果から特定されるポリゴン内の点情報に基づいて、表示切り替え前後の地図Ａ，Ｂと位相構造が等しい中間地図の地図データを生成するモーフィング部７を備える。このように構成することにより、視認性を落とさずに例えば縮尺の異なる地図Ａ（詳細地図）から地図Ｂ（広域地図）への表示切り替えを行うことができる。【００７０】
また、上記実施の形態１では、処理対象の地図データがベクタ地図データである場合を示したが、ラスタ地図データを用いてもよい。この場合、ステップＳＴ２の処理を変更する必要がある。具体的には、ラスタ地図では点という概念がないため、上述のマッチング処理によって対応点を抽出することができない。【００７１】
そこで、ユーザが、入力部２を用いて地図上に対応点を設定するか、地図上の基準点が予め分かっている場合はそれを対応点として利用する。対応点を決定した後のステップＳＴ３からの処理は、図２を用いて上述した内容と同様である。なお、この場合には、自己交差なし等は考慮されない。【００７２】
実施の形態２．
上記実施の形態１は、地図表示装置を１つのコンピュータで実現する構成例を示した。この構成では、オンライン処理、すなわち地図ＤＢ部８から地図データを読み出して順に処理を行うことによって地図の表示切り替えにおけるモーフィングが実行される。オンライン処理の場合、モーフィング処理を行う前の地図データのみを保持すればよいため、最小限のデータサイズでモーフィング処理することができる。【００７３】
これに対して、この実施の形態２は、地図ＤＢ部の地図データに対して三角形分割までの処理を予め行って処理結果を保持しておき、ユーザからの地図表示の切り替えが要求されると、切り替えに対応する地図データの三角形分割後のデータを読み出してモーフィング処理を行う。つまり、オフラインで地図ＤＢ部の全地図データについて三角形分割までの処理を行っておき、オンラインで地図表示すべき地図データに対応する三角形分割後のデータを順に処理することによりモーフィングを行う。【００７４】
図１０は、この発明の実施の形態２による地図表示装置の構成を示すブロック図である。図１０において、地図表示装置１Ａは、前処理部１ａ及び後処理部１ｂを備える。前処理部１ａは、地図表示装置１Ａで取り扱う全ての地図データについて三角形分割までの処理を実行し、実行結果を保持する。この前処理部１ａは、制御部３ａ、地図ポリゴン化部５、三角形分割部６、地図データベース（ＤＢ）部８ａ及び出力部９を備える。【００７５】
制御部３ａは、前処理部１ａにおけるポリゴン化部５及び三角形分割部６の動作を制御することにより、地図データについて三角形分割後のデータを生成して地図ＤＢ部８ａに格納する。地図ポリゴン化部５及び三角形分割部６は、上記実施の形態１と同様に機能する。出力部９は、三角形分割部６で得られた三角形分割後のデータを、これに対応する地図データに関連付けて地図ＤＢ部８ａに格納する。地図ＤＢ部８ａは、地図データ及びその三角形分割までの処理で得られたデータを保持するデータベースである。【００７６】
なお、出力部９は、地図ＤＢ部８ａに格納される地図データの各点に対してモーフィングで利用する係数（上記式（１）〜（３））を追加しても構わない。また、地図ＤＢ部８ａ若しくはその他のデータベースシステムに新たな地図データを作成し、格納しても構わない。【００７７】
後処理部１ｂは、地図表示の切り替え要求などに応じて、地図ＤＢ部８ａ内の対応するデータを読み出してモーフィング処理を順次実行する。この後処理部１ｂは、入力部２、制御部３ｂ、表示部４及びモーフィング部７を備える。入力部２、表示部４及びモーフィング部７は、上記実施の形態１と同様に機能する。制御部３ｂは、モーフィング部７の動作を制御する構成要素であり、入力部２を介して要求された地図データに対応するデータを地図ＤＢ部８ａから読み込ませてモーフィング処理を実行させる。【００７８】
このように、実施の形態２による地図表示装置１Ａでは、前処理部１ａがオフラインで三角形分割後のデータまでを作成し、後処理部１ｂがオンラインで中間地図の作成処理を含むモーフィング処理を実行する。【００７９】
以上のように、この実施の形態２によれば、表示切り替え前後の地図データを互いに同一の位相構造を有するポリゴンに変換する地図ポリゴン化部５と、地図ポリゴン化部５で得られたポリゴンにおいて、表示切り替え前後の地図間で対応する点の接続関係が等しい三角形分割を求める三角形分割部６と、三角形分割部６で得られた三角形分割の結果を対応する地図データに関連付けて記憶する地図ＤＢ部８ａとを有する前処理部１ａと、地図データを表示する表示部４と、表示部４の地図表示をモーフィングさせて切り替えるにあたり、地図ＤＢ部８ａから読み出した三角形分割の結果から特定されるポリゴン内の点情報に基づいて、表示切り替え前後の各地図と位相構造が等しい中間地図の地図データを生成するモーフィング部７とを有する後処理部１ｂとを備える。このように構成することにより、上記実施の形態１の構成と比較して地図表示装置１Ａ内で保持すべきデータサイズは増加するが、後処理部１ｂではモーフィングにおける中間地図の作成処理のみを行えばよい。このため、地図表示切り替えのモーフィングを行う際の処理量を軽減することができる。
【産業上の利用可能性】
【００８０】
この発明に係る地図表示装置は、地図切り替えにモーフィングを適用することにより、縮尺の異なる地図間であっても視認性の良い切り替えが可能であるので、カーナビゲーションシステムの地図表示等に適している。
【図１】
2009104218.tif 000005
【図２】
2009104218.tif 000006
【図３】
2009104218.tif 000007
【図４】
2009104218.tif 000008
【図５】
2009104218.tif 000009
【図６】
2009104218.tif 000010
【図７】
2009104218.tif 000011
【図８】
2009104218.tif 000012
【図９】
2009104218.tif 000013
【図１０】
2009104218.tif 000014
【図１１】
2009104218.tif 000015
【図１２】
2009104218.tif 000016
【図１３】
2009104218.tif 000017
【図１４】
2009104218.tif 000018
【図１５】
2009104218.tif 000019
【国際調査報告】
2009104218.tif 000020
2009104218.tif 000021
2009104218.tif 000022
2009104218.tif 000023