JPH08329236A - 輪郭データ簡略化方法 - Google Patents

Abstract

(57)【要約】 【目的】 原輪郭データにおける概略輪郭形状を簡略化
処理後にも忠実に維持し、複数の輪郭が近傍にあっても
それらが重なったり交差したりすることを防止できるよ
うにする。 【構成】 輪郭形状における局所的な小さな凹凸部分を
検出し（１０１）、局所的な凹凸部分に係る頂点座標デ
ータを除去することにより（１０３）、原輪郭データを
簡略化した輪郭データに変換する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は輪郭データ簡略化方法に
関し、例えば、３次元地形のデータ及びその地形上の区
画形状のデータを実時間で更新しながら表示出力するこ
とが求められるフライトシミュレーション装置等に適用
し得るものである。

【０００２】

【従来の技術】例えば、フライトシミュレーション装置
は、３次元地形やその地形上の区画形状等を表示させる
と共に、ユーザの操縦指令に応じて、実時間で視点位置
や視線方向が変更された３次元地形や地形上の区画形状
に更新し、表示し直すことを繰返すものである。

【０００３】このように３次元で地形図を表示させるた
めの１つの原データとしては、グリッドベースの地形デ
ータ（標高データ）が使用されている。これは、図２
（Ａ）に示すように、東西、南北を各辺とする長方形又
は正方形の表示可能領域を、東西及び南北方向について
一定のピッチで等分して、長方形又は正方形形状の複数
の領域（それぞれをメッシュと呼ぶ）３に分割し、各格
子点１上の標高（海抜）を、図２（Ｂ）に示すように数
値で表したデータ２である。

【０００４】このグリッドベースの地形データを基に３
次元地形表示する際には、メッシュが基本要素となり、
メッシュの４つの頂点に記録されているそれぞれの座標
値に基づいて、図２（Ｃ）に示すように、メッシュを２
個の三角形（このような描画単位の平面をポリゴンと呼
ぶ）４、５に分けて表示する。これら２個のポリゴン
は、それぞれ標高差に応じた面の向きをもつため、メッ
シュの表面に凹凸が生じ、これらのメッシュを個々に全
て表示することによって、土地の傾きや山の尾根などの
形状を再現することができる。

【０００５】このようにして表示された３次元地形の上
に、建物単体、又は、複数の建物の集合が位置する区画
形状の情報（以下、単に区画情報と呼ぶ）を表示する。
区画情報は、国土地理院等で入手可能な既存のデータで
あり、図３（Ａ）に示すように、連続する折れ線でなる
輪郭形状において、始点から終点への順における、始
点、複数の曲点、終点のある基準点（一般的には原点）
に対する３次元座標データ（ベクトルデータ）の集合で
なっている。従って、これら座標点を順に線で結ぶこと
により、市街地等の区画の様子が３次元的に表現でき、
図３（Ｂ）に示すように、標高データによる３次元地形
の起伏の上に、土地利用や街並の様子を表すことができ
る。

【０００６】３次元地形の上に区画情報を重ねた景観を
表現する場合、膨大な量の画像要素を表示する必要性が
ある。表示する画像要素の数を増やせば増やすほど、生
成される画像は質の高いものとなるが、生成時間が長く
なる。この生成時間の長期化は、３次元地形図の画像を
実時間でインタラクティブに更新していく上で大きな問
題となっている。

【０００７】文献『岡崎彰夫、加藤伸子共著、「形状簡
略化に基づく３次元オブジェクト空間の最適高速表
示」、電子情報通信学会論文誌、Ｄ−ＩＩ、Ｖｏｌ．Ｊ
７６−Ｄ−ＩＩ、Ｎｏ．８、ｐｐ．１７１２−１７２
１、１９９３年８月』 ところで、上記文献は、建物等のオブジェクトを付加し
た３次元地形図を表示する際、画像の質をある程度維持
したまま仮想空間内を実時間でインタラクティブに動き
回るために、オブジェクトの間引きや削除、オブジェク
トの形の簡略化等を行なうことを提案している。建物等
のように水平断面が比較的単純で個々に独立なオブジェ
クトとして扱える場合には、オブジェクトの形状を、例
えば６角柱のものを、断面上の１又は２程度の頂点を省
略して５角柱や４角柱にするような簡略化を行なってい
る。そして、いくつかのレベルで簡略化したオブジェク
トの形状を階層的に複数準備し、視点位置からの距離に
応じて、簡略化したオブジェクトを段階的に変更して描
画することで、画像の更新の高速化を可能としている。

【０００８】この文献記載の方法は、区画情報の簡略化
にも適用可能であり、３次元地形に区画情報を重ねて表
示する際にも適用可能である。

【０００９】

【発明が解決しようとする課題】しかしながら、上記文
献記載の簡略化方法では、図４（Ａ）に示す３個の建物
（オブジェクト）でなる原形状が、簡略化を行なった後
には、図４（Ｂ）に示すように、隣合う建物同士が結合
してしまうような状態が生じる。扱うオブジェクトを区
画として、上記文献記載の簡略化方法を適用した場合に
は、図５（Ａ）に示すように、区画と区画との間にある
道路が、簡略化処理後には、図５（Ｂ）に示すように、
区画同士の接続や交差のために道路と認識できないもの
となり、不自然な画像が生成されてしまう。

【００１０】そのため、区画等の輪郭データを、表示画
像に違和感がない自然な画像に実時間で簡略化できる輪
郭データ簡略化方法が求められている。

【００１１】

【課題を解決するための手段】かかる課題を解決するた
め、本発明は、輪郭形状上を所定回りに順次位置する各
頂点の座標データの集合でなる原輪郭データのデータ量
を減少させた輪郭データを得るる輪郭データ簡略化方法
において、原輪郭データが表す輪郭形状における局所的
な凹凸部分を検出する局所凹凸検出処理と、検出された
局所的な凹凸部分に係る頂点座標データを原輪郭データ
から除去する局所凹凸除去処理とでなることを特徴とす
る。

【００１２】

【作用】本発明の輪郭データ簡略化方法においては、輪
郭形状における局所的な小さな凹凸部分を検出し、局所
的な凹凸部分に係る頂点座標データを原輪郭データから
除去することにより、原輪郭データを簡略化した輪郭デ
ータに変換する。

【００１３】その結果、原輪郭データにおける概略輪郭
形状は、簡略化処理後にも忠実に維持でき、複数の輪郭
が近傍にあっても、それらが重なったり交差したりする
ことを防止することができる。

【００１４】

【実施例】以下、本発明による輪郭データ簡略化方法
を、区画データの簡略化表示を伴う３次元地形表示シス
テムに適用した一実施例を図面を参照しながら詳述す
る。

【００１５】この実施例に係る３次元地形表示システム
は、ハードウェア的には、例えば図６に示すような複数
の構成要素を備えた、コンピュータグラフィックス用の
ワークステーションによって実現される。すなわち、中
央処理ユニット（ＣＰＵ：主メモリやワーキングメモリ
を含んだものとする）２３及び表示用画像が描画される
画像メモリ２４とでなるワークステーション本体２５
と、入力装置としての３次元又は２次元マウス２０及び
キーボード２１と、出力装置としてのＣＲＴディスプレ
イ２２と、後述する区画データや各区画の総頂点数を記
憶している外部記憶装置２６とでなるワークステーショ
ンによって実行される。

【００１６】ここでは、ＣＰＵ２３によるソフトウェア
処理によって区画データの簡略化が実行されることを想
定しており、従って、図１は、区画データ簡略化方法
（輪郭データ簡略化方法）の処理手順を示したフローチ
ャートと見ることもできる。また、図６では示していな
いが、所定の処理を専用の画像処理ボードで実行させる
こともでき、この場合には、図１を機能ブロック図と見
ることもできる。

【００１７】この実施例の場合、区画描画を高速にでき
るようにするための簡略化は、簡略化後の区画形状が他
の区画との関係からも不自然になることがないように、
『区画の概略形状』を忠実に維持すると共に、『区画の
内部方向への局所的なくぼみ形状（以下、袋小路と呼
ぶ）』を除去することで行なう。

【００１８】すなわち、図７（Ａ）に示す区画ＫＡ０に
ついては、簡略化処理によって、袋小路ＨＡ及びＨＢを
除去した図７（Ｂ）に示す区画データＫＡ１に変更し、
図７（Ａ）に示す区画ＫＢ０については、袋小路が存在
しないので簡略化処理後も図７（Ｂ）に示すようにその
区画データＫＢ１を維持するように、簡略化処理を行な
う。

【００１９】このような袋小路の簡略化処理を伴う区画
の表示手順は、図１に示す処理手順で実行される。

【００２０】３次元地形データに対する描画メモリ２４
への描画処理が終了したときには、ＣＰＵ２３は、図１
に示す処理ルーチンを開始し、まず、処理対象区画を規
定する区画パラメータｋを初期値０に設定する（ステッ
プ１００）。そして、処理対象区画ｋに対する袋小路検
出処理を行ない（ステップ１０１）、袋小路が検出され
たか否かを判定する（ステップ１０２）。袋小路が検出
されれば袋小路の除去処理を実行して（ステップ１０
３）、袋小路の検出処理に戻る。

【００２１】なお、ステップ１０１の袋小路の検出処理
の詳細は図８に示しており、後で詳述するが、袋小路を
検出した場合にはフラグｆｌｇを「ｙｅｓ」に設定し、
袋小路を検出しない場合にはフラグｆｌｇを「ｎｏ」に
設定するようになされており、従って、ステップ１０２
の判定は、フラグｆｌａｇが「ｙｅｓ」か「ｎｏ」かに
基づいて実行される。また、ステップ１０３の袋小路の
除去処理の詳細は図９に示しており、後で詳述する。

【００２２】ここで、袋小路の検出、除去に供する区画
データは、外部記憶装置２６に格納されており、これを
読出して用いる。また、袋小路除去後の区画データも、
外部記憶装置２６に格納する。さらに、区画データは、
上述したように、連続する折れ線でなる輪郭形状におい
て、始点から終点への順における、始点、複数の曲点、
終点（以下、これらを全て頂点と呼ぶ）のある基準点
（一般的には原点）に対する３次元座標データ（ベクト
ルデータ）の集合でなっている。

【００２３】以上のようなステップ１０１〜１０３を繰
返すことにより処理対象区画ｋに存在する袋小路が全て
除去され、処理対象区画ｋに袋小路がなくなると（当初
からない場合を含む）、区画パラメータｋを１インクリ
メントして次の区画を指示するものに変更し（ステップ
１０４）、そのインクリメントされた区画パラメータｋ
を区画総数Ｎと比較することにより、全ての区画に対す
る袋小路の検出及び除去処理が行なわれたか否かを判定
する（ステップ１０５）。

【００２４】Ｎ個の全区画に対する処理が終了していな
ければ、上述したステップ１０１に戻って、インクリメ
ントされた区画パラメータｋが指示する新たな区画に対
する袋小路の検出及び除去処理を実行する。

【００２５】このようにして袋小路の検出、除去が全て
の区画に対して終了すると、区画の描画処理に進み（ス
テップ１０６）、現在の視点位置、視線方向で画面上に
表示される領域（可視領域）を計算し、その領域に含ま
れる、袋小路の除去がなされた区画データだけを画像メ
モリ２４に描画する。また、視点位置や視線方向等が変
更されて再描画の命令が与えられたか否かを判定し（ス
テップ１０７）、その命令が与えられた場合には、ステ
ップ１０６に戻って、新たな視点位置や視線方向等に応
じた描画処理を行なう。再描画の命令が与えられない場
合には、一連の区画表示処理を終了する。

【００２６】次に、ステップ１０１の袋小路の検出処理
について、図８のフローチャートを参照しながら詳述す
る。

【００２７】まず、図８の処理手順を説明する前に、図
８の処理手順を採用した考え方について、簡単に説明す
る。なお、区画データが頂点（始点、曲点、終点）の３
次元座標（又は２次元座標）の順番のデータでなってい
ることを前提としている。

【００２８】(1) 上記図７（Ａ）の区画ＫＡ０及びＫＢ
０の比較から明らかなように、袋小路ＨＡ及びＨＢを有
する区画ＫＡ０の総頂点数は多くなっており、袋小路を
有しない区画ＫＢ０の総頂点数は少なくなっている。言
い換えると、対象区画ｋが、総頂点数Ｍｋが少ない３角
形や４角形等の単純な形状の場合には袋小路は存在せ
ず、総頂点数によって袋小路の存在の有無を判定でき
る。

【００２９】(2) 図７（Ａ）に示すように、袋小路への
入口を規定する２頂点間の距離Ｌは短く、２個の頂点間
の距離によって、袋小路への入口になっているか否かを
判定できる。

【００３０】(3) 袋小路の入口から中に入った袋小路部
分での頂点数はある程度の範囲内の数であり（袋小路Ｈ
Ａの場合２、袋小路ＨＢの場合６）、言い換えると、入
口か否かを判定する２頂点の順番差はある程度の範囲
（ｓｔａｒｔ〜ｅｎｄ）内の値であり、距離を算出する
２頂点の組み合わせは限定される。例えば、区画データ
で順番が連続する２頂点が袋小路の入口を規定する２頂
点となっていることはなく、それらの距離算出は不要で
ある。

【００３１】おおむねこのような考え方に従っている図
８に示す処理ルーチンに入ると、ＣＰＵ２３は、まず、
現在の処理対象区画ｋの総頂点数Ｍｋを単純形状判定用
閾値Ｕと大小比較する（ステップ２００）。総頂点数Ｍ
ｋが単純形状判定用閾値Ｕ以下であると、袋小路が存在
しないほどの単純形状であるので、検出フラグｆｌａｇ
を「ｎｏ」として図１に示したメインルーチンのステッ
プ１０２に進む（ステップ２１１）。

【００３２】総頂点数Ｍｋからは袋小路の存在の可能性
があると判定されると（ステップ２００で肯定結果）、
基準入口頂点パラメータｍを区画データの最初の頂点を
規定する初期値０に設定すると共に（ステップ２０
１）、基準入口頂点からの頂点の順番差を表す基準頂点
偏差パラメータｎを値ｓｔａｒｔに設定する（ステップ
２０２）。後者の設定は、言い換えると、ｍ番目の頂点
である基準入口頂点ｐ［ｍ］から値ｓｔａｒｔ先の頂点
を、基準入口頂点ｐ［ｍ］に対向する入口頂点の可能性
を判定する参照頂点に設定したことを意味する。

【００３３】なお、表記ｐ［ｍ］はｍ番目の頂点である
基準入口頂点の座標データを意味しており、後述する表
記ｐ［ｍ＋ｎ］はｍ＋ｎ番目の頂点である参照頂点の座
標データを意味している。

【００３４】そして、両パラメータｍ、ｎの和ｍ＋ｎが
最終順番の頂点番号（Ｍｋ−１）を越えていないことを
確認して、言い換えると、基準入口頂点ｐ［ｍ］に対す
る参照頂点ｐ［ｍ＋ｎ］が実存することを確認して、両
頂点のｘｙ平面上での距離Ｌを算出し（ステップ２０
４）、その距離Ｌが袋小路の入口距離要件を満たしてい
るか否かを距離閾値Ｔと大小比較することで判定する
（ステップ２０５）。

【００３５】距離Ｌが袋小路の入口距離要件を満たして
いない場合には、基準入口頂点からの参照頂点への順番
差を表す基準頂点偏差パラメータｎを１インクリメント
した後（ステップ２０６）、新たなパラメータｎの値が
基準入口頂点ｐ［ｍ］から考慮する最終の順番差ｅｎｄ
−１以下であるか否かを判定する（ステップ２０７）。
パラメータｎが現在の基準入口頂点ｐ［ｍ］に対向する
参照頂点までの順番偏差としてまだ考慮するものである
と、上述したステップ２０３に戻る。

【００３６】このように入口距離要件を満たす参照頂点
ｐ［ｍ＋ｎ］が検索されなければ、参照頂点の変更がな
され、ステップ２０３〜２０７でなる処理ループが入口
距離要件を満たす参照頂点が見つかるまで、若しくは、
参照頂点の可変範囲の限界頂点まで繰返される。そし
て、現在の基準入口頂点ｐ［ｍ］に対する処理すべき各
参照頂点ｐ［ｍ＋ｎ］（但しｍ＋ｎはｍ＋ｓｔａｒｔ〜
ｍ＋ｅｎｄ又はＭｋ−１）との距離が全て、袋小路の入
口距離要件を満たしていない場合には（ステップ２０３
で否定結果、又は、ステップ２０７で否定結果）、基準
入口頂点パラメータｍを１インクリメントして基準入口
頂点を次のものに変更し（ステップ２０８）、新たなパ
ラメータｍ＋ｓｔａｒｔと総頂点数Ｍｋとを大小比較す
ることを通じて、このパラメータｍが規定する基準入口
頂点に対する考慮すべき参照頂点が実在することを確認
して、上記ステップ２０２に戻る（ステップ２０９）。

【００３７】なお、パラメータｍが規定する新たな基準
入口頂点に対する考慮すべき参照頂点が実在しない場合
には、入口距離要件を満たす２頂点の組み合わせが１個
もないので、検出フラグｆｌａｇを「ｎｏ」として図１
に示したメインルーチンのステップ１０２に進む（ステ
ップ２１１）。

【００３８】パラメータｍが規定する現在の基準入口頂
点ｐ［ｍ］と、それよりｎ個先の参照頂点ｐ［ｍ＋ｎ］
との距離Ｌが入口距離要件を満たす場合には（ステップ
２０５で肯定結果）、今回検出された袋小路を除去した
後の区画形状があまりにも単純になるか（区画がなくな
ることを含む）否かを、値Ｍｋ−ｎ＋１（除去後の総頂
点数を表している）と除去後形状頂点数閾値Ｖとを大小
比較して判定する（ステップ２１０）。除去後の区画形
状があまりにも単純になる場合には、除去を禁止するた
め、検出フラグｆｌａｇを「ｎｏ」として図１に示した
メインルーチンのステップ１０２に進む（ステップ２１
１）。一方、除去後の区画形状が許容し得る頂点数でな
る形状であると（ステップ２１０で否定結果）、検出フ
ラグｆｌａｇを「ｙｅｓ」として図１に示したメインル
ーチンのステップ１０２に進む（ステップ２１２）。

【００３９】以上のような処理により、袋小路の入口距
離に着目して１回の一連の処理で１個の袋小路を検出す
る。

【００４０】次に、ステップ１０３の袋小路の除去処理
について、図９のフローチャートを参照しながら詳述す
る。

【００４１】ＣＰＵ２３は、当該処理ルーチンに入る
と、上記袋小路検出処理で認識された袋小路の入口の両
頂点ｐ［ｍ］及びｐ［ｍ＋ｎ］間の全ての頂点ｐ［ｍ＋
１］、…、ｐ［ｍ＋ｎ−１］のデータを外部記憶装置２
６から除去し（ステップ３００）、その後、総頂点数Ｍ
ｋも除去された頂点数ｎ−１個だけ少なく更新して除去
処理を終了する（ステップ３０１）。

【００４２】次に、図１０を用いて、袋小路の検出処理
及び除去処理の具体例を説明する。ここでは、閾値Ｕが
６、パラメータｓｔａｒｔが３、パラメータｅｎｄが
４、閾値Ｖが４として説明する。また、距離閾値Ｔは頂
点ｖ２及びｖ５間の距離より僅かに大きいとする。

【００４３】図１０（Ａ）に示す原区画形状の総頂点数
Ｍｋが１０であって、単純形状判定用閾値Ｕより大きい
ので、入口距離Ｌに基づいた袋小路の検出に進む。

【００４４】まず、最初に頂点ｖ０が基準入口頂点ｐ
［ｍ］となったとする。パラメータｓｔａｒｔが３であ
るので頂点ｖ３を参照頂点とし、両頂点ｖ０及びｖ３の
距離が求められるが、距離閾値Ｔより算出距離Ｌが大き
いので、参照頂点を頂点ｖ４とする。この場合の両頂点
ｖ０及びｖ４の距離も距離閾値Ｔより大きい。今回の参
照頂点ｖ４は、パラメータｅｎｄに係る頂点であるの
で、頂点ｖ０を入口頂点とする袋小路がないとして、基
準入口頂点ｐ［ｍ］を今までのｍ番目（０番目）より１
大きい１番目の頂点ｖ１とする。

【００４５】パラメータｓｔａｒｔ及びｅｎｄが３及び
４であるため、この入口基準頂点ｖ１に対しては、頂点
ｖ４及びｖ５との距離が順次求められて判定されるが、
距離が大きいため袋小路の検出は否定される。

【００４６】次に、頂点ｖ２が基準入口頂点ｐ［ｍ］と
なったとする。この場合、最初にはパラメータｓｔａｒ
ｔ（＝３）に係る頂点ｖ５が参照頂点となるが、これら
両頂点ｖ２及びｖ５の距離は距離閾値Ｔより小さいの
で、除去後の頂点数が求められるが、除去後の頂点数が
８であって除去後形状頂点数閾値Ｖ（＝４）以上である
ので、フラグｆｌａｇに「ｙｅｓ」がセットされ、かか
る検出処理後の最初の袋小路除去処理によって、頂点ｖ
３及びｖ４のデータが除去され、すなわち、図１０
（Ｂ）に示すように、頂点ｖ２及びｖ５を入口とする袋
小路部分が除去される。また、このとき、総頂点数Ｍｋ
も１０−２＝８に更新される。

【００４７】図１のステップ１０１〜１０３に示したよ
うに、１個の袋小路を除去しても同一区画ｋの袋小路の
検出処理が実行される。

【００４８】今度は、図１０（Ｂ）に示す区画データが
対象となるが、総頂点数Ｍｋが８であって、単純形状判
定用閾値Ｕより大きいので、入口距離Ｌに基づいた袋小
路の検出に進む。最初に頂点ｖ０が基準入口頂点ｐ
［ｍ］となったときには、パラメータｓｔａｒｔ及びｅ
ｎｄが３及び４であるため、この入口基準頂点ｖ１に対
しては、３個及び４個先の頂点ｖ５及びｖ６との距離が
順次求められて判定されるが、算出距離が閾値Ｔより大
きいので、袋小路の検出は否定される。

【００４９】そこで次に、頂点ｖ１が基準入口頂点ｐ
［ｍ］になるが、この場合、パラメータｓｔａｒｔ（＝
３）に係る最初の参照頂点ｖ６との距離が距離閾値Ｔよ
り小さいので、除去後の頂点数が求められる。除去後の
頂点数は６であって除去後形状頂点数閾値Ｖ（＝４）以
上であるので、フラグｆｌａｇに「ｙｅｓ」がセットさ
れる。これにより、かかる検出処理後の最初の袋小路除
去処理によって、頂点ｖ２及びｖ５のデータが除去さ
れ、すなわち、図１０（Ｃ）に示すように、頂点ｖ１及
びｖ６を入口とする袋小路部分が除去される。また、こ
のとき、総頂点数Ｍｋも８−２＝６に更新される。

【００５０】除去処理が実行されたので、区画ｋに対す
る袋小路の検出処理が再度実行される。図１０（Ｃ）に
示す区画データが対象となっても、総頂点数Ｍｋが６で
あって、単純形状判定用閾値Ｕより大きいので、入口距
離Ｌに基づいた袋小路の検出に進む。頂点ｖ０、ｖ１及
びｖ６が基準入口頂点に順になるがこれら頂点が基準入
口頂点になったときには、入口距離要件を満たす参照頂
点がないので、やがて頂点ｖ７が基準入口頂点になる。
このときには、パラメータｓｔａｒｔが３であるため、
参照頂点になる頂点自体が存在しないので、距離の算出
を実行することなく、フラグｆｌａｇに「ｎｏ」がセッ
トされる。その結果、袋小路の除去処理は実行されず、
区画パラメータｋが次の区画を示すものに更新され、今
まで処理対象であった区画の袋小路の検出、除去が完了
する。

【００５１】次に、袋小路の検出処理におけるパラメー
タｓｔａｒｔ、ｅｎｄや閾値Ｕ、Ｔ、Ｖの機能について
説明する。

【００５２】パラメータｓｔａｒｔ及びｅｎｄは共に、
上述したように、基準入口頂点ｐ［ｍ］に対する参照頂
点の可変範囲を規定するものである。

【００５３】パラメータｓｔａｒｔは直接的には順番的
に最も基準入口頂点ｐ［ｍ］に近い参照頂点を規定する
ものである。言い換えると、パラメータｓｔａｒｔは、
除去対象の袋小路の最少頂点数を規定しているものであ
り、この値が小さいほど浅い袋小路（内部で折れ曲った
りしていない袋小路）も除去でき、この値が大きいほど
ある程度深い袋小路から除去を始めることになる。パラ
メータｓｔａｒｔが２であれば図１１（Ａ）〜（Ｃ）に
示す全ての袋小路が検出されて除去されるが、パラメー
タｓｔａｒｔが３であれば図１１（Ｂ）及び（Ｃ）に示
す袋小路が検出されて除去され、パラメータｓｔａｒｔ
が４であれば図１１（Ｃ）に示す袋小路だけが検出され
て除去される。このように、パラメータｓｔａｒｔは除
去対象の袋小路の形状の簡単側を規定している。

【００５４】パラメータｅｎｄは直接的には順番的に最
も基準入口頂点ｐ［ｍ］に遠い参照頂点を規定するもの
である。言い換えると、パラメータｅｎｄは、除去対象
の袋小路の最多頂点数を規定しているものであり、この
値が小さいほど１回で除去できる袋小路が小さくなり、
この値が大きいほど１回で除去できる袋小路が深く大き
なものとなる。パラメータｅｎｄが７であれば図１２
（Ａ）〜（Ｃ）に示す全ての袋小路が検出されて除去さ
れるが、パラメータｅｎｄが６であれば図１２（Ａ）及
び（Ｂ）に示す袋小路が検出されて除去され、パラメー
タｅｎｄが５であれば図１２（Ａ）に示す袋小路だけが
検出されて除去される。このように、パラメータｅｎｄ
は除去対象の袋小路の形状の複雑側を規定している。

【００５５】このパラメータｅｎｄを大きくすれば１回
の処理で大きな袋小路を検出できるが、内部に大きな表
示に値する空間領域を有する区画のその内部領域も除去
する恐れが高いので、このパラメータｅｎｄを小さく押
さえて、袋小路を部分的かつ再帰的に除去することが実
際的である。

【００５６】図１３は、パラメータｅｎｄを小さく押さ
えて再帰的な処理を繰返すことにより、頂点数が多い袋
小路を除去した様子を示している。

【００５７】単純形状判定用閾値Ｕは、上述したよう
に、袋小路の検出処理を行なう区画形状の複雑さを規定
しているものである。この値Ｕが小さいほど、簡単な形
状でも距離に基づく袋小路の検出を行なうことになる。
閾値Ｕが５であれば図１４（Ａ）〜（Ｆ）に示す全ての
区画について距離に基づく袋小路の検出処理が実行さ
れ、閾値Ｕが６であれば図１４（Ｃ）〜（Ｆ）に示す区
画について距離に基づく袋小路の検出処理が実行され、
閾値Ｕが７であれば図１４（Ｅ）及び（Ｆ）に示す区画
について距離に基づく袋小路の検出処理が実行される。

【００５８】距離閾値Ｔは、上述したように、袋小路の
入口と認められる入口の両頂点間の距離の最大値を規定
するものである。この値Ｔが大きいほど、幅広い袋小路
も検出し得るが、図１５（Ｃ）に示す袋小路以外の部分
ＮＡを袋小路と検出する恐れも大きくなる。閾値ＴがＬ
３以上であれば図１５（Ａ）〜（Ｃ）に示す全ての袋小
路の検出、排除が実行され、閾値ＴがＬ３未満Ｌ２以上
であれば図１５（Ａ）及び（Ｂ）に示す袋小路の検出、
排除が実行され、閾値ＴがＬ２未満Ｌ１以上であれば図
１５（Ａ）に示す袋小路の検出、排除が実行される。

【００５９】除去後形状頂点数閾値Ｖは、除去後の形状
として表示にある程度絶えられるものを確保するための
閾値である。また、かかる閾値Ｖを用いた判定によっ
て、距離からは誤って袋小路と判定された部分の除去を
禁止する機能をも担っている。例えば、図１６に示すよ
うに、２頂点の距離判定からは全体の区画形状が袋小路
と判定されることもあり、これを防ぐ機能を担ってい
る。なお、この値Ｖを非常に小さい値にすることによ
り、除去後の形状を判定に反映しなくすることもでき
る。

【００６０】以上のようなパラメータや閾値は適宜選定
すれば良い。例えば、視点位置からの距離を階層的に別
けて、各階層によってこれらパラメータや閾値の値を変
更するようにしても良い。図１７は、これらパラメータ
等の選定によって原区画データが同じであっても（図１
７（Ａ１）及び（Ｂ１））、最終的に得られる区画デー
タが図１７（Ａ２）及び（Ｂ２）に示すように異なるよ
うになることを示したものである。

【００６１】上記実施例によれば、区画形状の袋小路を
検出して除去するという簡略化を行なっているので、区
画形状の概略輪郭を忠実に維持したまま区画形状を簡略
化することができ、他の区画形状と重なったり交差した
りすることを防止することができる。その結果、３次元
地形に区画を重畳表示したとしても良好な表示品質を達
成することができる。

【００６２】しかも、袋小路の検出に必要な演算は、大
半が頂点数の加減算と大小比較であり、複雑な演算は距
離演算だけであるので、高速に区画形状の簡略化を実行
することができる。

【００６３】なお、上記実施例においては、基準入口頂
点にパラメータｎ又はｓｔａｒｔを加算した値の参照頂
点が区画データの最終頂点を越えた場合には距離算出の
対象にしないものを示したが（ステップ２０３やステッ
プ２０９参照）、このときにはその加算値から総頂点数
を減算した値に対応する始点側の頂点を参照頂点として
距離算出に供するようにしても良い。

【００６４】また、上記実施例においては、袋小路を除
去した際に、その入口の領域頂点のデータを区画データ
に残すものを示したが、その両頂点の袋小路側でない隣
合う２個の頂点を結ぶ線分上に入口の両頂点が存在する
かを確認して、線分上にある場合にはその入口の両頂点
のデータも削除するようにしても良い。

【００６５】さらに、上記実施例においては、袋小路の
検出処理後にフラグ判定してから袋小路の排除処理に進
むものを示したが、袋小路の検出したときに直ちに排除
処理し、その後、再帰処理を行なうか次の区画に進むか
をフラグ判定するようにしても良い。

【００６６】さらにまた、上記実施例においては、簡略
化の対象となる輪郭データが区画データであるものを示
したが、座標を表すベクトルデータの集合でなる、水域
データや等高線データや温度分布データ等の他の輪郭デ
ータの簡略化に本発明を適用することができる。

【００６７】なお、区画データの場合には、局所的な凸
部分はほとんど考えられず、上記処理によって袋小路
（凹部分）だけが除去されると考えられる。しかし、図
８及び図９に示した方法では、輪郭形状における局所的
な凸部分も除去することができ、水域データや等高線デ
ータや温度分布データ等においては局所的な凸部分の除
去が好ましいこともある。

【００６８】また、輪郭データの各頂点を規定するベク
トルデータは、３次元ベクトルデータに限定されず、２
次元ベクトルデータであっても良い。

【００６９】

【発明の効果】以上のように、本発明の輪郭データ簡略
化方法によれば、輪郭形状における局所的な凹凸部分を
検出し、局所的な凹凸部分に係る頂点座標データを除去
することにより、原輪郭データを簡略化した輪郭データ
に変換するようにしたので、原輪郭データにおける概略
輪郭形状は、簡略化処理後にも忠実に維持でき、複数の
輪郭が近傍にあっても、それらが重なったり交差したり
することを防止することができる。

【図面の簡単な説明】

【図１】実施例の全体処理を示すフローチャートであ
る。

【図２】３次元地形表示の説明図である。

【図３】区画データの説明図である。

【図４】従来の簡略化方法の欠点説明図（その１）であ
る。

【図５】従来の簡略化方法の欠点説明図（その２）であ
る。

【図６】実施例に係るハードウェア構成を示すブロック
図である。

【図７】実施例の簡略化方法の原理的考え方の説明図で
ある。

【図８】実施例の袋小路の検出処理を示すフローチャー
トである。

【図９】実施例の袋小路の排除処理を示すフローチャー
トである。

【図１０】実施例の袋小路の検出、排除の具体的な様子
を示す説明図である。

【図１１】実施例のパラメータｓｔａｒｔの意味説明図
である。

【図１２】実施例のパラメータｅｎｄの意味説明図であ
る。

【図１３】実施例の袋小路の再帰的な除去の様子の説明
図である。

【図１４】実施例の閾値Ｕの意味説明図である。

【図１５】実施例の閾値Ｔの意味説明図である。

【図１６】実施例の閾値Ｖの意味説明図である。

【図１７】実施例のパラメータ等の違いによる簡略化後
区画データの相違を示す説明図である。

【符号の説明】

２０…マウス、２１…キーボード、２２…ＣＲＴディス
プレイ、２３…中央処理ユニット（ＣＰＵ）、２４…画
像メモリ、２５…ワークステーション本体、２６…外部
記憶装置。

Claims (4)

【特許請求の範囲】
1. 【請求項１】 輪郭形状上を所定回りに順次位置する各
   頂点の座標データの集合でなる原輪郭データのデータ量
   を減少させた輪郭データを得る輪郭データ簡略化方法に
   おいて、 上記原輪郭データが表す輪郭形状における局所的な凹凸
   部分を検出する局所凹凸検出処理と、 検出された局所的な凹凸部分に係る頂点座標データを原
   輪郭データから除去する局所凹凸除去処理とでなること
   を特徴とする輪郭データ簡略化方法。
2. 【請求項２】 上記局所凹凸検出処理は、原輪郭データ
   の総頂点数が所定数より少ない場合には、局所的な凹凸
   部分が存在しないと判定することを特徴とする請求項１
   に記載の輪郭データ簡略化方法。
3. 【請求項３】 上記局所凹凸検出処理は、任意の２個の
   頂点座標データの距離が所定値より短く、それら２個の
   頂点座標データ間に介在する輪郭上の他の頂点座標デー
   タの個数が所定個数範囲に属するときに、それら２個の
   頂点座標データ間の輪郭部分を局所的な凹凸部分として
   検出することを特徴とする請求項１又は２に記載の輪郭
   データ簡略化方法。
4. 【請求項４】 上記局所凹凸検出処理は、任意の２個の
   頂点座標データの距離が所定値より短く、それら２個の
   頂点座標データ間に介在する輪郭上の他の頂点座標デー
   タの個数が所定個数範囲に属しても、その局所的な凹凸
   部分に係る頂点座標データを除去したと仮定した場合の
   総頂点数が所定個数より少ない場合には、それら２個の
   頂点座標データ間の輪郭部分を局所的な凹凸部分と認定
   することを禁止することを特徴とする請求項３に記載の
   輪郭データ簡略化方法。