JPH077456B2

JPH077456B2 - 重合度による図形の認識装置

Info

Publication number: JPH077456B2
Application number: JP63286519A
Authority: JP
Inventors: 正行谷守
Original assignee: Dainippon Screen Manufacturing Co Ltd
Current assignee: Dainippon Screen Manufacturing Co Ltd
Priority date: 1988-11-11
Filing date: 1988-11-11
Publication date: 1995-01-30
Anticipated expiration: 2010-01-30
Also published as: JPH02132569A; US5179645A

Description

【発明の詳細な説明】〔産業上の利用分野〕この発明は、ICなどの回路パターン設計などに用いられ
るCADや、図形を出力するプロッターなどに用いられる
重合度による図形の認識装置に関する。

〔従来の技術〕

周知のように、重合度による図形の認識装置は従来より
いくつか提案されている。これらの例として特開昭57−
14964や特開昭59−60560が挙げられる。

特開昭57−14964においては、ある図形の端点のうち他
の図形の閉ループに含まれていない端点を基点として、
図形を所定の方向にたどり、交点に達したら他の図形の
閉ループにスイッチしていく方法が開示されている。こ
のような方法においては、ある点が閉ループの内か外か
という判定や、ループを順にたどっていくという工程に
多大な時間を要する。またAND図形やOR図形を認識する
工程を別に設ける必要がある。

また、特開昭59−60560においては、与えられた複数の
閉図形を各スリットごとに分割して、各図形平面の重合
度を認識するという装置が開示されている。このような
装置においては、各スリットの分割に従って閉図形を構
成するラインが不必要に分断され、後処理のつなぎ換え
に多大な時間を要する。

さらに円弧などのパラメトリックな部分（半径などのパ
ラメータを有する関数による図形）を含む図形に対して
は、多角形近似により直線図形に置き換えて上述のよう
な処理を行っていた。このため多角形近似のために多大
な時間を要し、また出力された図形も不正確な形になる
ことが多い。

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

以上のように従来の方法では、ある点が閉ループの内か
外かの判定や、ループをたどっていく処理、または構成
ラインを不要に分割し再度つなぎ直す処理などのため、
全体処理に多大な時間を要するという問題点があった。
この傾向は処理しようとする図形が複雑になればなるほ
ど増大する。

また、各重合度に対応して図形を出力する場合、別々の
工程を経なければならないという問題点もあった。

さらに、円弧などのパラメトリックな部分を含む図形に
対して短時間で正確に重合度に応じた図形の出力などの
演算処理動作が行える装置は開発されていなかった。

〔発明の目的〕この発明は以上のような事情を考慮してなされたもので
あり、複雑な図形に対しても処理全体に要する時間を大
幅に短縮でき、重合度の異なる図形についてもそれらを
認識する工程を共通化し、さらにパラメトリックな部分
を含む図形の処理においても短時間で正確に演算処理が
行えるような重合度による図形の認識方法を得ることを
目的とする。

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

この発明に係る重合度による図形の認識装置は、複数の
閉図形から図形の重なり態様を示す指定された重合度に
よる図形を認識するにあたって、まず複数の閉図形の構
成ラインのデータをベクトル形式で表現してリスト構造
で蓄積する（蓄積手段）。また、これら複数の図形が形
成する交点を検出する（交点検出手段）。

次に、分断手段によって、交点のそれぞれにつき、当該
交点において各構成ラインを分断して分断ラインとす
る。

また、この装置は、交点ごとに、当該交点への各分断ラ
インの出入方向を区別しつつ、分断ラインの位置に応じ
た順序で各分断ラインを登録するバッファメモリを備え
ている。後述する実施例における「ライトバッファ」お
よび「レフトバッファ」に相当する。

そして、交点ごとに、当該交点に出入りする各分断ライ
ンで分割された各分割平面を当該交点をまわる方向に沿
って追跡しつつ、各分割平面に至るまでに分断ラインを
通過した数を前記出入方向を正負の符号で区別しつつカ
ウントして、そのカウント値に応じた数値フラグを各分
割平面について決定するとともに、前記バッファメモリ
中の各分断ラインに、当該分断ラインの前記出入り方向
に向かって一方の側に隣接する分割平面についての前記
数値フラグを付与する（カウント手段）。

この数値フラグは後述する実施例における「プライオリ
ティーフラグ」に相当し、各交点において生成された分
断ラインがどのような重合部分の輪郭に相当するライン
であるかを表現している。

分断ラインはつなぎ換え手段によってつなぎ換えられる
が、それにあたっては交点のそれぞれについて前記バッ
ファメモリをアドレス順に検索し、前記出入方向が逆で
あり、かつ前記数値フラグが同一値である分断フラグの
対を発見する都、それらの対を相互に接続させる。

このような分断およびつなぎ換えを経た後の構成ライン
の中から、所望の重合度に応じて指定されるスタートラ
インにつながった構成ラインの組合わせを抽出する（抽
出手段）。

そして、抽出された構成ラインの組合わせを、所望の重
合度を有する図形の認識結果として出力する（出力手
段）。

この発明の装置は、CADやプロッタなど所定の画像処理
装置を用いた図形記録または図形表示のために使用され
る。

〔作用〕

この発明におけるラインの分断およびつなぎ換えは、図
形の交点のみに着目して行わるので、重合度による図形
を認識する装置を簡略化する。

またラインの分断およびつなぎ換えが行われ、再構成さ
れたラインのデータはリスト構造により認識されるの
で、所望の重合度に応じたスタートラインを指定するこ
とにより、それにつながる構成ラインの組合わせで構成
された、任意の重合度に対応する図形が出力される。

〔実施例〕

A.全体構成と概略構成第２図はこの発明の一実施例を適用する図形の入出力装
置を示す概念図である。入力タブレット１上にスタイラ
スペン２などによって、処理対象となる閉図形を入力す
る。入力された閉図形は処理装置３において、後述する
論理画像処理などを施され、CRT4などの出力機器に出力
される B.準備工程第１図はこの発明の一実施例による重合度による図形の
認識装置の準備工程を示すフローチャートである。また
第3A図はこの方法を適用する対象図形の例で、一部重な
りを有する２つの三角形△ABCと△DEFを示す図である。

まず、ステップS11に示されている閉図形の認識方法に
ついて説明する。三角形△ABCは第3B図に示すように三
角形の内部がその進行方向の左側になるような３つのラ
イン（ベクトル）AB,BC,CAに分解される。同様に三角形
△DEFはラインDE,EF,FDに分解される。これらのライン
はその始点および終点を記憶することにより認識でき
る。さらに閉図形を認識するためには、各ライン間の接
続関係を認識する必要がある。ここではリスト構造を導
入し、着目したラインの前後のラインをそれぞれ着目し
たラインのデータ内に含まれるポインタP1,P2（図示せ
ず）で指定しておく。表１は三角形△ABC,△DEFをそれ
ぞれリスト構造によりデータ構成した場合の、各データ
間の関係を示したものである。

実際のデータの構造においては、ポインタP1,P2は、そ
の前後のラインの始点および終点のデータが格納されて
いるアドレスまたはファイルネームなどをそれぞれ指示
する。ここでは、それらを一括してラインの名称によっ
て代表させている。また、ラインのデータはハード構成
上ラインバッファLNB（後述する第16図参照）に格納さ
れる。なお、以下の説明において、各バッファやメモリ
等の参照符号は、第16図の構成に対応している。

次に、ステップS12に進み頂点を認識する。頂点は各ラ
インの始点または終点として、おのおの少なくとも一度
ずつ現れる。始点だけに着目すればすべての頂点を漏れ
なく列挙できる。さらに後で平面走査法を用いるため
に、表２に示すように頂点のｘ座標に関するソーティン
グを行う。なお、同じｘ座標を有するものはｙ座標につ
いてもソーティングを行う。

このような処理はハード構成上、下記表３のような記憶
内容を持つ頂点バッファAPBを設けてその中で行えばよ
い。

さらに、各頂点のうち最も左側のものから順番に平面走
査法を適用し、周知のベントレーオットマン（Bentley-
Ottmann）の交差判定により各頂点を通るスィープライ
ンSL（後述する第４図の例ではSL₁₀〜SL₅₀）上の各ライ
ン間の交点を求める。なおスィープラインSL上のライン
の認識はワークリストWLを設けて行う。また交点が求ま
った場合は順次交点バッファCRBに登録していく。これ
らのハード構成については後で詳述する。この際、現在
交差判定を行っているスィープランSLより、左側にある
交点については、すでに処理済みであるので登録せず、
右側にあるものだけを登録する。また交点においても頂
点と同様に、平面走査法を適用し、後述するラインの分
断とつなぎ換えとを行う。交点が交点バッファCRBに登
録された時点で次の頂点のｘ座標との比較を行い、それ
らのうちの最もｘ座標の小さいものについて、次のスイ
ープラインSLの設定を行う。

第４図は第3B図に示す図形に対して交差判定を行った時
のようすを示す図である。

前述した表２に示すように、ソーティングされた頂点の
うちまず頂点ＢについてスイープラインSL₁₀を設定す
る。ワークリストWL内には、ラインABおよびラインBCが
登録されている。この２つのライン間で頂点Ｂを除いて
交差判定を行う。交点が存在しないので、次の頂点、こ
の例では頂点D,Aに共通にスイープラインSL₂₀を設定す
る。ワークリストWL内にはラインFD,DEおよびラインCA
が追加される。またラインABについては、始点，終点と
ともに走査されたので処理済みと見做してワークリスト
WLより削除する。以下、同様の順によりワークリストWL
へのラインの追加，削除をくり返す。なおワークリスト
WLは後述するラインの分断とつなぎ換えとにおいても用
いられ、ラインの分断などによりその内容は一部変更さ
れる。その場合の構成については後で詳述する。

スイープラインSL₂₀においてワークリストWL内にはライ
ンBC,DE,FDおよびCAが登録されている。これらのライン
はｙ座標について小さいものからソーティングされ、同
じｙ座標を有するものについては、そのラインのｘ−ｙ
座標上での直線の傾きについて小さいものから順にソー
ティングされている。交点を求める際には、新たにワー
クリストWLに追加するラインDEと、その上下に隣接する
ラインとについて交差判定を行う。ラインDEについて交
差判定を行ったら、次の新たにワークリストWLに追加す
るラインFDについて、同様の交差判定を行う。このよう
にして、少なくとも現在の頂点と次の頂点との間に存在
する交点はすべて求められる。なおワークリストWL内の
ラインのソーティング順は逆（ｙ座標の大きい方および
傾きの大きい方優先）でもよい。このようにしてライン
BCとラインDEの交点X1およびラインFDとラインCAの交点
X2が求まる。これらはスイープラインSL₂₀より右側にあ
るので、交点バッファCRBに登録される。表４は交点バ
ッファCRBの一例を示したものであり、各交点はｘ座標
によってソーティングされる。

交点X2,X1は次の頂点Ｃよりも左側にあるので、まずス
イープラインSL₂₁が交点X2に、次のスイープラインSL₂₂
が交点X1の位置に設定される。この位置でのワークリス
の内容等は後述するラインの分断とつなぎ換えとに関連
して説明する。

この交点X2,X1の次に頂点ＣにスイープラインSL₃₀、頂
点ＥにスイープラインSL₄₀および頂点Ｆにスイープライ
ンSL₅₀が設定され、最も右側の頂点Ｆにおいて平面走査
が終了する。これらの位置でのワークリストWLの内容に
ついても後述する。

次にステップS13におけるラインの分断，つなぎ換えに
ついて説明する。実際には平面走査により頂点，交点を
認識し、スイープラインSLを設定するたびに、ラインの
分断とつなぎ換えとを行うべきかどうかを判断する。

まず交点X2におけるつなぎ換えについて第５図を参照し
て説明する。頂点におけるつなぎ換えについては後述す
る。交点X2において、一つ前のスイープラインSL₂₀にお
けるワークリストWL0と現在のスイープラインSL₂₁にお
けるワークリストWL1をワークリストWLとは別に準備す
る。ワークリストWL1は、ワークリストWL0を基にして、
交点X2で交差しているラインFDおよびラインCAの順番を
入れ換えた内容になっている。

またラインCAおよびFDを交点X2において分断し、その方
向は保ったままラインCAからラインＣ・X2とラインX2・
Ａとを、また、ラインFDからラインＦ・X2とラインX2・
Ｄをそれぞれ形成する（これらがこの発明における「分
断ライン」に相当する）。これらのラインのうち、交点
X2より左側にあるものを用いてワークリストWL0を、右
側にあるものを用いてワークリストWL1を表5,表６のよ
うに書き換える。なおラインバッファLNBの内容もこの
分断により書き換えられる。

次にラインのつなぎ換えを行うためにワークリストWL0,
WL1から交点X2に関するラインX2・D,X2・A,F・X2および
Ｃ・X2を抽出し、交点より左側のものはレフトバッファ
LBに、右側のものはライトバッファRBに、順番を保った
まま登録する。レフトバッファLBおよびライトバッファ
RBは、つなぎ換えを行う時にのみ構築される。

さらにプライオリティーフラグPFを次のように規定す
る。交点X2に関するラインによって分割された各平面に
対して、交点X2から見て最も下側の平面においてPF＝０
とする。そして、第6A図に示すように、ｙ軸の正方向に
進行していき、右向きまたは垂直上向きのラインを通過
した時には、その平面に対してプライオリティーフラグ
PFを１だけ増加させ、左向きまたは垂直下向きのライン
を通過した時にはプライオリティーフラグPFを１だけ減
少させる。なお垂直なラインを通過する時は右から左に
通過する。このようにして交点のまわりのラインにより
分割された各平面にプライオリティーフラグPFを付与す
る。次に各ラインの進行方向に対して左側の平面のプラ
イオリティーフラグPFをそのラインのプライオリティー
フラグPFとする。次に、以上の規定によって、レフトバ
ッファLBおよびライトバッファRB内の各ラインについ
て、プライオリティーフラグPFを付与する処理を行う。

第6B図は交点X2において、各ラインにプライオリティー
フラグPFを付与した時のようすを示した図である。まず
全てのラインより見て下側に位置する領域R1においてプ
ライオリティーフラグPF＝０とする。領域R1からライン
Ｃ・X2を通過した位置にある領域R2においては、ライン
Ｃ・X2が左向きなので、プライオリティーフラグPFは０
から１減少してPF＝−１となる。同様に領域R3において
もPF＝−１、また領域R4においてはPF＝−２となる。

次に各ラインに対して、その左側の領域の有するプライ
オリティーフラグPFを、そのラインのプライオリティー
フラグPFとして付与していく。つまり、ラインＣ・X2,X
2・ＤにはPF＝0,ラインＦ・X2,X2・ＡにはPF＝−１を付
与する。

また交点X2が各ラインの始点または終点のいずれになる
かを判定し、各ラインに方方向フラグDFを付与する。交
点X2に入ってくるラインならDF＝１、出ていくラインな
らDF＝０とする。また後述するつなぎ換え処理を行った
かどうかを示す処理フラグRF（処理済ならRF＝１、未処
理ならRF＝０）を各ラインに付与し、下記表7,表８に示
すようにレフトバッファLB,ライトバッファRBをそれぞ
れ完成する。なお表7,表８においては第６図のラインの
接続関係との対照のために各ラインのデータを昇順に記
している。

以上のように各バッファを完成したら、交点より右側で
かつ最も下側のラインからつなぎ換え処理を行う。着目
しているラインとプライオリティーフラグPFが等しくか
つ、交点に対する向きが逆向きの（進行フラグDFが等し
くない）ラインを反時計まわりに検索し、該当するライ
ンが存在したらその２つのラインを接続する。そして次
のラインに移り、同様の動作を行う。この際いったんつ
なぎ換えの対象になったラインは処理フラグRFを１にし
ておき次回以後の検索対象外とする。

反時計まわりに検索するには、ライトバッファRBの最も
アドレスの小さいラインから始め、ライトバッファRB内
ではアドレスのインクリメント動作を行い、全て検索し
たらレフトバッファLB内の最アドレスの大きいラインに
移りアドレスのデクリメント動作を行えばよい。またラ
インのつなぎ換え動作によるデータの変更は、各ライン
のデータがリスト構造であるため、各ラインのポインタ
P1,P2を書き換えることによって簡単に行える。

表7,表８に示す交点X2におけるレフトバッファLB,ライ
トバッファRBにおいて、ラインＣ・X2から上記の検索を
行った場合、ラインＣ・X2とラインX2・Ｄおよびライン
Ｆ・X2とラインX2・Ａが新たに接続される。これらのラ
インの接続関係はリスト構造により記憶され、各ライン
のデータはラインバッファLNBに再格納される。同様の
処理を交点X1においても行うと、ラインDEはラインＤ・
X1,X1・Ｅに、ラインBCはラインＢ・X1,X1・Ｃに分断さ
れ、ラインＤ・X1とラインX1・ＣおよびラインＢ・X1と
ラインX1・Ｅがそれぞれ新たに接続される。

また、頂点ＣにおけるスイープラインSL₃₀についてのワ
ークリストWLの内容は、これらの分断，つなぎ換えが行
われたラインのデータを用いる。頂点C,E,Fについては
ラインの分断，つなぎ換えを行わず、単にワークリスト
WL内にラインの追加，削除を行うだけである。頂点F,ス
イープラインSL₅₀において平面走査を終了し、ラインの
再構成を完了する。

また後述する演算出力工程において用いるために、各頂
点，交点においてラインの分断，つなぎ換えを行った時
はつなぎ換え後のパターン、つなぎ換えを行わない時は
元のパターンからスタートラインを取り出し、スタート
ラインメモリSTLMに記憶しておく。

スタートライとは、後述するように、所要の図形をとり
出すための最初の構成ラインとなるものであり、第7A図
〜第7D図に示すパターンのように、その頂点を構成する
すべてのラインが頂点よりも左側にない場合において、
それらのラインのうちの右向きのものをさす。つまり、
図においては、頂点を通るスイープラインSL₇₁,SL₇₂,SL
₇₃およびSL₇₄より左側にあるラインがないので、それら
のラインの中の右向きのラインL1,L2,L3およびL4がそれ
ぞれの場合のスタートラインとなる。

また、あるスイープラインSLにおいて、上述したような
スタートラインが発生した場合は、以下に述べる規則に
従って各スタートラインに白黒カウンタWBを付与する。
まず、着目しているスイープラインSLにおけるワークリ
ストWL内のすべてのラインから見て、最の下側の分割さ
れた平面においてWB＝０とする。次にプライオリティー
フラグPFの場合と同様にｙ軸の正方向に進行していく。
つまり、ワークリストWL内のラインを下から順にたどっ
ていき、右向きのラインを通過した時にはその平面に対
して白黒カウンタWBを１増加させ、左向きのラインを通
過した時には白黒カウンタWBを１減少させる。分割され
た各平面に白黒カウンタが付与されたら、各スタートラ
インの進行方向に対して左側の平面の白黒カウンタWBを
そのスタートラインの白黒カウンタWBとする。

なお、スタートラインの認識は、各頂点，交点ごとに、
第７図に示すような条件を満足した時だけ行われるの
で、第１図のフローチャートには明記していない。

以上のように各点において平面走査を完了したら、新た
に構成された各ラインのデータをラインバッファLNBに
格納し、準備工程を終了する。第８図は第3A図に示す図
形に以上の工程を施して得られた最終的なパターンであ
り、ラインSTL1,STL2はそれぞれWB＝1,2であるスタート
ラインを、また矢印を付した円弧は各ライン間の接続関
係を示している。

C.演算出力工程第９図はこの発明の一実施例での重合度による図形の認
識方法の演算出力工程を示すフローチャートである。ス
テップS91において、前述した準備工程で再構成された
閉図形のデータをラインバッファLNBから読み出す。ま
た、次のステップS92で、スタートラインメモリSTLMか
らスタートラインを読み出す。以上の工程は準備工程で
用意されたデータを再び読み出すものである。

ステップS93において、重合度に応じたスタートライン
を指定し、対応する図形を求める。この分割された各平
面の重合度は白黒カウンタWBによって示される。OR図形
なら白黒カウンタWBが１の平面を指定すればよく、AND
図形なら白黒カウンタWBが２の平面を指定すればよい。
これらの図形の最外形線は、各出力図形の重合度に応じ
た白黒カウンタWBを有するスタートラインを指定し、そ
こから順に元のスタートラインにもどるまで各ラインを
接続していくことにより求められる。

前述した第８図から、第3A図に示す三角形△ABC,△DEF
のAND図形を求める場合について説明する。まずWB＝２
であるスタートラインSTL2をまず指定し、リスト構造に
よりラインL12,L22,L32とたどっていき、ラインSTL2に
もどり閉ループを形成したら、その内部がAND図形とな
る。またOR図形についてもWB＝１であるラインSTL1を指
定し、ラインL11,L21,L31,L41,L51とたどっていけば同
様にして得られる。

また、排他的OR図形なども、このようにして得られたOR
図形にAND図形の周知のヌキ動作を施せば簡単に得られ
る。

さらに、より複雑な図形において２重AND,3重AND図形を
得たい場合には、WB＝3,4のスタートラインをそれぞれ
指定することにより同様にして得られる。

ステップS94において、得られた図形をCRTやプロッター
などの出力機器に出力する。以上の工程を経て演算出力
工程を終了する。

D.応用例次にこの発明の重合度による図形の認識装置を円弧など
のパラメトリックな図形を含む複数の閉図形に適用する
場合について説明する。

第10図はこの発明の適用対象の一例であるパラメトリッ
ク図形を含む複数の閉図形を示す図である。三角形△AB
Cおよび円弧JKGを含む閉図形のGHJKが示されている。点
Ｋにおいて円弧JKGはｙ軸に平行なスイープラインSL_ｋ
に接し、かつ曲線の方向がｘ軸について逆になっている
ので点Ｋは変曲点となる。なお、ここでで言う「変曲
点」とは、通常の意味における変曲点（２階微係数の符
号変化点）ではなく、着目している構成ラインを所定の
方向にたどり、ｘ方向に関して、そのラインの方向が変
化する点を指すものとする。

まず前処理として、このような変曲点を求めておき、次
に隣接する頂点から仮想ラインJK,KGを第11図に示すよ
うに想定する。このような処理は平面走査を行うに際し
て、一つのラインが一スイープラインSL上で２つ以上の
ｙ座標を持たないようにするためのものである。

次に第１図に示す準備工程のステップS11と同様に閉図
形の入力を行う。三角形△ABCは前述した例と同様の形
で入力される。また図形GHJKは変曲点Ｋを求められ、第
10図，第11図に示すようにラインGH,HJおよび円弧JK,KG
に分割して入力される。また円弧JK,KGに対応する仮想
ラインJK,KGも同時に求められ入力される。

次にステップS12と同様に頂点および交点を平面走査法
により認識する。第12図に示すスイープラインSL_ｈにお
いて、ワークリストWL内にはラインHJ,GH,BC,CAが登録
されており、これらはすべて通常のラインであるので前
述した交差判定方法を用い、交点X10を認識する。ライ
ンの分断，つなぎ換えも前述した方法により同様に行
う。

スイープラインSL_ｇに進むと仮想ラインKGがワークリス
トWL内に登録される。仮想ラインが登録された場合は、
もとの円弧KGのデータを用いて交差判定を行う。なお他
の通常のラインの間の交差判定は、前述したとおりであ
る。

円弧KGとラインCAとの交点X20が求まったら、この交点
のデータを用いて、仮想ラインKGのかわりに仮想ライン
Ｋ・X20,X20・Ｇを登録する。

次に第13図を参照して、交点X20でのラインの分断，つ
なぎ換えを説明する。

前述した例と同様に、各ラインおよび各仮想ラインを交
点X20で分断し、プライオリティーフラグPF,方向フラグ
DF,処理フラグRFを付与する。レフトバッファLB,ライト
バッファRBは下記表9,10のようになる。

この表9,10から前述した規則に従って（仮想）ラインの
つなぎ換えを行う。ラインＧ・X20と仮想ラインX20・Ｇ
および仮想ラインＫ・X20とラインX20・Ａとがそれぞれ
新たに接続される。

交点X20における処理が終了したら、頂点C,J,Kにおいて
ワークリストWLに各（仮想）ラインの登録，削除を行う
だけである。以上の準備工程を終了した後の各（仮想）
ラインの接続関係を第14図に示す。

さらに演算出力工程においては、仮想ラインにより記憶
されている部分をもとのパラメトリックな図形におきか
えて第15A図，第15B図のようにそれぞれOR図形,AND図形
を出力することができる。

以上のようにパラメトリックな図形に対しても、その認
識のための分割を最小に抑え、交点の認識および演算出
力以外は直線図形と同様の手順よって図形の論理演算を
行うことができる。

E.回路構成以上のような処理を行う処理装置３（第２図）の回路構
成を第16図のブロック図に示す。入力ポートIPから処理
対象となる複数の閉図形がCPUに入力される。CPUは閉図
形のパターンを認識し、リスト構造を有するラインのデ
ータおよび頂点のデータをそれぞれ、ラインバッファLN
Bおよび頂点バッファAPBに入力する。また、前述した平
面走査により、現在のワークリストWL1および１つ前の
ワークリストWL0が構築され、ワークリストWL0からはレ
フトバッファLBが、ワークリストWL1からはライトバッ
ファRBが前述したラインの分断，つなぎ換えのために構
築される。この時プライオリティーフラグ用カウンタPF
Cも構築される。

平面走査を行い交点が認識された場合は交点バッファCR
Bに、またスタートラインが認識された場合はスタート
ラインメモリSTLMに入力される。前述したように図形の
演算出力工程においてスタートラインは白黒カウンタWB
Cから白黒カウンタWBを付与される。さらにこのスター
トラインをもとにして、指定された重合度に応じたライ
ンが出力ポートOPから読み出される。出力ポートOPは通
常CRT,プロッターなどの出力機器のバッファに接続され
ている。

F.変換例第17A図，第17B図はラインの分断，つなぎ換えを行うべ
き頂点の例を示す図である。第17A図はラインL71,L72で
形成された頂点を別のラインL73が通過している場合、
第17B図は２以上の頂点が重なっており、それぞれのラ
インの組（L74,L75）と（L76,L77）とから形成される２
つの領域に一部重なりがある場合である。このような頂
点は、各ラインの上下関係、すなわちその頂点から出る
ラインおよびその頂点に入るラインが上下方方向にどの
ような順序で配列しているかによって認識され、前述し
たラインの分断，つなぎ換え処理の対象となる。

なお、以上の実施例においては、ｘ方向に対して平面走
査を行う例について述べたが、ｙ方向に対して平面走査
を行う場合についても同様の手法を適用できる。

〔発明の効果〕

以上のようにこの発明によれば、入力された複数の閉図
形において、それらの閉図形の交点のみに着目してライ
ンの分断およびつなぎ換えを行うので、装置全体の構成
が簡略化され、処理全体に要する時間を大幅に短縮でき
る。

また、ラインの分断およびつなぎ換え処理を施され、再
構成された閉図形のデータは、リスト構造により認識さ
れるので、任意の重合度に応じて対応する図形が出力で
き、重合度の異なる図形についても、処理のための構成
を共通化できる。

さらに、パラメトリックな部分を含む図形の処理にも適
用でき、近似ラインを少なくし、また必要に応じて元の
データを読み出すことにより、短時間で正確に図形の演
算処理が行える。また、ラインのつなぎ換えにあたって
は、各交点において生成された分断ラインにその分断ラ
インがどのような重合部分の輪郭に相当するラインであ
るかを表現する数値フラグを付与し、その数値フラグに
基づいてつなぎ換えを行っているため、２つの図形のみ
ならずそれ以上の図形が重なっている場合でも、高速か
つ自動的な重合度ごとの図形認識が可能となる。

【図面の簡単な説明】

第１図はこの発明の一実施例による重合度による図形の
認識装置の準備工程を示すフローチャート、第２図はこの発明の一実施例にかかる装置の概略図、第３図はこの発明を適用する対象の一例である三角形お
よび、その構成ベクトルを示す図、第４図は第３図に示す三角形を平面走査して、交差判定
を行うようすを示す図、第５図は交点におけるラインの分断，つなぎ換えのよう
すを示す図、第６図はプライオリティーフラグの付与方法を示す図、第７図はスタートラインを示す図、第８図は第３図に示す三角形を再構成して得たたパター
ンを示す図、第９図はこの発明の一実施例による重合度による図形の
認識装置の演算出力工程を示すフローチャート、第10図はパラメトリック図形を含む閉図形を示す図、第11図は第10図に示す閉図形の仮想ラインを示した図、第12図は第11図に示す図形に平面走査を適用したようす
を示した図、第13図は第11図に示す図形の交点におけるラインの分
断，つなぎ換えのようすを示した図、第14図は再構成されたパラメトリック図形の例を示す
図、第15図は第14図に示す図形から演算出力された図形を示
す図、第16図はこの発明の実施例である装置の回路構成を示す
ブロック図、第17図は頂点におけるつなぎ換えのようすを示す図であ
る。１……入力タブレット、２……スタイラスペン、３……処理装置、４……CRT、 LNB……ラインバッファ、 APB……頂点バッファ、CRB……交点バッファ、 WL……ワークリスト、 PFC……プライオリティーフラグ用カウンタ、 STLM……スタートラインメモリ、 WBC……白黒カウンタ

Claims

【特許請求の範囲】

【請求項１】所定の画像処理装置を用いた図形記録また
は図形表示のために、複数の閉図形に対して図形の重な
り態様を示す重合度を指定することにより、前記重合度
による図形を認識する装置であって、前記複数の閉図形の構成ラインのデータをベクトル形式
で表現してリスト構造により蓄積する蓄積手段と、前記複数の図形が形成する交点を検出する交点検出手段
と、前記交点のそれぞれにつき、当該交点において各構成ラ
インを分断して分断ラインとする分断手段と、前記交点ごとに、当該交点への各分断ラインの出入方向
を区別しつつ、前記分断ラインの位置に応じた順序で前
記分断ラインを登録するバッファメモリと、前記交点ごとに、当該交点に出入りする各分断ラインで
分割された各分割平面を当該交点をまわる方向に沿って
追跡しつつ、各分割平面に至るまでに分断ラインを通過
した数を前記出入方向を正負の符号で区別しつつカウン
トして、そのカウント値に応じた数値フラグを各分割平
面について決定するとともに、前記バッファメモリ中の
各分断ラインに、当該分断ラインの前記出入り方向に向
かって一方の側に隣接する分割平面についての前記数値
フラグを付与するカウント手段と、前記交点のそれぞれについて前記バッファメモリをアド
レス順に検索し、前記出入方向が逆であり、かつ前記数
値フラグが同一値である分断フラグの対を発見する都
度、それらの対を相互に接続させることにより、各交点
において前記構成ラインのつなぎ換えを行うつなぎ換え
手段と、前記分断およびつなぎ換えを経た後の前記構成ラインの
中から、所望の重合度に応じて指定されるスタートライ
ンにつながった構成ラインの組合わせを抽出する抽出手
段と、前記抽出された構成ラインの組合わせを、前記所望の重
合度を有する図形の認識結果として出力する出力手段
と、を備えることを特徴とする、重合度による図形の認識装
置。