JPH11102380A - 図形処理方法、図形処理装置、及び、記録媒体 - Google Patents

Abstract

(57)【要約】 【課題】処理の高速化とリソース量の低減を図ることの
できる図形処理方法を提供すること。 【解決手段】入力したレイアウトデータに対して、各セ
ル毎に展開した時の存在領域を設定し、各存在領域の領
域枠，パターンの枠よりなるセル枠の情報を作成し、レ
イアウトデータに含まれるセルを順次処理対象セルに設
定し、処理対象セル以下の階層のセル，パターンのセル
枠に対して階層構造に応じた種類を設定する。そして、
幾何学的に重なりがあるセル枠，パターンに対して、異
なる種類が設定されている場合には重なり有りと判定
し、セル枠同士又はセル枠とパターンに重なり有りと判
定した場合には重なりがあるセル枠に含まれる下層のセ
ル枠，パターンを更に読み込み、パターン同士に重なり
があると判定した場合には該パターンの重なりを確定す
る。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、半導体集積回路装
置のパターンデータにおける階層間の重なりを容易に認
識することができる図形処理方法、図形処理装置、及
び、記録媒体に関するものである。

【０００２】近年の半導体集積回路装置（ＬＳＩ）は高
集積化が進められ、それに伴いＬＳＩの設計データのデ
ータ量も膨大になってきているため、データを記憶する
磁気ディスク装置等の容量が不足するおそれがある。ま
た、ＬＳＩのレイアウト検証やＥＢデータ作成処理に必
要となる図形処理にかかる時間が長くなってきている。
リソース量の増加や処理時間の長期化はコストアップを
招くことから、図形処理に要する時間の短縮とリソース
量の低減が要求されている。

【０００３】

【従来の技術】従来、レイアウト検証やＥＢデータ作成
処理等に必要となる図形処理は、ＬＳＩのレイアウトデ
ータから図形の重なりを調べ、重なり合う図形に対して
図形論理演算を行うことにより、検証や作成処理に必要
となる図形を作成する。そして、作成した図形に基づい
てレイアウト検証やＥＢデータ作成処理等が行われてい
る。

【０００４】

【発明が解決しようとする課題】ＬＳＩのレイアウトデ
ータは、階層構造にて構成され、設計効率の向上やデー
タ量の削減が図られている。そのようなレイアウトデー
タは実際には重なり合うパターンが異なる階層に存在し
たり同一階層にある他のセルに含まれるため、パターン
の重なりがすぐには判別できない場合がある。

【０００５】そこで、レイアウトデータの全てのパター
ンデータを同一階層に展開して図形論理演算を行う方法
がある。しかし、この方法では、複数使用しているセル
をその使用数分だけ設けて展開する事になるためパター
ン数が多くなってデータ量が膨大となり、ディスク装置
等に全てのデータが格納しきれない、所謂リソース量が
不足する。また、データ量が多くなると処理速度の低下
を招き、処理時間が長くなる。

【０００６】また、セルの中の重なりのあるパターンの
みを上層に持ち上げて（パターンを上層のデータに変更
して）図形論理演算する方法がある。この方法は、重な
りのないパターンにより新たなセルを構成することによ
り、階層構造を維持してデータ量の増大を抑える効果が
ある。しかしながら、この方法では、重なりのあるセル
が多いと、上記の全てのパターンを展開する方法と同様
となるので、やはりリソースの不足と処理速度の低下を
招く。

【０００７】また、重なりのあるセルのパターンのみを
展開してデータ量の増大を抑えようとする方法がある。
しかし、この方法では、重なり合うセルの数が多いと、
上記の全てのパターンを展開する方法と同様となるの
で、やはりリソースの不足と処理速度の低下を招く。

【０００８】更に、予め処理対象となるセルを調べる前
に、その時々に基準とするセルに含まれ、そのセルより
下の階層のセル（子孫セル）の重なりを除去した新たな
セルを作成しておき、その新たなセルを参照する方法が
ある。この方法では、同じ重なりを何度も調べることは
回避できるので、処理時間の短縮に寄与する。しかし、
予め重なりを除去した新たなセルを作成しなければなら
ないため、処理に長時間を要するという問題がある。

【０００９】本発明は上記問題点を解決するためになさ
れたものであって、その目的は処理の高速化とリソース
量の低減を図ることのできる図形処理方法、図形処理装
置、及び、記録媒体を提供することにある。

【００１０】

【課題を解決するための手段】上記目的を達成するた
め、請求項１に記載の発明は、セル及びパターンが階層
構造に構成されたレイアウトデータに対して、パターン
の幾何学的な重なりを検出する図形処理方法であって、
前記レイアウトデータを入力し、各セル毎に展開した時
の存在領域を設定し、各存在領域の領域枠，パターンの
枠よりなるセル枠の情報を作成し、前記レイアウトデー
タに含まれるセルを順次処理対象セルに設定し、前記処
理対象セル以下の階層のセル，パターンのセル枠に対し
て階層構造に応じた種類を設定し、前記幾何学的に重な
りがあるセル枠，パターンに対して、異なる種類が設定
されている場合には重なり有りと判定し、セル枠同士又
はセル枠とパターンに重なり有りと判定した場合には重
なりがあるセル枠に含まれる下層のセル枠，パターンを
更に読み込み、パターン同士に重なりがあると判定した
場合には該パターンの重なりを確定するようにした。

【００１１】請求項２に記載の発明は、セル及びパター
ンが階層構造に構成されたレイアウトデータに対して、
パターンの幾何学的な重なりを検出する図形処理方法で
あって、前記レイアウトデータを入力し、各セル毎に展
開した時の存在領域を作成し、作成した各存在領域の領
域枠，パターンの枠よりなるセル枠の情報を階層構造に
てファイルに格納するステップと、前記レイアウトデー
タに含まれるセルを順次処理対象セルに設定するステッ
プと、前記処理対象セル以下の階層のセル，パターンの
セル枠に対して階層構造に応じた種類を設定するステッ
プと、前記処理対象セル、又は重なり有りと判定したセ
ル枠に含まれるセル枠，パターンを読み込むステップ
と、前記新たに読み込んだセル枠のうち、種類が異なる
セル枠同士、又はセル枠とパターンに重なりがあるか判
定するステップと、前記新たに読み込んだセル枠に重な
りがない場合に、前記読み込んだパターンのうち、種類
の異なるパターンに重なりがあるか判定するステップ
と、前記重なり有りと判定されたパターンの重なりを確
定し、幾何学的に重なるパターンの重なり情報を含むテ
ーブルを作成するステップを備えた。

【００１２】請求項３に記載の発明は、請求項１又は２
に記載の図形処理方法において、前記セル枠，パターン
に対して種類を設定する場合に、セル枠に対しては、該
セル枠又は該セル枠の所属セルが処理対象セルの場合に
は該セル枠に対して独自の種類を設定し、該セル枠又は
該セル枠の所属セルが処理対象セルではない場合には所
属セルと同じ種類を設定し、パターンに対しては、所属
セルと同じ種類を設定するようにした。

【００１３】請求項４に記載の発明は、請求項１乃至３
のうちの何れか１項に記載の図形処理方法において、前
記処理対象セルに対して、該スイープ法を用いて幾何学
的に重なるセル又はパターンを検出し、検出したセル
枠，パターンにおいて重なりを判定するようにした。

【００１４】請求項５に記載の発明は、セル及びパター
ンが階層構造に構成されたレイアウトデータに対して、
パターンの幾何学的な重なりを検出する図形処理装置で
あって、前記レイアウトデータを入力し、各セル毎に展
開した時の存在領域を設定し、各存在領域の領域枠，パ
ターンの枠よりなるセル枠の情報を作成する領域枠作成
手段と、前記レイアウトデータに含まれるセルを順次処
理対象セルに設定する処理対象セル設定手段と、前記処
理対象セル以下の階層のセル，パターンのセル枠に対し
て階層構造に応じた種類を設定する種類設定手段とを備
え、前記幾何学的に重なりがあるセル枠，パターンに対
して、異なる種類が設定されている場合には重なり有り
と判定し、セル枠同士又はセル枠とパターンに重なり有
りと判定した場合には重なりがあるセル枠に含まれる下
層のセル枠，パターンを更に読み込み、パターン同士に
重なりがあると判定した場合には該パターンの重なりを
確定するようにした。

【００１５】請求項６に記載の発明は、セル及びパター
ンが階層構造に構成されたレイアウトデータに対して、
パターンの幾何学的な重なりを検出する図形処理装置で
あって、前記レイアウトデータを入力し、各セル毎に展
開した時の存在領域を作成し、作成した各存在領域の領
域枠，パターンの枠よりなるセル枠の情報を階層構造に
てファイルに格納する領域枠作成手段と、前記レイアウ
トデータに含まれるセルを順次処理対象セルに設定する
処理対象セル設定手段と、前記処理対象セル以下の階層
のセル，パターンのセル枠に対して階層構造に応じた種
類を設定する種類設定手段と、前記処理対象セル、又は
重なり有りと判定したセル枠に含まれるセル枠，パター
ンを読み込むデータ読み込み手段と、前記新たに読み込
んだセル枠のうち、種類が異なるセル枠同士、又はセル
枠とパターンに重なりがあるか判定する第１重なり判定
手段と、前記新たに読み込んだセル枠に重なりがない場
合に、前記読み込んだパターンのうち、種類の異なるパ
ターンに重なりがあるか判定する第２重なり判定手段
と、前記重なり有りと判定されたパターンの重なりを確
定し、幾何学的に重なるパターンの重なり情報を含むテ
ーブルを作成する重なり確定手段とを備えた。

【００１６】請求項７に記載の発明は、請求項５又は６
に記載の図形処理装置において、前記種類設定手段にお
いて、セル枠に対しては、該セル枠又は該セル枠の所属
セルが処理対象セルの場合には該セル枠に対して独自の
種類を設定し、該セル枠又は該セル枠の所属セルが処理
対象セルではない場合には所属セルと同じ種類を設定
し、パターンに対しては、所属セルと同じ種類を設定す
るようにした。

【００１７】請求項８に記載の発明は、請求項５乃至７
のうちの何れか１項に記載の図形処理装置において、前
記処理対象セルに対して、該スイープ法を用いて幾何学
的に重なるセル又はパターンを検出し、検出したセル
枠，パターンにおいて重なりを判定するようにした。

【００１８】請求項９に記載の発明は、請求項１乃至４
のうちの何れか１項に記載の図形処理方法にて重なりを
検出する図形処理プログラムを記録した記録媒体であ
る。 （作用）従って、請求項１又は２に記載の発明によれ
ば、各セルの存在領域に対して設定された種類に基づい
て、幾何学的に重なりがあるセル枠，パターンに対し
て、異なる種類が設定されている場合には重なり有りと
判定され、セル枠同士又はセル枠とパターンに重なり有
りと判定した場合には重なりがあるセル枠に含まれる下
層のセル枠，パターンが更に読み込まれ、パターン同士
に重なりがあると判定した場合にはそのパターンの重な
りが確定される。そのため、同じ種類のセル枠が展開さ
れないため、必要とするリソース量が少なくなる。ま
た、設定した種類によって余分な重なりを検出しないの
で、処理時間が短い。

【００１９】請求項３に記載の発明によれば、セル枠に
対しては、そのセル枠又はそのセル枠の所属セルが処理
対象セルの場合にはそのセル枠に対して独自の種類が設
定され、そのセル枠又はそのセル枠の所属セルが処理対
象セルではない場合には所属セルと同じ種類が設定され
る。また、パターンに対しては、所属セルと同じ種類が
設定される。そのため、レイアウトデータの階層構造に
応じた種類が容易に設定される。

【００２０】請求項４に記載の発明によれば、処理対象
セルに対して、そのスイープ法が用いられ、幾何学的に
重なるセル又はパターンが容易に検出される。そのた
め、重なりあうパターンが容易に検出され、処理時間が
短い。

【００２１】請求項５又は６に記載の発明によれば、領
域枠作成手段は、入力されたレイアウトデータに対し
て、各セル毎に展開した時の存在領域を設定し、各存在
領域の領域枠，パターンの枠よりなるセル枠の情報を作
成する。処理対象セル設定手段は、レイアウトデータに
含まれるセルを順次処理対象セルに設定する。種類設定
手段は、処理対象セル以下の階層のセル，パターンのセ
ル枠に対して階層構造に応じた種類を設定する。そし
て、幾何学的に重なりがあるセル枠，パターンに対し
て、異なる種類が設定されている場合には重なり有りと
判定し、セル枠同士又はセル枠とパターンに重なり有り
と判定した場合には重なりがあるセル枠に含まれる下層
のセル枠，パターンを更に読み込み、パターン同士に重
なりがあると判定した場合にはそのパターンの重なりを
確定するようにした。そのため、同じ種類のセル枠が展
開されないため、必要とするリソース量が少なくなる。
また、設定した種類によって余分な重なりを検出しない
ので、処理時間が短い。

【００２２】請求項７に記載の発明によれば、種類設定
手段は、セル枠に対しては、そのセル枠又はそのセル枠
の所属セルが処理対象セルの場合にはそのセル枠に対し
て独自の種類を設定し、そのセル枠又はそのセル枠の所
属セルが処理対象セルではない場合には所属セルと同じ
種類を設定する。また、パターンに対しては、所属セル
と同じ種類を設定するようにした。そのため、そのた
め、レイアウトデータの階層構造に応じた種類が容易に
設定される。

【００２３】請求項８に記載の発明によれば、処理対象
セルに対して、そのスイープ法を用いて幾何学的に重な
るセル又はパターンを検出し、検出したセル枠，パター
ンにおいて重なりを判定するようにした。そのため、重
なり合うパターンを容易に検出することができ、処理時
間が短い。

【００２４】請求項９に記載の発明によれば、記録媒体
には、請求項１乃至４のうちの何れか１項に記載の図形
処理方法にて重なりを検出する図形処理プログラムが記
録され、容易に提供される。

【００２５】

【発明の実施の形態】以下、本発明を具体化した一実施
の形態を図１〜図１９に従って説明する。図３は、本実
施形態の図形処理装置のシステム構成を示す。図形処理
装置１は、中央処理装置（以下、ＣＰＵという）２、メ
モリ３、磁気ディスク装置４、表示器５、キーボード６
及び磁気テープ装置７を備え、それらはバス８により相
互に接続されている。

【００２６】磁気ディスク装置４には、図１，図２に示
す図形処理のプログラムデータ（以下、単にプログラム
という）が記憶されている。このプログラムは、階層構
造のレイアウトデータの中から、重なりのあるパターン
データを検出する重なり検出処理を実行するためのもの
である。プログラムデータは記録媒体としての磁気テー
プ９に記録され供給される。ＣＰＵ２は、磁気テープ装
置７を制御して磁気テープ９からプログラムデータを読
み出し、磁気ディスク装置４に記憶させる。

【００２７】磁気ディスク装置４には、図１に示す第
１，第２データファイル１１，１２が記憶されている。
第１データファイル１１には、予めＣＡＤ装置（図示
略）により回路設計及びレイアウト設計により作成され
た半導体装置のレイアウトデータが格納されている。第
２データファイル１２は作業ファイルであり、ＣＰＵ２
は、重なり検出処理中に作成する一時的なデータを第２
データファイル１２に格納する。尚、第２データファイ
ル１２は、図３のメモリ３に作成されても良い。

【００２８】図３中のメモリ３には、図１に示される第
３データファイル１３が格納される。第３データファイ
ル１３は、重なり検出処理の処理結果を格納するための
ファイルである。ＣＰＵ２は、重なり検出処理を実行し
て検出した重なりのあるパターンデータ及びそのパター
ンデータを含むセルのセル名を重なり情報として第３デ
ータファイル１３に格納する。尚、第３データファイル
１３は、図３の磁気ディスク装置４に作成されても良
い。

【００２９】次に、図形処理（重なり検出処理）を図
１，図２のフローチャートに従って説明する。ＣＰＵ２
は、キーボード６の操作に基づき、図１のフローチャー
トに示すステップ２１〜２８に従って図形処理（重なり
検出処理）を実行する。

【００３０】先ず、ステップ２１は領域枠作成処理（領
域枠作成手段）であり、図３のＣＰＵ２は、第１データ
ファイル１１に格納されたレイアウトデータを入力す
る。そのレイアウトデータに対して、ＣＰＵ２は、各階
層において各セル毎に展開した場合の全てのパターンを
含む存在領域をボトムアップ（最下層から上層に向かっ
て順番に）で設定する。そして、ＣＰＵ２は、設定した
各階層の存在領域の境界線（存在領域を囲む線）をセル
枠とする。各セルはそれぞれセル枠を有する。ＣＰＵ２
は、設定したセル枠のデータと、パターンのデータを第
２データファイル１２に格納する。

【００３１】例えば、図４に示すように、階層構造に構
成されたレイアウトデータ４０がある。このレイアウト
データ４０は、最上層にセルＡＡＡを備える。セルＡＡ
Ａは、下層に設けられたセルＢＢＢとセルＣＣＣを含
む。セルＢＢＢとセルＣＣＣは、同一階層に設けられ、
レイアウトデータが異なるセルである。更に、セルＢＢ
Ｂは、下層に設けられたセルＤＤＤを備え、そのセルＤ
ＤＤは下層に設けられたパターンＰＤ１を含む。セルＣ
ＣＣは、下層に設けられたパターンＰＣ１，ＰＣ２を含
む。パターンＰＤ１，ＰＤ２は形状が異なるパターンで
あり、セルＤＤＤと同一階層に設けられている。

【００３２】図５は、領域枠作成処理により作成される
各層のセル枠を示す説明図である。尚、セルと作成され
たセル枠との関係を分かり易くするため、セル枠に対し
てセルと同じ符号を付してある。また、各階層におい
て、セルに含まれる１階層下のセル，パターンを破線に
て示してある。

【００３３】図３のＣＰＵ２は、レイアウトデータ４０
に対して、各階層におけるセル枠の作成をボトムアップ
にて作成する。即ち、ＣＰＵ２は、先ず、最下層に存在
するパターンＰＤ１に対して、そのパターンＰＤ１を含
み、上層のセルＤＤＤが存在する領域を設定する。そし
て、ＣＰＵ２は、設定した存在領域の枠であるセル枠Ｄ
ＤＤを作成する。従って、セルＤＤＤはセル枠ＤＤＤを
有し、パターンＰＤ１を含む。

【００３４】同様に、ＣＰＵ２は、セルＤＤＤに対し
て、そのセルＤＤＤを含み、上層のセルＢＢＢが存在す
る領域を設定し、設定した存在領域の枠であるセル枠Ｂ
ＢＢを作成する。従って、セルＢＢＢはセル枠ＢＢＢを
有し、セルＤＤＤを含む。

【００３５】また、ＣＰＵ２は、セルＤＤＤと同じ階層
のパターンＰＣ１，ＰＣ２に対して、そのパターンＰＣ
１，ＰＣ２を含み、上層のセルＣＣＣが存在する領域を
設定し、設定した存在領域の枠であるセル枠ＣＣＣを作
成する。従って、セルＣＣＣはセル枠ＣＣＣを有し、パ
ターンＰＣ１，ＰＣ２を含む。

【００３６】更に、ＣＰＵ２は、セルＢＢＢ，ＣＣＣに
対して、そのセルＢＢＢ，ＣＣＣを含み、上層のセルＡ
ＡＡが存在する領域を設定し、設定した存在領域の枠で
あるセル枠ＡＡＡを作成する。従って、セルＡＡＡはセ
ル枠ＡＡＡを有し、セルＢＢＢ，ＣＣＣを含む。

【００３７】そして、ＣＰＵ２は、作成したセル枠ＡＡ
Ａ，ＢＢＢ，ＣＣＣ，ＤＤＤの情報を図１の第２データ
ファイル１２に格納する。また、ＣＰＵ２は、レイアウ
トデータ４０に含まれるパターンＰＣ１，ＰＣ２，ＰＤ
１の情報を第２データファイル１２に格納する。

【００３８】各セル枠ＡＡＡ〜ＤＤＤに対して格納する
情報は、各セル枠ＡＡＡ〜ＤＤＤの座標値、存在する階
層の値、等を含む。各パターンＰＣ１〜ＰＤ１に対して
格納する情報は、各パターンの座標値、存在する階層の
値、等を含む。

【００３９】レイアウトデータに対して作成したセル
枠、パターンの情報を格納すると、ＣＰＵ２は、図１の
ステップ２１からステップ２２に移る。ステップ２２は
処理対象セル設定処理（処理対象セル設定手段）であ
り、図３のＣＰＵ２は、レイアウトデータを構成する全
セルのなかから、その時々において重なり検出処理の対
象とするセル（セル枠）を選択する。ＣＰＵ２は、選択
したセルを処理対象セルとして扱う。ＣＰＵ２は、処理
対処セルを最上階層として階層構造を構成するセル及び
パターンに対して、ステップ２３〜２５の処理を繰り返
し実行（ステップ２３〜２５のループを実行）し、トッ
プダウン（最上階層の処理対象セルから下層に向かって
順番）に重なりがあるか否かを判断するようにプログラ
ムが構成されている。ＣＰＵ２は、その時の処理対象セ
ルを設定すると、ステップ２２からステップ２３に移
る。

【００４０】ステップ２３はデータ読み込み処理（デー
タ読み込み手段）であり、ＣＰＵ２は、着目したセルに
含まれるレイアウトレイアウトデータの情報を第２デー
タファイル１２から読み込む。その情報は、着目したセ
ルの１階層下のセル（以下、子セルという）とパターン
の枠データを含む。その枠データは、セル枠の座標値、
パターンの外形の座標値を含む。ＣＰＵ２は、必要な枠
データの読み込みを終了すると、ステップ２３からステ
ップ２４に移る。

【００４１】その時々に着目するセルは、ステップ２２
において設定された処理対象セルを最上階層とする階層
構造を構成するセルのうちの１つである。ＣＰＵ２は、
また、階層構造を構成するセルのうち、最上階層のセル
から順番にその時々に着目するセルに設定する。例え
ば、図４においてＣＰＵ２は、セルＡＡＡを処理対象セ
ルとした場合に、セルＡＡＡ→セルＢＢＢ→セルＤＤＤ
→セルＣＣＣの順番に着目セルとする。また、ＣＰＵ２
は、セルＢＢＢを処理対象セルとした場合、そのセルＢ
ＢＢ→セルＣＣＣの順番に着目セルとし、セルＡＡＡ及
びセルＣＣＣに着目しない。

【００４２】従って、ステップ２３〜２５のループを実
行する上で、先ず最初のループにおいてＣＰＵ２は最上
階層の処理対象セルに含まれるセル枠，パターンの枠デ
ータを読み込む。２回目以降のループにおいて、ＣＰＵ
２は、処理対象セルから下の階層に含まれるセル枠，パ
ターンの枠データを順次読み込む。

【００４３】尚、子セルは、処理対象セルの１階層下の
セルだけでなく、その時々に着目したセルの１階層下の
セルの事をいう。逆に、その時々に着目したセルが含ま
れるセルを親セルという。例えば、図４のレイアウトデ
ータ４０において、その時にセルＢＢＢに着目したした
場合、そのセルＢＢＢはセルＡＡＡの子セルであり、セ
ルＢＢＢの親セルはセルＡＡＡである。また、その時に
セルＤＤＤに着目した場合、そのセルＤＤＤはセルＢＢ
Ｂの子セルであり、セルＤＤＤの親セルはセルＢＢＢで
ある。

【００４４】ステップ２４は種類設定処理（種類設定手
段）であり、図３のＣＰＵ２は、ステップ２２において
設定した処理対象セルを最上階層とする階層構造のデー
タを構成する構造体（セル，パターンを含み、以下スト
ラクチャという）に対して、図２のフローチャートに示
すステップ３１〜３７に従って種類を設定する。

【００４５】先ず、ステップ３１において、ＣＰＵ２
は、ストラクチャがセルかパターンかを判断する。ＣＰ
Ｕ２は、ストラクチャがパターンの場合、ステップ３２
に移る。そのステップ３２において、ＣＰＵ２は、パタ
ーンに対して、そのパターンの所属セルと同じ種類を設
定する。パターンの所属セルは、そのパターンを有する
上層のセルのことをいう。

【００４６】ステップ３１においてストラクチャがパタ
ーンではない、即ちストラクチャがセルの場合、ＣＰＵ
２は、ステップ３１からステップ３３に移る。ステップ
３３において、ＣＰＵ２は、そのセルが処理対象セルか
否かを判断する。ＣＰＵ２は、セルが処理対象セルの場
合、ステップ３３からステップ３４に移る。ステップ３
４において、ＣＰＵ２は、セルに対して独自の種類を設
定する。

【００４７】ステップ３３においてストラクチャである
セルが処理対象セルではない場合、ＣＰＵ２はステップ
３３からステップ３５に移る。ステップ３５において、
ＣＰＵ２は、ストラクチャの所属セルが処理対象セルか
否かを判断する。ストラクチャの所属セルは、そのスト
ラクチャを含むセル、即ちストラクチャの１階層上のセ
ルであってストラクチャの親セルである。ＣＰＵ２は、
所属セルが処理対象セルの場合、ステップ３５からステ
ップ３６に移る。ステップ３６において、ＣＰＵ２は、
ストラクチャに対して独自の種類を設定する。

【００４８】ステップ３５において所属セルが処理対象
セルではない場合、ＣＰＵ２はステップ３５からステッ
プ３７に移る。ステップ３７において、ＣＰＵ２は、ス
トラクチャに対して所属セルと同じ種類を設定する。

【００４９】上記の種類設定処理を図５を用いて説明す
る。尚、ここでは、セルＡＡＡを処理対象セルに設定し
た場合について説明する。ストラクチャがパターンＰＤ
１の場合、ＣＰＵ２は、図２のステップ３２においてパ
ターンＰＤ１の所属セルと同じ種類をパターンＰＤ１に
対して設定する。パターンＰＤ１の所属セルはセルＤＤ
Ｄである。従って、ＣＰＵ２は、パターンＰＤ１に対し
て所属セルであるセルＤＤＤと同じ種類を設定する。

【００５０】同様に、ストラクチャがパターンＰＣ１，
ＰＣ２の場合、パターンＰＣ１，ＰＣ２の所属セルはセ
ルＣＣＣである。従って、ＣＰＵ２は、図２のステップ
３２においてパターンＰＣ１，ＰＣ２に対して所属セル
であるセルＣＣＣと同じ種類を設定する。

【００５１】また、ストラクチャがセルＤＤＤの場合、
そのセルＤＤＤは処理対象セルではない。また、セルＤ
ＤＤの所属セルであるセルＢＢＢは処理対象セルではな
い。従って、ＣＰＵ２は、図３のステップ３７において
セルＤＤＤに対して所属セルであるセルＢＢＢと同じ種
類を設定する。

【００５２】また、ストラクチャがセルＢＢＢの場合、
そのセルＢＢＢは処理対象セルではない。また、セルＢ
ＢＢの所属セルであるセルＡＡＡは所属セルである。従
って、ＣＰＵ２は、図３のステップ３６においてセルＢ
ＢＢに対して独自の種類を設定する。

【００５３】同様に、ストラクチャがセルＣＣＣの場
合、そのセルＣＣＣは処理対象セルではない。また、セ
ルＣＣＣの所属セルであるセルＡＡＡは所属セルであ
る。従って、ＣＰＵ２は、図３のステップ３６において
セルＣＣＣに対して独自の種類を設定する。

【００５４】更にまた、ストラクチャがセルＡＡＡの場
合、そのセルＡＡＡは処理対象セルである。従って、Ｃ
ＰＵ２は、図３のステップ３４においてセルＡＡＡに対
して独自の種類を設定する。

【００５５】種類の設定は、各ストラクチャのデータに
対して、所定の領域に種類を示すデータを書き込むこと
により行われる。図６は、図４，５のレイアウトデータ
４０を構成するストラクチャのデータを示す説明図であ
る。

【００５６】セルＡＡＡからパターンＰＤ１の各階層を
構成する各ストラクチャには、それぞれデータ領域４１
〜４７が設定されている。これらのデータ領域４１〜４
７は、例えば図１のステップ２１における領域枠作成処
理においてメモリ３に作成される。また、データ領域４
１〜４７は、図形処理プログラムの実行に先立って作成
されても良い。また、ステップ２２における処理対象セ
ル設定処理において作成されても良く、この場合には設
定される処理対象セルを最上層とする階層構造を構成す
るストラクチャに対してのみデータ領域を作成されても
良い。

【００５７】各データ領域４１〜４７は、それぞれ第
１，第２領域４８，４９を含む。第１領域４８は、スト
ラクチャの種類（セル枠又はパターン）、各ストラクチ
ャに設定される種類を書き込みために設けられている。
また、第１領域４８には、図１のステップ２２において
設定される処理対象セルを示す情報が書き込まれる。第
２領域４９は、各ストラクチャの所属セルへのポインタ
を格納するために設けられている。ポインタは、例えば
各ストラクチャの所属セルのデータ領域を示すアドレス
である。このポインタにより、各ストラクチャの所属セ
ルを容易に判断することができる。

【００５８】図１のステップ２４における種類設定処理
を終了すると、図３のＣＰＵ２は、ステップ２４からス
テップ２５に移る。ステップ２５は第１重なり判定処理
（第１重なり判定手段）であり、セル枠に重なりがある
か否かを判定するセル枠重なり判定処理である。ステッ
プ２５において、ＣＰＵ２は、ステップ２３で読み込ん
だ枠データにおいて、その枠データがセル枠の情報の場
合に、セル枠の重なりを調べる。セル枠の重なりは、セ
ル枠と他のセル枠、セル枠とパターンの重なりの場合で
ある。セル枠に重なりがある場合、ＣＰＵ２は、ステッ
プ２５からステップ２３に戻り、そのセルの子セル枠，
パターンを読み込む。即ち、ＣＰＵ２は、重なりのある
セル枠に対して、そのセル枠の１つ下の階層の枠データ
を読み込む。ＣＰＵ２は、ステップ２５においてセル枠
の重なりを調べる。そして、ＣＰＵ２は、セル枠に重な
りが無い場合、ステップ２５からステップ２６に移る。

【００５９】従って、ＣＰＵ２は、ステップ２３〜２５
のループをセル枠の重なりがなくなるまで階層が深くな
る方向、即ち処理対象セルから下層に向かって繰り返し
行う。そして、セル枠に重なりが無くなると、ＣＰＵ２
は、ステップ２５からステップ２６に移る。

【００６０】ステップ２６は第２重なり判定処理（第２
重なり判定手段）であり、パターンに重なりがあるか否
かを判定するパターン重なり判定処理である。ステップ
２６において、図３のＣＰＵ２は、パターン同士に重な
りがある場合、ステップ２６からステップ２７に移る。

【００６１】ステップ２７は重なり確定処理（重なり確
定手段）であり、図３のＣＰＵ２は、ステップ２６にお
いて重なり有りを判定したパターンに対して重なりを確
定する。ＣＰＵ２は、確定したパターンの情報を重なり
情報として第３データファイル１３に格納する。重なり
情報は、重なりがあるパターンを示す情報であり、パタ
ーンを含むセルのセル名、パターンが存在する階層、パ
ターンの座標値、等を含む。

【００６２】図１のステップ２６においてパターン同士
に重なりが無い場合、ＣＰＵ２はステップ２６からステ
ップ２８に移る。ステップ２８は終了判定処理であり、
図３のＣＰＵ２は、全てのセルに対して重なり検出処理
を実施したか否かを判断する。この判断には、ステップ
２２において設定される処理対象セルの情報が用いられ
る。ＣＰＵ２は、レイアウトデータを構成する全てのセ
ルを処理対象セルに設定したか否かを判断する。ＣＰＵ
２は、全てのセルを処理対象セルに設定していない場
合、ステップ２８からステップ２２に移る。そして、処
理対象セルに設定していないセルが無くなるまでステッ
プ２２からステップ２７のループを繰り返し実行し、全
てのセルを処理対象セルとした重なり検出処理を実行す
る。

【００６３】ステップ２８において全てのセルの処理を
終了した、即ち全てのセルを処理対象セルとしてパター
ンの重なりを判定する処理を終了した場合、ＣＰＵ２は
図形処理を終了する。

【００６４】上記の図形処理（重なり検出処理）におい
て第３データファイル１３に格納された重なり情報は、
レイアウト検証やＥＢデータ作成処理等に利用される。
例えば、レイアウト検証では、第３データファイル１３
に格納された重なり情報に基づいて、重なりある図形に
対して図形論理処理が行われ、検証に必要な図形が作成
される。また、ＥＢデータ作成処理では、第３データフ
ァイル１３に格納された重なり情報に基づいて、重なり
があるレイアウトデータの重なりを除去した露光データ
を作成する。その露光データにより、重なりが無い分だ
け露光時間の短縮や周りに対する影響をなくすことがで
きる。

【００６５】このレイアウト検証やＥＢデータ作成処理
等において、予め重なり合うパターンの情報が作成され
ているため、全てのセルに対して重なりを調べる必要が
ない。また、従来のように全てのレイアウトデータを展
開したり、重なりの無い新たなセルを作成する必要がな
い。そのため、処理時間の高速化とリソース量の低減が
図られる。

【００６６】次に、上記の図形処理（重なり検出処理）
を、図７〜図１３を用いて説明する。図７は、レイアウ
トデータ５１の階層構造を示す説明図である。図８は、
レイアウトデータ５１を展開した状態を示すレイアウト
図である。図９は、レイアウトデータ５１の各階層に含
まれるストラクチャを示すレイアウト図である。

【００６７】レイアウトデータ５１は、最上層にセルＡ
ＡＡを備える。セルＡＡＡは、下層に設けられた２つの
同一レイアウトのセルＢＢＢを備える。尚、同一レイア
ウトのセルを区別するために、以下の説明において括弧
付き数字をセルの符号に付して説明する。従って、セル
ＡＡＡは、セルＢＢＢ（１），ＢＢＢ（２）を備える。

【００６８】セルＢＢＢ（１），ＢＢＢ（２）は、それ
ぞれ下層に設けられた２つのセルＣＣＣ（１１），ＣＣ
Ｃ（１２），ＣＣＣ（２１），ＣＣＣ（２２）を備え
る。各セルＣＣＣ（１１）〜ＣＣＣ（２２）は、それぞ
れ下層に設けられた２つのセルＤＤＤ（１１１），ＤＤ
Ｄ（１１２）〜ＤＤＤ（２２１），ＤＤＤ（２２２）を
備える。更に、各セルＤＤＤ（１１１），ＤＤＤ（１１
２）〜ＤＤＤ（２２１），ＤＤＤ（２２２）は、それぞ
れ下層に設けられた２つのパターンＰＤ１，ＰＤ２（図
９参照）を備える。

【００６９】図９には、各階層において重なりがあるス
トラクチャに対してハッチングを付してある。セルＡＡ
Ａに含まれるセルＢＢＢ（１），ＢＢＢ（２）は重なり
合っている。また、各セルＢＢＢに含まれるセルＣＣＣ
（１），ＣＣＣ（２）は重なり合っている。更に、各セ
ルＣＣＣに含まれるセルＤＤＤ（１），ＤＤＤ（２）は
重なり合っている。そして、各セルＤＤＤに含まれるパ
ターンＰＤ１，ＰＤ２は重なり合っていない。

【００７０】図８には、全ての階層を展開した場合に重
なるストラクチャをハッチングを付して示してある。図
８に示すように、セルＤＤＤ（１１１）に含まれるパタ
ーンＰＤ１，ＰＤ２とセルＤＤＤ（１１２）に含まれる
パターンＰＤ１に重なりがある。セルＤＤＤ（１１２）
に含まれるパターンＰＤ２とセルＤＤＤ（１２１）に含
まれるパターンＰＤ２に重なりがある。セルＤＤＤ（１
２１）に含まれるパターンＰＤ１とセルＤＤＤ（１２
２）に含まれるパターンＰＤ１，ＰＤ２に重なりがあ
る。更に、セルＤＤＤ（１２２）に含まれるパターンＰ
Ｄ２とセルＤＤＤ（２１１）に含まれるパターンＰＤ
１、セルＤＤＤ（１２２）に含まれるパターンＰＤ１と
セルＤＤＤ（２１１）に含まれるパターンＰＤ２に重な
りがある。セルＤＤＤ（２１１）に含まれるパターンＰ
Ｄ１，ＰＤ２とセルＤＤＤ（２１２）に含まれるパター
ンＰＤ１に重なりがある。セルＤＤＤ（２１２）に含ま
れるパターンＰＤ２とセルＤＤＤ（２２１）に含まれる
パターンＰＤ２に重なりがある。セルＤＤＤ（２２１）
に含まれるパターンＰＤ１とセルＤＤＤ（２２２）に含
まれるパターンＰＤ１，ＰＤ２に重なりがある。

【００７１】上記のレイアウトデータ５１に対する図形
処理を説明する。 ［セルＤＤＤを処理対象セルに設定した場合］処理対象
セルに設定したセルＤＤＤ（１１１）を最上階層とした
階層構造を構成する各ストラクチャに対して、ＣＰＵ２
は以下のように種類を設定する。

【００７２】先ず、ＣＰＵ２はセルＤＤＤ（１１１）に
種類を設定する。セルＤＤＤ（１１１）は処理対象セル
である。従って、ＣＰＵ２は、セルＤＤＤ（１１１）に
独自の種類［ＤＤＤ（１１１）］を設定する。

【００７３】次に、ＣＰＵ２は、セルＤＤＤ（１１１）
に含まれるパターンＰＤ１，ＰＤ２に対して、パターン
ＰＤ１，ＰＤ２の所属セルであるセルＤＤＤ（１１１）
と同じ種類［ＤＤＤ（１１１）］を設定する。

【００７４】ＣＰＵ２は、図１の図形処理におけるステ
ップ２３〜２５のループを繰り返し実行し、重なりを検
出する。１回目のループにおいて、先ず、ＣＰＵ２は、
セルＤＤＤ（１１１）に含まれる枠データを図１の第２
データファイル１２から読み込む。図１０に示すよう
に、セルＤＤＤ（１１１）はパターンＰＤ１，ＤＰ２を
含む。従って、ＣＰＵ２は、パターンＰＤ１，ＰＤ２の
枠データを第２データファイル１２から読み込む。

【００７５】セルＤＤＤ（１１１）はセルを含まないた
め、次に読み込むセル枠はない。従って、ＣＰＵ２は、
パターンＰＤ１，ＰＤ２において重なりを判定する。こ
の場合、パターンＰＤ１，ＰＤ２に重なりが無いため、
ＣＰＵ２はセルＤＤＤ（１１１）において「重なり無
し」と判定する。

【００７６】また、ＣＰＵ２は、セルＤＤＤ（１１２）
〜ＤＤＤ（２２２）に対して、セルＤＤＤ（１１１）と
同じ処理を実行する。そして、ＣＰＵ２は、各セルＤＤ
Ｄ（１１２）〜ＤＤＤ（２２２）において、セルＤＤＤ
（１１１）と同様に「重なり無し」と判定する。

【００７７】［セルＣＣＣを処理対象セルに設定した場
合］処理対象セルに設定したセルＣＣＣ（１１）を最上
階層とした階層構造を構成する各ストラクチャに対し
て、ＣＰＵ２は以下のように種類を設定する。

【００７８】先ず、ＣＰＵ２は、セルＣＣＣ（１１）に
種類を設定する。セルＣＣＣ（１１）は処理対象セルで
ある。従って、ＣＰＵ２は、セルＣＣＣ（１１）に独自
の種類［ＣＣＣ（１１）］を設定する。

【００７９】次に、ＣＰＵ２は、セルＣＣＣ（１１）に
含まれるセルＤＤＤ（１１１），ＤＤＤ（１１２）に種
類を設定する。セルＤＤＤ（１１１），ＤＤＤ（１１
２）の所属セルであるセルＣＣＣ（１１）は処理対象セ
ルである。従って、ＣＰＵ２は、各セルに独自の種類を
設定する。即ち、ＣＰＵ２は、セルＤＤＤ（１１１）に
対して独自の種類［ＤＤＤ（１１１）］を、セルＤＤＤ
（１１２）に対して独自の種類［ＤＤＤ（１１２）］を
設定する。

【００８０】更に、ＣＰＵ２は、セルＤＤＤ（１１１）
に含まれるパターンＰＤ１，ＰＤ２に対して、パターン
ＰＤ１，ＰＤ２の所属セルであるセルＤＤＤ（１１１）
と同じ種類［ＤＤＤ（１１１）］を設定する。また、Ｃ
ＰＵ２は、セルＤＤＤ（１１２）に含まれるパターンＰ
Ｄ１，ＰＤ２に対して、パターンＰＤ１，ＰＤ２の所属
セルであるセルＤＤＤ（１１２）と同じ種類［ＤＤＤ
（１１２）］を設定する。

【００８１】ＣＰＵ２は、図１の図形処理におけるステ
ップ２３〜２５のループを繰り返し実行し、重なりを検
出する。１回目のループにおいて、先ず、ＣＰＵ２は、
セルＣＣＣ（１１）に含まれる枠データを図１の第２デ
ータファイル１２から読み込む。図１１の上段に示すよ
うに、セルＣＣＣ（１１）はセルＤＤＤ（１１１），Ｄ
ＤＤ（１１２）を含む。従って、ＣＰＵ２は、セルＤＤ
Ｄ（１１１），ＤＤＤ（１１２）の枠データを第２デー
タファイル１２から読み込む。

【００８２】次に、ＣＰＵ２は、読み込んだセルＤＤＤ
（１１１），ＤＤＤ（１１２）の枠データに重なりがあ
るか判定する。セルＤＤＤ（１１１），ＤＤＤ（１１
２）のセル枠には、図１１の上段に示すように重なりが
ある。また、セルＤＤＤ（１１１），ＤＤＤ（１１２）
は、それぞれ独自の種類が設定されているため、種類が
異なる。

【００８３】従って、２回目のループにおいて、ＣＰＵ
２は、セルＤＤＤ（１１１），ＤＤＤ（１１２）をそれ
ぞれ構成するストラクチャの枠データを読み込む。図１
１の下段に示すように、セルＤＤＤ（１１１），ＤＤＤ
（１１２）は、パターンＰＤ１，ＰＤ２をそれぞれ含
む。従って、ＣＰＵ２は、セルＤＤＤ（１１１），ＤＤ
Ｄ（１１２）のパターンＰＤ１，ＰＤ２の枠データを第
２データファイル１２から読み込む。

【００８４】セルＤＤＤ（１１１），ＤＤＤ（１１２）
はセルを含まないため、次に読み込むセル枠はない。従
って、ＣＰＵ２は、各セルＤＤＤ（１１１），ＤＤＤ
（１１２）に含まれるパターンＰＤ１，ＰＤ２において
重なりを判定する。

【００８５】この場合、図１１の下段に示すように、セ
ルＤＤＤ（１１１）のパターンＰＤ１，ＰＤ２と、セル
ＤＤＤ（１１２）のパターンＰＤ１に重なりがある。ま
た、セルＤＤＤ（１１１）のパターンＰＤ１，ＰＤ２
と、セルＤＤＤ（１１２）のパターンＰＤ１は種類が異
なる。従って、ＣＰＵ２はセルＤＤＤ（１１１）とセル
ＤＤＤ（１１２）において「重なり有り」と判定する。
そして、ＣＰＵ２は、重なりがあるセルＤＤＤ（１１
１）のパターンＰＤ１，ＰＤ２と、セルＤＤＤ（１１
２）のパターンＰＤ１の重なり情報を図１の第３データ
ファイル１３に格納する。

【００８６】尚、図７のセルＣＣＣ（１２）を処理対象
セルに設定した場合、ＣＰＵ２は、セルＣＣＣ（１１）
を処理対象セルに設定した場合と同様に動作する。即
ち、ＣＰＵ２は、セルＣＣＣ（２）を最上階層とする階
層構造を構成する各ストラクチャに対して種類を設定す
る。そして、ＣＰＵ２は、図８のセルＤＤＤ（１２１）
とセルＤＤＤ（１２２）における重なりを検出する。そ
して、ＣＰＵ２は、重なりがあるセルＤＤＤ（１２１）
のパターンＰＤ１と、セルＤＤＤ（１２２）のパターン
ＰＤ１，ＰＤ２の重なり情報を、図１の第３データファ
イル１３に格納する。

【００８７】また、セルＣＣＣ（２１）を処理対象セル
に設定した場合、ＣＰＵ２は、セルＣＣＣ（１１）を処
理対象セルに設定した場合と同様に動作する。即ち、Ｃ
ＰＵ２は、セルＣＣＣ（２１）を最上階層とする階層構
造を構成する各ストラクチャに対して種類を設定する。
そして、ＣＰＵ２は、図８のセルＤＤＤ（２１１）とセ
ルＤＤＤ（２１２）における重なりを検出する。そし
て、ＣＰＵ２は、重なりがあるセルＤＤＤ（２１１）の
パターンＰＤ１，ＰＤ２と、セルＤＤＤ（２１２）のパ
ターンＰＤ１の重なり情報を、図１の第３データファイ
ル１３に格納する。

【００８８】更に、セルＣＣＣ（２２）を処理対象セル
に設定した場合、ＣＰＵ２は、セルＣＣＣ（１１）を処
理対象セルに設定した場合と同様に動作する。即ち、Ｃ
ＰＵ２は、セルＣＣＣ（２２）を最上階層とする階層構
造を構成する各ストラクチャに対して種類を設定する。
そして、ＣＰＵ２は、図８のセルＤＤＤ（２２１）とセ
ルＤＤＤ（２２１）における重なりを検出する。そし
て、ＣＰＵ２は、重なりがあるセルＤＤＤ（２２１）の
パターンＰＤ１と、セルＤＤＤ（２２２）のパターンＰ
Ｄ１，ＰＤ２の重なり情報を、図１の第３データファイ
ル１３に格納する。

【００８９】［処理対象セルにセルＢＢＢを設定した場
合］処理対象セルに設定したセルＢＢＢ（１）を最上階
層とした階層構造を構成する各ストラクチャに対して、
ＣＰＵ２は以下のように種類を設定する。

【００９０】先ず、ＣＰＵ２は、セルＢＢＢ（１）に種
類を設定する。セルＢＢＢ（１）は処理対象セルであ
る。従って、ＣＰＵ２は、セルＢＢＢ（１）に独自の種
類［ＢＢＢ（１）］を設定する。

【００９１】次に、ＣＰＵ２は、セルＢＢＢ（１）に含
まれるセルＣＣＣ（１１），ＣＣＣ（１２）に種類を設
定する。セルＣＣＣ（１１），ＣＣＣ（１２）の所属セ
ルであるセルＢＢＢ（１）は処理対象セルである。従っ
て、ＣＰＵ２はセルＣＣＣ（１１），ＣＣＣ（１２）に
対してそれぞれ独自の種類［ＣＣＣ（１１）］，［ＣＣ
Ｃ（１２）］を設定する。

【００９２】次に、ＣＰＵ２は、セルＣＣＣ（１１）に
含まれるセルＤＤＤ（１１１），ＤＤＤ（１１２）に対
して種類を設定する。セルＤＤＤ（１１１），ＤＤＤ
（１１２）の所属セルはセルＣＣＣ（１１）であり、こ
のセルＣＣＣ（１１）は処理対象セルではない。従っ
て、ＣＰＵ２は、セルＤＤＤ（１１１），ＤＤＤ（１１
２）に所属セルであるセルＣＣＣ（１１）と同じ種類
［ＣＣＣ（１１）］を設定する。同様に、ＣＰＵ２は、
セルＣＣＣ（１２）に含まれるセルＤＤＤ（１２１），
ＤＤＤ（１２２）に対して、所属セルＣＣＣ（１２）と
同じ種類［ＣＣＣ（１２）］を設定する。

【００９３】更に、ＣＰＵ２は、セルＤＤＤ（１１１）
に含まれるパターンＰＤ１，ＰＤ２に対して、パターン
ＰＤ１，ＰＤ２の所属セルであるセルＤＤＤ（１１１）
と同じ種類［ＣＣＣ（１１）］を設定する。また、ＣＰ
Ｕ２は、セルＤＤＤ（１１２）に含まれるパターンＰＤ
１，ＰＤ２に対して、パターンＰＤ１，ＰＤ２の所属セ
ルであるセルＤＤＤ（１１２）と同じ種類［ＣＣＣ（１
２）］を設定する。

【００９４】ＣＰＵ２は、図１の図形処理におけるステ
ップ２３〜２５のループを繰り返し実行し、重なりを検
出する。１回目のループにおいて、先ず、図３のＣＰＵ
２は、セルＢＢＢ（１）に含まれるストラクチャの枠デ
ータを図１の第２データファイル１２から読み込む。図
１２の上段に示すように、セルＢＢＢ（１）はセルＣＣ
Ｃ（１１），ＣＣＣ（１２）を含む。従って、ＣＰＵ２
は、セルＣＣＣ（１１），ＣＣＣ（１２）の枠データを
第２データファイル１２から読み込む。

【００９５】次に、ＣＰＵ２は、読み込んだセルＣＣＣ
（１１），ＣＣＣ（１２）の枠データに重なりがあるか
判定する。図１２の上段に示すように、セルＣＣＣ（１
１），ＣＣＣ（１２）のセル枠には、重なりがある。ま
た、セルＣＣＣ（１１），ＣＣＣ（１２）は、それぞれ
独自の種類に設定されているため、種類が異なる。

【００９６】従って、２回目のループにおいて、ＣＰＵ
２は、次にセルＣＣＣ（１１），ＣＣＣ（１２）にそれ
ぞれ含まれるストラクチャの枠データを読み込む。図１
２の中段に示すように、セルＣＣＣ（１１）は、セルＤ
ＤＤ（１１１），ＤＤＤ（１１２）を含む。セルＣＣＣ
（１２）はセルＤＤＤ（１２１），ＤＤＤ（１２２）を
含む。従って、ＣＰＵ２は、セルＤＤＤ（１１１）〜Ｄ
ＤＤ（１２２）の枠データを第２データファイル１２か
ら読み込む。

【００９７】次に、ＣＰＵ２は、読み込んだセルＤＤＤ
（１１１）〜ＤＤＤ（１２２）の枠データに重なりがあ
るか判定する。図１２の中段に示すように、セルＤＤＤ
（１１１）とセルＤＤＤ（１１２）のセル枠には重なり
がある。セルＤＤＤ（１１２）とセルＤＤＤ（１２１）
のセル枠には重なりがある。更に、セルＤＤＤ（１２
１）とセルＤＤＤ（１２２）のセル枠には重なりがあ
る。

【００９８】しかし、セルＤＤＤ（１１１）とセルＤＤ
Ｄ（１１２）の種類はそれぞれ種類［ＣＣＣ（１１）］
であり同じである。また、セルＤＤＤ（１２１）とセル
ＤＤＤ（１２２）の種類はそれぞれ種類［ＣＣＣ（１
２）］であり同じである。従って、ＣＰＵ２は、同じ種
類であるセルＤＤＤ（１１１），ＤＤＤ（１１２）間、
セルＤＤＤ（１２１），ＤＤＤ（１２２）間に「重なり
無し」と判定する。

【００９９】一方、セルＤＤＤ（１１２）とセルＤＤＤ
（１２１）は種類がそれぞれ種類［ＣＣＣ（１１）］，
［ＣＣＣ（１２）］であり異なる。従って、ＣＰＵ２
は、セルＤＤＤ（１１２），ＤＤＤ（１２１）間に「重
なり有り」と判定する。

【０１００】従って、３回目のループにおいて、ＣＰＵ
２は、「重なり有り」と判定したセルＤＤＤ（１１
２），ＤＤＤ（１２１）に含まれるストラクチャの枠デ
ータを第２データファイル１２から読み込む。即ち、図
１２の下段に示すように、ＣＰＵ２は、セルＤＤＤ（１
１２），ＤＤＤ（１２１）にそれぞれ含まれるパターン
ＰＤ１，ＰＤ２の枠データを第２データファイル１２か
ら読み込む。

【０１０１】この時、ＣＰＵ２は、「重なり無し」と判
定したセルＤＤＤ（１１１）とセルＤＤＤ（１２２）に
含まれるストラクチャの枠データを読み込まない。即
ち、ＣＰＵ２は、「重なり無し」と判定したセルに含ま
れる枠データを読み込まない。従って、メモリ３等のリ
ソースの使用量が全て（セルＤＤＤ（１１１）〜ＤＤＤ
（１２２）の枠データ）を読み込む場合に比べて少な
い。

【０１０２】セルＤＤＤ（１１２），ＤＤＤ（１２１）
はセルを含まないため、次に読み込むセル枠はない。従
って、ＣＰＵ２は、各セルＤＤＤ（１１２），ＤＤＤ
（１２１）に含まれるパターンＰＤ１，ＰＤ２において
重なりを判定する。

【０１０３】この場合、図１２の下段に示すように、セ
ルＤＤＤ（１１２）のパターンＰＤ２と、セルＤＤＤ
（１２１）のパターンＰＤ２に重なりがある。また、セ
ルＤＤＤ（１１２）のパターンＰＤ２と、セルＤＤＤ
（１２１）のパターンＰＤ２は種類はそれぞれ種類［Ｃ
ＣＣ（１１）］，［ＣＣＣ（１２）］であり異なる。従
って、ＣＰＵ２はセルＤＤＤ（１１２）とセルＤＤＤ
（１２１）において「重なり有り」と判定する、即ちセ
ルＤＤＤ（１１２）とセルＤＤＤ（１２１）における重
なりを検出する。。そして、ＣＰＵ２は、重なりがある
セルＤＤＤ（１１２）のパターンＰＤ２と、セルＤＤＤ
（１２１）のパターンＰＤ２の重なり情報を図１の第３
データファイル１３に格納する。

【０１０４】尚、図７のセルＢＢＢ（２）を処理対象セ
ルに設定した場合、ＣＰＵ２は、セルＢＢＢ（１）を処
理対象セルに設定した場合と同様に動作する。即ち、Ｃ
ＰＵ２は、セルＢＢＢ（２）を最上階層とする階層構造
を構成する各ストラクチャに対して種類を設定する。そ
して、ＣＰＵ２は、図８のセルＤＤＤ（２１２）とセル
ＤＤＤ（２２１）における重なりを検出する。そして、
ＣＰＵ２は、重なりがあるセルＤＤＤ（２１２）のパタ
ーンＰＤ２と、セルＤＤＤ（２２１）のパターンＰＤ２
の重なり情報を、図１の第３データファイル１３に格納
する。

【０１０５】［セルＡＡＡを処理対象セルに設定した場
合］処理対象セルに設定したセルＡＡＡを最上階層とし
た階層構造を構成する各ストラクチャに対して、ＣＰＵ
２は以下のように種類を設定する。

【０１０６】先ず、ＣＰＵ２は、セルＡＡＡに種類を設
定する。セルＡＡＡは処理対象セルである。従って、Ｃ
ＰＵ２は、セルＡＡＡに独自の種類［ＡＡＡ］を設定す
る。次に、ＣＰＵ２は、セルＡＡＡに含まれるセルＢＢ
Ｂ（１），ＢＢＢ（２）に対して種類を設定する。セル
ＢＢＢ（１），ＢＢＢ（２）の所属セルであるセルＡＡ
Ａは処理対象セルである。従って、ＣＰＵ２はセルＢＢ
Ｂ（１），ＢＢＢ（２）に対してそれぞれ独自の種類
［ＢＢＢ（１）］，［ＢＢＢ（２）］を設定する。

【０１０７】次に、ＣＰＵ２は、セルＢＢＢ（１）に含
まれるセルＣＣＣ（１１），ＣＣＣ（１２）に対して種
類を設定する。セルＣＣＣ（１１），ＣＣＣ（１２）の
所属セルであるセルＢＢＢ（１）は処理対象セルではな
い。従って、ＣＰＵ２はセルＣＣＣ（１１），ＣＣＣ
（１２）に対して所属セルであるセルＢＢＢ（１）と同
じ種類［ＢＢＢ（１）］を設定する。同様に、ＣＰＵ２
は、セルＢＢＢ（２）に含まれるセルＣＣＣ（１１），
ＣＣＣ（１２）に対して、所属セルＢＢＢ（２）と同じ
種類［ＢＢＢ（２）］を設定する。

【０１０８】次に、ＣＰＵ２は、セルＣＣＣ（１１）に
含まれるセルＤＤＤ（１１１），ＤＤＤ（１１２）に対
して種類を設定する。この時、セルＤＤＤ（１１１），
ＤＤＤ（１１２）の所属セルであるセルＣＣＣ（１１）
は処理対象セルではない。従って、ＣＰＵ２は、セルＤ
ＤＤ（１１１），ＤＤＤ（１１２）に所属セルであるセ
ルＣＣＣ（１１）と同じ種類［ＢＢＢ（１）］を設定す
る。

【０１０９】同様に、ＣＰＵ２は、セルＣＣＣ（１２）
に含まれるセルＤＤＤ（１２１），ＤＤＤ（１２２）に
対して、所属セルであるセルＣＣＣ（１２）が処理対象
セルではないため、セルＣＣＣ（１２）と同じ種類［Ｂ
ＢＢ（１）］を設定する。また、ＣＰＵ２は、セルＣＣ
Ｃ（２１）に含まれるセルＤＤＤ（２１１），ＤＤＤ
（２１２）に対して、所属セルであるセルＣＣＣ（２
１）が処理対象セルではないため、セルＣＣＣ（２１）
と同じ種類［ＢＢＢ（２）］を設定する。更に、ＣＰＵ
２は、セルＣＣＣ（２２）に含まれるセルＤＤＤ（２２
１），ＤＤＤ（２２２）に対して、所属セルであるセル
ＣＣＣ（２２）が処理対象セルではないため、セルＣＣ
Ｃ（２２）と同じ種類［ＢＢＢ（２）］を設定する。

【０１１０】更に、ＣＰＵ２は、セルＤＤＤ（１１１）
に含まれるパターンＰＤ１，ＰＤ２に対して、パターン
ＰＤ１，ＰＤ２の所属セルであるセルＤＤＤ（１１１）
と同じ種類［ＢＢＢ（１）］を設定する。また、ＣＰＵ
２は、セルＤＤＤ（１１２）に含まれるパターンＰＤ
１，ＰＤ２に対して、パターンＰＤ１，ＰＤ２の所属セ
ルであるセルＤＤＤ（１１２）と同じ種類［ＢＢＢ
（１）］を設定する。

【０１１１】同様に、ＣＰＵ２は、セルＤＤＤ（１２
１），ＤＤＤ（１２２）にそれぞれ含まれるパターンＰ
Ｄ１，ＰＤ２に対して、パターンＰＤ１，ＰＤ２の所属
セルであるセルＤＤＤ（１２１），ＤＤＤ（１２２）と
同じ種類［ＢＢＢ（１）］を設定する。更に、ＣＰＵ２
は、セルＤＤＤ（２１１）〜ＤＤＤ（２２２）にそれぞ
れ含まれるパターンＰＤ１，ＰＤ２に対して、パターン
ＰＤ１，ＰＤ２の所属セルであるセルＤＤＤ（２１１）
〜ＤＤＤ（２２２）と同じ種類［ＢＢＢ（２）］を設定
する。

【０１１２】ＣＰＵ２は、図１の図形処理におけるステ
ップ２３〜２５のループを繰り返し実行し、重なりを検
出する。１回目のループにおいて、先ず、ＣＰＵ２は、
セルＡＡＡに含まれるストラクチャの枠データを図１の
第２データファイル１２から読み込む。図１３の最上段
に示すように、セルＡＡＡはセルＢＢＢ（１），ＢＢＢ
（２）を含む。従って、ＣＰＵ２は、セルＢＢＢ
（１），ＢＢＢ（２）の枠データを第２データファイル
１２から読み込む。

【０１１３】次に、ＣＰＵ２は、読み込んだセルＢＢＢ
（１），ＢＢＢ（２）の枠データに重なりがあるか判定
する。図１３の上段に示すように、セルＢＢＢ（１），
ＢＢＢ（２）のセル枠には、重なりがある。また、セル
ＢＢＢ（１），ＢＢＢ（２）は、それぞれ独自の種類に
設定されているため、種類が異なる。

【０１１４】従って、２回目のループにおいて、ＣＰＵ
２は、セルＢＢＢ（１）に含まれるストラクチャの枠デ
ータを図１の第２データファイル１２から読み込む。図
１３の２段目に示すように、セルＢＢＢ（１）はセルＣ
ＣＣ（１１），ＣＣＣ（１２），ＣＣＣ（２１），ＣＣ
Ｃ（２２）を含む。従って、ＣＰＵ２は、セルＣＣＣ
（１１）〜ＣＣＣ（２２）の枠データを第２データファ
イル１２から読み込む。

【０１１５】次に、ＣＰＵ２は、読み込んだセルＣＣＣ
（１１）〜ＣＣＣ（２２）の枠データに重なりがあるか
判定する。図１３の２段目に示すように、セルＣＣＣ
（１１）とセルＣＣＣ（１２）のセル枠には重なりがあ
る。また、セルＣＣＣ（１２）とセルＣＣＣ（２１）の
セル枠には重なりがある。更に、セルＣＣＣ（２１）と
セルＣＣＣ（２２）のセル枠には重なりがある。

【０１１６】しかし、セルＣＣＣ（１１）とセルＣＣＣ
（１２）の種類はそれぞれ種類［ＢＢＢ（１）］であり
同じである。また、セルＣＣＣ（２１）とセルＣＣＣ
（２２）の種類はそれぞれ種類［ＢＢＢ（２）］であり
同じである。従って、ＣＰＵ２は、同じ種類であるセル
ＣＣＣ（１１），ＣＣＣ（１２）間、セルＣＣＣ（２
１），ＣＣＣ（２２）間に「重なり無し」と判定する。

【０１１７】一方、セルＣＣＣ（１２）とセルＣＣＣ
（２１）の種類はそれぞれ種類［ＢＢＢ（１）］，［Ｂ
ＢＢ（２）］であり異なる。従って、ＣＰＵ２は、セル
ＣＣＣ（１２），ＣＣＣ（２１）間に「重なり有り」と
判定する。

【０１１８】従って、３回目のループにおいて、ＣＰＵ
２は、「重なり有り」と判定したセルＣＣＣ（１２），
ＣＣＣ（２１）にそれぞれ含まれるストラクチャの枠デ
ータを読み込む。図１３の３段目に示すように、セルＣ
ＣＣ（１２）は、セルＤＤＤ（１２１），ＤＤＤ（１２
２）を含む。セルＣＣＣ（２１）はセルＤＤＤ（２１
１），ＤＤＤ（２１２）を含む。従って、ＣＰＵ２は、
セルＤＤＤ（１２１），ＤＤＤ（１２２），ＤＤＤ（２
１１），ＤＤＤ（２１２）の枠データを第２データファ
イル１２から読み込む。

【０１１９】次に、ＣＰＵ２は、読み込んだセルＤＤＤ
（１２１），ＤＤＤ（１２２），ＤＤＤ（２１１），Ｄ
ＤＤ（２１２）の枠データに重なりがあるか判定する。
図１３の３段目に示すように、セルＤＤＤ（１２１）と
セルＤＤＤ（１２２）のセル枠には重なりがある。ま
た、セルＤＤＤ（１２２）とセルＤＤＤ（２１１）のセ
ル枠には重なりがある。更に、セルＤＤＤ（２１１）と
セルＤＤＤ（２１２）のセル枠には重なりがある。

【０１２０】しかし、セルＤＤＤ（１２１）とセルＤＤ
Ｄ（１２２）の種類はそれぞれ種類［ＢＢＢ（１）］で
あり同じである。また、セルＤＤＤ（２１１）とセルＤ
ＤＤ（２１２）の種類はそれぞれ種類［ＢＢＢ（２）］
であり同じである。従って、ＣＰＵ２は、同じ種類であ
るセルＤＤＤ（１２１），ＤＤＤ（１２２）間、セルＤ
ＤＤ（２１１），ＤＤＤ（２１２）間にそれぞれ「重な
り無し」と判定する。

【０１２１】一方、セルＤＤＤ（１２２）とセルＤＤＤ
（２１１）の種類はそれぞれ種類［ＣＣＣ（１１）］，
［ＣＣＣ（１２）］であり異なる。従って、ＣＰＵ２
は、セルＤＤＤ（１１２），ＤＤＤ（２１１）間に「重
なり有り」と判定する。

【０１２２】従って、４回目のループにおいて、ＣＰＵ
２は、「重なり有り」と判定したセルＤＤＤ（１１
２），ＤＤＤ（２１１）に含まれるストラクチャの枠デ
ータを第２データファイル１２から読み込む。即ち、Ｃ
ＰＵ２は、図１３の最下段に示すように、セルＤＤＤ
（１１２），ＤＤＤ（２１１）にそれぞれ含まれるパタ
ーンＰＤ１，ＰＤ２の枠データを第２データファイル１
２から読み込む。

【０１２３】この時、ＣＰＵ２は、「重なり無し」と判
定したセルＤＤＤ（１２１）とセルＤＤＤ（２１２）に
含まれるストラクチャの枠データを読み込まない。即ち
ＣＰＵ２は、「重なり無し」と判定したセルに含まれる
枠データを読み込まない。従って、メモリ３等のリソー
スの使用量が全て（セルＤＤＤ（１１１）〜ＤＤＤ（２
１２）の枠データ）を読み込む場合に比べて少ない。

【０１２４】セルＤＤＤ（１１２），ＤＤＤ（２１１）
はセルを含まないため、次に読み込むセル枠はない。従
って、ＣＰＵ２は、各セルＤＤＤ（１１２），ＤＤＤ
（２１１）に含まれるパターンＰＤ１，ＰＤ２において
重なりを判定する。

【０１２５】この場合、図１３の最下段に示すように、
セルＤＤＤ（１２２）のパターンＰＤ２と、セルＤＤＤ
（２１１）のパターンＰＤ１に重なりがある。また、セ
ルＤＤＤ（１２２）のパターンＰＤ１と、セルＤＤＤ
（２１１）のパターンＰＤ２に重なりがある。

【０１２６】そして、セルＤＤＤ（１２２）のパターン
ＰＤ１と、セルＤＤＤ（２１１）のパターンＰＤ１はそ
れぞれ種類［ＣＣＣ（１１）］，［ＣＣＣ（１２）］で
あり異なる。また、セルＤＤＤ（１２２）のパターンＰ
Ｄ２と、セルＤＤＤ（２１１）のパターンＰＤ２は、は
それぞれ種類［ＣＣＣ（１１）］，［ＣＣＣ（１２）］
であり異なる。

【０１２７】従って、ＣＰＵ２はセルＤＤＤ（１１２）
とセルＤＤＤ（２１１）において「重なり有り」と判定
する。そして、ＣＰＵ２は、重なりがあるセルＤＤＤ
（１１２）のパターンＰＤ２，ＰＤ１と、セルＤＤＤ
（２１１）のパターンＰＤ１，ＰＤ２の重なり情報を図
１の第３データファイル１３に格納する。

【０１２８】以上の処理によって、全ての重なりを重複
することなく検出することができるので、処理に要する
時間が短い。しかも、重なりがあるセルに対して、各セ
ルが同じ種類の場合に「重なり無し」と判断してそのセ
ルに含まれるストラクチャを読み込まないようにしたた
め、読み込むデータ数が少なくなってリソースが不足す
ることがない。

【０１２９】ところで、従来の方式では、種類が設定さ
れていないため、本実施形態で「重なり無し」と判断し
た枠を「重なり有り」として動作していた。例えば、図
１３の２段目において、セルＣＣＣ（１１）とセルＣＣ
Ｃ（１２）、セルＣＣＣ（２１）とセルＣＣ（２２）を
従来では「重なり有り」と判断していた。その結果、余
計な重なりも調べることになり、処理に時間がかかる。
また、「重なり無し」とするために、予め重なりを除去
したデータ（新たなセル）を作成する等の方法を行った
りするものもあるが、重なりを除去したデータを作成す
るためにリソース（ディスク資源等）をよけいに消費す
るとともに、処理に時間がかかる。

【０１３０】しかしながら、本実施形態では、各セルの
枠に対して種類を設定し、同じ種類の枠は「重なり無
し」として処理しているため、余計な重なりは調べない
ので、処理時間が短くなる。また、「重なり無し」と判
定したセル枠に含まれるストラクチャを読み込まない、
即ち、「重なり無し」と判定したセル枠と展開しないた
め、その時々に処理するデータ数が少なくなって必要と
するリソース量が少なくなる。更に、予め重なりを除去
したデータを作成する必要がない。そのため、リソース
が不足することがなく、処理時間が短くなる。

【０１３１】［スイープ法を用いた重なり検出処理］次
に、スイープ法を用いて重なり検出処理を実行する場合
を、図１４〜図１９を用いて説明する。スイープ法は、
図形の形状や重なり合い等の状態を検出するのに有効な
方法であり、一般的に用いられる。

【０１３２】図１４は、レイアウトデータ６１の階層構
造を示す説明図である。図１５は、レイアウトデータ６
１を展開した状態を示すレイアウト図である。図１６
は、レイアウトデータ６１の各階層に含まれるストラク
チャを示すレイアウト図である。

【０１３３】図１４に示すように、レイアウトデータ６
１は、最上層にセルＴＯＰを備える。セルＴＯＰは、下
層に設けられた２つの同一レイアウトのセルＡＡＡ
（１），ＡＡＡ（２）と、セルＢＢＢを含む。セルＡＡ
Ａ（１）はセルＣＣＣ（１）を含み、セルＡＡＡ（２）
はセルＣＣＣ（２）を含む。各セルＣＣＣ（１），ＣＣ
Ｃ（２）は、それぞれセルＥＥＥとパターンＰＣ１（図
１６参照）を含む。セルＥＥＥはパターンＰＥ１，ＰＥ
２を含む。

【０１３４】前記セルＢＢＢは２つの同一レイアウトの
セルＤＤＤ（１），ＤＤＤ（２）と、パターンＰＢ１，
ＰＢ２（図１６参照）を含む。セルＤＤＤは、パターン
ＰＤ１，ＰＤ２（図１６参照）を含む。

【０１３５】図１６には、各階層において重なりがある
ストラクチャに対してハッチングを付してある。セルＴ
ＯＰに含まれるセルＡＡＡ（１），ＡＡＡ（２），ＢＢ
Ｂは重なり合っている。また、セルＢＢＢに含まれるセ
ルＤＤＤ（１），ＤＤＤ（２）は重なり合っている。

【０１３６】図１５には、全ての階層を展開した場合に
重なるストラクチャをハッチングを付して示してある。
図１５に示すように、セルＣＣＣ（１）に含まれるセル
ＥＥＥ（１）を構成するパターンＰＥ１と、セルＣＣＣ
（２）に含まれるパターンＰＣ１に重なりがある。ま
た、セルＤＤＤ（１）に含まれるパターンＰＤ１とセル
ＤＤＤ（２）に含まれるパターンＰＤ１、セルＤＤＤ
（１）に含まれるパターンＰＤ２とセルＤＤＤ（２）に
含まれるパターンＰＤ２に重なりがある。

【０１３７】上記のレイアウトデータ６１に対してスイ
ープ法を用いた場合について説明する。先ず、ＣＰＵ２
は、各セルの存在領域をボトムアップにて計算して各セ
ルの枠データを作成する。そして、ＣＰＵ２は、作成し
た各セルの枠データを第２データファイル１２に格納す
る。

【０１３８】次に、ＣＰＵ２は、処理対象セルを設定す
る。ここでは、セルＴＯＰを処理対象セルに設定した場
合について説明する。次に、ＣＰＵ２は、設定した処理
対象セルに基づいて、各セルの種類を設定する。

【０１３９】処理対象セルに設定したセルＡＡＡを最上
階層とした階層構造を構成する各ストラクチャに対し
て、ＣＰＵ２は以下のように種類を設定する。先ず、Ｃ
ＰＵ２は、セルＴＯＰが処理対象セルであるため、セル
ＴＯＰに独自の種類［ＴＯＰ］を設定する。

【０１４０】次に、ＣＰＵ２は、セルＴＯＰに含まれる
セルＡＡＡ（１），ＡＡＡ（２），ＢＢＢに対して、各
セルの所属セルが処理対象セルであるため、各セルＡＡ
Ａ（１），ＡＡＡ（２），ＢＢＢにそれぞれ独自の種類
［ＡＡＡ（１）］［ＡＡＡ（２）］，［ＢＢＢ］を設定
する。

【０１４１】そして、ＣＰＵ２は、セルＡＡＡ（１）以
下の階層に含まれる各セル，各パターンに対して、所属
セルであるセルＡＡＡ（１）と同じ種類［ＡＡＡ
（１）］を設定する。また、ＣＰＵ２は、セルＡＡＡ
（２）以下の階層に含まれる各セル，各パターンに対し
て、所属セルであるセルＡＡＡ（２）と同じ種類［ＡＡ
Ａ（２）］を設定する。更に、ＣＰＵ２は、セルＢＢＢ
以下の階層に含まれる各セル，各パターンに対して、所
属セルであるセルＢＢＢと同じ種類［ＢＢＢ］を設定す
る。

【０１４２】次に、ＣＰＵ２は、スイープラインＳＬを
処理対象セルとしたセルＴＯＰに対して、セル枠の左辺
から右辺に向かってスイープする。尚、スイープライン
ＳＬを処理対象セルに設定したセル枠の右辺から左辺に
向かってスイープしてもよい。

【０１４３】次に、ＣＰＵ２は、スイープラインＳＬに
おいてＸ座標が同じ複数のセル枠が存在する場合、それ
らの複数のセル枠が重なり合うと判定する。そして、Ｃ
ＰＵ２は、重なると判定した複数のセルのセル枠を読み
込む。

【０１４４】例えば、図１７のスイープラインＳＬの位
置において、セルＡＡＡ（１），ＡＡＡ（２），ＢＢＢ
が重なっている。従って、ＣＰＵ２は、セルＡＡＡ
（Ａ），ＡＡＡ（２），ＢＢＢのセル枠を読み込む。

【０１４５】ここで、セル枠ＡＡＡ（１）とセル枠ＡＡ
Ａ（２）、セル枠ＡＡＡ（２）とセル枠ＢＢＢは、それ
ぞれ幾何学的に重なりがある。また、各セル枠ＡＡＡ
（１），ＡＡＡ（２），ＢＢＢは、所属セルが処理対象
セルであるため、それぞれ独自の種類が設定されてい
る。従って、ＣＰＵ２は、各セル枠ＡＡＡ（１），ＡＡ
Ａ（２），ＢＢＢに含まれるストラクチャ、即ち各セル
の１つ下の階層のセル，パターンのセル枠を読み込む。
そして、ＣＰＵ２は、読み込んだ全てのセル枠の名前等
の情報を格納したワークリストをメモリ３に作成する。

【０１４６】図１８に示すように、セルＡＡＡ（１）は
セルＣＣＣ（１）を含み、セルＡＡＡ（２）はセルＣＣ
Ｃ（２）を含む。また、セルＢＢＢはセルＤＤＤ
（１），ＤＤＤ（２）とパターンＰＢ１，ＰＢ２を含
む。従って、ＣＰＵ２は、ワークリストに、セルＣＣＣ
（１），ＣＣＣ（２），セルＤＤＤ（１），ＤＤＤ
（２）と、パターンＰＢ１，ＰＢ２の情報を格納する。

【０１４７】それぞれのセルＣＣＣ（１），ＣＣＣ
（２），ＤＤＤ（１），ＤＤＤ（１）は、種類［ＡＡＡ
（１）］，［ＡＡＡ（２）］，［ＢＢＢ］，［ＢＢＢ］
を持つ。従って、ＣＰＵ２は、セルＣＣＣ（１）とセル
ＣＣＣ（２）、セルＣＣＣ（２）とセルＤＤＤ（１）は
「重なり有り」と判定する。また、ＣＰＵ２は、セルＤ
ＤＤ（１）とセルＤＤＤ（２）は「重なり無し」と判定
する。

【０１４８】ＣＰＵ２は、上記の処理を階層構造に構成
されたレイアウトデータ６１に対して、上層から下層に
向かって繰り返し実行する。すると、ワークリストに
は、パターンのみが残る。そこで、ＣＰＵ２は、残った
パターンに重なりがないかを調べる。

【０１４９】ここで、図１９に示すように、セルＥＥＥ
（１）に含まれるパターンＰＥ２と、セルＣＣＣ（２）
に含まれるパターンＰＣ１に重なりがあり、それぞれに
異なる種類［ＡＡＡ（１）］，［ＡＡＡ（２）］が設定
されている。従って、ＣＰＵ２は、パターンＰＥ２とパ
ターンＰＣ１を「重なり有り」と判定する。そして、Ｃ
ＰＵ２は、重なりがあるパターンＰＥ１，ＰＣ１の重な
り情報を図１の第３データファイル１３に格納する。

【０１５０】上記のように、スイープ法を用いることに
より、重なりのあるパターンを容易に検出することがで
きるので、処理時間が短くなる。以上記述したように、
本実施の形態によれば、以下の効果を奏する。

【０１５１】（１）入力したレイアウトデータに対し
て、各セル毎に展開した時の存在領域を設定し、各存在
領域の領域枠，パターンの枠よりなるセル枠の情報を作
成し、レイアウトデータに含まれるセルを順次処理対象
セルに設定し、処理対象セル以下の階層のセル，パター
ンのセル枠に対して階層構造に応じた種類を設定する。
そして、幾何学的に重なりがあるセル枠，パターンに対
して、異なる種類が設定されている場合には重なり有り
と判定し、セル枠同士又はセル枠とパターンに重なり有
りと判定した場合には重なりがあるセル枠に含まれる下
層のセル枠，パターンを更に読み込み、パターン同士に
重なりがあると判定した場合には該パターンの重なりを
確定するようにした。

【０１５２】その結果、各セルの枠に対して種類を設定
し、同じ種類の枠は「重なり無し」として処理している
ため、余計な重なりは調べないので、処理時間を短くす
ることができる。

【０１５３】（２）また、「重なり無し」と判定したセ
ル枠に含まれるストラクチャを読み込まない、即ち、
「重なり無し」と判定したセル枠と展開しないため、そ
の時々に処理するデータ数が少なくなって必要とするリ
ソース量を少なくすることができる。

【０１５４】（３）更に、予め重なりを除去したデータ
を作成する必要がない。そのため、リソースが不足する
ことがなく、処理時間を短くすることができる。 （４）セル枠に対しては、そのセル枠又はそのセル枠の
所属セルが処理対象セルの場合にはそのセル枠に対して
独自の種類を設定し、そのセル枠又はそのセル枠の所属
セルが処理対象セルではない場合には所属セルと同じ種
類を設定する。また、パターンに対しては、所属セルと
同じ種類を設定するようにした。そのため、レイアウト
データの階層構造に応じた種類を容易に設定することが
できる。

【０１５５】（４）図形の状態を検出するためにスイー
プ法を用いたため、重なりのあるパターンを容易に検出
することができる。そのため、図形処理の処理時間が短
くなり、処理の高速化を図ることができる。

【０１５６】

【発明の効果】以上詳述したように、本発明によれば、
処理の高速化とリソース量の低減を図ることが可能な図
形処理方法、図形処理装置、及び、記録媒体を提供する
ことができる。

【図面の簡単な説明】

【図１】 図形処理のフローチャート。

【図２】 種類設定処理のフローチャート。

【図３】 一実施形態の図形処理装置の概略構成図。

【図４】 図形の階層構造を示す説明図。

【図５】 図形の階層構造を説明するための斜視図。

【図６】 データの関連を示す説明図。

【図７】 図形の階層構造を示す説明図。

【図８】 展開された図形を示すレイアウト図。

【図９】 図形の階層構造を示すレイアウト図。

【図１０】 図形処理を説明するためのレイアウト図。

【図１１】 図形の展開処理を示すレイアウト図。

【図１２】 図形の展開処理を示すレイアウト図。

【図１３】 図形の展開処理を示すレイアウト図。

【図１４】 別の図形の階層構造を示す説明図。

【図１５】 別の展開された図形を示すレイアウト図。

【図１６】 別の図形の階層構造を示すレイアウト図。

【図１７】 別の図形処理を説明するためのレイアウト
図。

【図１８】 別の図形の展開処理を示すレイアウト図。

【図１９】 別の図形の展開処理を示すレイアウト図。

【符号の説明】

１１ 第１データファイル（レイアウトデータ） １３ 第３データファイル（重なり情報） ２１ 領域枠作成手段 ２２ 処理対象セル設定手段 ２３ データ読み込み手段 ２４ 種類設定手段 ２５ 第１重なり判定手段 ２６ 第２重なり判定手段 ２７ 重なり確定手段

Claims (9)

【特許請求の範囲】
1. 【請求項１】 セル及びパターンが階層構造に構成され
   たレイアウトデータに対して、パターンの幾何学的な重
   なりを検出する図形処理方法であって、 前記レイアウトデータを入力し、各セル毎に展開した時
   の存在領域を設定し、各存在領域の領域枠，パターンの
   枠よりなるセル枠の情報を作成し、 前記レイアウトデータに含まれるセルを順次処理対象セ
   ルに設定し、 前記処理対象セル以下の階層のセル，パターンのセル枠
   に対して階層構造に応じた種類を設定し、 前記幾何学的に重なりがあるセル枠，パターンに対し
   て、異なる種類が設定されている場合には重なり有りと
   判定し、セル枠同士又はセル枠とパターンに重なり有り
   と判定した場合には重なりがあるセル枠に含まれる下層
   のセル枠，パターンを更に読み込み、パターン同士に重
   なりがあると判定した場合には該パターンの重なりを確
   定するようにした図形処理方法。
2. 【請求項２】 セル及びパターンが階層構造に構成され
   たレイアウトデータに対して、パターンの幾何学的な重
   なりを検出する図形処理方法であって、 前記レイアウトデータを入力し、各セル毎に展開した時
   の存在領域を作成し、作成した各存在領域の領域枠，パ
   ターンの枠よりなるセル枠の情報を階層構造にてファイ
   ルに格納するステップと、 前記レイアウトデータに含まれるセルを順次処理対象セ
   ルに設定するステップと、 前記処理対象セル以下の階層のセル，パターンのセル枠
   に対して階層構造に応じた種類を設定するステップと、 前記処理対象セル、又は重なり有りと判定したセル枠に
   含まれるセル枠，パターンを読み込むステップと、 前記新たに読み込んだセル枠のうち、種類が異なるセル
   枠同士、又はセル枠とパターンに重なりがあるか判定す
   るステップと、 前記新たに読み込んだセル枠に重なりがない場合に、前
   記読み込んだパターンのうち、種類の異なるパターンに
   重なりがあるか判定するステップと、 前記重なり有りと判定されたパターンの重なりを確定
   し、幾何学的に重なるパターンの重なり情報を含むテー
   ブルを作成するステップを備えた図形処理方法。
3. 【請求項３】 請求項１又は２に記載の図形処理方法に
   おいて、 前記セル枠，パターンに対して種類を設定する場合に、 セル枠に対しては、 該セル枠又は該セル枠の所属セルが処理対象セルの場合
   には該セル枠に対して独自の種類を設定し、 該セル枠又は該セル枠の所属セルが処理対象セルではな
   い場合には所属セルと同じ種類を設定し、 パターンに対しては、所属セルと同じ種類を設定するよ
   うにした図形処理方法。
4. 【請求項４】 請求項１乃至３のうちの何れか１項に記
   載の図形処理方法において、 前記処理対象セルに対して、該スイープ法を用いて幾何
   学的に重なるセル又はパターンを検出し、検出したセル
   枠，パターンにおいて重なりを判定するようにした図形
   処理方法。
5. 【請求項５】 セル及びパターンが階層構造に構成され
   たレイアウトデータに対して、パターンの幾何学的な重
   なりを検出する図形処理装置であって、 前記レイアウトデータを入力し、各セル毎に展開した時
   の存在領域を設定し、各存在領域の領域枠，パターンの
   枠よりなるセル枠の情報を作成する領域枠作成手段と、 前記レイアウトデータに含まれるセルを順次処理対象セ
   ルに設定する処理対象セル設定手段と、 前記処理対象セル以下の階層のセル，パターンのセル枠
   に対して階層構造に応じた種類を設定する種類設定手段
   とを備え、 前記幾何学的に重なりがあるセル枠，パターンに対し
   て、異なる種類が設定されている場合には重なり有りと
   判定し、セル枠同士又はセル枠とパターンに重なり有り
   と判定した場合には重なりがあるセル枠に含まれる下層
   のセル枠，パターンを更に読み込み、パターン同士に重
   なりがあると判定した場合には該パターンの重なりを確
   定するようにした図形処理装置。
6. 【請求項６】 セル及びパターンが階層構造に構成され
   たレイアウトデータに対して、パターンの幾何学的な重
   なりを検出する図形処理装置であって、 前記レイアウトデータを入力し、各セル毎に展開した時
   の存在領域を作成し、作成した各存在領域の領域枠，パ
   ターンの枠よりなるセル枠の情報を階層構造にてファイ
   ルに格納する領域枠作成手段と、 前記レイアウトデータに含まれるセルを順次処理対象セ
   ルに設定する処理対象セル設定手段と、 前記処理対象セル以下の階層のセル，パターンのセル枠
   に対して階層構造に応じた種類を設定する種類設定手段
   と、 前記処理対象セル、又は重なり有りと判定したセル枠に
   含まれるセル枠，パターンを読み込むデータ読み込み手
   段と、 前記新たに読み込んだセル枠のうち、種類が異なるセル
   枠同士、又はセル枠とパターンに重なりがあるか判定す
   る第１重なり判定手段と、 前記新たに読み込んだセル枠に重なりがない場合に、前
   記読み込んだパターンのうち、種類の異なるパターンに
   重なりがあるか判定する第２重なり判定手段と、 前記重なり有りと判定されたパターンの重なりを確定
   し、幾何学的に重なるパターンの重なり情報を含むテー
   ブルを作成する重なり確定手段とを備えた図形処理装
   置。
7. 【請求項７】 請求項５又は６に記載の図形処理装置に
   おいて、 前記種類設定手段において、 セル枠に対しては、 該セル枠又は該セル枠の所属セルが処理対象セルの場合
   には該セル枠に対して独自の種類を設定し、 該セル枠又は該セル枠の所属セルが処理対象セルではな
   い場合には所属セルと同じ種類を設定し、 パターンに対しては、所属セルと同じ種類を設定するよ
   うにした図形処理装置。
8. 【請求項８】 請求項５乃至７のうちの何れか１項に記
   載の図形処理装置において、 前記処理対象セルに対して、該スイープ法を用いて幾何
   学的に重なるセル又はパターンを検出し、検出したセル
   枠，パターンにおいて重なりを判定するようにした図形
   処理装置。
9. 【請求項９】 請求項１乃至４のうちの何れか１項に記
   載の図形処理方法にて重なりを検出する図形処理プログ
   ラムを記録した記録媒体。