地図生成装置及び地図生成方法
【課題】高速で再現性の高い地図を生成する地図生成装置を提供する。
【解決手段】河川ポリゴンを構成する構成点のうち、任意の２つの構成点を初期点として選択するとともに（ステップＳ７０２）、他の構成点の中から所定の条件を満たす構成点を１つ検出する（ステップＳ７０３）。そして、当該条件を満たす構成点と任意の２つの構成点とで三角形を形成した場合において最小角が最大となるような構成点を選択する（ステップＳ７０６）。次に、上述した任意の２つの構成点と選択された構成点とで構成される三角形により、河川ポリゴンを新たな２つの河川ポリゴンに分割する（ステップＳ７０７）。
【解決手段】河川ポリゴンを構成する構成点のうち、任意の２つの構成点を初期点として選択するとともに（ステップＳ７０２）、他の構成点の中から所定の条件を満たす構成点を１つ検出する（ステップＳ７０３）。そして、当該条件を満たす構成点と任意の２つの構成点とで三角形を形成した場合において最小角が最大となるような構成点を選択する（ステップＳ７０６）。次に、上述した任意の２つの構成点と選択された構成点とで構成される三角形により、河川ポリゴンを新たな２つの河川ポリゴンに分割する（ステップＳ７０７）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、縮尺の大きい詳細地図から縮尺の小さい広域地図を生成するための地図生成技術に関するものである。
【背景技術】
【０００２】
地図情報の電子データ化は、印刷物の時代に限定されていた地図の機能、用途、可能性を飛躍的に押し広げることになった。近年、地図を用いる仕事はコンピュータ上で行う地図情報システム（ＧＩＳ：Geographic Information System ）によって、データベース化された結果、データの加工等が容易になり、効率よく仕事が行えるようになった。例えば、カーナビゲーションシステム、運送会社の配車支援、上下水道/電気/電話等の施設管理、河川管理といった様々な場面でＧＩＳが利用されている。これらのシステムにおいて、コンピュータ上で利用できる状態の電子地図は必要不可欠となっている。
【０００３】
このとき、これらのシステムでは用途によって異なる尺度や異なる表示方法の地図が必要となる。現在までにこのような様々な電子地図データを自動作成する技術が研究されている。例えば、非特許文献１には、現在地と目的地の位置関係を把握しやすいような電子地図データの自動作成を行うシステムが紹介されている。また、非特許文献２には、モバイルなどの表示画面が小さなものでも表示できるようなデフォルメマップ作成技術が紹介されている。
【０００４】
また道路ネットワークを標本化・量子化することにより地図を見やすくする技術や、広告などに用いられる道路案内地図の自動作成手法など様々な地図を自動作成する技術が存在する。これらのほとんどは同一の尺度の下で電子地図データの簡略化を行うというものである。
【先行技術文献】
【特許文献】
【０００５】
【非特許文献１】馬場口登、堀江政彦、上田俊彦、淡誠一郎：経路理解支援のための略地図とその案内文の生成システム、電子情報通信学会論文誌、Vol.J80-DII、No.3、pp.791-800、1997
【非特許文献２】浅原彰規、嶋田茂、丸山貴志子：広域道路網の要約地図形成のためのネットワーク構造ようやくアルゴリズムとその評価、情報処理学会論文誌、Vol.47、No.12、pp.3068-3078、2006
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、実際の電子地図データには尺度の異なる複数の地図が用いられている。これら尺度の異なる複数地図は、元となる詳細な電子地図データを測量等で作成し、その詳細なデータからデータの間引き等の処理を施し、尺度の異なる電子地図データを予め作成、処理するのが一般的である。これら尺度の異なる電子地図データは処理時間や精度の問題から現在手作業で行われている。そのため、電子地図データの作成には多大なコストを要するというのが実情である。
【０００７】
本発明は、上記の課題を解決することを目的としている。すなわち、詳細な電子地図データからデータの間引きを行うことで一般的な広域地図を高速に自動作成することができる地図生成装置、地図生成方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記課題を解決するために、本発明は、複数の構成点を頂点とするポリゴンで表現される地物が含まれる電子地図データを記憶する記憶部と、前記電子地図データに基づいて所定範囲の地図を生成する制御部とを備えた地図生成装置であって、前記制御部は、前記ポリゴンを、前記構成点における任意の初期点を頂点として含む三角形であってドロネー三角形分割手法を用いて算出された三角形によりに分割するとともに、前記三角形により分割された複数のポリゴンをドロネー三角形分割手法を用いて算出された三角形により、分割される全てのポリゴンの形状が三角形になるまで、再帰的に分割する分割機能と、算出された前記三角形を構成する辺であって前記ポリゴンの内部に存在する辺の中点を連結することによりライン状のデータを生成するラインデータ生成機能とを有することを特徴とする。
なお、上述した特徴は、本発明の特徴の全てを列挙したものではなく、これらを要部とする構成や方法等もまた発明となり得る。
【発明の効果】
【０００９】
本発明によれば、高速で再現性の高い地図を表示することができる。
【図面の簡単な説明】
【００１０】
【図１】地図表示システムの構成図。
【図２】地図表示処理のフローチャート。
【図３】ライン化処理のフローチャート。
【図４】ドロネー三角分割手法の説明図。
【図５】ドロネー三角分割手法の説明図。
【図６】ドロネー三角分割手法の説明図。
【図７】ライン化処理のフローチャート。
【図８】ライン化処理のフローチャート。
【図９】再帰的ドロネー三角分割手法の説明図。
【図１０】再帰的ドロネー三角分割手法の説明図。
【図１１】再帰的ドロネー三角分割手法の説明図。
【発明を実施するための形態】
【００１１】
以下、本発明を具体化した実施例を説明する。
図１に示すように、本実施例における地図表示システムは、地図生成装置としてのコンピュータ１１を備える。コンピュータ１１は、地図などの各種画像、文字等を表示可能な表示部としてのディスプレイ１２、入力部としてのキーボード１３、記憶部としてのハードディスク１４、キャッシュメモリ１５、制御部としてのＣＰＵ１６を備える。
【００１２】
ハードディスク１４には、各種プログラムや、所定の領域についての詳細な地図（例えば１万分の１）を表示するために用いられる電子地図データが記憶されている。電子地図データは、地図として表示される各種地物（建物、道路、河川）の形状を表す形状データで構成されている。形状データは、ポリゴンデータ形式である。ここで、ポリゴンデータ（以下、単に「ポリゴン」と表現する場合もある。）とは経度・緯度等の座標値で表される複数の構成点を結ぶ多角形形状のデータであり、一筆書きが可能な閉曲線で表される。また、ポリゴンデータの始点と終点とは同一であり、更にそのポリゴンデータ自身と交差することがないといった特徴を有する。
【００１３】
キャッシュメモリ１５は、ＳＲＡＭ（Static
Random Access Memory ）等で構成されており、各種データを一時的に記憶する機能を有する。
ＣＰＵ１６（Central
Processing Unit ）は、ハードディスク１４に記憶されている各種ソフトウェア（プログラム）を実行することにより、本実施例における地図表示システム全体の各種制御を実施する。例えば、地図をディスプレイ１２上に表示したり、表示用電子地図データの加工を実行したりする。
【００１４】
具体的に、ＣＰＵ１６は、分割機能、ラインデータ生成機能、ライン接続機能、表示制御機能を有する。
分割機能は、ポリゴンを、ドロネー三角形分割手法を用いて算出された三角形により再帰的に複数のポリゴンに分割する機能である。本実施例では、全てのポリゴンの形状が三角形になるまで再帰的に分割される。
【００１５】
ラインデータ生成機能は、地図を構成するポリゴンを縮小する際に、ライン化（線状化）する機能である。
ライン接続機能は、互いに隣接するポリゴンをライン化する際に、当該ライン同士を接続する機能である。
表示制御機能は、ハードディスク１４から読み出された所定領域の地図や、縮小された地図等をディスプレイ１２に表示させる機能である。
【００１６】
次に、本実施例における地図表示システムを使用して地図を縮小表示する処理について説明する。
図２に示すように、まず、ＣＰＵ１６は、ディスプレイ１２に所定の縮尺で所定の領域の地図を表示する（ステップＳ２１）。次に、ＣＰＵ１６によって、表示されている地図の縮尺を小さくする縮小表示命令がキーボード１３や図示しないマウス等の入力機器を介して出されたか否かが判定される（ステップＳ２２）。縮小表示命令が出されていないと判定された場合には、ＣＰＵ１６は、通常の地図の表示処理を継続する。
【００１７】
一方、縮小表示命令が出されたと判定された場合には、ＣＰＵ１６は、現在表示されている地図を構成するポリゴンのうち、ライン化の対象となるポリゴンを選択する（ステップＳ２３）。選択されるポリゴンとしては、例えば、河川ポリゴンや道路ポリゴン等が挙げられる。ポリゴンの属性（道路、河川、建物等）については、各ポリゴンに付与されている属性データを参照することにより判断される。以下では、河川ポリゴンを例に説明するが、他のポリゴンについても同様の処理が実行される。
【００１８】
次に、ＣＰＵ１６によって、選択されたポリゴンについて、ライン化処理が実行される（ステップＳ２４）。そして、ＣＰＵ１６によって、隣接するラインを接続する処理が実行された後に（ステップＳ２５）、ディスプレイ１２上に縮小された地図が表示される（ステップＳ２６）。なお、ライン化処理（ステップＳ２４）及び隣接するラインの接続処理（ステップＳ２５）の詳細については、後述する。
【００１９】
（Ａ）ポリゴンのライン化処理
ポリゴンをライン化する処理は、地図の表示速度に影響するものであることから、いかに処理速度の高速化を図るかが課題となる。
本実施例においては、ドロネー三角形分割手法を用いてライン化を実行する。ドロネー三角形分割手法とは、ポリゴンを、その構成点を頂点とする複数の三角形に分割する手法である。そして、当該分割された三角形を構成する各辺の中点をラインの候補点とするとともに、それら中点を連結することによってライン化する。特に、ドロネー三角形分割手法の中でも輪郭や穴抜けなどの条件を考慮した分割法である制約付ドロネー三角分割手法を用いる。
【００２０】
（制約付ドロネー三角分割手法）
制約付ドロネー三角分割手法とは、具体的には、平面上に与えられたポリゴンの候補点のうち３点を頂点とする三角形を規定する。そして、当該三角形の外接円の内部に他の三角形の頂点を含まないような三角形でポリゴンを分割する方法である。この三角形分割法によれば、分割された三角形の最小角を最大にすることができるという特徴を持っている。
【００２１】
以下に、制約付ドロネー三角分割手法を用いて、地図を構成するポリゴンをライン化する手法の手順について説明する。
図３、４に示すように、まず、ＣＰＵ１６は、１つの河川ポリゴン４１を選択するとともに、当該河川ポリゴン４１を構成する全ての構成点４２の座標データをキャッシュメモリ１５に読み込む（ステップＳ３１）。次に、ＣＰＵ１６は、読み込まれた河川ポリゴン４１の構成点４２から３つの頂点を選択して（ステップＳ３２）、当該頂点の外接円４３の内側に他の構成点４２が存在するか否かの判定を行う（ステップＳ３３）。
【００２２】
外接円４３の内側に他の構成点４２が存在する場合には、ＣＰＵ１６は、当該３つの頂点からなる三角形を形成することなく、別の３つの頂点を選択する。一方、外接円４３の内側に他の構成点４２が存在しない場合には、当該３つの頂点からなる三角形はドロネー三角形の条件に適合するため、ＣＰＵ１６は、この三角形で河川ポリゴン４１を分割する（ステップＳ３４）。
【００２３】
次に、ＣＰＵ１６によって、三角形への分割処理が終了したか否かが判定される（ステップＳ３５）。三角形への分割処理が終了していないと判定された場合には、ＣＰＵ１６は分割処理を継続する。この分割処理は、河川ポリゴン４１を構成する構成点４２のうち、順次選択される３つの構成点４２の全て組み合わせに対して実行される。
一方、三角形への分割処理が終了したと判定された場合、図５に示すように、ＣＰＵ１６は分割された三角形４４を構成する各辺４５の中点４６をラインの候補点に設定する（ステップＳ３６）。
【００２４】
ここで、三角形４４を構成する各辺４５のうち、河川ポリゴン４１を構成する辺４７については、ＣＰＵ１６は、候補点を設定する処理の対象から除外する。
次に、ＣＰＵ１６は、河川ポリゴン４１を構成する辺４７のうち２辺が同一の三角形の辺として採用されているものを抽出する。そして、ＣＰＵ１６は、当該２辺を接続する頂点を、端点の候補点４２ａとして決定するとともに、当該端点をラインの候補点として追加する（ステップＳ３７）。
【００２５】
そして、図６に示すように、ＣＰＵ１６は、一方の端点の候補点４２ａから他方の端点の候補点４２ａまで、角度変化と距離とを考慮しつつラインの候補点４６を順に接続することで、ライン４８を生成する（ステップＳ３８）。
なお、他の河川ポリゴンとの繋がりを考慮するため、ＣＰＵ１６は、生成されたライン４８から端点の候補点４２ａに接続するライン４９を除去する。以上の処理は、表示対象となる全ての領域におけるポリゴンについて実行される。
【００２６】
（再帰的制約付ドロネー三角分割手法）
以上説明した制約付ドロネー三角分割手法は、全ての河川ポリゴンの構成点から抽出される３点の全ての組み合わせに対して分割できるか否かを判断するものであるから、構成点の数が増加するにつれて処理時間も長くなる。
そこで、制約付ドロネー三角分割手法を改良してラインを生成する際における処理時間の短縮化を実現する手法について説明する。
【００２７】
ドロネー三角形の判定回数を減らす、つまり分割する際に判定の対象となる三角形の数を減らすことができれば、その分だけ処理時間を短縮することができる。本実施例では、河川ポリゴンに対して制約付ドロネー三角分割手法を適用する場合に、一定の条件を満たした三角形を河川ポリゴンから除外して、河川ポリゴンを三角形に再帰的に分割していくという方法を採用する。
【００２８】
本アルゴリズムの概要は、以下のとおりである。まず、ポリゴンを構成する任意の２つの構成点を固定して、ドロネー三角形の条件を満たす残りの１点を検出する。そして、これら３点で構成される三角形によって分割される２つのポリゴンを新たに生成し、再びそれらのポリゴンに対して制約付ドロネー三角分割を実行する。この処理を、逐次生成されるポリゴンの構成点が３点となるまで、すなわち、全てのポリゴンが三角形になるまで実行することでラインの候補点を算出する。
【００２９】
以下に、制約付ドロネー三角分割手法を再帰的に用いて、ポリゴンをライン化する手順について具体的に説明する。
図７、９（ａ）に示すように、まず、ＣＰＵ１６は、処理対象となる１つの河川ポリゴン９１を選択する。そして、ＣＰＵ１６は当該河川ポリゴン９１における構成点９２の全ての座標データをキャッシュメモリ１５に読み込む（ステップＳ７０１）。
【００３０】
次に、図９（ｂ）に示すように、読み込まれた全ての構成点９２のうち、ＣＰＵ１６は、任意の２つの構成点９２ａ，９２ｂを初期点として選択するとともに（ステップＳ７０２）、他の構成点９２の中から以下の４つの条件を満たす構成点９２を１つ検出する（ステップＳ７０３）。
（ａ）任意の２つの構成点９２ａ，９２ｂと検出された１つの構成点との３点を頂点とする三角形の外接円内に他の構成点が入っていない。
（ｂ）３点を頂点とする三角形の重心点が河川ポリゴン９１の内部に存在する。
（ｃ）３点を頂点とする三角形の辺の中点が河川ポリゴン９１の内部に存在する。
（ｄ）３点を頂点とする三角形の辺が河川ポリゴン９１の各辺と交差しない。
【００３１】
ここで、初期点は、ＣＰＵ１６の初期点選択機能によって選択するようにしてもよい。例えば、ＣＰＵ１６は、任意の初期点として、分割される複数の河川ポリゴン９１における構成点９２の数が略同一となるような点を選択する。このような初期点を選択することで、分割されるそれぞれの河川ポリゴンにおける構成点９２の数が略同一となるため、更なる河川ポリゴンの分割処理が効率化される。
【００３２】
次に、ＣＰＵ１６は、上記（ａ）〜（ｄ）の４つの条件を全て満たす構成点が存在するか否かを判定する（ステップＳ７０４）。当該構成点が存在しないと判定した場合、ＣＰＵ１６は、河川ポリゴン９１を構成する全ての構成点９２を対象として改めて（ｂ）〜（ｄ）の３つの条件を満たす構成点を検出する（ステップＳ７０５）。そして、ＣＰＵ１６は、当該条件を満たす３つの構成点９２で三角形を形成した場合において最小角が最大となるような構成点を選択する（ステップＳ７０６）。
【００３３】
一方、上記（ａ）〜（ｄ）の４つの条件を全て満たす構成点が存在すると判定した場合、ＣＰＵ１６は、当該条件を満たす構成点と任意の２つの構成点９２ａ，９２ｂとで三角形を形成した場合において最小角が最大となるような構成点９２ｃを選択する（ステップＳ７０６）。
次に、図９（ｂ）（ｃ）に示すように、ＣＰＵ１６は、上述した任意の２つの構成点９２ａ，９２ｂと選択された構成点９２ｃとで構成される三角形９３により、河川ポリゴン９１を新たな２つの河川ポリゴン９１ａ、９１ｂに分割する（ステップＳ７０７）。
【００３４】
このとき、新たに生成される２つの河川ポリゴン９１ａ、９１ｂを構成する辺の一部として、三角形９３を構成する２つの構成点９２ａ、９２ｃ及び９２ｂ、９２ｃをそれぞれ接続することによって生成された辺が採用される。これは、分割して生成された河川ポリゴン９１ａ、９１ｂにおいて、生成された三角形９３の辺を基準として１点を探すため、ラインの候補点が端点の候補点まで繋がり関係を保ったまま記憶できるようにするためである。
【００３５】
次に、図１０に示すように、ＣＰＵ１６は、最初に読み込んだ２つの構成点９２ａ、９２ｂと検出された構成点９２ｃとのそれぞれの中点９４ａ、９４ｂをラインの候補点としてキャッシュメモリ１５に記憶する。また、ＣＰＵ１６は、最初に読み込んだ２つの構成点と隣り合う点以外の構成点を検出した場合（分割後の河川ポリゴンを構成する構成点の総数が２点以上で構成される場合）、最初に読み込んだ２つの構成点の中点を分岐点としてキャッシュメモリ１５に記憶する（ステップＳ７０８）。
【００３６】
そして、ＣＰＵ１６は、新たに生成された河川ポリゴンの構成点の総数が３（河川ポリゴンが三角形）であった場合、当該河川ポリゴンの構成点を端点の候補点、及びラインの候補点としてキャッシュメモリ１５に記憶する（ステップＳ７０９）。
次に、ＣＰＵ１６は、新たに生成される河川ポリゴンの構成点の総数が３（全ての河川ポリゴンが三角形）となったか否かを判定する（ステップＳ７１０）。新たに生成される河川ポリゴンの構成点の総数が４以上である場合には、当該河川ポリゴンの分割処理を継続する（ステップＳ７０２）。一方、新たに生成される河川ポリゴンの構成点の総数が３である場合には分割処理を終了する。
【００３７】
図１０に示す例の場合、新たに生成された河川ポリゴン９１ａ、９１ｂの構成点９２の総数は、それぞれ４、８であり、何れも３ではない。したがって、河川ポリゴン９１ａ、９１ｂの分割処理は継続される。すなわち、ＣＰＵ１６は、河川ポリゴン９１ａを更に河川ポリゴン９１ｃ、９１ｄに分割するとともに、河川ポリゴン９１ｂを更に河川ポリゴン９１ｅ〜９１ｊに分割する。そして、ＣＰＵ１６は、三角形となった各河川ポリゴン９１ｃ〜９１ｊを構成する辺の中点をラインの候補点９４及び分岐点９５としてキャッシュメモリ１５に記憶する。更に、ＣＰＵ１６は、端点の候補点９６についても、キャッシュメモリ１５に記憶する。
【００３８】
次に、図１１（ａ）に示すように、ＣＰＵ１６は、キャッシュメモリ１５に記憶されたラインの候補点９４、端点の候補点９６、分岐点９５の各座標データを読み込む。そして、ＣＰＵ１６は、ラインの候補点９４を順に読み込み、当該ラインの候補点９４のうち、端点の候補点９６及び分岐点９５と一致する点を検出する（ステップＳ７１１）。これと同時に、ラインの候補点９４間の距離に関する距離情報をキャッシュメモリ１５に記憶する。
【００３９】
図１１（ｂ）に示すように、分岐点９５と一致する点があった場合、ＣＰＵ１６は、ラインの候補点９４間の距離情報を初期化して再び端点の候補点９６、分岐点９５と一致する点を検出する。そして、端点の候補点９６を検出した場合、ＣＰＵ１６は、距離情報をキャッシュメモリ１５に記憶し、再び端点の候補点９６、分岐点９５と一致する点を検出する。連続して端点の候補点９６を検出した場合には、ＣＰＵ１６は距離情報を比較して短い方の点情報をラインの候補点９４、端点の候補点９６、及び分岐点９５から削除する。その後、ステップＳ７１１からの処理を繰り返す。
【００４０】
図１１（ｃ）に示すように、ＣＰＵ１６は、河川ポリゴン９１が分割された三角形の端点の候補点９６が２つになった時点で処理を終了するとともに、その２つの候補点９６がラインの始点及び終点になるようラインの候補点９４を接続する（ステップＳ７１２）。この処理によって、河川ポリゴン９１に対応するラインが生成される。
【００４１】
そして、ＣＰＵ１６は、分割された三角形の端点における候補点９６のうち、最初に読み込んだ河川ポリゴン９１を構成する構成点の初期点から遠い方の構成点を新たな初期点として河川ポリゴン９１の構成点の順序を並べ替えるとともに、再度ステップＳ７０１からの処理を実行することにより最も長いラインを検出する（ステップＳ７１３）。
なお、このようにして生成されたライン９７は分岐点９５で必ず別々の端点の候補点９６に向かって２本のラインが形成される。そのため、分岐点９５から各端点の候補点９６までの距離を比較することによってより長いラインを作成することができる。
【００４２】
しかしながら、最初に三角分割を行ったラインの候補点９４が必ずラインを構成する点として残ってしまうため（河川ポリゴン９１の初期点を固定して三角分割処理を開始しているため）、最も長いラインとはならない可能性がある。そこで一度生成したライン９７のポリゴンの初期点から遠い方の端点の候補点を河川ポリゴンの初期点として再度ラインの検出処理を行うことで最も長いラインの検出が可能になる。
【００４３】
（Ｂ）隣接するラインの接続処理
実際にライン化の処理対象となるポリゴンのほとんどが別のポリゴンと隣接している。この場合、単にそれぞれのポリゴンをライン化しただけでは、ポリゴン同士の接続部分が不連続となり、見栄えに影響を及ぼす場合もある。そこで、隣接するポリゴンについては、ライン化する際に、接続する接続処理を施す。
【００４４】
隣接するポリゴンをライン化する際における、ラインの接続方法について説明する。
まず、ＣＰＵ１６は、隣接するポリゴン同士の接続部分にラインを接続するための点（以下、「接続点」ともいう。）を設定する。このとき、接続点は隣接するポリゴン同士の接点における両端の垂直二等分線とポリゴンの輪郭とが交わった点とする。この接続点から処理対象となっているラインの構成点のうち最も近い点がラインの端点であれば、ＣＰＵ１６は、その接続点を対象となるポリゴンから作成されたラインに加える。
【００４５】
隣接するデータがポリゴンであった場合、ＣＰＵ１６は、この時点で作成されたものをラインデータとする。隣接するデータがラインデータになっていた場合、ＣＰＵ１６は、接続点から最も近くにある隣接するラインの構成点を検出する。このとき、ＣＰＵ１６は、当該構成点が隣接するラインの端点でない場合のみ対象となっているラインにこの構成点を加える。
【００４６】
この構成点が隣接するラインの端点であった場合、端点を接続してしまうと隣接するラインに同様の処理を行う際に隣接するラインからも対象の端点までラインを伸ばしてしまうための重複が起きることになる。そのため、ＣＰＵ１６は、接続点から最も近い隣接するラインの構成点が隣接するラインの端点であった場合、対象となるラインには接続点のみを加える。
【００４７】
以上の手法をポリゴンをライン化した後に適応することで自然なラインを作成することができる。
また、実際のデータにはポリゴンのみでなくラインも存在している。ここで、ポリゴンをライン化したため、そのポリゴンと繋がっていたラインの接続部が途切れてしまう場合がある。そのため、ＣＰＵ１６は接続点をラインと元のポリゴンの接続点として同様の処理を行うことで、より自然なラインを作成する。
【００４８】
（その他の高速化手法について）
地図を表示する際の処理を高速化するべく、ＣＰＵ１６は、河川ポリゴンや道路ポリゴンの幅を検出して、その幅に関する情報に基づいて河川ポリゴン等をライン状に変換するか否か決定する判断機能を備えてもよい。そして、その幅が予め設定されている条件を満たす場合にのみ、当該河川ポリゴンや道路ポリゴン等についてのライン化を行う。例えば、幅が予め設定されている閾値以下であった場合にのみ、ＣＰＵ１６はポリゴンのライン化を行う。地図上には様々な幅を持つポリゴンが存在しており、太い幅のポリゴンを細い幅のポリゴンと同様にライン化するとかえって見づらい地図になる場合もあるからである。
【００４９】
ポリゴンの幅を検出する手法としては、以下の手法がある。
・手法１：垂線の長さを用いる
ＣＰＵ１６は、ポリゴンをライン化した後に、ラインの構成点から垂線を延ばし、その垂線と元のポリゴンが交わった点の距離が最も小さいものの２倍をその点におけるポリゴンの幅とする。そして、全ての点におけるポリゴンの幅の平均をとることで、そのポリゴン全体の幅とする。
【００５０】
・手法２：分割した三角形の辺の長さを利用する
ＣＰＵ１６は、ポリゴンを複数の三角形に分割して、ラインの候補点を検出する際に、ラインの候補点を検出した三角形の辺の長さをその候補点におけるポリゴンの幅として記憶する。そして、ＣＰＵ１６は、その候補点の中からラインの構成点となった点におけるポリゴンの幅の平均をとることで、そのポリゴン全体の幅を求める。
そのほかにも、ポリゴンに予め属性データとして幅のレベル情報を付与しておき、ＣＰＵ１６が当該属性データに基づいてライン化を行うか否か決定するなどの手法も考えられる。
【００５１】
（実施例の効果）
以上説明したとおり、本実施例の地図表示システムは、以下の効果を奏する。
・縮尺の大きな電子地図データから縮尺の小さな電子地図データを生成するようにしたため、複数の縮尺の異なる地図をハードディスク１４に記憶させておく必要がない。
・河川ポリゴンの構成点数をｎとした場合、改良前の制約付ドロネー三角分割手法における処理時間のオーダはＯ(n(n-1)(n-2)/6)となる。一方、改良後の再帰的な制約付ドロネー三角分割手法における処理時間のオーダはＯ((n-1)(n-2)/2)となる。したがって、河川ポリゴンを構成する構成点が多いほど、処理時間の短縮化の効果は顕著となる。
【００５２】
・河川ポリゴンの形状を考慮してライン化するため、縮尺が小さな地図に表示を切り替える場合であっても、再現性のよい河川や道路等を表示することができる。
・縮尺の小さな地図を、詳細地図から生成することができるので、尺度の異なる複数の地図を必要とせず、記憶容量の低減を実現することができる。
・幅が予め設定されている閾値以下であった場合にのみ、ポリゴンのライン化を行うようにしたことで、不要なライン化を抑制することができる。したがって、表示処理の高速化を実現しつつ、見やすい地図を表示することが可能となる。
【００５３】
（変形例）
・本実施例は、縮尺が大きな地図から縮尺が小さな地図を生成する場合に適用してもよい。例えば、広範囲（例えば日本全国）の大縮尺（詳細）地図データから、小縮尺地図データを生成するバッチ処理等にも適用可能である。
【００５４】
・ＣＰＵ１６は、河川ポリゴンを構成する構成点の数を間引く間引き機能を備えるようにしてもよい。制約付ドロネー三角分割手法の処理回数を削減することができるため、結果として処理速度の高速化を実現することができるからである。具体的には、例えば隣接する２つの座標点間の距離が予め設定されている所定の距離となるように河川ポリゴンの構成点の間引きを実行する。また、河川ポリゴンを構成する構成点に対して、１点間隔で間引くなど、一定の間隔で間引きを実行するようにしてもよい。
【００５５】
・地図表示システムは、インターネット等のネットワークを介して通信可能に接続されているサーバとクライアント端末とを含んで構成するようにしてもよい。
・電子地図データを構成する各種地物の形状は、ポリゴンデータ形式のほかに、ラスタデータ形式、ベクトルデータ形式、その他種々のデータ形式を採用するとともに、表示する際にこれらのデータ形式をポリゴンデータ形式に変換するようにしてもよい。
・ＣＰＵ１６によって選択される初期点を１つとし、他の構成点９２の中から条件を満たす構成点９２を２つ検出するようにしてもよい。
【符号の説明】
【００５６】
１１…地図生成装置としてのコンピュータ
１２…表示部としてのディスプレイ
１４…記憶部としてのハードディスク
１５…キャッシュメモリ
１６…制御部としてのＣＰＵ
【技術分野】
【０００１】
本発明は、縮尺の大きい詳細地図から縮尺の小さい広域地図を生成するための地図生成技術に関するものである。
【背景技術】
【０００２】
地図情報の電子データ化は、印刷物の時代に限定されていた地図の機能、用途、可能性を飛躍的に押し広げることになった。近年、地図を用いる仕事はコンピュータ上で行う地図情報システム（ＧＩＳ：Geographic Information System ）によって、データベース化された結果、データの加工等が容易になり、効率よく仕事が行えるようになった。例えば、カーナビゲーションシステム、運送会社の配車支援、上下水道/電気/電話等の施設管理、河川管理といった様々な場面でＧＩＳが利用されている。これらのシステムにおいて、コンピュータ上で利用できる状態の電子地図は必要不可欠となっている。
【０００３】
このとき、これらのシステムでは用途によって異なる尺度や異なる表示方法の地図が必要となる。現在までにこのような様々な電子地図データを自動作成する技術が研究されている。例えば、非特許文献１には、現在地と目的地の位置関係を把握しやすいような電子地図データの自動作成を行うシステムが紹介されている。また、非特許文献２には、モバイルなどの表示画面が小さなものでも表示できるようなデフォルメマップ作成技術が紹介されている。
【０００４】
また道路ネットワークを標本化・量子化することにより地図を見やすくする技術や、広告などに用いられる道路案内地図の自動作成手法など様々な地図を自動作成する技術が存在する。これらのほとんどは同一の尺度の下で電子地図データの簡略化を行うというものである。
【先行技術文献】
【特許文献】
【０００５】
【非特許文献１】馬場口登、堀江政彦、上田俊彦、淡誠一郎：経路理解支援のための略地図とその案内文の生成システム、電子情報通信学会論文誌、Vol.J80-DII、No.3、pp.791-800、1997
【非特許文献２】浅原彰規、嶋田茂、丸山貴志子：広域道路網の要約地図形成のためのネットワーク構造ようやくアルゴリズムとその評価、情報処理学会論文誌、Vol.47、No.12、pp.3068-3078、2006
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、実際の電子地図データには尺度の異なる複数の地図が用いられている。これら尺度の異なる複数地図は、元となる詳細な電子地図データを測量等で作成し、その詳細なデータからデータの間引き等の処理を施し、尺度の異なる電子地図データを予め作成、処理するのが一般的である。これら尺度の異なる電子地図データは処理時間や精度の問題から現在手作業で行われている。そのため、電子地図データの作成には多大なコストを要するというのが実情である。
【０００７】
本発明は、上記の課題を解決することを目的としている。すなわち、詳細な電子地図データからデータの間引きを行うことで一般的な広域地図を高速に自動作成することができる地図生成装置、地図生成方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記課題を解決するために、本発明は、複数の構成点を頂点とするポリゴンで表現される地物が含まれる電子地図データを記憶する記憶部と、前記電子地図データに基づいて所定範囲の地図を生成する制御部とを備えた地図生成装置であって、前記制御部は、前記ポリゴンを、前記構成点における任意の初期点を頂点として含む三角形であってドロネー三角形分割手法を用いて算出された三角形によりに分割するとともに、前記三角形により分割された複数のポリゴンをドロネー三角形分割手法を用いて算出された三角形により、分割される全てのポリゴンの形状が三角形になるまで、再帰的に分割する分割機能と、算出された前記三角形を構成する辺であって前記ポリゴンの内部に存在する辺の中点を連結することによりライン状のデータを生成するラインデータ生成機能とを有することを特徴とする。
なお、上述した特徴は、本発明の特徴の全てを列挙したものではなく、これらを要部とする構成や方法等もまた発明となり得る。
【発明の効果】
【０００９】
本発明によれば、高速で再現性の高い地図を表示することができる。
【図面の簡単な説明】
【００１０】
【図１】地図表示システムの構成図。
【図２】地図表示処理のフローチャート。
【図３】ライン化処理のフローチャート。
【図４】ドロネー三角分割手法の説明図。
【図５】ドロネー三角分割手法の説明図。
【図６】ドロネー三角分割手法の説明図。
【図７】ライン化処理のフローチャート。
【図８】ライン化処理のフローチャート。
【図９】再帰的ドロネー三角分割手法の説明図。
【図１０】再帰的ドロネー三角分割手法の説明図。
【図１１】再帰的ドロネー三角分割手法の説明図。
【発明を実施するための形態】
【００１１】
以下、本発明を具体化した実施例を説明する。
図１に示すように、本実施例における地図表示システムは、地図生成装置としてのコンピュータ１１を備える。コンピュータ１１は、地図などの各種画像、文字等を表示可能な表示部としてのディスプレイ１２、入力部としてのキーボード１３、記憶部としてのハードディスク１４、キャッシュメモリ１５、制御部としてのＣＰＵ１６を備える。
【００１２】
ハードディスク１４には、各種プログラムや、所定の領域についての詳細な地図（例えば１万分の１）を表示するために用いられる電子地図データが記憶されている。電子地図データは、地図として表示される各種地物（建物、道路、河川）の形状を表す形状データで構成されている。形状データは、ポリゴンデータ形式である。ここで、ポリゴンデータ（以下、単に「ポリゴン」と表現する場合もある。）とは経度・緯度等の座標値で表される複数の構成点を結ぶ多角形形状のデータであり、一筆書きが可能な閉曲線で表される。また、ポリゴンデータの始点と終点とは同一であり、更にそのポリゴンデータ自身と交差することがないといった特徴を有する。
【００１３】
キャッシュメモリ１５は、ＳＲＡＭ（Static
Random Access Memory ）等で構成されており、各種データを一時的に記憶する機能を有する。
ＣＰＵ１６（Central
Processing Unit ）は、ハードディスク１４に記憶されている各種ソフトウェア（プログラム）を実行することにより、本実施例における地図表示システム全体の各種制御を実施する。例えば、地図をディスプレイ１２上に表示したり、表示用電子地図データの加工を実行したりする。
【００１４】
具体的に、ＣＰＵ１６は、分割機能、ラインデータ生成機能、ライン接続機能、表示制御機能を有する。
分割機能は、ポリゴンを、ドロネー三角形分割手法を用いて算出された三角形により再帰的に複数のポリゴンに分割する機能である。本実施例では、全てのポリゴンの形状が三角形になるまで再帰的に分割される。
【００１５】
ラインデータ生成機能は、地図を構成するポリゴンを縮小する際に、ライン化（線状化）する機能である。
ライン接続機能は、互いに隣接するポリゴンをライン化する際に、当該ライン同士を接続する機能である。
表示制御機能は、ハードディスク１４から読み出された所定領域の地図や、縮小された地図等をディスプレイ１２に表示させる機能である。
【００１６】
次に、本実施例における地図表示システムを使用して地図を縮小表示する処理について説明する。
図２に示すように、まず、ＣＰＵ１６は、ディスプレイ１２に所定の縮尺で所定の領域の地図を表示する（ステップＳ２１）。次に、ＣＰＵ１６によって、表示されている地図の縮尺を小さくする縮小表示命令がキーボード１３や図示しないマウス等の入力機器を介して出されたか否かが判定される（ステップＳ２２）。縮小表示命令が出されていないと判定された場合には、ＣＰＵ１６は、通常の地図の表示処理を継続する。
【００１７】
一方、縮小表示命令が出されたと判定された場合には、ＣＰＵ１６は、現在表示されている地図を構成するポリゴンのうち、ライン化の対象となるポリゴンを選択する（ステップＳ２３）。選択されるポリゴンとしては、例えば、河川ポリゴンや道路ポリゴン等が挙げられる。ポリゴンの属性（道路、河川、建物等）については、各ポリゴンに付与されている属性データを参照することにより判断される。以下では、河川ポリゴンを例に説明するが、他のポリゴンについても同様の処理が実行される。
【００１８】
次に、ＣＰＵ１６によって、選択されたポリゴンについて、ライン化処理が実行される（ステップＳ２４）。そして、ＣＰＵ１６によって、隣接するラインを接続する処理が実行された後に（ステップＳ２５）、ディスプレイ１２上に縮小された地図が表示される（ステップＳ２６）。なお、ライン化処理（ステップＳ２４）及び隣接するラインの接続処理（ステップＳ２５）の詳細については、後述する。
【００１９】
（Ａ）ポリゴンのライン化処理
ポリゴンをライン化する処理は、地図の表示速度に影響するものであることから、いかに処理速度の高速化を図るかが課題となる。
本実施例においては、ドロネー三角形分割手法を用いてライン化を実行する。ドロネー三角形分割手法とは、ポリゴンを、その構成点を頂点とする複数の三角形に分割する手法である。そして、当該分割された三角形を構成する各辺の中点をラインの候補点とするとともに、それら中点を連結することによってライン化する。特に、ドロネー三角形分割手法の中でも輪郭や穴抜けなどの条件を考慮した分割法である制約付ドロネー三角分割手法を用いる。
【００２０】
（制約付ドロネー三角分割手法）
制約付ドロネー三角分割手法とは、具体的には、平面上に与えられたポリゴンの候補点のうち３点を頂点とする三角形を規定する。そして、当該三角形の外接円の内部に他の三角形の頂点を含まないような三角形でポリゴンを分割する方法である。この三角形分割法によれば、分割された三角形の最小角を最大にすることができるという特徴を持っている。
【００２１】
以下に、制約付ドロネー三角分割手法を用いて、地図を構成するポリゴンをライン化する手法の手順について説明する。
図３、４に示すように、まず、ＣＰＵ１６は、１つの河川ポリゴン４１を選択するとともに、当該河川ポリゴン４１を構成する全ての構成点４２の座標データをキャッシュメモリ１５に読み込む（ステップＳ３１）。次に、ＣＰＵ１６は、読み込まれた河川ポリゴン４１の構成点４２から３つの頂点を選択して（ステップＳ３２）、当該頂点の外接円４３の内側に他の構成点４２が存在するか否かの判定を行う（ステップＳ３３）。
【００２２】
外接円４３の内側に他の構成点４２が存在する場合には、ＣＰＵ１６は、当該３つの頂点からなる三角形を形成することなく、別の３つの頂点を選択する。一方、外接円４３の内側に他の構成点４２が存在しない場合には、当該３つの頂点からなる三角形はドロネー三角形の条件に適合するため、ＣＰＵ１６は、この三角形で河川ポリゴン４１を分割する（ステップＳ３４）。
【００２３】
次に、ＣＰＵ１６によって、三角形への分割処理が終了したか否かが判定される（ステップＳ３５）。三角形への分割処理が終了していないと判定された場合には、ＣＰＵ１６は分割処理を継続する。この分割処理は、河川ポリゴン４１を構成する構成点４２のうち、順次選択される３つの構成点４２の全て組み合わせに対して実行される。
一方、三角形への分割処理が終了したと判定された場合、図５に示すように、ＣＰＵ１６は分割された三角形４４を構成する各辺４５の中点４６をラインの候補点に設定する（ステップＳ３６）。
【００２４】
ここで、三角形４４を構成する各辺４５のうち、河川ポリゴン４１を構成する辺４７については、ＣＰＵ１６は、候補点を設定する処理の対象から除外する。
次に、ＣＰＵ１６は、河川ポリゴン４１を構成する辺４７のうち２辺が同一の三角形の辺として採用されているものを抽出する。そして、ＣＰＵ１６は、当該２辺を接続する頂点を、端点の候補点４２ａとして決定するとともに、当該端点をラインの候補点として追加する（ステップＳ３７）。
【００２５】
そして、図６に示すように、ＣＰＵ１６は、一方の端点の候補点４２ａから他方の端点の候補点４２ａまで、角度変化と距離とを考慮しつつラインの候補点４６を順に接続することで、ライン４８を生成する（ステップＳ３８）。
なお、他の河川ポリゴンとの繋がりを考慮するため、ＣＰＵ１６は、生成されたライン４８から端点の候補点４２ａに接続するライン４９を除去する。以上の処理は、表示対象となる全ての領域におけるポリゴンについて実行される。
【００２６】
（再帰的制約付ドロネー三角分割手法）
以上説明した制約付ドロネー三角分割手法は、全ての河川ポリゴンの構成点から抽出される３点の全ての組み合わせに対して分割できるか否かを判断するものであるから、構成点の数が増加するにつれて処理時間も長くなる。
そこで、制約付ドロネー三角分割手法を改良してラインを生成する際における処理時間の短縮化を実現する手法について説明する。
【００２７】
ドロネー三角形の判定回数を減らす、つまり分割する際に判定の対象となる三角形の数を減らすことができれば、その分だけ処理時間を短縮することができる。本実施例では、河川ポリゴンに対して制約付ドロネー三角分割手法を適用する場合に、一定の条件を満たした三角形を河川ポリゴンから除外して、河川ポリゴンを三角形に再帰的に分割していくという方法を採用する。
【００２８】
本アルゴリズムの概要は、以下のとおりである。まず、ポリゴンを構成する任意の２つの構成点を固定して、ドロネー三角形の条件を満たす残りの１点を検出する。そして、これら３点で構成される三角形によって分割される２つのポリゴンを新たに生成し、再びそれらのポリゴンに対して制約付ドロネー三角分割を実行する。この処理を、逐次生成されるポリゴンの構成点が３点となるまで、すなわち、全てのポリゴンが三角形になるまで実行することでラインの候補点を算出する。
【００２９】
以下に、制約付ドロネー三角分割手法を再帰的に用いて、ポリゴンをライン化する手順について具体的に説明する。
図７、９（ａ）に示すように、まず、ＣＰＵ１６は、処理対象となる１つの河川ポリゴン９１を選択する。そして、ＣＰＵ１６は当該河川ポリゴン９１における構成点９２の全ての座標データをキャッシュメモリ１５に読み込む（ステップＳ７０１）。
【００３０】
次に、図９（ｂ）に示すように、読み込まれた全ての構成点９２のうち、ＣＰＵ１６は、任意の２つの構成点９２ａ，９２ｂを初期点として選択するとともに（ステップＳ７０２）、他の構成点９２の中から以下の４つの条件を満たす構成点９２を１つ検出する（ステップＳ７０３）。
（ａ）任意の２つの構成点９２ａ，９２ｂと検出された１つの構成点との３点を頂点とする三角形の外接円内に他の構成点が入っていない。
（ｂ）３点を頂点とする三角形の重心点が河川ポリゴン９１の内部に存在する。
（ｃ）３点を頂点とする三角形の辺の中点が河川ポリゴン９１の内部に存在する。
（ｄ）３点を頂点とする三角形の辺が河川ポリゴン９１の各辺と交差しない。
【００３１】
ここで、初期点は、ＣＰＵ１６の初期点選択機能によって選択するようにしてもよい。例えば、ＣＰＵ１６は、任意の初期点として、分割される複数の河川ポリゴン９１における構成点９２の数が略同一となるような点を選択する。このような初期点を選択することで、分割されるそれぞれの河川ポリゴンにおける構成点９２の数が略同一となるため、更なる河川ポリゴンの分割処理が効率化される。
【００３２】
次に、ＣＰＵ１６は、上記（ａ）〜（ｄ）の４つの条件を全て満たす構成点が存在するか否かを判定する（ステップＳ７０４）。当該構成点が存在しないと判定した場合、ＣＰＵ１６は、河川ポリゴン９１を構成する全ての構成点９２を対象として改めて（ｂ）〜（ｄ）の３つの条件を満たす構成点を検出する（ステップＳ７０５）。そして、ＣＰＵ１６は、当該条件を満たす３つの構成点９２で三角形を形成した場合において最小角が最大となるような構成点を選択する（ステップＳ７０６）。
【００３３】
一方、上記（ａ）〜（ｄ）の４つの条件を全て満たす構成点が存在すると判定した場合、ＣＰＵ１６は、当該条件を満たす構成点と任意の２つの構成点９２ａ，９２ｂとで三角形を形成した場合において最小角が最大となるような構成点９２ｃを選択する（ステップＳ７０６）。
次に、図９（ｂ）（ｃ）に示すように、ＣＰＵ１６は、上述した任意の２つの構成点９２ａ，９２ｂと選択された構成点９２ｃとで構成される三角形９３により、河川ポリゴン９１を新たな２つの河川ポリゴン９１ａ、９１ｂに分割する（ステップＳ７０７）。
【００３４】
このとき、新たに生成される２つの河川ポリゴン９１ａ、９１ｂを構成する辺の一部として、三角形９３を構成する２つの構成点９２ａ、９２ｃ及び９２ｂ、９２ｃをそれぞれ接続することによって生成された辺が採用される。これは、分割して生成された河川ポリゴン９１ａ、９１ｂにおいて、生成された三角形９３の辺を基準として１点を探すため、ラインの候補点が端点の候補点まで繋がり関係を保ったまま記憶できるようにするためである。
【００３５】
次に、図１０に示すように、ＣＰＵ１６は、最初に読み込んだ２つの構成点９２ａ、９２ｂと検出された構成点９２ｃとのそれぞれの中点９４ａ、９４ｂをラインの候補点としてキャッシュメモリ１５に記憶する。また、ＣＰＵ１６は、最初に読み込んだ２つの構成点と隣り合う点以外の構成点を検出した場合（分割後の河川ポリゴンを構成する構成点の総数が２点以上で構成される場合）、最初に読み込んだ２つの構成点の中点を分岐点としてキャッシュメモリ１５に記憶する（ステップＳ７０８）。
【００３６】
そして、ＣＰＵ１６は、新たに生成された河川ポリゴンの構成点の総数が３（河川ポリゴンが三角形）であった場合、当該河川ポリゴンの構成点を端点の候補点、及びラインの候補点としてキャッシュメモリ１５に記憶する（ステップＳ７０９）。
次に、ＣＰＵ１６は、新たに生成される河川ポリゴンの構成点の総数が３（全ての河川ポリゴンが三角形）となったか否かを判定する（ステップＳ７１０）。新たに生成される河川ポリゴンの構成点の総数が４以上である場合には、当該河川ポリゴンの分割処理を継続する（ステップＳ７０２）。一方、新たに生成される河川ポリゴンの構成点の総数が３である場合には分割処理を終了する。
【００３７】
図１０に示す例の場合、新たに生成された河川ポリゴン９１ａ、９１ｂの構成点９２の総数は、それぞれ４、８であり、何れも３ではない。したがって、河川ポリゴン９１ａ、９１ｂの分割処理は継続される。すなわち、ＣＰＵ１６は、河川ポリゴン９１ａを更に河川ポリゴン９１ｃ、９１ｄに分割するとともに、河川ポリゴン９１ｂを更に河川ポリゴン９１ｅ〜９１ｊに分割する。そして、ＣＰＵ１６は、三角形となった各河川ポリゴン９１ｃ〜９１ｊを構成する辺の中点をラインの候補点９４及び分岐点９５としてキャッシュメモリ１５に記憶する。更に、ＣＰＵ１６は、端点の候補点９６についても、キャッシュメモリ１５に記憶する。
【００３８】
次に、図１１（ａ）に示すように、ＣＰＵ１６は、キャッシュメモリ１５に記憶されたラインの候補点９４、端点の候補点９６、分岐点９５の各座標データを読み込む。そして、ＣＰＵ１６は、ラインの候補点９４を順に読み込み、当該ラインの候補点９４のうち、端点の候補点９６及び分岐点９５と一致する点を検出する（ステップＳ７１１）。これと同時に、ラインの候補点９４間の距離に関する距離情報をキャッシュメモリ１５に記憶する。
【００３９】
図１１（ｂ）に示すように、分岐点９５と一致する点があった場合、ＣＰＵ１６は、ラインの候補点９４間の距離情報を初期化して再び端点の候補点９６、分岐点９５と一致する点を検出する。そして、端点の候補点９６を検出した場合、ＣＰＵ１６は、距離情報をキャッシュメモリ１５に記憶し、再び端点の候補点９６、分岐点９５と一致する点を検出する。連続して端点の候補点９６を検出した場合には、ＣＰＵ１６は距離情報を比較して短い方の点情報をラインの候補点９４、端点の候補点９６、及び分岐点９５から削除する。その後、ステップＳ７１１からの処理を繰り返す。
【００４０】
図１１（ｃ）に示すように、ＣＰＵ１６は、河川ポリゴン９１が分割された三角形の端点の候補点９６が２つになった時点で処理を終了するとともに、その２つの候補点９６がラインの始点及び終点になるようラインの候補点９４を接続する（ステップＳ７１２）。この処理によって、河川ポリゴン９１に対応するラインが生成される。
【００４１】
そして、ＣＰＵ１６は、分割された三角形の端点における候補点９６のうち、最初に読み込んだ河川ポリゴン９１を構成する構成点の初期点から遠い方の構成点を新たな初期点として河川ポリゴン９１の構成点の順序を並べ替えるとともに、再度ステップＳ７０１からの処理を実行することにより最も長いラインを検出する（ステップＳ７１３）。
なお、このようにして生成されたライン９７は分岐点９５で必ず別々の端点の候補点９６に向かって２本のラインが形成される。そのため、分岐点９５から各端点の候補点９６までの距離を比較することによってより長いラインを作成することができる。
【００４２】
しかしながら、最初に三角分割を行ったラインの候補点９４が必ずラインを構成する点として残ってしまうため（河川ポリゴン９１の初期点を固定して三角分割処理を開始しているため）、最も長いラインとはならない可能性がある。そこで一度生成したライン９７のポリゴンの初期点から遠い方の端点の候補点を河川ポリゴンの初期点として再度ラインの検出処理を行うことで最も長いラインの検出が可能になる。
【００４３】
（Ｂ）隣接するラインの接続処理
実際にライン化の処理対象となるポリゴンのほとんどが別のポリゴンと隣接している。この場合、単にそれぞれのポリゴンをライン化しただけでは、ポリゴン同士の接続部分が不連続となり、見栄えに影響を及ぼす場合もある。そこで、隣接するポリゴンについては、ライン化する際に、接続する接続処理を施す。
【００４４】
隣接するポリゴンをライン化する際における、ラインの接続方法について説明する。
まず、ＣＰＵ１６は、隣接するポリゴン同士の接続部分にラインを接続するための点（以下、「接続点」ともいう。）を設定する。このとき、接続点は隣接するポリゴン同士の接点における両端の垂直二等分線とポリゴンの輪郭とが交わった点とする。この接続点から処理対象となっているラインの構成点のうち最も近い点がラインの端点であれば、ＣＰＵ１６は、その接続点を対象となるポリゴンから作成されたラインに加える。
【００４５】
隣接するデータがポリゴンであった場合、ＣＰＵ１６は、この時点で作成されたものをラインデータとする。隣接するデータがラインデータになっていた場合、ＣＰＵ１６は、接続点から最も近くにある隣接するラインの構成点を検出する。このとき、ＣＰＵ１６は、当該構成点が隣接するラインの端点でない場合のみ対象となっているラインにこの構成点を加える。
【００４６】
この構成点が隣接するラインの端点であった場合、端点を接続してしまうと隣接するラインに同様の処理を行う際に隣接するラインからも対象の端点までラインを伸ばしてしまうための重複が起きることになる。そのため、ＣＰＵ１６は、接続点から最も近い隣接するラインの構成点が隣接するラインの端点であった場合、対象となるラインには接続点のみを加える。
【００４７】
以上の手法をポリゴンをライン化した後に適応することで自然なラインを作成することができる。
また、実際のデータにはポリゴンのみでなくラインも存在している。ここで、ポリゴンをライン化したため、そのポリゴンと繋がっていたラインの接続部が途切れてしまう場合がある。そのため、ＣＰＵ１６は接続点をラインと元のポリゴンの接続点として同様の処理を行うことで、より自然なラインを作成する。
【００４８】
（その他の高速化手法について）
地図を表示する際の処理を高速化するべく、ＣＰＵ１６は、河川ポリゴンや道路ポリゴンの幅を検出して、その幅に関する情報に基づいて河川ポリゴン等をライン状に変換するか否か決定する判断機能を備えてもよい。そして、その幅が予め設定されている条件を満たす場合にのみ、当該河川ポリゴンや道路ポリゴン等についてのライン化を行う。例えば、幅が予め設定されている閾値以下であった場合にのみ、ＣＰＵ１６はポリゴンのライン化を行う。地図上には様々な幅を持つポリゴンが存在しており、太い幅のポリゴンを細い幅のポリゴンと同様にライン化するとかえって見づらい地図になる場合もあるからである。
【００４９】
ポリゴンの幅を検出する手法としては、以下の手法がある。
・手法１：垂線の長さを用いる
ＣＰＵ１６は、ポリゴンをライン化した後に、ラインの構成点から垂線を延ばし、その垂線と元のポリゴンが交わった点の距離が最も小さいものの２倍をその点におけるポリゴンの幅とする。そして、全ての点におけるポリゴンの幅の平均をとることで、そのポリゴン全体の幅とする。
【００５０】
・手法２：分割した三角形の辺の長さを利用する
ＣＰＵ１６は、ポリゴンを複数の三角形に分割して、ラインの候補点を検出する際に、ラインの候補点を検出した三角形の辺の長さをその候補点におけるポリゴンの幅として記憶する。そして、ＣＰＵ１６は、その候補点の中からラインの構成点となった点におけるポリゴンの幅の平均をとることで、そのポリゴン全体の幅を求める。
そのほかにも、ポリゴンに予め属性データとして幅のレベル情報を付与しておき、ＣＰＵ１６が当該属性データに基づいてライン化を行うか否か決定するなどの手法も考えられる。
【００５１】
（実施例の効果）
以上説明したとおり、本実施例の地図表示システムは、以下の効果を奏する。
・縮尺の大きな電子地図データから縮尺の小さな電子地図データを生成するようにしたため、複数の縮尺の異なる地図をハードディスク１４に記憶させておく必要がない。
・河川ポリゴンの構成点数をｎとした場合、改良前の制約付ドロネー三角分割手法における処理時間のオーダはＯ(n(n-1)(n-2)/6)となる。一方、改良後の再帰的な制約付ドロネー三角分割手法における処理時間のオーダはＯ((n-1)(n-2)/2)となる。したがって、河川ポリゴンを構成する構成点が多いほど、処理時間の短縮化の効果は顕著となる。
【００５２】
・河川ポリゴンの形状を考慮してライン化するため、縮尺が小さな地図に表示を切り替える場合であっても、再現性のよい河川や道路等を表示することができる。
・縮尺の小さな地図を、詳細地図から生成することができるので、尺度の異なる複数の地図を必要とせず、記憶容量の低減を実現することができる。
・幅が予め設定されている閾値以下であった場合にのみ、ポリゴンのライン化を行うようにしたことで、不要なライン化を抑制することができる。したがって、表示処理の高速化を実現しつつ、見やすい地図を表示することが可能となる。
【００５３】
（変形例）
・本実施例は、縮尺が大きな地図から縮尺が小さな地図を生成する場合に適用してもよい。例えば、広範囲（例えば日本全国）の大縮尺（詳細）地図データから、小縮尺地図データを生成するバッチ処理等にも適用可能である。
【００５４】
・ＣＰＵ１６は、河川ポリゴンを構成する構成点の数を間引く間引き機能を備えるようにしてもよい。制約付ドロネー三角分割手法の処理回数を削減することができるため、結果として処理速度の高速化を実現することができるからである。具体的には、例えば隣接する２つの座標点間の距離が予め設定されている所定の距離となるように河川ポリゴンの構成点の間引きを実行する。また、河川ポリゴンを構成する構成点に対して、１点間隔で間引くなど、一定の間隔で間引きを実行するようにしてもよい。
【００５５】
・地図表示システムは、インターネット等のネットワークを介して通信可能に接続されているサーバとクライアント端末とを含んで構成するようにしてもよい。
・電子地図データを構成する各種地物の形状は、ポリゴンデータ形式のほかに、ラスタデータ形式、ベクトルデータ形式、その他種々のデータ形式を採用するとともに、表示する際にこれらのデータ形式をポリゴンデータ形式に変換するようにしてもよい。
・ＣＰＵ１６によって選択される初期点を１つとし、他の構成点９２の中から条件を満たす構成点９２を２つ検出するようにしてもよい。
【符号の説明】
【００５６】
１１…地図生成装置としてのコンピュータ
１２…表示部としてのディスプレイ
１４…記憶部としてのハードディスク
１５…キャッシュメモリ
１６…制御部としてのＣＰＵ
【特許請求の範囲】
【請求項１】
複数の構成点を頂点とするポリゴンで表現される地物が含まれる電子地図データを記憶する記憶部と、
前記電子地図データに基づいて所定範囲の地図を生成する制御部と
を備えた地図生成装置であって、
前記制御部は、
前記ポリゴンを、前記構成点における任意の初期点を頂点として含む三角形であってドロネー三角形分割手法を用いて算出された三角形によりに分割するとともに、前記三角形により分割された複数のポリゴンをドロネー三角形分割手法を用いて算出された三角形により、分割される全てのポリゴンの形状が三角形になるまで、再帰的に分割する分割機能と、
算出された前記三角形を構成する辺であって前記ポリゴンの内部に存在する辺の中点を連結することによりライン状のデータを生成するラインデータ生成機能と
を有することを特徴とする地図生成装置。
【請求項２】
前記制御部は、前記任意の初期点として、分割される複数のポリゴンにおける前記構成点の数が略同一となる点を選択する初期点選択機能を更に有することを特徴とする請求項１に記載の地図生成装置。
【請求項３】
前記制御部は、前記構成点の数を間引く間引き機能を更に有することを特徴とする請求項１又は請求項２に記載の地図生成装置。
【請求項４】
前記制御部は、前記ポリゴンの幅に関する情報に基づいて該ポリゴンをライン状に変換するか否か決定する判断機能を更に有することを特徴とする請求項１〜３のうち何れか一項に記載の地図生成装置。
【請求項５】
コンピュータが、
記憶部に記憶されている電子地図データに含まれる地物を表現するための複数の構成点を頂点とするポリゴンについて、前記構成点における任意の初期点を頂点として含む三角形であってドロネー三角形分割手法を用いて算出された三角形により分割するとともに、前記三角形により分割された複数のポリゴンをドロネー三角形分割手法を用いて算出された三角形により、分割される全てのポリゴンの形状が三角形になるまで、再帰的に分割する分割工程と、
算出された前記三角形を構成する辺であって前記ポリゴンの内部に存在する辺の中点を連結することによりライン状のデータを生成するラインデータ生成機能と、
前記ライン状のデータで表される地物が含まれる所定範囲の地図を生成する地図生成工程と
を実行することを特徴とする地図生成方法。
【請求項１】
複数の構成点を頂点とするポリゴンで表現される地物が含まれる電子地図データを記憶する記憶部と、
前記電子地図データに基づいて所定範囲の地図を生成する制御部と
を備えた地図生成装置であって、
前記制御部は、
前記ポリゴンを、前記構成点における任意の初期点を頂点として含む三角形であってドロネー三角形分割手法を用いて算出された三角形によりに分割するとともに、前記三角形により分割された複数のポリゴンをドロネー三角形分割手法を用いて算出された三角形により、分割される全てのポリゴンの形状が三角形になるまで、再帰的に分割する分割機能と、
算出された前記三角形を構成する辺であって前記ポリゴンの内部に存在する辺の中点を連結することによりライン状のデータを生成するラインデータ生成機能と
を有することを特徴とする地図生成装置。
【請求項２】
前記制御部は、前記任意の初期点として、分割される複数のポリゴンにおける前記構成点の数が略同一となる点を選択する初期点選択機能を更に有することを特徴とする請求項１に記載の地図生成装置。
【請求項３】
前記制御部は、前記構成点の数を間引く間引き機能を更に有することを特徴とする請求項１又は請求項２に記載の地図生成装置。
【請求項４】
前記制御部は、前記ポリゴンの幅に関する情報に基づいて該ポリゴンをライン状に変換するか否か決定する判断機能を更に有することを特徴とする請求項１〜３のうち何れか一項に記載の地図生成装置。
【請求項５】
コンピュータが、
記憶部に記憶されている電子地図データに含まれる地物を表現するための複数の構成点を頂点とするポリゴンについて、前記構成点における任意の初期点を頂点として含む三角形であってドロネー三角形分割手法を用いて算出された三角形により分割するとともに、前記三角形により分割された複数のポリゴンをドロネー三角形分割手法を用いて算出された三角形により、分割される全てのポリゴンの形状が三角形になるまで、再帰的に分割する分割工程と、
算出された前記三角形を構成する辺であって前記ポリゴンの内部に存在する辺の中点を連結することによりライン状のデータを生成するラインデータ生成機能と、
前記ライン状のデータで表される地物が含まれる所定範囲の地図を生成する地図生成工程と
を実行することを特徴とする地図生成方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１１−３３９８７（Ｐ２０１１−３３９８７Ａ）
【公開日】平成２３年２月１７日（２０１１．２．１７）
【国際特許分類】
【出願番号】特願２００９−１８２５６９（Ｐ２００９−１８２５６９）
【出願日】平成２１年８月５日（２００９．８．５）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 研究集会名 熊本大学大学院自然科学研究科博士前期課程情報電気電子工学専攻・複合新領域科学専攻 平成２０年度修士論文試問会 主催者名 国立大学法人熊本大学 開催日 平成２１年２月６日
【出願人】（５０４１５９２３５）国立大学法人 熊本大学 (314)
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
【公開日】平成２３年２月１７日（２０１１．２．１７）
【国際特許分類】
【出願日】平成２１年８月５日（２００９．８．５）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 研究集会名 熊本大学大学院自然科学研究科博士前期課程情報電気電子工学専攻・複合新領域科学専攻 平成２０年度修士論文試問会 主催者名 国立大学法人熊本大学 開催日 平成２１年２月６日
【出願人】（５０４１５９２３５）国立大学法人 熊本大学 (314)
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
[ Back to top ]