面積を持つ導体領域や禁止エリアのパターンメンテンス方法の閉図形抽出方法に関する。[0002]【従来の技術】従来の閉図形抽出方法は、独立に与えられた線分群に対し、それぞれの端点を共有する線分を順次トレースし、分岐点に達した場合は始めに見つけた線分を優先してトレースし、他の分岐線分はトレースは行わない。example,順次トレースして閉図形300を検出する。トレースしながらトレース済みの線分にフラグを立て、二度とトレースしない様にする。この様なシーケンスをフラグの立っていない線分がなくなるまで繰り返す。eliminated.【0003】図4において、1回目のトレースが行われなかった線分群301は閉図形を形成しないため、2回目のトレース時においてコの字型の閉じていない線分と見なされ閉図形としてはキャンセルされる。[0004]【発明が解決しようとする課題】上述した従来の閉図形抽出方法は、与えられた線分群の中に分岐点が存在した場合、その中の1つのみを有効にしてトレースしていたため、場合によっては検出できない閉図形があった。したがって、コンピュータが理解できるように、データ入力者が慎重にデータ入力を行っていた。閉図形内にもう一つの閉図形が含まれているドーナツ状の閉図形表現として図2の様に変形した凹図形は扱えないという難点があった。point,もう一方の端点に接続する他の線分を探索する事を繰り返し線分を連鎖的にトレースする手順と、トレース時にトレース済みのフラグを立てていく手順と、端点を共有する線分が複数存在した場合に手前の線分とのなす角度が最も大きくなる線分を選び出す手順と、他の線分をスタックしておく手順と、トレースによって開始点に戻った場合トレースした線分を閉図形を構成する辺として出力する手順と、スタックしておいた線分を開始線分として同様にトレースをする手順と、スタックしておいた線分にトレース済みのフラグが立っているものをキャンセルする手順を備えて構成される。[0006]【実施例】次に、本発明の実施例について図面を参照して説明する。Diagram)形式のフローチャートである。FIG.【0008】図1は本発明が提案するアルゴリズムのフローチャートを示し、この図1のアルゴリズムにしたがって、図2以降で具体的に説明する。later.【0009】図2の様な線分群が与えられた場合、任意の線分をまず抽出する事になるが、ここでは後に続くトレース処理を反時計方向に進めるため、できるだけ左下の端点を抽出する事とする。そのために最小のy座標を含む線分をまず求め、さらに水平線とのなす角度が小さい線分を更に選択する。図2では最小のy座標を含む線分として線分101、線分112、線分102が候補に上がるが、水平線とのなす角度が小さい線分101なのでこれを開始線分として選出する。1に決定し、端点2を共有する線分102を検出する。反対側の端点3を共有する線分を検出するが、これは線分103、線分107、線分108が存在する。これらの内、線分102とのなす角度が最大のものは、線分103および線分107であるが、さらに長さの短い線分103が採用される。したがって、トレースとしては端点4を共有する線分を探す事になる。この際線分107と線分108をスタックしておく。このようにしてトレースを続けると線分107に到達するが、端点3にも同様の分岐が存在することから、上記と同様の規則を適用すると線分108がトレース線分として選び出され、かつ線分102と線分103がスタックされる。この様にして線分110に至り、開始点1に到達して閉図形200が出力される。出力時に閉図形の辺をなす線分にはそれを表現するフラグを立てておく。stacked,閉図形の検出を開始するが、線分107と線分108および線分102、線分103はすでに閉図形として検出済みであることが上記のフラグで判明するので、開始線分としての候補からははずされ、スタックが空になった事から処理が終了する。completed.【0011】もう一例として、図3の場合で説明する。123で構成される閉図形を作成した後、この図形を大きくするように修正しようと試み線分124、線分125、線分126を追加した状況で起こる。not,図面としてはそのままにしても、問題はない。segment0が選ばれる。トレースを開始して線分121に至るがここで線分124がスタックされ、線分122でトレースが進められる。output.【0012】次にスタック内の線分124から開始点を端点22としてトレースが開始される。線分125、線分126と進み、ここで分岐点である端点23に到達するので、線分123がスタックされ、線分122でトレースが再開される。この段階で開始点である端点22に到達するので、2つ目の閉図形202が出力される。output.【0013】さて、残されたスタックには線分123と線分126が存在しているが、すでに出力された閉図形の辺の構成要素としてのフラグが立っているので、開始線分としての候補とはならず処理が終了する。[0014]【発明の効果】以上説明したように、本発明の閉図形抽出方法は、複数の線分が端点を共有する際、その分岐点をスタックしておくことで、閉図形となりうる図形は漏らさず検出することが可能である。分岐における複数の線分から、どれをトレース対象とし、どれをスタックするかを一意的に決定する方法を与える事で、実行時の偶然性を排除することが可能である。分岐におけるトレース対象の抽出において、直前の線分との角度が最大であるものという条件と、トレース開始の線分の決定方法とで、極力小刻みに閉図形を出力する様になり、与えられた線分群の情報を漏らさず閉図形にする考慮が可能となる。Diagram)形式のフローチャートである。format.【図2】本実施例の閉図形抽出方法における動作の一例を示す図である。embodiment.【図3】本実施例の閉図形抽出方法における動作の一例を示す図である。embodiment.【図4】従来の閉図形抽出方法における動作を示す図である。claims]【請求項1】両端点の座標が与えられた複数の線分に対し任意の線分を抽出しその片側を開始点として記憶する手順と、もう一方の端点に接続する他の線分を探索する事を繰り返し線分を連鎖的にトレースする手順と、トレース時にトレース済みのフラグを立てていく手順と、端点を共有する線分が複数存在した場合に手前の線分とのなす角度が最も大きくなる線分を選び出す手順と、他の線分をスタックしておく手順と、トレースによって開始点に戻った場合トレースした線分を閉図形を構成する辺として出力する手順と、スタックしておいた線分を開始線分として同様にトレースをする手順と、スタックしておいた線分にトレース済みのフラグが立っているものをキャンセルする手順を備えることを特徴とする閉図形抽出方法。