JPH04372068A - 閉図形デ−タ処理方法 - Google Patents
閉図形デ−タ処理方法Info
- Publication number
- JPH04372068A JPH04372068A JP3149115A JP14911591A JPH04372068A JP H04372068 A JPH04372068 A JP H04372068A JP 3149115 A JP3149115 A JP 3149115A JP 14911591 A JP14911591 A JP 14911591A JP H04372068 A JPH04372068 A JP H04372068A
- Authority
- JP
- Japan
- Prior art keywords
- closed
- overlap
- line segment
- degree
- data processing
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【０００１】
【産業上の利用分野】本発明は、プリント基板のパタ−
ンや商品形状等の図形デ−タ処理方法に関し、特にそれ
らのパタ−ンを閉図形として取り扱い、その重複を高速
に検出することができる閉図形デ−タ処理方法に関する
。
ンや商品形状等の図形デ−タ処理方法に関し、特にそれ
らのパタ−ンを閉図形として取り扱い、その重複を高速
に検出することができる閉図形デ−タ処理方法に関する
。
【０００２】
【従来の技術】ＣＡＤ等の方法では、通常、異なる複数
の図形を重ね合わせて、その重複度を検出する処理が必
要である。従来、このような処理に関するものとしては
、例えば、特開平２−５３８２３号公報に記載された図
形デ−タ処理方法がある。これによれば、閉図形の線分
化を行って、その向きにより＋−を付した後、縦方向に
領域分割線を決定し、領域毎に下方から上方に向って順
次線分数を加減算していく（＋のとき加算、−のとき減
算）。そして、加減算した結果を多重度とするのである
。これにより、中抜き空間域の重なりも多重度を計測す
ることができる。
の図形を重ね合わせて、その重複度を検出する処理が必
要である。従来、このような処理に関するものとしては
、例えば、特開平２−５３８２３号公報に記載された図
形デ−タ処理方法がある。これによれば、閉図形の線分
化を行って、その向きにより＋−を付した後、縦方向に
領域分割線を決定し、領域毎に下方から上方に向って順
次線分数を加減算していく（＋のとき加算、−のとき減
算）。そして、加減算した結果を多重度とするのである
。これにより、中抜き空間域の重なりも多重度を計測す
ることができる。
【０００３】
【発明が解決しようとする課題】このように、従来の閉
図形の重複度決定方法は、閉図形を構成する各線分に向
きを与え、線用の端点を通るＹ軸に平行な直線により他
の線分を分割し、Ｙ座標の小さい順に並べ換えて、その
後Ｙ座標の小さい順に線分の向きに従って各線分に多重
度を設定することにより、閉図形の重なりを検出してい
た。しかしながら、この方法によれば、閉図形の重なり
部分は検出できるが、どの閉図形とどの閉図形とが重複
しているかを検出することができなかった。本発明の目
的は、このような従来の課題を解決し、閉図形デ−タの
重なりを高速に検出するとともに、どの閉図形とどの閉
図形とが重複しているかを検出することが可能な閉図形
デ−タ処理方法を提供することにある。
図形の重複度決定方法は、閉図形を構成する各線分に向
きを与え、線用の端点を通るＹ軸に平行な直線により他
の線分を分割し、Ｙ座標の小さい順に並べ換えて、その
後Ｙ座標の小さい順に線分の向きに従って各線分に多重
度を設定することにより、閉図形の重なりを検出してい
た。しかしながら、この方法によれば、閉図形の重なり
部分は検出できるが、どの閉図形とどの閉図形とが重複
しているかを検出することができなかった。本発明の目
的は、このような従来の課題を解決し、閉図形デ−タの
重なりを高速に検出するとともに、どの閉図形とどの閉
図形とが重複しているかを検出することが可能な閉図形
デ−タ処理方法を提供することにある。
【０００４】
【課題を解決するための手段】上記目的を達成するため
、本発明の閉図形デ−タ処理方法は、（イ）座標軸に平
行な線分により構成される複数の閉図形の重なりを判定
する閉図形デ−タ処理方法において、入力情報として閉
図形が中抜きか否かの情報が与えられると、閉図形を構
成する各線分に対して、中抜きの場合には右回りに、そ
うでない場合には左回りに、それぞれ方向を与える第１
ステップと、各閉図形毎に固有の正数値を各線分に対し
て付与し、かつ線分のＸおよびＹ座標が増加する方向を
持つ時には正数値を、減少する方向を持つ時には正数値
×（−１）を与える第２ステップと、各線分の端点を通
り、予め決められた座標軸と平行な直線により他の線分
を分割する第３ステップと、第３ステップで用いた軸と
交差する軸に平行な方向に、最下側ないし最上側から上
昇ないし下降しながら重なり度をチェックしていき、線
分の持つ値が正数の時には重なりを＋１し、負数の時に
は重なりを−１して計数する第４ステップを有すること
に特徴がある。また、（ロ）第４ステップでは、第２ス
テップで付与された数値を用いて、どの閉図形とどの閉
図形とが重複しているかを判定することにも特徴がある
。また、（ハ）第１から第４ステップの他に、重なり１
以上の閉図形と重なり０以下の閉図形（中抜き）に分け
るステップを有することにも特徴がある。さらに、（ニ
）第４ステップで、隣接する直線間の領域の重なりを決
定する場合に、重なりを０から始めて０で終ることをチ
ェックし、入力閉図形群が正しいか否かを判定すること
にも特徴がある。
、本発明の閉図形デ−タ処理方法は、（イ）座標軸に平
行な線分により構成される複数の閉図形の重なりを判定
する閉図形デ−タ処理方法において、入力情報として閉
図形が中抜きか否かの情報が与えられると、閉図形を構
成する各線分に対して、中抜きの場合には右回りに、そ
うでない場合には左回りに、それぞれ方向を与える第１
ステップと、各閉図形毎に固有の正数値を各線分に対し
て付与し、かつ線分のＸおよびＹ座標が増加する方向を
持つ時には正数値を、減少する方向を持つ時には正数値
×（−１）を与える第２ステップと、各線分の端点を通
り、予め決められた座標軸と平行な直線により他の線分
を分割する第３ステップと、第３ステップで用いた軸と
交差する軸に平行な方向に、最下側ないし最上側から上
昇ないし下降しながら重なり度をチェックしていき、線
分の持つ値が正数の時には重なりを＋１し、負数の時に
は重なりを−１して計数する第４ステップを有すること
に特徴がある。また、（ロ）第４ステップでは、第２ス
テップで付与された数値を用いて、どの閉図形とどの閉
図形とが重複しているかを判定することにも特徴がある
。また、（ハ）第１から第４ステップの他に、重なり１
以上の閉図形と重なり０以下の閉図形（中抜き）に分け
るステップを有することにも特徴がある。さらに、（ニ
）第４ステップで、隣接する直線間の領域の重なりを決
定する場合に、重なりを０から始めて０で終ることをチ
ェックし、入力閉図形群が正しいか否かを判定すること
にも特徴がある。
【０００５】
【作用】本発明においては、中抜きの閉図形に右回りの
方向を与えて、そうでない閉図形には左回りの方向を与
えておけば、複数の閉図形が入力されて、それらが重な
っている部分において、最も多重になっている部分（四
辺形）でもやはり中抜きの四辺形は右回りの方向を持ち
、そうでない四辺形は左回りの方向を持つという性質に
着目している。このため、重なり度を０から始めて各四
辺形の線分の向きを調べていくことにより、四辺形の重
なり度を検出することができる。各閉図形に異なる正数
値を割り当てているので、その重なり度のチェックを通
じて、どの閉図形とどの閉図形とが重複しているが判定
できる。先ず、（ａ）中抜きの時には右回りの方向を、
そうでない時には左回りの方向を、閉図形の各線分に与
える。次に、（ｂ）各閉図形に異なる正数値を与え、そ
の数値について各線分の方向を考慮して、線分値として
各線分に与える。具体的には、線分の方向がＸ座標また
はＹ座標が増加するときには、閉図形に与えた正数値自
体を与え、Ｘ座標またはＹ座標が減少するときには、閉
図形に与えた正数値×（−１）を与える。さらに、（ｃ
）各線分の端点を通り、予め決められている座標軸に平
行な直線が他の線分と交差するときには、その交点で線
分を分割する。最後に、（ｄ）線分分割で用いた軸と交
差する軸に平行な方向で考えた時に、最下側（または最
上側）にある線分から順に上昇方向（最上側から始める
時には下降方向）にある線分から順に、各線分の持つ値
をチェックしながら閉図形の重なりを検出する。具体的
には、重なり０から開始して線分の持つ値が正数の時に
は重なりを＋１し、負数の時には−１する。
方向を与えて、そうでない閉図形には左回りの方向を与
えておけば、複数の閉図形が入力されて、それらが重な
っている部分において、最も多重になっている部分（四
辺形）でもやはり中抜きの四辺形は右回りの方向を持ち
、そうでない四辺形は左回りの方向を持つという性質に
着目している。このため、重なり度を０から始めて各四
辺形の線分の向きを調べていくことにより、四辺形の重
なり度を検出することができる。各閉図形に異なる正数
値を割り当てているので、その重なり度のチェックを通
じて、どの閉図形とどの閉図形とが重複しているが判定
できる。先ず、（ａ）中抜きの時には右回りの方向を、
そうでない時には左回りの方向を、閉図形の各線分に与
える。次に、（ｂ）各閉図形に異なる正数値を与え、そ
の数値について各線分の方向を考慮して、線分値として
各線分に与える。具体的には、線分の方向がＸ座標また
はＹ座標が増加するときには、閉図形に与えた正数値自
体を与え、Ｘ座標またはＹ座標が減少するときには、閉
図形に与えた正数値×（−１）を与える。さらに、（ｃ
）各線分の端点を通り、予め決められている座標軸に平
行な直線が他の線分と交差するときには、その交点で線
分を分割する。最後に、（ｄ）線分分割で用いた軸と交
差する軸に平行な方向で考えた時に、最下側（または最
上側）にある線分から順に上昇方向（最上側から始める
時には下降方向）にある線分から順に、各線分の持つ値
をチェックしながら閉図形の重なりを検出する。具体的
には、重なり０から開始して線分の持つ値が正数の時に
は重なりを＋１し、負数の時には−１する。
【０００６】
【実施例】以下、本発明の実施例を、図面により詳細に
説明する。図１は、本発明において、入力される閉図形
の線分構成図である。図１において、いま図形１，３を
中抜き閉図形とし、図形２，４をそうでない閉図形であ
るとする。座標系の５，６をそれぞれＸ軸、Ｙ軸とした
時、閉図形１，３は中抜きであるため、右回りの方向を
、また閉図形２，４はそうでない閉図形であるため、左
回りの方向を、それぞれ与える。これにより、各閉図形
を構成する線分には、図２に示すような方向が与えられ
ることになる。
説明する。図１は、本発明において、入力される閉図形
の線分構成図である。図１において、いま図形１，３を
中抜き閉図形とし、図形２，４をそうでない閉図形であ
るとする。座標系の５，６をそれぞれＸ軸、Ｙ軸とした
時、閉図形１，３は中抜きであるため、右回りの方向を
、また閉図形２，４はそうでない閉図形であるため、左
回りの方向を、それぞれ与える。これにより、各閉図形
を構成する線分には、図２に示すような方向が与えられ
ることになる。
【０００７】図２は、入力閉図形が中抜きか否かに応じ
て与えられた線分の向きの説明図である。図２のような
方向が与えられた各閉図形１〜４に対して、それぞれ１
から順に閉図形固有の整数値を与えることにより、縦方
向の矩形に１と２が、横方向矩形に３と４が、それぞれ
付与される。このように、閉図形に固有の数値を与える
ことが、本実施例の１つの特徴である。これにより、各
線分については、図２に示す方向に従ってＸ座標または
Ｙ座標が増加する方向の時には、その数値自体（つまり
、＋）が割り当てられ、また減少する方向の時には、そ
の数値に−１を乗じた数値が割り当てられる。すなわち
、閉図形１と３については、右回りであって、上辺はＸ
軸で増加する方向であるため、正の整数が、右辺はＹ軸
で減少する方向であるため、−１を乗じた整数、下辺も
Ｘ軸で減少する方向であるため、−１を乗じた整数、左
辺はＹ軸で増加する方向にあるため、正の整数が、それ
ぞれ与えられる。また、閉図形２と４については、左回
りであって、上辺はＸ軸で減少する方向にあるため、−
１を乗じた整数、右辺はＹ軸で増加する方向にあるため
、正の整数、下辺はＸ軸で増加する方向にあるため、正
の整数、左辺はＹ軸で減少する方向にあるため、−１を
乗じた整数が、それぞれ与えられる。その割り当てられ
た結果を、図３に示す。
て与えられた線分の向きの説明図である。図２のような
方向が与えられた各閉図形１〜４に対して、それぞれ１
から順に閉図形固有の整数値を与えることにより、縦方
向の矩形に１と２が、横方向矩形に３と４が、それぞれ
付与される。このように、閉図形に固有の数値を与える
ことが、本実施例の１つの特徴である。これにより、各
線分については、図２に示す方向に従ってＸ座標または
Ｙ座標が増加する方向の時には、その数値自体（つまり
、＋）が割り当てられ、また減少する方向の時には、そ
の数値に−１を乗じた数値が割り当てられる。すなわち
、閉図形１と３については、右回りであって、上辺はＸ
軸で増加する方向であるため、正の整数が、右辺はＹ軸
で減少する方向であるため、−１を乗じた整数、下辺も
Ｘ軸で減少する方向であるため、−１を乗じた整数、左
辺はＹ軸で増加する方向にあるため、正の整数が、それ
ぞれ与えられる。また、閉図形２と４については、左回
りであって、上辺はＸ軸で減少する方向にあるため、−
１を乗じた整数、右辺はＹ軸で増加する方向にあるため
、正の整数、下辺はＸ軸で増加する方向にあるため、正
の整数、左辺はＹ軸で減少する方向にあるため、−１を
乗じた整数が、それぞれ与えられる。その割り当てられ
た結果を、図３に示す。
【０００８】図３は、線分の向きと閉図形の値から計算
した各線分の線分値を示す図である。図３において、次
に各線分の端点を通り、予め決められた座標軸（ここで
はＹ軸とする）に平行な直線で他の線分を分割する。す
なわち、重なりの数を計数する処理の準備のために、線
分を分割して四辺形が集合した領域として取り扱う。分
割された結果を、図４に示す。
した各線分の線分値を示す図である。図３において、次
に各線分の端点を通り、予め決められた座標軸（ここで
はＹ軸とする）に平行な直線で他の線分を分割する。す
なわち、重なりの数を計数する処理の準備のために、線
分を分割して四辺形が集合した領域として取り扱う。分
割された結果を、図４に示す。
【０００９】図４は、線分の端点を通る直線による線分
り分割を示す図である。図４では、各線分の直線による
分割点を小さな黒角マ−クを使って表わしている。また
、分割のために用いた直線は、破線で示している。次に
、本実施例の重なり度の計数処理に移る。すなわち、分
割された線分により囲まれた四辺形について、分割に分
いた直線のＸ座標の小さい順に最下側から重なり度を計
数する。線分が正の数を持つ時には重なりを＋１し、負
の数を持つ時には重なりを−１するものである。
り分割を示す図である。図４では、各線分の直線による
分割点を小さな黒角マ−クを使って表わしている。また
、分割のために用いた直線は、破線で示している。次に
、本実施例の重なり度の計数処理に移る。すなわち、分
割された線分により囲まれた四辺形について、分割に分
いた直線のＸ座標の小さい順に最下側から重なり度を計
数する。線分が正の数を持つ時には重なりを＋１し、負
の数を持つ時には重なりを−１するものである。
【００１０】図５は、線分により挟まれた領域の重なり
度計数処理の説明図である。ここでは、直線７と８の間
の領域を例にとって、その処理を説明する。先ず、直線
７，８の間の領域内の最下側に存在する線分９の持つ値
（線分値とする）は２であるため（図３参照）、線分９
より上に位置する領域の重なり度は１となる。次に、存
在するのは線分１０であり、その線分値は４である（図
３参照）。このため、重なり度は＋１され、線分１０よ
り上の領域の重なり度は２となる。従って、線分９、１
０の間の領域の重なり度が１であると確定する。さらに
、線分１０の上に線分１１が存在し、線分１１の線分値
は−１である（図３参照）。線分値が負であるため、重
なり度は−１されて１となる。従って、線分１０，１１
の間の領域の重なり度が２であると確定する。次に、存
在する線分は１２であり、その線分値は−３である（図
３参照）。線分値が負であるため、重なり度は−１され
て０となる。従って、線分１１と１２の間の領域の重な
り度が１であると確定する。次に、存在する線分は１３
であり、線分値は３である。重なり度は＋１されて２と
なる。従って、線分１２，１３間の領域の重なり度は２
であると確定する。次に、存在する線分は１４であり、
線分値は１である。重なり度は＋１されて３となる。従
って、線分１３，１４間の領域の重なり度は３であると
確定する。次に、存在する線分は１５であり、線分値は
−４である。重なり度は−１されて２となる。従って、
線分１４，１５間の領域の重なり度は２であると確定す
る。次に、存在する線分は１６であり、線分値は−２で
ある。重なり度は−１されて１になる。従って、線分１
５，１６間の領域の重なり度は１であると確定する。こ
のようにして、図５における直線７，８の間の線分９〜
１６の線分値をチェックすることにより、隣り合う２つ
の線分間の領域の重なり度を確定することができる。同
じようにして、全ての直線の間の線分間の領域の重なり
度をチェックする。
度計数処理の説明図である。ここでは、直線７と８の間
の領域を例にとって、その処理を説明する。先ず、直線
７，８の間の領域内の最下側に存在する線分９の持つ値
（線分値とする）は２であるため（図３参照）、線分９
より上に位置する領域の重なり度は１となる。次に、存
在するのは線分１０であり、その線分値は４である（図
３参照）。このため、重なり度は＋１され、線分１０よ
り上の領域の重なり度は２となる。従って、線分９、１
０の間の領域の重なり度が１であると確定する。さらに
、線分１０の上に線分１１が存在し、線分１１の線分値
は−１である（図３参照）。線分値が負であるため、重
なり度は−１されて１となる。従って、線分１０，１１
の間の領域の重なり度が２であると確定する。次に、存
在する線分は１２であり、その線分値は−３である（図
３参照）。線分値が負であるため、重なり度は−１され
て０となる。従って、線分１１と１２の間の領域の重な
り度が１であると確定する。次に、存在する線分は１３
であり、線分値は３である。重なり度は＋１されて２と
なる。従って、線分１２，１３間の領域の重なり度は２
であると確定する。次に、存在する線分は１４であり、
線分値は１である。重なり度は＋１されて３となる。従
って、線分１３，１４間の領域の重なり度は３であると
確定する。次に、存在する線分は１５であり、線分値は
−４である。重なり度は−１されて２となる。従って、
線分１４，１５間の領域の重なり度は２であると確定す
る。次に、存在する線分は１６であり、線分値は−２で
ある。重なり度は−１されて１になる。従って、線分１
５，１６間の領域の重なり度は１であると確定する。こ
のようにして、図５における直線７，８の間の線分９〜
１６の線分値をチェックすることにより、隣り合う２つ
の線分間の領域の重なり度を確定することができる。同
じようにして、全ての直線の間の線分間の領域の重なり
度をチェックする。
【００１１】図６は、本発明の一実施例を示す閉図形デ
−タ処理方法の手順のＰＡＤ図である。先ず、閉図形番
号を０に初期化し（ステップ１０００）、入力閉図形が
終るまで重なり準備処理を実行する（ステップ２０００
）。すなわち、閉図形に固有の番号をインクリメントし
ながら順次付与する（ステップ３０００）。そして、閉
図形が中抜きのとき（ステップ４０００）、線分を右回
りに方向付けし（ステップ５０００）、そうでないとき
、線分を左回りに方向付けする（ステップ６０００）。 そして、線分値割り当て（固有の整数に＋または−を付
す）を行う（ステップ７０００）。次に、線分端点を通
る直線による線分分割を行う（直線１〜ｎ）（ステップ
８０００）。そして、その直線１〜ｎのうち、１〜ｎ−
１について次の処理を行う（ステップ９０００）。すな
わち、ある直線とそれに隣接する直線の間の線分を取り
出し（線分１〜ｍ）（ステップ１００００）、１〜ｍ−
１に対して次の処理を行う（ステップ１２０００）。す
なわち、線分の値が正のとき（ステップ１３０００）、
重なりをインクリメントする（ステップ１４０００）。 負のときには、重なりをデクリメントする（ステップ１
５０００）。そして、隣り合う線分間の重なりを確定す
る（ステップ１７０００）。確定した重なり度をテ−ブ
ルに登録する（ステップ１８０００）。
−タ処理方法の手順のＰＡＤ図である。先ず、閉図形番
号を０に初期化し（ステップ１０００）、入力閉図形が
終るまで重なり準備処理を実行する（ステップ２０００
）。すなわち、閉図形に固有の番号をインクリメントし
ながら順次付与する（ステップ３０００）。そして、閉
図形が中抜きのとき（ステップ４０００）、線分を右回
りに方向付けし（ステップ５０００）、そうでないとき
、線分を左回りに方向付けする（ステップ６０００）。 そして、線分値割り当て（固有の整数に＋または−を付
す）を行う（ステップ７０００）。次に、線分端点を通
る直線による線分分割を行う（直線１〜ｎ）（ステップ
８０００）。そして、その直線１〜ｎのうち、１〜ｎ−
１について次の処理を行う（ステップ９０００）。すな
わち、ある直線とそれに隣接する直線の間の線分を取り
出し（線分１〜ｍ）（ステップ１００００）、１〜ｍ−
１に対して次の処理を行う（ステップ１２０００）。す
なわち、線分の値が正のとき（ステップ１３０００）、
重なりをインクリメントする（ステップ１４０００）。 負のときには、重なりをデクリメントする（ステップ１
５０００）。そして、隣り合う線分間の重なりを確定す
る（ステップ１７０００）。確定した重なり度をテ−ブ
ルに登録する（ステップ１８０００）。
【００１２】図７は、重なり度が確定した矩形の説明図
であり、図８は、重なり度が確定した矩形を登録するテ
−ブル構成図である。図７において、１７が線分Ｊ−１
、１８が線分Ｊである。ここでは、重なり度ｎが確定し
ている。図８において、重なり度が登録されるテ−ブル
には、矩形始点座標と矩形終点座標と重なり度とが記憶
される。矩形始点座標と矩形終点座標は、図７を参照す
ることにより明らかとなる。矩形始点座標は、図７に示
すように、四辺形領域の左下の座標であり、矩形終点座
標は、四辺形領域の右上の座標である。このようにして
、閉図形の重なりを検出し、決定しているので、重なり
２以上となる部分を構成する線分の持つ値やチェックし
てきた線分の持つ値を保持しておくことにより、どの閉
図形とどの閉図形とが重複しているかが容易に判定でき
る。また、重なりを判定した図形は各座標軸に平行な線
分で構成される四辺形で表現されている。この四辺形に
与えられた重なり度を区分することにより、重なり１以
上の四辺形と重なり０以下（中抜き）の四辺形に分ける
ことは容易に行える。さらに、この処理で、重なり０か
ら各四辺形の重なり度をチェックした場合、入力した図
形が正しければ、最後に来る線分の先の領域の重なり度
も０となるはずである。このことを用いれば、入力図形
の構成が正しいか否かの判定も可能となる。
であり、図８は、重なり度が確定した矩形を登録するテ
−ブル構成図である。図７において、１７が線分Ｊ−１
、１８が線分Ｊである。ここでは、重なり度ｎが確定し
ている。図８において、重なり度が登録されるテ−ブル
には、矩形始点座標と矩形終点座標と重なり度とが記憶
される。矩形始点座標と矩形終点座標は、図７を参照す
ることにより明らかとなる。矩形始点座標は、図７に示
すように、四辺形領域の左下の座標であり、矩形終点座
標は、四辺形領域の右上の座標である。このようにして
、閉図形の重なりを検出し、決定しているので、重なり
２以上となる部分を構成する線分の持つ値やチェックし
てきた線分の持つ値を保持しておくことにより、どの閉
図形とどの閉図形とが重複しているかが容易に判定でき
る。また、重なりを判定した図形は各座標軸に平行な線
分で構成される四辺形で表現されている。この四辺形に
与えられた重なり度を区分することにより、重なり１以
上の四辺形と重なり０以下（中抜き）の四辺形に分ける
ことは容易に行える。さらに、この処理で、重なり０か
ら各四辺形の重なり度をチェックした場合、入力した図
形が正しければ、最後に来る線分の先の領域の重なり度
も０となるはずである。このことを用いれば、入力図形
の構成が正しいか否かの判定も可能となる。
【００１３】
【発明の効果】以上説明したように、本発明によれば、
複数の閉図形の重なりが高速、かつ簡単に求められるた
め、プリント基板における導体の重なりや、搭載部品の
重なりのチェックも高速化され、その利点は大である。
複数の閉図形の重なりが高速、かつ簡単に求められるた
め、プリント基板における導体の重なりや、搭載部品の
重なりのチェックも高速化され、その利点は大である。
【００１４】
【図１】本発明の入力閉図面の構成を示す図である。
【図２】入力閉図面が中抜きか否かに応じて与えられた
線分の向きの説明図である。
線分の向きの説明図である。
【図３】線分の向きと閉図面の値から計算した各線分の
線分値を示す図である。
線分値を示す図である。
【図４】線分の端点を通る直線による線分の分割を示し
た図である。
た図である。
【図５】線分による挟まれた領域の重なり度計数の説明
図である。
図である。
【図６】本発明の一実施例を示す閉図形デ−タ処理方法
の手順のＰＡＤ図である。
の手順のＰＡＤ図である。
【図７】重なり度が確定した矩形の説明図である。
【図８】重なり度が確定した矩形を登録するテ−ブルの
構成図である。
構成図である。
１，３ 中抜き入力閉図形、
２，４ 入力閉図形（中抜きでないもの）５ Ｘ軸
６ Ｙ軸
７，８ 線分分割直線
９〜１４ 分割された線分
１７ 線分Ｊ−１
１８ 線分Ｊ
Claims (4)
- 【請求項１】 座標軸に平行な線分により構成される
複数の閉図形の重なりを判定する閉図形デ−タ処理方法
において、入力情報として上記閉図形が中抜きか否かの
情報が与えられると、該閉図形を構成する各線分に対し
て、中抜きの場合には右回りに、そうでない場合には左
回りに、それぞれ方向を与える第１ステップと、各閉図
形毎に固有の正数値を各線分に対して付与し、かつ該線
分のＸおよびＹ座標が増加する方向を持つ時には正数値
を、減少する方向を持つ時には該正数値×（−１）を与
える第２ステップと、各線分の端点を通り、予め決めら
れた座標軸と平行な直線により他の線分を分割する第３
ステップと、第３ステップで用いた軸と交差する軸に平
行な方向に、最下側ないし最上側から上昇ないし下降し
ながら重なり度をチェックしていき、線分の持つ値が正
数の時には重なりを＋１し、負数の時には重なりを−１
して計数する第４ステップを有することを特徴とする閉
図形デ−タ処理方法。 - 【請求項２】 上記第４ステップでは、第２ステップ
で付与された数値を用いて、どの閉図形とどの閉図形と
が重複しているかを判定することを特徴とする請求項１
に記載の閉図形デ−タ処理方法。 - 【請求項３】 上記第１から第４ステップの他に、重
なり１以上の閉図形と重なり０以下の閉図形（中抜き）
に分けるステップを有することを特徴とする請求項１に
記載の閉図形デ−タ処理方法。 - 【請求項４】 上記第４ステップで、隣接する直線間
の領域の重なりを決定する場合に、重なりを０から始め
て０で終ることをチェックし、入力閉図形群が正しいか
否かを判定することを特徴とする請求項１に記載の閉図
形デ−タ処理方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP3149115A JPH04372068A (ja) | 1991-06-21 | 1991-06-21 | 閉図形デ−タ処理方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP3149115A JPH04372068A (ja) | 1991-06-21 | 1991-06-21 | 閉図形デ−タ処理方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH04372068A true JPH04372068A (ja) | 1992-12-25 |
Family
ID=15468044
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP3149115A Pending JPH04372068A (ja) | 1991-06-21 | 1991-06-21 | 閉図形デ−タ処理方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH04372068A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109145378A (zh) * | 2018-07-19 | 2019-01-04 | 郑州云海信息技术有限公司 | 一种快速复制pcb线段的方法及系统 |
-
1991
- 1991-06-21 JP JP3149115A patent/JPH04372068A/ja active Pending
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109145378A (zh) * | 2018-07-19 | 2019-01-04 | 郑州云海信息技术有限公司 | 一种快速复制pcb线段的方法及系统 |
| CN109145378B (zh) * | 2018-07-19 | 2022-02-18 | 郑州云海信息技术有限公司 | 一种快速复制pcb线段的方法及系统 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US3702004A (en) | Process and system for routing interconnections between logic system elements | |
| JPS60180200A (ja) | 部品重なりチエツク処理方式 | |
| JP2566788B2 (ja) | プリント板の配線方式 | |
| JP2713969B2 (ja) | 自動配線パターン設定方式 | |
| JP2987919B2 (ja) | プリント配線板の配線処理装置 | |
| JP2523703B2 (ja) | 半導体集積回路の自動配線方法 | |
| JPH01318300A (ja) | 実装順序決定処理方式 | |
| JP2655473B2 (ja) | 対話型配線設計方法 | |
| JPH07141413A (ja) | 配線パターンの配線方法 | |
| JPH07152814A (ja) | 空線分による経路探索方法 | |
| JP2536119B2 (ja) | 配線処理方式 | |
| JP2593202B2 (ja) | 多層プリント配線板自動設計装置の自動配線処理装置 | |
| JPS62120042A (ja) | 自動配線方式 | |
| JPH05258015A (ja) | プリント基板ｃａｍデータ算出装置 | |
| JPS63115273A (ja) | Ｃａｄシステム | |
| JPS61187293A (ja) | プリント回路基板配線方法 | |
| JPS60179885A (ja) | パタ−ン処理方式 | |
| JPH04299464A (ja) | 配線状態識別方法 | |
| JPS6332662A (ja) | クリアランスチエツク方式 | |
| JPS61134878A (ja) | 配線制御処理方式 | |
| JPH0696160A (ja) | プリント回路基板の領域設定方法 | |
| JPH0821802A (ja) | 基板におけるパターンの良否識別方法 | |
| JPH02234455A (ja) | 半導体集積回路の信号線配線方法 | |
| JPH0267789A (ja) | プリント配線板パターン図面の自動作図方法 | |
| JPH0398185A (ja) | 文字読取装置における文字切り出し方法 |