地表面ポリゴン生成方法
【課題】 自然な３次元表示を実現可能な地表面ポリゴンデータを提供する。
【解決手段】 地表面ポリゴンデータ生成装置としての端末１００は、一定間隔の矩形状格子で、各地点の標高を与える地表面データ２０２を入力する。端末１００は、地表面データの矩形状の各格子を対角線で分割して三角形の地表面ポリゴンデータを生成する。この際、各格子の２本の対角線のうち、両端の標高差が小さい側を選択する。こうすることにより、斜面上の格子についても、稜線ではなく、等高線に比較的沿う方向に分割されることになる。従って、３次元表示時に不自然な稜線が表れることを抑制できる。
【解決手段】 地表面ポリゴンデータ生成装置としての端末１００は、一定間隔の矩形状格子で、各地点の標高を与える地表面データ２０２を入力する。端末１００は、地表面データの矩形状の各格子を対角線で分割して三角形の地表面ポリゴンデータを生成する。この際、各格子の２本の対角線のうち、両端の標高差が小さい側を選択する。こうすることにより、斜面上の格子についても、稜線ではなく、等高線に比較的沿う方向に分割されることになる。従って、３次元表示時に不自然な稜線が表れることを抑制できる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、地表面を３次元表示するための三角形ポリゴンデータの生成方法に関する。
【背景技術】
【０００２】
電子地図データを利用して地表面および建物の３次元表示が実現されている。地表面の標高データは、５０ｍなど一定間隔で用意された四角形のメッシュの交点で与えられることが多い。これら４点は、必ずしも同一平面上に存在するとは限らないため、平面ポリゴンを用いて３次元表示を行う都合上、地表面の３次元表示には、地表面を三角形に分割した三角形ポリゴンが利用される。分割方法として、例えば、特許文献１には、「四角形各々について、２本の対角線のうち、標高差がより大きい方の１本を選択して結び、当該四角形各々を２つずつの三角形に分割」する方法が開示されている。
【０００３】
【特許文献１】特許第３３７６８６８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
上述の通り、従来技術は、標高差が大きい方の対角線を利用する。これは、例えば、地表面が斜面となっている場合、四角形ポリゴンをその稜線に沿って分割することとほぼ同義となる。しかし、この分割方法では、地表面の３次元表示が不自然となる恐れがあることが見いだされた。図８は従来技術による３次元表示例を示す説明図である。山の傾斜地に建築された建物および道路Ｒｐを示した。従来技術では、稜線に沿ってポリゴンが分割される結果、等高線に沿うように走る道路Ｒｐ上に、図示する通り、稜線Ｌｐが顕著に現れる。また、建物の設置部Ｂｐは地面に埋まっているかのように表示されることがある。本発明は、かかる課題を解決し、自然な３次元表示を実現可能な地表面ポリゴンデータの生成技術を提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明のポリゴンデータ生成装置は、以下の手順で、地表面を３次元表示するための三角形ポリゴンデータを生成する。ポリゴンデータ生成装置は、複数の格子点について、位置および標高を記録した地表面データを入力する。そして、複数の格子点から順次、４点を処理対象として特定する。但しこの４点は、内部に他の格子点を含まない四角形を形成できるように特定する。次に、ポリゴンデータ生成装置は、特定された４点で形成される四角形の２本の対角線のうち、両端の標高差が小さい側の対角線で四角形を分割することで、２つの三角形ポリゴンデータを生成する。
【０００６】
本発明によれば、従来技術とは逆に、標高差が小さい側の対角線を採用する。こうすることにより、斜面上の四角形ポリゴンについても、稜線ではなく、等高線に比較的沿う方向に分割されることになる。従って、道路を横断して稜線が表れるなど、不自然な表示を回避することが可能となる。
【０００７】
本発明は、非構造格子の格子点、および構造格子の格子点のいずれを対象としてもよい。後者の例としては、例えば、矩形の構造格子を用いることができる。かかる構造格子としては、５０ｍなど、一定距離間隔の正方形メッシュが挙げられる。かかる構造格子について、各格子の４頂点を対象としてポリゴンの分割を行えば、処理の簡略化を図ることができる。
【０００８】
四角形を分割する際、２本の対角線に対する標高差の差違が所定値以下の場合、例えば、ほぼ同値の場合が生じ得る。かかる場合には、いずれか一本をランダムに選んでも差し支えないし、一定の規則に従って選んでもよい。後者の例として、例えば、四角形に隣接する格子の境界線との連続性が高い側の対角線を選択してもよい。連続性は、種々の態様で評価することができる。例えば、対角線を、他のポリゴンの境界線上にある限り、処理対象となっている四角形外に延長し、その長さで評価する方法を採ることができる。別の方法として、対角線の端が、隣接する四角形ポリゴンを分割した対角線と、接続されている場合に１点、接続されていない場合に０点というように、点数評価してもよい。これらの方法によって、格子を分割する境界線の連続性を考慮することにより、さらに自然な３次元表示を実現することが可能となる。
【０００９】
本発明においては、必ずしも全格子について、上述の分割方法を適用する必要はない。地図内には、山間部など、稜線を強調して３次元表示した方が好ましい領域も存在する。従って、各格子点がこのように稜線を強調すべき領域に存在するか否かを判断するために使用する領域属性データを用意して、複数種類の分割方法を使い分けても良い。領域属性データは、例えば、各格子点に対応づけて設定してもよいし、２次元の地図データのように地表面データとは別のデータベースとして用意してもよい。ポリゴンデータ生成装置は、この属性データに基づいて、処理対象となる四角形が、稜線を強調すべき領域に存在すると判断される場合には、対角線のうち両端の標高差が大きい側の対角線で分割することで稜線を強調する。その他の場合には、上述の分割処理を適用してもよいし、更に、異種の分割処理を設け、条件によって使い分けるようにしてもよい。
【００１０】
本発明は、上述した特徴を全て備えている必要はなく、一部を省略したり適宜、組み合わせたりしてもよい。本発明は、ポリゴンデータ生成装置としての態様の他、コンピュータによってポリゴンデータを生成するポリゴンデータ生成方法として構成してもよい。また、かかる処理をコンピュータに実現させるためのコンピュータプログラム、このコンピュータプログラムを記録したコンピュータ読み取り可能な記録媒体として構成してもよい。ポリゴンデータ生成装置として構成する場合、スタンドアロンで稼働する装置としてもよいし、端末とサーバとをネットワークで接続して構成してもよい。記録媒体としては、フレキシブルディスク、ＣＤ−ＲＯＭ、光磁気ディスク、ＩＣカード、ＲＯＭカートリッジ、パンチカード、バーコードなどの符号が印刷された印刷物、コンピュータの内部記憶装置（ＲＡＭやＲＯＭなどのメモリ）および外部記憶装置等、コンピュータが読取り可能な種々の媒体を利用できる。
【発明を実施するための最良の形態】
【００１１】
本発明の実施例について以下の順序で説明する。
Ａ．システム構成：
Ｂ．地表面データ：
Ｃ．地表面ポリゴンデータ生成処理：
Ｃ１．分割処理：
Ｃ２．稜線強調処理：
Ｃ３．分割処理の変形例：
Ｄ．効果：
【００１２】
Ａ．システム構成：
図１は実施例としてのポリゴンデータ生成システムの全体構成を示す説明図である。実施例の経路案内システムは、ポリゴンデータ生成装置として機能する端末１００と、種々のデータベースを提供するための各種サーバをネットワークＮＥＴで接続することで構成される。ネットワークＮＥＴは、ＬＡＮやイントラネットのように限定的なものであってもよいし、インターネットのように広域的なものであってもよい。
【００１３】
サーバによって提供されるデータベースとしては、地表面データ２０２、２次元地図ＤＢ２０４、３次元地図ＤＢ２１０が挙げられる。地表面データ２０２は、５０ｍメッシュで各地点の標高を与えるデータである。２次元地図ＤＢ２０４は、２次元地図を表示するためのデータであり、地形、地物を表すポリゴンデータおよび属性データを格納している。３次元地図ＤＢ２１０は、地図の３次元表示を行うためのデータベースであり、地表面ポリゴンデータ２１２、地物ポリゴンデータ２１４を含む。地表面ポリゴンデータ２１２は、地表面を３次元的に表示するためのデータであり、端末１００によって生成される。地物ポリゴンデータ２１４は、道路、建物その他の地物を３次元表示するためのデータである。本実施例では、地物ポリゴンデータ２１４は、予め用意されているものとして説明する。
【００１４】
図中に端末１００の機能ブロックを併せて示した。本実施例では、これらの機能ブロックは、端末１００にインストールされた所定のコンピュータプログラムをＣＰＵが実行することにより、ソフトウェア的に構成される。機能ブロックの少なくとも一部を、ハードウェア的に実現しても構わない。
【００１５】
コマンド入力部１０２は、端末１００のキーボード、マウスなどに対するユーザの操作に基づいてコマンドを入力する。データ入出力部１０４は、ネットワークＮＥＴを介して、各種データベースとデータの授受を行う。地図表示部１１２は、３次元地図ＤＢ２１０に基づき、端末１００上に、地図を３次元表示する。
【００１６】
地表面ポリゴンデータ２１２の生成は、領域判定部１０６、分割処理部１０８、稜線強調処理部１１０によって実現される。領域判定部１０６は、地表面データ２０２の各地点の地形を判断し分割処理部１０８、稜線強調処理部１１０のいずれを使うか判断する。分割処理部１０８および稜線強調処理部１１０は、それぞれ地表面データ２０２を三角形のポリゴンに分割する。両者は、分割処理の方法が異なる。分割処理部１０８および稜線強調処理部１１０それぞれの分割処理の内容については後述する。こうして生成された地表面ポリゴンデータ２１２は、データ入出力部１０４によって、３次元地図ＤＢ２１０の地表面ポリゴンデータ２１２に格納される。
【００１７】
端末１００には、更に、地物ポリゴンデータ２１４を生成するための機能ブロックなどを用意してもよい。また、分割処理を行うために、分割処理部１０８、稜線強調処理部１１０以外の機能ブロックを設け、領域判定部１０６が、３者以上の使い分けを制御するようにしてもよい。逆に、稜線強調処理部１１０を省略し、全地点について、分割処理部１０８を適用するようにしてもよい。この構成では、領域判定部１０６を省略することも可能である。
【００１８】
Ｂ．地表面データ：
図２は地表面データ２０２の構造を示す説明図である。説明の便宜上、２次元地図ＤＢ２０４のデータ例と併せて斜視図的に示した。上側に位置するのが２次元地図ＤＢ２０４のデータであり、下側に位置するのが地表面データ２０２である。
【００１９】
２次元地図ＤＢ２０４は、図示する通り、地形や地物の描画データおよび属性データを記録している。これらのデータの格納には、周知の種々のデータ構造を適用可能であるため、データ構造に関する詳細な説明は省略する。２次元地図ＤＢには、上述の通り属性データが記録されているため、緯度、経度を特定して、２次元地図ＤＢ２０４を参照することにより、各地点について、陸地／海の区別、建造物の有無などを判断することができる。
【００２０】
地表面データ２０２は、図示する通り、一定間隔の矩形状メッシュで構成される。本実施例では、５０ｍ間隔とした。各メッシュは、平面上に定義されたｘ、ｙ座標で規定される。メッシュの格子点を「Ｐ［ｘ方向の番号、ｙ方向の番号］」の形式で表した。各格子点には、３次元の位置情報（緯度、経度、標高）が対応づけられている。例えば、格子点Ｐ［１，０］は、「緯度＝Ｌａｔ，経度＝Ｌｏｎ，標高＝Ｈ」である。標高は、本実施例では、格子点を中心とする５０ｍ四方の領域内における確率的な値を意味している。即ち、この標高値は、格子点の厳密な標高値ではなく、かかる領域内のいずれかの地点における標高値を表すに過ぎない。 本実施例では、地表面データ２０２は、正方形メッシュで規定されているが、ｘ方向、ｙ方向でメッシュの間隔が異なっていても良い。
【００２１】
Ｃ．地表面ポリゴンデータ生成処理：
図３は地表面ポリゴンデータ生成処理のフローチャートである。ユーザのコマンドに従って端末１００のＣＰＵが実行する処理である。この処理が開始されると、ＣＰＵはネットワークＮＥＴ経由で地表面データ２０２を入力し（ステップＳ１０）、以下に示す処理を、全格子について順次実行する（ステップＳ１２〜Ｓ５２）。
【００２２】
まず、ＣＰＵは処理対象となる格子を特定する（ステップＳ１４）。未処理の格子からランダムに特定してもよいし、一定の規則に従って特定してもよい。以下、特定された格子を処理対象格子と呼ぶ。
【００２３】
ＣＰＵは、処理対象格子がどのような領域に存在するかを判断する（ステップＳ１６）。本実施例では、住宅、道路、鉄道などの地物が存在する街領域と、これらの地物が存在しない山間領域に区分するものとした。この判断は、２次元地図ＤＢ２０４の属性データを用いて、以下の手順で行う。図中に判断方法を併せて示した。
【００２４】
ＣＰＵは、処理対象格子Ｐ１の周囲に、一定の直径の円領域Ｃ１を設定する。円領域Ｃ１の半径は任意に設定可能であるが、本実施例では、地表面データ２０２のメッシュ間隔と同値とした。こうして設定された円領域Ｃ１の内部に住宅Ｂ１、道路、鉄道などの地物が存在する場合、ＣＰＵは、処理対象格子は街領域に存在すると判断し、そうでない場合には、山間領域に存在すると判断する。図中の例では、格子Ｐ１は街領域、格子Ｐ２は山間領域にそれぞれ存在することになる。
【００２５】
領域の判断は、この他にも種々の手法を適用可能である。例えば、円領域を設定するまでなく、処理対象格子内に地物が存在するか否かで判断するようにしてもよい。本実施例では、２次元地図ＤＢ２０４を参照して判断したが、各格子点に、街領域、山間領域という属性データを付与しておくようにしてもよい。
【００２６】
ＣＰＵは領域の判断結果に応じて、２通りの方法を使い分けて地表面ポリゴンデータを生成する。山間領域でない場合（ステップＳ１８）、即ち街領域に対しては、分割処理（ステップＳ２０）を適用し、山間領域については稜線強調処理を適用する（ステップＳ４０）。それぞれの処理内容は、後述する。本実施例では、２通りの処理を使い分けているが、更に多くの処理を使い分けるようにしてもよい。逆に、ステップＳ１６，Ｓ１８，Ｓ４０を省略し、全処理対象格子について分割処理（ステップＳ２０）のみを統一的に用いるようにしても差し支えない。
【００２７】
ＣＰＵは、分割処理（ステップＳ２０）、または稜線強調処理（ステップＳ４０）によって生成された地表面ポリゴンデータをネットワークＮＥＴ経由で３次元地図ＤＢ２１０に格納する（ステップ５０）。以上の処理を全格子について実行して（ステップＳ５２）、地表面ポリゴンデータ生成処理を完了する。
【００２８】
Ｃ１．分割処理：
図４は分割処理のフローチャートである。地表面ポリゴンデータ生成処理（図３）のステップＳ２０に相当する処理である。この処理では、矩形の処理対象格子を対角線で分割して、三角形のポリゴンデータを生成する。
【００２９】
ＣＰＵは、処理対象格子の各格子点の標高を入力し（ステップＳ２１）、２本の対角線について両端の標高差ｄｈ１、ｄｈ２を算出する（ステップＳ２２）。図中に算出方法を示した。処理対象格子の各格子点の標高がそれぞれＨ１、Ｈ２、Ｈ３、Ｈ４であるとする。この場合、２本の対角線の標高差は、「ｄｈ１＝｜Ｈ１−Ｈ３｜、ｄｈ２＝｜Ｈ２−Ｈ４｜」で与えられる。
【００３０】
ＣＰＵは、２つの値ｄｈ１、ｄｈ２について、両者の差分の絶対値｜ｄｈ１−ｄｈ２｜と所定の閾値Ｔｈとを比較する（ステップＳ２３）。絶対値｜ｄｈ１−ｄｈ２｜が、閾値Ｔｈより大きい場合には、ＣＰＵは標高差ｄｈ１、ｄｈ２間には有意差が存在すると判断し、標高差が小さい側の対角線で格子を分割する（ステップＳ２４）。例えば、ｄｈ１＞ｄｈ２の時には、ステップＳ２２で示した図中のＨ１、Ｈ３を結ぶ対角線で格子を分割する。逆に、ｄｈ１＜ｄｈ２の時には、Ｈ２、Ｈ４を結ぶ対角線で格子を分割する。ステップＳ２３で用いる閾値Ｔｈは、このように標高差ｄｈ１、ｄｈ２に有意差が存在するか否かの判断基準値であり、任意に設定可能である。Ｔｈを値０に設定すれば、標高差ｄｈ１、ｄｈ２に計算誤差程度の微差がある場合でも、ステップＳ２４の処理が行われることになる。
【００３１】
絶対値｜ｄｈ１−ｄｈ２｜が、閾値Ｔｈ以下の場合（ステップＳ２３）、ＣＰＵは標高差ｄｈ１、ｄｈ２はほぼ同値と判断し、格子の分割に使用すべき対角線を選択するための指標として、各対角線の連続性指標Ｖ１、Ｖ２を設定する（ステップＳ２５）。連続性指標とは、処理対象格子の対角線が、格子外に連続して延伸する程度を表す指標である。本実施例では、延伸可能な長さを指標として用いるものとした。
【００３２】
図中に、連続性指標Ｖ１、Ｖ２の設定方法を例示した。処理対象格子Ｐの２本の対角線ＤＬ１、ＤＬ２を評価する場合を考える。処理対象格子Ｐの周囲における格子、およびその分割に使用された対角線を破線で示した。対角線ＤＬ１は、右下の格子における対角線ＤＬ１１のみと連続している。対角線ＤＬ１の長さを「１」とすれば、延伸可能な長さは「２」となるため、連続性指標Ｖ１は「２」と設定される。対角線ＤＬ２は、右上の対角線ＤＬ２１、および左下の対角線ＤＬ２２と連続している。従って、連続性指標Ｖ２は「３」と設定される。図示した範囲外でも対角線が連続している場合には、連続性指標は、更に大きな値を採り得る。
【００３３】
連続性指標は、種々の設定が可能であり、例えば、処理対象格子に隣接する格子（図示した破線の８個の格子）内でのみ評価するようにしてもよい。この評価方法では、連続する対角線の本数を点数化して評価することができる。例えば、対角線ＤＬ１については、対角線ＤＬ１１のみが連続しているため連続性指標Ｖ１を１点とし、対角線ＤＬ２については連続性指標Ｖ２を２点としてもよい。また、処理対象格子の上下左右に隣接する格子における対角線との平行性を考慮してもよい。例えば、対角線ＤＬ１については、左右および下の対角線が平行となっているため３点、対角線ＤＬ２については上の対角線のみが平行となっているため１点と評価し、この評価値を加味して、連続性指標を設定するようにしてもよい。
【００３４】
ＣＰＵは、こうして設定された連続性指標に基づき、その値が大きい側の対角線で格子を分割する（ステップＳ２６）。こうすることにより、格子の境界線が比較的広域にわたって連続するため、地表面について、より自然な３次元表示を実現することが可能となる。
【００３５】
分割処理は、種々の方法を採ることができ、例えば、標高差ｄｈ１、ｄｈ２がほぼ同値と判断できる場合（ステップＳ２３：ＹＥＳ）、２本の対角線のいずれか一方を、ランダムに選択するようにしても良い。連続性指標は、処理対象格子の対角線が必ずしも直線状に延伸可能な程度を評価するものである必要はなく、地表面データ２０２が、非構造格子で与えられている場合には、折れ線状に延伸可能な長さに基づいて連続性指標を設定してもよい。
【００３６】
Ｃ２．稜線強調処理：
地表面ポリゴンデータ生成処理（図３）における稜線強調処理（ステップＳ４０）は、上述した分割処理（図４）のステップＳ２４において、選択する対角線を逆転させた処理である。即ち、稜線強調処理では、ＣＰＵは、２本の対角線の標高差ｄｈ１、ｄｈ２に有意差が存在する場合には、標高差が大きい側の対角線で格子を分割する。
【００３７】
標高差ｄｈ１、ｄｈ２がほぼ同値と判断される場合には、稜線強調処理においても、分割処理と同様の処理を実行する（図４のステップＳ２５、Ｓ２６）。ただし、これらの処理についても分割処理と逆の選択を行い、ステップＳ２６で、連続性指標が小さい側の対角線で格子を分割するようにしてもよい。
【００３８】
Ｃ３．分割処理の変形例：
格子を分割する対角線の選択方法としては、対角線両端の標高差ｄｈ１、ｄｈ２に代えて、対角線で仮に分割した場合に生成される三角形ポリゴンの法線長さを利用した方法が挙げられる。かかる選択方法について変形例として説明する。この選択方法は、図４のステップＳ２２、Ｓ２３に代わる処理である。
【００３９】
図５は三角形ポリゴンの法線を用いた対角線の選択方法を示す説明図である。処理対象格子の格子点Ｐ０、Ｐ１、Ｐ２、Ｐ３を、平面上の位置座標ｘ、ｙおよび標高ｈに従って斜視図で示した。処理対象格子を対角線Ｐ１Ｐ３で分割したとすれば、三角形Ｐ０Ｐ１Ｐ３、Ｐ２Ｐ１Ｐ３という２つの三角形ポリゴンが生成される。これらの各三角形ポリゴンについては、正規化された法線ベクトルＮ１，Ｎ２を求めることができる。また、各法線ベクトルＮ１、Ｎ２のｘｙ平面上の成分をＮ１ｘｙ、Ｎ２ｘｙとする。三角形ポリゴンの地表面からの傾きが大きいほど、この成分値は大きくなる。変形例では、この成分値の和、即ち「Ｎ１ｘｙ＋Ｎ２ｘｙ」を標高差に代わる評価値として用いる。
【００４０】
図５中では、対角線Ｐ１Ｐ３で格子を分割した状態を例示したが、対角線Ｐ０Ｐ２で分割した状態についても、同様にして法線およびｘｙ平面上の成分を求めることができる。この法線に基づいて得られる評価値を「Ｎ３ｘｙ＋Ｎ４ｘｙ」とする。
【００４１】
変形例では、こうして得られた評価値に基づいて、格子の分割に使用すべき対角線を選択する。分割処理（図４）においては、ステップＳ２４では、評価値が小さくなる側の対角線を選択し、稜線強調処理では、評価値が大きくなる側の対角線を選択する。
【００４２】
変形例において、対角線Ｐ１Ｐ３で格子を分割した状態についての評価値は、各法線ベクトルＮ１、Ｎ２のｘｙ平面上の成分Ｎ１ｘｙ、Ｎ２ｘｙのうち大きい側を用いるようにしてもよい。対角線Ｐ０Ｐ２で分割した状態についての評価値は、法線およびｘｙ平面上の成分Ｎ３ｘｙ、Ｎ４ｘｙのうち大きい側を用いることになる。そして、分割処理では、こうして得られた評価値の小さい方に対応する対角線を用いる。このように、分割処理においては、対角線の両端の標高差が小さい側の対角線を選択するのと、同等の選択基準となる種々の手法を適用することができる。
【００４３】
Ｄ．効果：
図６は本実施例に基づく地表面の３次元表示例を示す説明図である。山の傾斜地に建築された建物および道路Ｒｐを示した。従来技術による表示（図８）と異なり、本実施例による地表面ポリゴンデータを用いた場合には、道路Ｒｄを横断する稜線が顕著には表れない。このように本実施例の地表面ポリゴンデータ生成システムによれば、地表面の３次元表示における不自然さを抑制することができる。
【００４４】
実施例では、街領域と山間領域で分割処理と稜線強調処理を使い分けた。かかる使い分けは本実施例に必須ではないが、このような使い分けをすることにより、地物が存在する街領域では、不自然な稜線が表れることを抑制しつつ（図６参照）、山間領域では、稜線を強調した３次元表示を行うことが可能となる。
【００４５】
Ｅ．第２実施例：
第１実施例では、正方形の構造格子で与えられた地表面データ２０２を用いて地表面ポリゴンデータを生成する例を示した。本実施例は、非構造格子で与えられる地表面データにも適用可能である。かかる例について、第２実施例で説明する。
【００４６】
図７は第２実施例としての地表面ポリゴンデータ生成処理のフローチャートである。第１実施例と同様、端末１００のＣＰＵが実行する処理に相当する。処理が開始されると、ＣＰＵは、地表面データを入力する（ステップＳ１００）。この例では、地表面データは、非構造格子で与えられているものとする。
【００４７】
ＣＰＵは、入力された全格子点について、以下の手順で地表面ポリゴンデータを生成する処理を実行する（ステップＳ１０２〜Ｓ１１２）。まず、ＣＰＵはデローニ分割処理により、地表面の三角形ポリゴンへの分割を試みる（ステップＳ１０４）。デローニ分割とは、非構造格子を規定するための数値幾何学上周知の処理である。
【００４８】
図中に、デローニ分割処理の方法を示した。黒丸が格子点を表している。デローニ分割では、これらの格子点の３点以上を通過する円を見つけ出す。但し、図中の円Ｃｄ２に示すように、他の格子点を内部に含む円は除外する。円Ｃｄ１、Ｃｄ３のように内部に他の格子点を含まない円（以下、「空円」と呼ぶ）を見いだす。円Ｃｄ３のように、４点以上の格子点を通過する状態を縮退と呼ぶ。
【００４９】
ＣＰＵは、空円の設定結果に基づき、縮退が生じているか否かを判断する（ステップＳ１０６）。縮退が生じていない場合には、空円上の３点によって三角形の地表面ポリゴンデータを生成、格納する（ステップＳ１１０）。縮退が生じている場合には、三角形が一義的に規定できないため、分割処理を行って（ステップＳ１０８）、地表面ポリゴンデータを生成、格納する（ステップＳ１１０）。
【００５０】
この分割処理には、第１実施例（図４）と同じ処理を適用できる。ステップＳ１０６とステップＳ１０８の間に、第１実施例における地表面ポリゴンデータ生成処理（図３）のステップＳ１６，Ｓ１８の処理を適用し、分割処理、稜線強調処理の使い分けを行っても良い。
【００５１】
第２実施例において、５点以上が空円上に存在する縮退が生じた場合には、例えば、いずれかの対角線によって四角形に分割した後、分割処理（ステップＳ１０８）を実行すればよい。この際、対角線はランダムに選択してもよいし、標高差が最小となる対角線を選択するようにしてもよい。
【００５２】
以上で説明した第２実施例によれば、第１実施例と同様、非構造格子についても、自然な３次元表示を行うことが可能な地表面ポリゴンデータを生成することができる。
【図面の簡単な説明】
【００５３】
【図１】実施例としてのポリゴンデータ生成システムの全体構成を示す説明図である。
【図２】地表面データ２０２の構造を示す説明図である。
【図３】地表面ポリゴンデータ生成処理のフローチャートである。
【図４】分割処理のフローチャートである。
【図５】三角形ポリゴンの法線を用いた対角線の選択方法を示す説明図である。
【図６】本実施例に基づく地表面の３次元表示例を示す説明図である。
【図７】第２実施例としての地表面ポリゴンデータ生成処理のフローチャートである。
【図８】従来技術による３次元表示例を示す説明図である。
【符号の説明】
【００５４】
１００…端末
１０２…コマンド入力部
１０４…データ入出力部
１０６…領域判定部
１０８…分割処理部
１１０…稜線強調処理部
１１２…地図表示部
２０２…地表面データ
２０４…２次元地図ＤＢ
２１０…３次元地図ＤＢ
２１２…地表面ポリゴンデータ
２１４…地物ポリゴンデータ
【技術分野】
【０００１】
本発明は、地表面を３次元表示するための三角形ポリゴンデータの生成方法に関する。
【背景技術】
【０００２】
電子地図データを利用して地表面および建物の３次元表示が実現されている。地表面の標高データは、５０ｍなど一定間隔で用意された四角形のメッシュの交点で与えられることが多い。これら４点は、必ずしも同一平面上に存在するとは限らないため、平面ポリゴンを用いて３次元表示を行う都合上、地表面の３次元表示には、地表面を三角形に分割した三角形ポリゴンが利用される。分割方法として、例えば、特許文献１には、「四角形各々について、２本の対角線のうち、標高差がより大きい方の１本を選択して結び、当該四角形各々を２つずつの三角形に分割」する方法が開示されている。
【０００３】
【特許文献１】特許第３３７６８６８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
上述の通り、従来技術は、標高差が大きい方の対角線を利用する。これは、例えば、地表面が斜面となっている場合、四角形ポリゴンをその稜線に沿って分割することとほぼ同義となる。しかし、この分割方法では、地表面の３次元表示が不自然となる恐れがあることが見いだされた。図８は従来技術による３次元表示例を示す説明図である。山の傾斜地に建築された建物および道路Ｒｐを示した。従来技術では、稜線に沿ってポリゴンが分割される結果、等高線に沿うように走る道路Ｒｐ上に、図示する通り、稜線Ｌｐが顕著に現れる。また、建物の設置部Ｂｐは地面に埋まっているかのように表示されることがある。本発明は、かかる課題を解決し、自然な３次元表示を実現可能な地表面ポリゴンデータの生成技術を提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明のポリゴンデータ生成装置は、以下の手順で、地表面を３次元表示するための三角形ポリゴンデータを生成する。ポリゴンデータ生成装置は、複数の格子点について、位置および標高を記録した地表面データを入力する。そして、複数の格子点から順次、４点を処理対象として特定する。但しこの４点は、内部に他の格子点を含まない四角形を形成できるように特定する。次に、ポリゴンデータ生成装置は、特定された４点で形成される四角形の２本の対角線のうち、両端の標高差が小さい側の対角線で四角形を分割することで、２つの三角形ポリゴンデータを生成する。
【０００６】
本発明によれば、従来技術とは逆に、標高差が小さい側の対角線を採用する。こうすることにより、斜面上の四角形ポリゴンについても、稜線ではなく、等高線に比較的沿う方向に分割されることになる。従って、道路を横断して稜線が表れるなど、不自然な表示を回避することが可能となる。
【０００７】
本発明は、非構造格子の格子点、および構造格子の格子点のいずれを対象としてもよい。後者の例としては、例えば、矩形の構造格子を用いることができる。かかる構造格子としては、５０ｍなど、一定距離間隔の正方形メッシュが挙げられる。かかる構造格子について、各格子の４頂点を対象としてポリゴンの分割を行えば、処理の簡略化を図ることができる。
【０００８】
四角形を分割する際、２本の対角線に対する標高差の差違が所定値以下の場合、例えば、ほぼ同値の場合が生じ得る。かかる場合には、いずれか一本をランダムに選んでも差し支えないし、一定の規則に従って選んでもよい。後者の例として、例えば、四角形に隣接する格子の境界線との連続性が高い側の対角線を選択してもよい。連続性は、種々の態様で評価することができる。例えば、対角線を、他のポリゴンの境界線上にある限り、処理対象となっている四角形外に延長し、その長さで評価する方法を採ることができる。別の方法として、対角線の端が、隣接する四角形ポリゴンを分割した対角線と、接続されている場合に１点、接続されていない場合に０点というように、点数評価してもよい。これらの方法によって、格子を分割する境界線の連続性を考慮することにより、さらに自然な３次元表示を実現することが可能となる。
【０００９】
本発明においては、必ずしも全格子について、上述の分割方法を適用する必要はない。地図内には、山間部など、稜線を強調して３次元表示した方が好ましい領域も存在する。従って、各格子点がこのように稜線を強調すべき領域に存在するか否かを判断するために使用する領域属性データを用意して、複数種類の分割方法を使い分けても良い。領域属性データは、例えば、各格子点に対応づけて設定してもよいし、２次元の地図データのように地表面データとは別のデータベースとして用意してもよい。ポリゴンデータ生成装置は、この属性データに基づいて、処理対象となる四角形が、稜線を強調すべき領域に存在すると判断される場合には、対角線のうち両端の標高差が大きい側の対角線で分割することで稜線を強調する。その他の場合には、上述の分割処理を適用してもよいし、更に、異種の分割処理を設け、条件によって使い分けるようにしてもよい。
【００１０】
本発明は、上述した特徴を全て備えている必要はなく、一部を省略したり適宜、組み合わせたりしてもよい。本発明は、ポリゴンデータ生成装置としての態様の他、コンピュータによってポリゴンデータを生成するポリゴンデータ生成方法として構成してもよい。また、かかる処理をコンピュータに実現させるためのコンピュータプログラム、このコンピュータプログラムを記録したコンピュータ読み取り可能な記録媒体として構成してもよい。ポリゴンデータ生成装置として構成する場合、スタンドアロンで稼働する装置としてもよいし、端末とサーバとをネットワークで接続して構成してもよい。記録媒体としては、フレキシブルディスク、ＣＤ−ＲＯＭ、光磁気ディスク、ＩＣカード、ＲＯＭカートリッジ、パンチカード、バーコードなどの符号が印刷された印刷物、コンピュータの内部記憶装置（ＲＡＭやＲＯＭなどのメモリ）および外部記憶装置等、コンピュータが読取り可能な種々の媒体を利用できる。
【発明を実施するための最良の形態】
【００１１】
本発明の実施例について以下の順序で説明する。
Ａ．システム構成：
Ｂ．地表面データ：
Ｃ．地表面ポリゴンデータ生成処理：
Ｃ１．分割処理：
Ｃ２．稜線強調処理：
Ｃ３．分割処理の変形例：
Ｄ．効果：
【００１２】
Ａ．システム構成：
図１は実施例としてのポリゴンデータ生成システムの全体構成を示す説明図である。実施例の経路案内システムは、ポリゴンデータ生成装置として機能する端末１００と、種々のデータベースを提供するための各種サーバをネットワークＮＥＴで接続することで構成される。ネットワークＮＥＴは、ＬＡＮやイントラネットのように限定的なものであってもよいし、インターネットのように広域的なものであってもよい。
【００１３】
サーバによって提供されるデータベースとしては、地表面データ２０２、２次元地図ＤＢ２０４、３次元地図ＤＢ２１０が挙げられる。地表面データ２０２は、５０ｍメッシュで各地点の標高を与えるデータである。２次元地図ＤＢ２０４は、２次元地図を表示するためのデータであり、地形、地物を表すポリゴンデータおよび属性データを格納している。３次元地図ＤＢ２１０は、地図の３次元表示を行うためのデータベースであり、地表面ポリゴンデータ２１２、地物ポリゴンデータ２１４を含む。地表面ポリゴンデータ２１２は、地表面を３次元的に表示するためのデータであり、端末１００によって生成される。地物ポリゴンデータ２１４は、道路、建物その他の地物を３次元表示するためのデータである。本実施例では、地物ポリゴンデータ２１４は、予め用意されているものとして説明する。
【００１４】
図中に端末１００の機能ブロックを併せて示した。本実施例では、これらの機能ブロックは、端末１００にインストールされた所定のコンピュータプログラムをＣＰＵが実行することにより、ソフトウェア的に構成される。機能ブロックの少なくとも一部を、ハードウェア的に実現しても構わない。
【００１５】
コマンド入力部１０２は、端末１００のキーボード、マウスなどに対するユーザの操作に基づいてコマンドを入力する。データ入出力部１０４は、ネットワークＮＥＴを介して、各種データベースとデータの授受を行う。地図表示部１１２は、３次元地図ＤＢ２１０に基づき、端末１００上に、地図を３次元表示する。
【００１６】
地表面ポリゴンデータ２１２の生成は、領域判定部１０６、分割処理部１０８、稜線強調処理部１１０によって実現される。領域判定部１０６は、地表面データ２０２の各地点の地形を判断し分割処理部１０８、稜線強調処理部１１０のいずれを使うか判断する。分割処理部１０８および稜線強調処理部１１０は、それぞれ地表面データ２０２を三角形のポリゴンに分割する。両者は、分割処理の方法が異なる。分割処理部１０８および稜線強調処理部１１０それぞれの分割処理の内容については後述する。こうして生成された地表面ポリゴンデータ２１２は、データ入出力部１０４によって、３次元地図ＤＢ２１０の地表面ポリゴンデータ２１２に格納される。
【００１７】
端末１００には、更に、地物ポリゴンデータ２１４を生成するための機能ブロックなどを用意してもよい。また、分割処理を行うために、分割処理部１０８、稜線強調処理部１１０以外の機能ブロックを設け、領域判定部１０６が、３者以上の使い分けを制御するようにしてもよい。逆に、稜線強調処理部１１０を省略し、全地点について、分割処理部１０８を適用するようにしてもよい。この構成では、領域判定部１０６を省略することも可能である。
【００１８】
Ｂ．地表面データ：
図２は地表面データ２０２の構造を示す説明図である。説明の便宜上、２次元地図ＤＢ２０４のデータ例と併せて斜視図的に示した。上側に位置するのが２次元地図ＤＢ２０４のデータであり、下側に位置するのが地表面データ２０２である。
【００１９】
２次元地図ＤＢ２０４は、図示する通り、地形や地物の描画データおよび属性データを記録している。これらのデータの格納には、周知の種々のデータ構造を適用可能であるため、データ構造に関する詳細な説明は省略する。２次元地図ＤＢには、上述の通り属性データが記録されているため、緯度、経度を特定して、２次元地図ＤＢ２０４を参照することにより、各地点について、陸地／海の区別、建造物の有無などを判断することができる。
【００２０】
地表面データ２０２は、図示する通り、一定間隔の矩形状メッシュで構成される。本実施例では、５０ｍ間隔とした。各メッシュは、平面上に定義されたｘ、ｙ座標で規定される。メッシュの格子点を「Ｐ［ｘ方向の番号、ｙ方向の番号］」の形式で表した。各格子点には、３次元の位置情報（緯度、経度、標高）が対応づけられている。例えば、格子点Ｐ［１，０］は、「緯度＝Ｌａｔ，経度＝Ｌｏｎ，標高＝Ｈ」である。標高は、本実施例では、格子点を中心とする５０ｍ四方の領域内における確率的な値を意味している。即ち、この標高値は、格子点の厳密な標高値ではなく、かかる領域内のいずれかの地点における標高値を表すに過ぎない。 本実施例では、地表面データ２０２は、正方形メッシュで規定されているが、ｘ方向、ｙ方向でメッシュの間隔が異なっていても良い。
【００２１】
Ｃ．地表面ポリゴンデータ生成処理：
図３は地表面ポリゴンデータ生成処理のフローチャートである。ユーザのコマンドに従って端末１００のＣＰＵが実行する処理である。この処理が開始されると、ＣＰＵはネットワークＮＥＴ経由で地表面データ２０２を入力し（ステップＳ１０）、以下に示す処理を、全格子について順次実行する（ステップＳ１２〜Ｓ５２）。
【００２２】
まず、ＣＰＵは処理対象となる格子を特定する（ステップＳ１４）。未処理の格子からランダムに特定してもよいし、一定の規則に従って特定してもよい。以下、特定された格子を処理対象格子と呼ぶ。
【００２３】
ＣＰＵは、処理対象格子がどのような領域に存在するかを判断する（ステップＳ１６）。本実施例では、住宅、道路、鉄道などの地物が存在する街領域と、これらの地物が存在しない山間領域に区分するものとした。この判断は、２次元地図ＤＢ２０４の属性データを用いて、以下の手順で行う。図中に判断方法を併せて示した。
【００２４】
ＣＰＵは、処理対象格子Ｐ１の周囲に、一定の直径の円領域Ｃ１を設定する。円領域Ｃ１の半径は任意に設定可能であるが、本実施例では、地表面データ２０２のメッシュ間隔と同値とした。こうして設定された円領域Ｃ１の内部に住宅Ｂ１、道路、鉄道などの地物が存在する場合、ＣＰＵは、処理対象格子は街領域に存在すると判断し、そうでない場合には、山間領域に存在すると判断する。図中の例では、格子Ｐ１は街領域、格子Ｐ２は山間領域にそれぞれ存在することになる。
【００２５】
領域の判断は、この他にも種々の手法を適用可能である。例えば、円領域を設定するまでなく、処理対象格子内に地物が存在するか否かで判断するようにしてもよい。本実施例では、２次元地図ＤＢ２０４を参照して判断したが、各格子点に、街領域、山間領域という属性データを付与しておくようにしてもよい。
【００２６】
ＣＰＵは領域の判断結果に応じて、２通りの方法を使い分けて地表面ポリゴンデータを生成する。山間領域でない場合（ステップＳ１８）、即ち街領域に対しては、分割処理（ステップＳ２０）を適用し、山間領域については稜線強調処理を適用する（ステップＳ４０）。それぞれの処理内容は、後述する。本実施例では、２通りの処理を使い分けているが、更に多くの処理を使い分けるようにしてもよい。逆に、ステップＳ１６，Ｓ１８，Ｓ４０を省略し、全処理対象格子について分割処理（ステップＳ２０）のみを統一的に用いるようにしても差し支えない。
【００２７】
ＣＰＵは、分割処理（ステップＳ２０）、または稜線強調処理（ステップＳ４０）によって生成された地表面ポリゴンデータをネットワークＮＥＴ経由で３次元地図ＤＢ２１０に格納する（ステップ５０）。以上の処理を全格子について実行して（ステップＳ５２）、地表面ポリゴンデータ生成処理を完了する。
【００２８】
Ｃ１．分割処理：
図４は分割処理のフローチャートである。地表面ポリゴンデータ生成処理（図３）のステップＳ２０に相当する処理である。この処理では、矩形の処理対象格子を対角線で分割して、三角形のポリゴンデータを生成する。
【００２９】
ＣＰＵは、処理対象格子の各格子点の標高を入力し（ステップＳ２１）、２本の対角線について両端の標高差ｄｈ１、ｄｈ２を算出する（ステップＳ２２）。図中に算出方法を示した。処理対象格子の各格子点の標高がそれぞれＨ１、Ｈ２、Ｈ３、Ｈ４であるとする。この場合、２本の対角線の標高差は、「ｄｈ１＝｜Ｈ１−Ｈ３｜、ｄｈ２＝｜Ｈ２−Ｈ４｜」で与えられる。
【００３０】
ＣＰＵは、２つの値ｄｈ１、ｄｈ２について、両者の差分の絶対値｜ｄｈ１−ｄｈ２｜と所定の閾値Ｔｈとを比較する（ステップＳ２３）。絶対値｜ｄｈ１−ｄｈ２｜が、閾値Ｔｈより大きい場合には、ＣＰＵは標高差ｄｈ１、ｄｈ２間には有意差が存在すると判断し、標高差が小さい側の対角線で格子を分割する（ステップＳ２４）。例えば、ｄｈ１＞ｄｈ２の時には、ステップＳ２２で示した図中のＨ１、Ｈ３を結ぶ対角線で格子を分割する。逆に、ｄｈ１＜ｄｈ２の時には、Ｈ２、Ｈ４を結ぶ対角線で格子を分割する。ステップＳ２３で用いる閾値Ｔｈは、このように標高差ｄｈ１、ｄｈ２に有意差が存在するか否かの判断基準値であり、任意に設定可能である。Ｔｈを値０に設定すれば、標高差ｄｈ１、ｄｈ２に計算誤差程度の微差がある場合でも、ステップＳ２４の処理が行われることになる。
【００３１】
絶対値｜ｄｈ１−ｄｈ２｜が、閾値Ｔｈ以下の場合（ステップＳ２３）、ＣＰＵは標高差ｄｈ１、ｄｈ２はほぼ同値と判断し、格子の分割に使用すべき対角線を選択するための指標として、各対角線の連続性指標Ｖ１、Ｖ２を設定する（ステップＳ２５）。連続性指標とは、処理対象格子の対角線が、格子外に連続して延伸する程度を表す指標である。本実施例では、延伸可能な長さを指標として用いるものとした。
【００３２】
図中に、連続性指標Ｖ１、Ｖ２の設定方法を例示した。処理対象格子Ｐの２本の対角線ＤＬ１、ＤＬ２を評価する場合を考える。処理対象格子Ｐの周囲における格子、およびその分割に使用された対角線を破線で示した。対角線ＤＬ１は、右下の格子における対角線ＤＬ１１のみと連続している。対角線ＤＬ１の長さを「１」とすれば、延伸可能な長さは「２」となるため、連続性指標Ｖ１は「２」と設定される。対角線ＤＬ２は、右上の対角線ＤＬ２１、および左下の対角線ＤＬ２２と連続している。従って、連続性指標Ｖ２は「３」と設定される。図示した範囲外でも対角線が連続している場合には、連続性指標は、更に大きな値を採り得る。
【００３３】
連続性指標は、種々の設定が可能であり、例えば、処理対象格子に隣接する格子（図示した破線の８個の格子）内でのみ評価するようにしてもよい。この評価方法では、連続する対角線の本数を点数化して評価することができる。例えば、対角線ＤＬ１については、対角線ＤＬ１１のみが連続しているため連続性指標Ｖ１を１点とし、対角線ＤＬ２については連続性指標Ｖ２を２点としてもよい。また、処理対象格子の上下左右に隣接する格子における対角線との平行性を考慮してもよい。例えば、対角線ＤＬ１については、左右および下の対角線が平行となっているため３点、対角線ＤＬ２については上の対角線のみが平行となっているため１点と評価し、この評価値を加味して、連続性指標を設定するようにしてもよい。
【００３４】
ＣＰＵは、こうして設定された連続性指標に基づき、その値が大きい側の対角線で格子を分割する（ステップＳ２６）。こうすることにより、格子の境界線が比較的広域にわたって連続するため、地表面について、より自然な３次元表示を実現することが可能となる。
【００３５】
分割処理は、種々の方法を採ることができ、例えば、標高差ｄｈ１、ｄｈ２がほぼ同値と判断できる場合（ステップＳ２３：ＹＥＳ）、２本の対角線のいずれか一方を、ランダムに選択するようにしても良い。連続性指標は、処理対象格子の対角線が必ずしも直線状に延伸可能な程度を評価するものである必要はなく、地表面データ２０２が、非構造格子で与えられている場合には、折れ線状に延伸可能な長さに基づいて連続性指標を設定してもよい。
【００３６】
Ｃ２．稜線強調処理：
地表面ポリゴンデータ生成処理（図３）における稜線強調処理（ステップＳ４０）は、上述した分割処理（図４）のステップＳ２４において、選択する対角線を逆転させた処理である。即ち、稜線強調処理では、ＣＰＵは、２本の対角線の標高差ｄｈ１、ｄｈ２に有意差が存在する場合には、標高差が大きい側の対角線で格子を分割する。
【００３７】
標高差ｄｈ１、ｄｈ２がほぼ同値と判断される場合には、稜線強調処理においても、分割処理と同様の処理を実行する（図４のステップＳ２５、Ｓ２６）。ただし、これらの処理についても分割処理と逆の選択を行い、ステップＳ２６で、連続性指標が小さい側の対角線で格子を分割するようにしてもよい。
【００３８】
Ｃ３．分割処理の変形例：
格子を分割する対角線の選択方法としては、対角線両端の標高差ｄｈ１、ｄｈ２に代えて、対角線で仮に分割した場合に生成される三角形ポリゴンの法線長さを利用した方法が挙げられる。かかる選択方法について変形例として説明する。この選択方法は、図４のステップＳ２２、Ｓ２３に代わる処理である。
【００３９】
図５は三角形ポリゴンの法線を用いた対角線の選択方法を示す説明図である。処理対象格子の格子点Ｐ０、Ｐ１、Ｐ２、Ｐ３を、平面上の位置座標ｘ、ｙおよび標高ｈに従って斜視図で示した。処理対象格子を対角線Ｐ１Ｐ３で分割したとすれば、三角形Ｐ０Ｐ１Ｐ３、Ｐ２Ｐ１Ｐ３という２つの三角形ポリゴンが生成される。これらの各三角形ポリゴンについては、正規化された法線ベクトルＮ１，Ｎ２を求めることができる。また、各法線ベクトルＮ１、Ｎ２のｘｙ平面上の成分をＮ１ｘｙ、Ｎ２ｘｙとする。三角形ポリゴンの地表面からの傾きが大きいほど、この成分値は大きくなる。変形例では、この成分値の和、即ち「Ｎ１ｘｙ＋Ｎ２ｘｙ」を標高差に代わる評価値として用いる。
【００４０】
図５中では、対角線Ｐ１Ｐ３で格子を分割した状態を例示したが、対角線Ｐ０Ｐ２で分割した状態についても、同様にして法線およびｘｙ平面上の成分を求めることができる。この法線に基づいて得られる評価値を「Ｎ３ｘｙ＋Ｎ４ｘｙ」とする。
【００４１】
変形例では、こうして得られた評価値に基づいて、格子の分割に使用すべき対角線を選択する。分割処理（図４）においては、ステップＳ２４では、評価値が小さくなる側の対角線を選択し、稜線強調処理では、評価値が大きくなる側の対角線を選択する。
【００４２】
変形例において、対角線Ｐ１Ｐ３で格子を分割した状態についての評価値は、各法線ベクトルＮ１、Ｎ２のｘｙ平面上の成分Ｎ１ｘｙ、Ｎ２ｘｙのうち大きい側を用いるようにしてもよい。対角線Ｐ０Ｐ２で分割した状態についての評価値は、法線およびｘｙ平面上の成分Ｎ３ｘｙ、Ｎ４ｘｙのうち大きい側を用いることになる。そして、分割処理では、こうして得られた評価値の小さい方に対応する対角線を用いる。このように、分割処理においては、対角線の両端の標高差が小さい側の対角線を選択するのと、同等の選択基準となる種々の手法を適用することができる。
【００４３】
Ｄ．効果：
図６は本実施例に基づく地表面の３次元表示例を示す説明図である。山の傾斜地に建築された建物および道路Ｒｐを示した。従来技術による表示（図８）と異なり、本実施例による地表面ポリゴンデータを用いた場合には、道路Ｒｄを横断する稜線が顕著には表れない。このように本実施例の地表面ポリゴンデータ生成システムによれば、地表面の３次元表示における不自然さを抑制することができる。
【００４４】
実施例では、街領域と山間領域で分割処理と稜線強調処理を使い分けた。かかる使い分けは本実施例に必須ではないが、このような使い分けをすることにより、地物が存在する街領域では、不自然な稜線が表れることを抑制しつつ（図６参照）、山間領域では、稜線を強調した３次元表示を行うことが可能となる。
【００４５】
Ｅ．第２実施例：
第１実施例では、正方形の構造格子で与えられた地表面データ２０２を用いて地表面ポリゴンデータを生成する例を示した。本実施例は、非構造格子で与えられる地表面データにも適用可能である。かかる例について、第２実施例で説明する。
【００４６】
図７は第２実施例としての地表面ポリゴンデータ生成処理のフローチャートである。第１実施例と同様、端末１００のＣＰＵが実行する処理に相当する。処理が開始されると、ＣＰＵは、地表面データを入力する（ステップＳ１００）。この例では、地表面データは、非構造格子で与えられているものとする。
【００４７】
ＣＰＵは、入力された全格子点について、以下の手順で地表面ポリゴンデータを生成する処理を実行する（ステップＳ１０２〜Ｓ１１２）。まず、ＣＰＵはデローニ分割処理により、地表面の三角形ポリゴンへの分割を試みる（ステップＳ１０４）。デローニ分割とは、非構造格子を規定するための数値幾何学上周知の処理である。
【００４８】
図中に、デローニ分割処理の方法を示した。黒丸が格子点を表している。デローニ分割では、これらの格子点の３点以上を通過する円を見つけ出す。但し、図中の円Ｃｄ２に示すように、他の格子点を内部に含む円は除外する。円Ｃｄ１、Ｃｄ３のように内部に他の格子点を含まない円（以下、「空円」と呼ぶ）を見いだす。円Ｃｄ３のように、４点以上の格子点を通過する状態を縮退と呼ぶ。
【００４９】
ＣＰＵは、空円の設定結果に基づき、縮退が生じているか否かを判断する（ステップＳ１０６）。縮退が生じていない場合には、空円上の３点によって三角形の地表面ポリゴンデータを生成、格納する（ステップＳ１１０）。縮退が生じている場合には、三角形が一義的に規定できないため、分割処理を行って（ステップＳ１０８）、地表面ポリゴンデータを生成、格納する（ステップＳ１１０）。
【００５０】
この分割処理には、第１実施例（図４）と同じ処理を適用できる。ステップＳ１０６とステップＳ１０８の間に、第１実施例における地表面ポリゴンデータ生成処理（図３）のステップＳ１６，Ｓ１８の処理を適用し、分割処理、稜線強調処理の使い分けを行っても良い。
【００５１】
第２実施例において、５点以上が空円上に存在する縮退が生じた場合には、例えば、いずれかの対角線によって四角形に分割した後、分割処理（ステップＳ１０８）を実行すればよい。この際、対角線はランダムに選択してもよいし、標高差が最小となる対角線を選択するようにしてもよい。
【００５２】
以上で説明した第２実施例によれば、第１実施例と同様、非構造格子についても、自然な３次元表示を行うことが可能な地表面ポリゴンデータを生成することができる。
【図面の簡単な説明】
【００５３】
【図１】実施例としてのポリゴンデータ生成システムの全体構成を示す説明図である。
【図２】地表面データ２０２の構造を示す説明図である。
【図３】地表面ポリゴンデータ生成処理のフローチャートである。
【図４】分割処理のフローチャートである。
【図５】三角形ポリゴンの法線を用いた対角線の選択方法を示す説明図である。
【図６】本実施例に基づく地表面の３次元表示例を示す説明図である。
【図７】第２実施例としての地表面ポリゴンデータ生成処理のフローチャートである。
【図８】従来技術による３次元表示例を示す説明図である。
【符号の説明】
【００５４】
１００…端末
１０２…コマンド入力部
１０４…データ入出力部
１０６…領域判定部
１０８…分割処理部
１１０…稜線強調処理部
１１２…地図表示部
２０２…地表面データ
２０４…２次元地図ＤＢ
２１０…３次元地図ＤＢ
２１２…地表面ポリゴンデータ
２１４…地物ポリゴンデータ
【特許請求の範囲】
【請求項１】
地表面を３次元表示するための三角形ポリゴンデータを生成するポリゴンデータ生成装置であって、
複数の格子点について、位置および標高を記録した地表面データを入力する地表面データ入力部と、
前記複数の格子点から、内部に該格子点を含まない四角形を形成可能な４点を処理対象として特定する対象格子点特定部と、
前記四角形の２本の対角線のうち、両端の標高差が小さい側の対角線で該四角形を分割することで、２つの三角形ポリゴンデータを生成する分割処理部とを備えるポリゴンデータ生成装置。
【請求項２】
請求項１記載のポリゴンデータ生成装置であって、
前記地表面データは、矩形の構造格子で与えられ、
前記処理対象は、前記構造格子における各格子の４頂点であるポリゴンデータ生成装置。
【請求項３】
請求項１記載のポリゴンデータ生成装置であって、
前記分割処理部は、前記２本の対角線に対する標高差の差違が所定値以下の場合、前記四角形に隣接する格子の境界線との連続性が高い側の対角線を用いて前記分割を行うポリゴンデータ生成装置。
【請求項４】
請求項１記載のポリゴンデータ生成装置であって、
前記地表面データ入力部は、前記各格子点が稜線を強調すべき領域に存在するか否かを判断するために使用する領域属性データを入力し、
前記対象格子点特定部によって特定された四角形が、前記領域属性データに基づいて、前記稜線を強調すべき領域に存在すると判断される場合に、前記四角形の２本の対角線のうち、両端の標高差が大きい側の対角線で該四角形を分割することで、２つの三角形ポリゴンデータを生成する稜線強調処理部を備えるポリゴンデータ生成装置。
【請求項５】
地表面を３次元表示するための三角形ポリゴンデータを生成するポリゴンデータ生成方法であって、
コンピュータが実行する工程として、
複数の格子点について、位置および標高を記録した地表面データを入力する地表面データ入力工程と、
前記複数の格子点から、内部に該格子点を含まない四角形を形成可能な４点を処理対象として特定する対象格子点特定工程と、
前記四角形の２本の対角線のうち、両端の標高差が小さい側の対角線で該四角形を分割することで、２つの三角形ポリゴンデータを生成する分割処理工程とを備えるポリゴンデータ生成方法。
【請求項６】
地表面を３次元表示するための三角形ポリゴンデータを生成するためのコンピュータプログラムであって、
複数の格子点について、位置および標高を記録した地表面データを入力する地表面データ入力プログラムコードと、
前記複数の格子点から、内部に該格子点を含まない四角形を形成可能な４点を処理対象として特定する対象格子点特定プログラムコードと、
前記四角形の２本の対角線のうち、両端の標高差が小さい側の対角線で該四角形を分割することで、２つの三角形ポリゴンデータを生成する分割処理プログラムコードとを備えるコンピュータプログラム。
【請求項１】
地表面を３次元表示するための三角形ポリゴンデータを生成するポリゴンデータ生成装置であって、
複数の格子点について、位置および標高を記録した地表面データを入力する地表面データ入力部と、
前記複数の格子点から、内部に該格子点を含まない四角形を形成可能な４点を処理対象として特定する対象格子点特定部と、
前記四角形の２本の対角線のうち、両端の標高差が小さい側の対角線で該四角形を分割することで、２つの三角形ポリゴンデータを生成する分割処理部とを備えるポリゴンデータ生成装置。
【請求項２】
請求項１記載のポリゴンデータ生成装置であって、
前記地表面データは、矩形の構造格子で与えられ、
前記処理対象は、前記構造格子における各格子の４頂点であるポリゴンデータ生成装置。
【請求項３】
請求項１記載のポリゴンデータ生成装置であって、
前記分割処理部は、前記２本の対角線に対する標高差の差違が所定値以下の場合、前記四角形に隣接する格子の境界線との連続性が高い側の対角線を用いて前記分割を行うポリゴンデータ生成装置。
【請求項４】
請求項１記載のポリゴンデータ生成装置であって、
前記地表面データ入力部は、前記各格子点が稜線を強調すべき領域に存在するか否かを判断するために使用する領域属性データを入力し、
前記対象格子点特定部によって特定された四角形が、前記領域属性データに基づいて、前記稜線を強調すべき領域に存在すると判断される場合に、前記四角形の２本の対角線のうち、両端の標高差が大きい側の対角線で該四角形を分割することで、２つの三角形ポリゴンデータを生成する稜線強調処理部を備えるポリゴンデータ生成装置。
【請求項５】
地表面を３次元表示するための三角形ポリゴンデータを生成するポリゴンデータ生成方法であって、
コンピュータが実行する工程として、
複数の格子点について、位置および標高を記録した地表面データを入力する地表面データ入力工程と、
前記複数の格子点から、内部に該格子点を含まない四角形を形成可能な４点を処理対象として特定する対象格子点特定工程と、
前記四角形の２本の対角線のうち、両端の標高差が小さい側の対角線で該四角形を分割することで、２つの三角形ポリゴンデータを生成する分割処理工程とを備えるポリゴンデータ生成方法。
【請求項６】
地表面を３次元表示するための三角形ポリゴンデータを生成するためのコンピュータプログラムであって、
複数の格子点について、位置および標高を記録した地表面データを入力する地表面データ入力プログラムコードと、
前記複数の格子点から、内部に該格子点を含まない四角形を形成可能な４点を処理対象として特定する対象格子点特定プログラムコードと、
前記四角形の２本の対角線のうち、両端の標高差が小さい側の対角線で該四角形を分割することで、２つの三角形ポリゴンデータを生成する分割処理プログラムコードとを備えるコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２００６−１１５４４（Ｐ２００６−１１５４４Ａ）
【公開日】平成１８年１月１２日（２００６．１．１２）
【国際特許分類】
【出願番号】特願２００４−１８３８９６（Ｐ２００４−１８３８９６）
【出願日】平成１６年６月２２日（２００４．６．２２）
【出願人】（５０２００２１８６）株式会社ジオ技術研究所 (23)
【Ｆターム（参考）】
【公開日】平成１８年１月１２日（２００６．１．１２）
【国際特許分類】
【出願日】平成１６年６月２２日（２００４．６．２２）
【出願人】（５０２００２１８６）株式会社ジオ技術研究所 (23)
【Ｆターム（参考）】
[ Back to top ]