JPH02115986A - 格子状点列データの等高線生成方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、格子状点列データの等高線生成方法に関し、
特に処理量を削減できる汎用的な等高線の作図法に関す
る。

〔従来の技術〕

従来のコンピュータ・ソフトウェアによる図形処理にお
いては、二次元差分法データに対する簡易で万能な等高
線作図アルゴリズムがなく、差分法の隣接する格子線で
囲まれる四角形を全て三角形に分割する方法が多く用い
られていた。

すなわち、従来の作図法は、例えば、特開昭６０−６５
３８０号公報に記載されているように、点列データに対
して３点のデータからなる三角形ごとに等高線のセグメ
ントを生成する処理を行っていた。この方法では、三次
元点列データメモリから曲面補間された三次元データを
読み取り、三角メツシュ・ジェネレータで三次元データ
を三角形に分割し、三角形単位で頂点に相当する内容を
メモリに格納した後、再び読み出して交点計算機で交点
計算を行っている。そして、等高値を検索し、連続等高
線を作成する。

〔発明が解決しようとする課題〕

しかし、三゛角形に分割する方法では、四角形内では等
高線が折れて作図されてしまうという問題がある。また
、このような従来の方法では、格子状態に分布する点列
データに対して、４点からなる矩形ごとに等高線のセグ
メントを生成する処理については配慮されていなかった
。このため、三角形ごとの処理は四角形ごとの処理の２
倍の処理が必要であり、セグメント生成のための処理量
が多くなっていた。

本発明の目的は、このような従来の課題を解決し、三角
形ごとに処理を行う方法に比べて、セグメント生成のた
めの処理量を削減することができる格子状点列データの
等高線生成方法を提供することにある。

〔課題を解決するための手段〕

上記目的を達成するため、本発明による格子状点列デー
タの等高線生成方法は、格子状に分布し、かつ高さを有
する二次元点列データと、等高線高さデータとから各々
セグメントを生成し、該セグメントで形成された等高線
を連結し、折れ線発生器により上記連結された等高線を
発生して、該等高線をグラフィック装置に表示する等高
線生成方法において、上記セグメントをプログラムによ
り自動的に生成する際に、４点のデータからなる矩形ご
とに周辺上の異なる交点の個数を調べ、交点数が２より
少ないときには等高線セグメントを生成せず、交点数が
２のときには例外の場合を除いて該２交点を始・終点と
する等高線セグメントを生成し、交点数が２より多いと
きには、４つの全頂点のデータ値が等高線高さと一致す
る場合を除き１等高線セグメントを生成し、３つの頂点
のデータ値が等高線高さと一致する場合には対角関係の
２頂点を始・終点とするセグメントを生成し。

また１矩形に対し２つのセグメントを生成できる場合に
は、対角線で２分割してできる２つの三角形について、
各々交点を通るセグメントを生成することに特徴がある
。

〔作　　用〕

本発明においては、格子状に分布する点列データに対し
て、４点からなる矩形ごとに等高線のセグメントを生成
する処理を行う。すなわち、格子状に分布する点列デー
タの４点からなる矩形について、その矩形の周と等高線
高さを格納したメモリから、所定の等高線高さとの交点
数を求める。

求められた交点数と交点パターンに従って、等高線のセ
グメントを１本または２本生成するか、あるいは生成し
ないですます。この場合、各矩形に対して、特定方向の
対角線を基準に交点パターンを識別することにより、高
さの異なる等高線が交差しないようにする。これにより
、三角形ごとに処理を行う方法に比べて、セグメントを
生成するための処理量を減少させることが可能である。

〔実施例〕

以下、本発明の一実施例を、図面により詳細に説明する
。

第４図は、本発明の一実施例を示す等高線描画処理装置
のブロック図である。

第４図において、１１は格子状に分布し、それぞれ高さ
を持つ二次元点列データを格納しておくための点列デー
タ格納メモリ、１２は点列データ格納メモリ１１からデ
ータを読み出すためのデータ読取り部、１３は描画する
等高線の高さのデータを平面的に配列したものを格納す
る等高線高さ格納メモリ、１４は本発明の中心をなす処
理部であって、データ読取り部１２により読み取られた
座標値とメモリ１３から所定の等高線高さとの交点計算
を行い、等高線セグメント座標を生成するためのセグメ
ント生成部、１５は生成されたセグメントを格納するた
めのセグメント格納メモリ、１６はセグメント格納メモ
リ１５に格納されているセグメント座標を取り出し、そ
れらのセグメントを連結して等高級を作成するための等
高級連結部、１７は連結されたセグメント群をグラフィ
ック装置１８に出力するために折れ線を発生する折れ線
発生部、１８は発生された折れ線を表示するためのグラ
フィック装置である。

本発明においては、このような構成の処理装置により、
セグメント主成部１４内でプログラムにより自動的に４
点のデータからなる矩形ごとにセグメントを生成し、そ
れらのセグメントを連結して、データの尾根と谷に該当
する部分、つまり格子点を通る等高級を作成する。

第２図は、第１図の装置により描画された等高線描画例
を示す図である。

第２図において、ｅ、＋はデータ値〉実線の等高級の高
さを満足する部分であり、ｅ、−は逆にデータ値く実線
の等高級の高さを満足する部分であり、０はデータ値＝
実線の等高級の高さを満足する部分であり、・は交点で
あって、ここでは１〜４のケース（これらについては、
第３図で説明する）についてのみ示している。また、第
２図では、図示された実線の等高級よりも高さの高い等
高級の一例を破線で示している。

ここでは、実線の等高級は、左下部分と中央部分と右上
部分の３つが示されている。この場合、左下の等高級と
の交点２個と、中央の等高級との交点２個とが同一の矩
形４に存在するようなケースを、２セグメント生成のケ
ースと呼ぶ。なお、交点が３個の矩形でも、２セグメン
ト生成の場合がある。また、中央の等高級で、等高級が
１つの矩形１内の４頂点のうち、２箇所で交差する場合
を゛２２頂例外ケースと呼ぶ。さらに、右上部の４個の
交点は、実線の等高級高さと同一の高さを有する頂点の
交点であって、これらが１つの矩形３に含まれているの
で、これを４頂点ケースと呼ぶ。

また、その下方の矩形は、３頂点ケー入と呼ばれるもの
で、１つの矩形２内の４頂点のうちの３つの点が等高級
と同一高さであり、そのうちの２つの頂点間に等高級が
引かれる。この等高級の方向を、基準となる対角線方向
と呼ぶ。

次に、各ケースの定義をする。

（ａ）　　ＩＩ’２頂点例外ケースｊ１は。

基準の対角線を挟んで向い合う２頂点におけるデータ値
が等高級高さと一致しくそれらの２頂点が交点）、他の
２頂点におけるデータ値が共に等高級高さより大（また
は小）である場合を言う。

（ｂ）　　ｌｉ’３頂点ケースＪ２は、３つの頂点にお
けるデータ値が等高級高さと一致する場合（３頂点が交
点）を言う。

（ｃ）［ｒ４４頂ケース」３は。

４つの全頂点におけるデータ値が、等高級高さと一致す
る場合（４頂点が交点）を言う。

第３図は、矩形と等高級高さとの交点パターンを示す図
である。

第３図において、１〜４の数字が付けられた矩形は、第
２図に対応するものであって、１が２頂点例外ケース、
２が３頂点ケース、３が４頂点ケース、４が２セグメン
ト生成のためのケースである。４頂点ケース３、および
２頂点例外ケース１は、それぞれ１つの場合しかないが
、３頂点ケース２は左上から右下のセグメントと、右上
から左下のセグメントの２つの場合がある。また、２セ
グメント生成のケース４は、−点鎖線内に示すように５
つの場合がある。すなわち、上２つの場合のように、左
上から右下に並行して２つのセグメントが引かれるが、
左側は囲まれた部分が周囲よりも高い場合であり、右側
は囲まれた部分が周囲よりも低い場合である。また、下
３つの場合のように、左上から右下に並行して２つのセ
グメントが引かれるが、そのうちの１つのセグメントが
ない場合と、並行する２つのセグメントが３つのうちの
１つで交差する場合である。

第３図の右上の１２個の矩形は、いずれも頂点でない位
置に等高級との交点が２つあるものであり、右上から左
下、左上から右下、縦横の各方向にセグメントが引かれ
る。

第３図の右下に示される１０個の矩形は、いずれも頂点
の１〜４個が等高級と等しい高さを有するものである。

この中に２頂点例外ケース１と４頂点ケース３も含まれ
ている。

第１図は、第４図におけるセグメント生成部の処理フロ
ーチャートである。

第２図および第３図を参照しながら、第１図によりセグ
メント生成処理を詳述する。

いま、格子状に分布する点列データがメモリ１１に、ま
た描画する等高級の高さがメモリ１３に、それぞれ格納
されているものとする。先ず、メモリ１３から所定の等
高級高さを入力しくステップ１０１）、次にメモリ１１
データ読取り部１２を介して読み取ったデータについて
、１矩形分のデータを取り出す（ステップ１０２）。こ
の矩形データと等高級高さとの交点計算を行い、矩形同
上の異なる交点の個数を調べる（ステップ１０３，１０
４）。交点が２より小さい場合（つまり、１個のとき）
、交点が２の場合、および交点が２より大きい場合（つ
まり、３個と４個のとき）の３つの場合がある。

（ｉ）交点数く２の場合 この場合には、等高線セグメントの生成は行わず、デー
タの終りでなければ５次の矩形データの取り出しを行い
（ステップ１１１，１０２）、処理を繰り返す。また、
データの終りであれば、処理を終了する（ステップ１１
１）。

（ｉｉ）交点数＝２の場合 この場合には、「２頂点例外ケースｊ１のときを除いて
、２交点を始・終点とする等高線セグメントの生成を行
い、これをメモリ１５に格納する（ステップ１０８）。

以下、交点数〈２の場合と同じ処理を繰り返す（ステッ
プ１１１，１０２）。

（ｉｉｉ）交点数〉２の場合 ｒｆ４頂点ケースＪ３の場合には、セグメントを生成し
ない（ステップ１０６）。また、「３頂点ケースＪ２の
場合には、３頂点におけるデータ値が等高級高さと一致
する場合であるが、このときには対角線にある２頂点を
始・終点とするセグメントを生成して、これを格納する
（ステップ１１０）。

その他の場合には、「２セグメントの生成」４の場合に
該当し、矩形を基準の対角線で２分割して形成される２
つの三角形につ゛いて、各々交点を通るセグメントを生
成して、これを格納する（ステップ１０９）。すなわち
、この場合には、１矩形に対して、２つのセグメントが
生成される。以下。

交点数く２の場合と同じような処理を繰り返す（ステッ
プ１１１，１０２）。

ところで、「２頂点例外ケースｊ１におし＼ては、第２
図の１に示すように、等高線セグメントを生成すると、
破線で示す他の等高級を同時表示した際に交差してしま
うことがわかる。これは、「２セグメントの生成」４の
場合の矩形の分割対角線方向との関連で発生する。これ
は、第３図に示す交点パターンを１つずつ調べることに
より、「２頂点例外ケースｊ１のみが、他の等高級と交
差する可能性のあることがわかる。

本実施例においては、格子状に分布する点列データに対
して、矩形単位に等高線セグメントの生成を行うことが
できるので、三角形単位に処理する場合に比べて処理量
が削減できる。その削減量の概算を以下に示す。

〔１〕三角形単位に行うセグメント生成処理に比べて、
セグメント生成の処理量を約２／３に削減することがで
きる。

（セグメント生成の処理量）弁（データ単位数）＊　（
データ単位当りの交点計算数） の算出式において、本実施例では、（データ単位数）が
２つの三角形を１つの矩形単位で扱えるので、処理量は
１／２となり、また（データ単位当りの交点計算数）は
、データ単位の辺の数に比例するので、三角形に比べて
矩形は４／３である。

従って、処理量の比は、 （１／２）　　申　（４／３）　　＝２／３となる。

〔２〕三角形単位に行うセグメント生成処理に比べて、
生成するセグメントの数も約２／３に削減することがで
きる。従って、等高級のプロット数も約２／３に削減で
きる。

すなわち、これを第３図で説明すると、等高級高さが矩
形の頂点のデータ値と一致することはまれであるため１
図の上３段のパターンのみについて考えれば充分である
。ここにおけるセグメント数は、全部で１６である。そ
れに対して、矩形を一定方向の対角線で分割して２つの
三角形単位に処理すると、セグメント数は２４になるこ
とがわかる。従って、一般に、等高級のプロット数の比
はセグメント数の比であるから、１６／２４＝２／３と
なる。

〔発明の効果〕

以上説明したように、本発明によれば、格子状に分布す
る点列データの等高線描画において、４点のデータから
なる矩形単位に等高線セグメントを生成できるので、三
角形単位にセグメントを生成する場合に比べて、処理量
を削減することが可能である。

【図面の簡単な説明】

第１図は本発明の一実施例を示すセグメント生成部の処
理フローチャート、第２図は第１図の処理による等高線
描画例を示す図、第３図は第１図の処理における矩形と
等高級高さとの交点パターンを示す図、第４図は本発明
の一実施例を示す等高線描画処理装置のブロック図であ
る。 １１：点列データ格納メモリ、１２：データ読取り部、
１３：等高級高さ格納メモリ、１４：セグメント生成部
、１５：セグメント格納メモリ、１６：等高級連結部、
１７：折れ線発生器、１８ニゲラフイツク装置。 第 図 ＋・、・データ値〉実線の等高級高さ ０　・・・　　／／　　ｗｍ　　　　／／く 交点（１〜４のケースについてのみ示す）第 図

Claims (1)

【特許請求の範囲】
1. １、格子状に分布し、かつ高さを有する二次元点列デー
   タと、等高線高さデータとから各々セグメントを生成し
   、該セグメントで形成された等高線を連結し、折れ線発
   生器により上記連結された等高線を発生して、該等高線
   をグラフィック装置に表示する等高線生成方法において
   、上記セグメントをプログラムにより自動的に生成する
   際に、４点のデータからなる矩形ごとに周辺上の異なる
   交点の個数を調べ、交点数が２より少ないときには等高
   線セグメントを生成せず、交点数が２のときには例外の
   場合を除いて該２交点を始・終点とする等高線セグメン
   トを生成し、交点数が２より多いときには、４つの全頂
   点のデータ値が等高線高さと一致する場合を除き、等高
   線セグメントを生成し、３つの頂点のデータ値が等高線
   高さと一致する場合には対角関係の２頂点を始・終点と
   するセグメントを生成し、また１矩形に対し２つのセグ
   メントを生成できる場合には、対角線で２分割してでき
   る２つの三角形について、各々交点を通るセグメントを
   生成することを特徴とする格子状点列データの等高線生
   成方法。