特許
J-GLOBAL ID：200903032259912185
図形処理方法
発明者：
出願人/特許権者：
代理人 (1件)：
綿貫 隆夫 (外1名)
公報種別：公開公報
出願番号（国際出願番号）：特願平11-085400
公開番号（公開出願番号）：特開2000-276519
出願日： 1999年03月29日
公開日（公表日）： 2000年10月06日
要約：
【要約】 (修正有)【課題】 マスク層合成等に於ける多量の図形相互間の交差関係を高速に判定する。【解決手段】 上辺、下辺がX軸と平行な複数の台形図形(台形)を下辺Y座標値(下辺 Y値)でグループ化し、ソートし、各グループ内に含まれる台形をその最小X座標値(Xmin)に基づいてソートする。各グループの内の一つを順番に判定対象グループ(判定対象G)とし、判定対象Gの台形の一つを順番に判定対象図形とし、判定対象図形の最大X座標値(Xmax)とソート順番が判定対象図形よりも後となる図形のXminを順次比較し、XmaxがXmin以上の場合にのみ交差判定処理を実行する。判定対象Gの台形の下辺Y 値とソート順番が判定対象Gよりも前のグループの内の台形の最大Y座標値(Ymax)を比較し、下辺 Y値がこのYmax以下の場合にのみ、判定対象Gの台形と比較対象Gの台形との間の交差判定処理を行う。
請求項（抜粋）：
上辺および下辺がX軸と平行な複数の台形図形の交差関係を判定する図形処理方法において、前記台形図形を下辺のY座標値が同じもの同士でグループ化し、各グループを前記下辺のY座標値に基づいてソートすると共に、前記各グループ内に含まれる台形図形を該台形図形の最小X座標値に基づいてソートして記憶するグループ化ステップと、前記各グループの内の一つをソートされた順番に従って判定対象グループとする判定対象グループ決定ステップと、該判定対象グループに含まれる前記台形図形の内の一つをソートされた順番に従って判定対象図形とすると共に、判定対象グループ内のソートの順番が前記判定対象図形よりも後となる台形図形の一つをソートの順番に従って順次比較対象図形とし、判定対象図形の最大X座標値と該比較対象図形の最小X座標値とを比較しながら、判定対象図形の最大X座標値が比較対象図形の最小X座標値以上の場合にのみ交差判定処理を実行することを、判定対象図形の最大X座標値が比較対象図形の最小X座標値より小さくなるか、若しくは比較対象図形が無くなるまで繰り返すグループ内判定ステップと、ソートの順番が前記判定対象グループよりも前となる前記グループの内の一つをソートの順番に従って比較対象グループとし、判定対象グループに含まれる台形図形の前記下辺のY座標値と前記比較対象グループに含まれる台形図形の最大Y座標値とを比較し、判定対象グループの下辺のY座標値が前記比較対象グループの前記最大Y座標値以下の場合にのみ、判定対象グループに含まれる台形図形と比較対象グループに含まれる台形図形との間の交差判定処理を行うグループ間判定ステップとを含み、前記判定対象グループ決定ステップにおいて、前記判定対象グループとすべきグループが無くなるまで、判定対象グループ決定ステップから前記グループ間判定ステップを繰り返すことを特徴とする図形処理方法。
IPC (2件)：
FI (4件)：
G06F 15/60 626 C
, G06F 15/60 666 E
, G06F 15/60 666 C
, G06F 15/62 K
5B046AA08
, 5B046BA05
, 5B046DA05
, 5B046FA07
, 5B046JA02
, 5B050AA04
, 5B050BA18
, 5B050EA17
