階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を行うパターンデータ処理方法において、セル毎に外部から当該セルに侵入する外部パターンを検出し、前記外部パターンが当該セルに侵入する領域を共通侵入領域として当該セルに関連付ける共通侵入領域算出ステップと、セルに関連付けられた前記共通侵入領域に基づいて、前記所定の処理の内容に応じて、当該セルの中で前記外部パターンとともに前記所定の処理を行う必要のある領域を当該セルの影響範囲として算出する影響範囲算出ステップと、セルのデータ存在領域から当該セルの影響範囲を除外した領域を当該セルの共通データ領域として算出する共通データ領域算出ステップと、前記各セルの共通データ領域については前記所定の処理を一度行うと共に前記影響範囲については当該セルに侵入する前記外部パターンとともに前記所定の処理を行うことにより、前記パターンデータに対する前記所定の処理を行うパターンデータ処理ステップとを備えて成ることを特徴とするパターンデータ処理方法。前記共通侵入領域算出ステップは、セルが同位階層の他のセルと重複する領域であるセル間重複領域を検出するセル間重複領域検出ステップと、各セルのパターンと各セルの最下位階層セルに至るまでの全ての下位階層セルのパターンの内、当該セルのセル間重複領域に重複するパターンであるセル間重複パターンを抽出するセル間重複パターン抽出ステップと、各セルに重複する同位階層の他のセルのセル間重複パターンと、当該セルの最上位階層に至るまでの全ての上位階層のセルのパターンのうち当該セルのデータ存在領域に重複するパターンとから成る前記共通侵入領域を算出する共通侵入領域検出ステップとを備えて成ることを特徴とする請求項1記載のパターンデータ処理方法。前記セル間重複領域検出ステップは、各セルと同位階層セルとの間の重複領域をセル間重複領域として検出する処理と、最上位階層セルから最下位階層セルまで順に各セルのセル間重複領域と上位階層の処理で検出した当該セルのパターン展開必要領域のOR領域の内、一階層下位のセルのデータ存在領域と重複する領域を下位階層のセルのパターン展開必要領域として検出する処理であり、前記セル間重複パターン抽出ステップは、最下位階層セルから最上位階層セルまで順に、各セルのパターンと下位階層から展開された評価対象パターンを合わせたパターンを当該セルの評価対象パターンとし、当該セルのセル間重複領域に重複する評価対象パターンを当該セルのセル間重複パターンとして抽出すると共に、前記当該セルのパターン展開必要領域に存在する当該セルの評価対象パターンを上位階層に展開する処理であり、前記共通侵入領域検出ステップは、最上位階層セルから最下位階層セルまで順に、各セルに重複する同位階層のセルのセル間重複パターンと、当該セルに重複する一階層上位のセルのパターンと、当該セルに重複する一階層上位のセルの共通侵入領域とから成る前記共通侵入領域を算出する処理であることを特徴とする請求項2記載のパターンデータ処理方法。階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を行うパターンデータ処理装置において、セル毎に外部から当該セルに侵入する外部パターンを検出し、前記外部パターンが当該セルに侵入する領域を共通侵入領域として当該セルに関連付ける共通侵入領域算出手段と、セルに関連付けられた前記共通侵入領域に基づいて、前記所定の処理の内容に応じて、当該セルの中で前記外部パターンとともに前記所定の処理を行う必要のある領域を当該セルの影響範囲として算出する影響範囲算出手段と、セルのデータ存在領域から当該セルの影響範囲を除外した領域を当該セルの共通データ領域として算出する共通データ領域算出手段と、前記各セルの共通データ領域については前記所定の処理を一度行うと共に前記影響範囲については当該セルに侵入する前記外部パターンとともに前記所定の処理を行うことにより、前記パターンデータに対する前記所定の処理を行うパターンデータ処理手段とを備えて成ることを特徴とするパターンデータ処理装置。前記共通侵入領域算出手段は、セルが同位階層の他のセルと重複する領域であるセル間重複領域を検出するセル間重複領域検出手段と、各セルのパターンと各セルの最下位階層に至るまでの全ての下位階層セルのパターンの内、当該セルのセル間重複領域に重複するパターンであるセル間重複パターンを抽出するセル間重複パターン抽出手段と、各セルに重複する同位階層の他のセルのセル間重複パターンと、当該セルの最上位階層に至るまでの全ての上位階層のセルのパターンのうち当該セルのデータ存在領域に重複するパターンとから成る前記共通侵入領域を算出する共通侵入領域検出手段とを備えて成ることを特徴とする請求項4記載のパターンデータ処理装置。前記セル間重複領域検出手段は、各セルと同位階層セルとの間の重複領域をセル間重複領域として検出すると共に、最上位階層セルから最下位階層セルまで順に各セルのセル間重複領域と上位階層の処理で検出した当該セルのパターン展開必要領域のOR領域の内、一階層下位のセルのデータ存在領域と重複する領域を下位階層のセルのパターン展開必要領域として検出し、前記セル間重複パターン抽出手段は、最下位階層セルから最上位階層セルまで順に、各セルのパターンと下位階層から展開された評価対象パターンを合わせたパターンを当該セルの評価対象パターンとし、当該セルのセル間重複領域に重複する評価対象パターンを当該セルのセル間重複パターンとして抽出すると共に、前記当該セルのパターン展開必要領域に存在する当該セルの評価対象パターンを上位階層に展開し、前記共通侵入領域検出手段は、最上位階層セルから最下位階層セルまで順に、各セルに重複する同位階層のセルのセル間重複パターンと、当該セルに重複する一階層上位のセルのパターンと、当該セルに重複する一階層上位のセルの共通侵入領域とから成る前記共通侵入領域を算出することを特徴とする請求項5記載のパターンデータ処理装置。コンピュータに、階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を実行させるためのパターンデータ処理用プログラムにおいて、コンピュータに請求項1乃至3のいずれか一に記載のパターンデータ処理方法を実行させることを特徴とするパターンデータ処理用プログラム。コンピュータに請求項1乃至3のいずれか一に記載のパターンデータ処理方法を実行させるためのパターンデータ処理用プログラムを記録したコンピュータ読み取り可能な記録媒体。本発明は、前述したような厳しい設計制約を設けることなく、階層化された複数のセルを有するパターンデータに対して論理演算処理等の予め定めた所定の処理を効率的に行うことを課題としている。本発明の第1の視点によれば、階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を行うパターンデータ処理方法において、セル毎に外部から当該セルに侵入する外部パターンを検出し、前記外部パターンが当該セルに侵入する領域を共通侵入領域として当該セルに関連付ける共通侵入領域算出ステップと、セルに関連付けられた前記共通侵入領域に基づいて、前記所定の処理の内容に応じて、当該セルの中で前記外部パターンとともに前記所定の処理を行う必要のある領域を当該セルの影響範囲として算出する影響範囲算出ステップと、セルのデータ存在領域から当該セルの影響範囲を除外した領域を当該セルの共通データ領域として算出する共通データ領域算出ステップと、前記各セルの共通データ領域については前記所定の処理を一度行うと共に前記影響範囲については当該セルに侵入する前記外部パターンとともに前記所定の処理を行うことにより、前記パターンデータに対する前記所定の処理を行うパターンデータ処理ステップとを備えて成ることを特徴とするパターンデータ処理方法が提供される。また、本発明の第2の視点によれば、階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を行うパターンデータ処理装置において、セル毎に外部から当該セルに侵入する外部パターンを検出し、前記外部パターンが当該セルに侵入する領域を共通侵入領域として当該セルに関連付ける共通侵入領域算出手段と、セルに関連付けられた前記共通侵入領域に基づいて、前記所定の処理の内容に応じて、当該セルの中で前記外部パターンとともに前記所定の処理を行う必要のある領域を当該セルの影響範囲として算出する影響範囲算出手段と、セルのデータ存在領域から当該セルの影響範囲を除外した領域を当該セルの共通データ領域として算出する共通データ領域算出手段と、前記各セルの共通データ領域については前記所定の処理を一度行うと共に前記影響範囲については当該セルに侵入する前記外部パターンとともに前記所定の処理を行うことにより、前記パターンデータに対する前記所定の処理を行うパターンデータ処理手段とを備えて成ることを特徴とするパターンデータ処理装置が提供される。また、本発明の第3の視点によれば、コンピュータに階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を実行させるためのパターンデータ処理用プログラムにおいて、本発明に係るパターンデータ処理方法をコンピュータに実行させることを特徴とするパターンデータ処理用プログラムが提供される。また、本発明の第4の視点によれば、コンピュータに本発明のパターンデータ処理方法を実行させるためのパターンデータ処理用プログラムを記録したコンピュータ読み取り可能な記録媒体が提供される。本発明のパターンデータ処理方法によれば、厳しい設計制約を設けることなく、階層化された複数のセルを有するパターンデータに対して論理演算処理等の予め定めた所定の処理を効率的に行うことが可能になる。また、本発明のパターンデータ処理装置によれば、厳しい設計制約を設けることなく、階層化された複数のセルを有するパターンデータに対して論理演算処理等の予め定めた所定の処理を効率的に行うことが可能になる。また、コンピュータが本発明のパターンデータ処理用プログラムを実行することにより、厳しい設計制約を設けることなく、階層化された複数のセルを有するパターンデータに対して論理演算処理等の予め定めた所定の処理を効率的に行うことが可能になる。また、本発明の記録媒体に記録したパターンデータ処理用プログラムをコンピュータに実行させることにより、厳しい設計制約を設けることなく階層化された複数のセルを有するパターンデータに対して論理演算処理等の予め定めた所定の処理を効率的に行うことが可能なパターンデータ処理装置を構築することが可能になる。本発明の実施の形態の概要を説明すると、階層化された複数のセルを有するパターンデータに対して論理演算処理等の予め定めた所定の処理パターンデータ処理を行う場合、先ず、パターンデータのレイヤ毎に、各セルの外部から各セル内に実際に侵入するパターン外部パターンの形状を検出する。セルはパターンの集合であり又パターンデータの構成要素である。各セルは、自セルの内部に他のセルを参照することによって階層構造を成している。パターンデータは前記階層化された複数のセルによって構成される。尚、或るセルへのパターンの侵入とは、参照点ごとに、或るセルと前記或るセルの傘下にある全ての下位階層セルとを除外した残り全てのパターンのうちの、いずれかのパターンが、前記或るセルのデータが存在する領域データ存在領域に対して重なることを意味している。ここで、或るセルの全ての下位階層セルとは、或るセルの傘下にある全ての下位の階層セルの意味である。或るセルの傘下にある下位階層セルとは、下位階層セルから順に上位階層へ辿って行ったとき、前記或るセルに到達することができる場合の当該下位階層セルを意味している。次に、各セルに侵入する前記外部パターンの形状のOR領域以下、共通侵入領域と称す。を求める。次に、前記共通侵入領域を基に、前記外部パターンの影響でパターンデータ処理の結果が不正確になる換言すれば、外部パターンが異なることによってパターンデータ処理の結果が異なる可能性がある各セル内領域以下、影響範囲と称す。を抽出する。前記影響範囲はパターン処理の内容に応じて定められる。このようにして、前記外部パターンの形状を基に前記影響範囲を求める。次に、前記処理結果が異なる可能性のあるセル内のパターンは、影響範囲を元に抽出することができる。したがって、前記処理結果が異なる可能性のあるセル内のパターンは、前記外部パターンとマージして前記所定のパターンデータ処理を行う。前記処理結果が共通となる換言すれば、外パターンが異なってもパターンデータ処理の結果が同じになるセルのパターンについても影響範囲を元に抽出することができ、これについては単独で一度だけ前記所定のパターンデータ処理を行う。尚、影響範囲は、セル内の演算結果が外部パターンの影響で変動する領域、換言すればセル内パターンの影響で外部の演算結果が変動する領域である。即ち、影響範囲は、パターンデータ全体について最終的に正しいパターンデータ処理の結果を得るためには、外部パターンとセル内のパターンをマージした上で演算することが必要なセル内領域を意味している。これにより、パターンデータ全体に対して所定のパターンデータ処理が行われる。このようにして、セル間のパターン重複領域をセル内周囲の領域に設定することなく、所定のパターンデータ処理を行うことが可能となる。したがって、厳しい設計制約を設けることなく、階層化された複数のセルを有するパターンデータに対して、論理演算処理等の予め定めた所定の処理を効率的に行うことが可能になる。パターンデータ処理には、パターンの論理演算を行う論理演算処理、パターンの大きさやパターン間の間隔等を変更する変更処理、パターンの大きさやパターン間の間隔等を検査する検証処理、パターンの形状やパターン間の重複関係でパターンを選択する選択処理などがある。より具体的には、AND処理やOR処理等の論理演算処理、配線や素子のパターンのサイズを変更するサイジング処理、パターンや素子等の寸法チェック処理、あるいは重複するパターンだけの抽出等を行う対象選択処理等、種々のパターンデータ処理がある。パターンデータ処理の内容に応じて影響範囲は異なることになる。しかしながら、いずれのパターンデータ処理の場合でも、パターンデータ処理の内容に応じて、外部パターンの形状を基に前記影響範囲を決定することが可能である。本発明の実施の形態の概要について更に詳しく説明すると、仮に、或るセルが参照している複数の同一構成のセル参照点に対して、参照点毎にセル内に外部パターンが侵入する領域パターン侵入領域を基にしてパターンデータ処理を行うとした場合には、参照点数に応じたオーダーの処理を行うことになり、各セルの全てのパターンを展開して処理することと同等の膨大なデータ処理量になってしまう。一方、参照点の一箇所でもパターン侵入領域が存在すると、影響範囲に対するパターンデータ処理の結果は前記パターン侵入領域の影響によって変わるため、全ての参照点で同一の処理結果が得られるわけではない。しかしながら、この影響範囲を除いた領域に対するパターンデータ処理の結果は、全ての参照点で同一となる。階層処理で必要なのは、同一の結果となるデータは一度だけの処理とすることであるから本発明の実施の形態では、先ず、セル毎に全ての参照点で外部パターンが侵入する形状のOR領域以下、共通侵入領域と称す。を求めておく。次に、前記共通侵入領域に基づいて、パターンデータ処理の内容に応じた影響範囲を算出し、セル内のパターンデータが存在し得る最大領域から前記影響範囲を除いた領域以下、共通データ領域と称す。についてパターンデータ処理を行う。前記共通データ領域についてのパターンデータ処理の結果をこの階層セルの処理結果とすることにより、共通データ領域についてのパターンデータ処理は一度だけの処理とすることが可能となる。前記影響範囲については、各セル毎に、外部パターンにマージして個別にパターンデータ処理を行う。このように共通データ領域と影響範囲に分けてパターンデータ処理を行い、それらの処理結果を統合することにより、パターンデータ全体についてのパターンデータ処理を行うことが可能になる。前記影響範囲は、パターンデータ処理の結果として得られるパターン形状が、共通侵入領域に含まれる外部パターンの影響を受けて変更される可能性のある、セル内の最大領域である。同様に共通データ領域は、共通侵入領域に含まれる外部パターンの影響を受けずに、パターンデータ処理を行うことが可能な領域であり、パターンデータ処理結果として得られるパターン形状が、外部パターンによって変更されることがないセル内の最大領域である。セルの共通データ領域は、当該セルのデータが存在する領域であるデータ存在領域から当該セルの影響範囲を除外した領域である。例えば、AND処理、OR処理、SUB処理等の論理演算処理では、共通侵入領域の内側領域の処理結果のみが外部パターンによって変更され、共通侵入領域の外側領域の処理結果が変更されることはない。また、WIDTH処理パターンの幅を指定した検証、SPACE処理パターンの間隔を指定した検証、ENC処理包含余裕を指定した検証等の寸法チェック処理やサイジング処理では、共通侵入領域からルールによって指定した幅に応じた外側の領域までの処理結果が変更される可能性がある。例えば、共通侵入領域からルール値の範囲は一般に影響を受けるが、コーナー部の仕様としてルール値の√2倍の距離まで外部パターンが影響する場合、これを考慮して影響範囲を算出する必要がある。また、指定レイヤと重複するパターンを抽出するなどの対象選択処理では、共通侵入領域と重複するセル内パターンは、外部パターンの有無により選択あるいは非選択の演算結果が異なる可能性があるため、前記共通侵入領域と重複するセル内パターン全体が影響範囲となる。このように、共通侵入領域が同一の場合でも、パターンデータ処理の内容によって影響範囲は異なることになる。共通侵入領域に含まれる外部パタ-ンの形状によってパターンデータ処理の結果が異なってしまう最大の領域を考慮して影響範囲を求めることにより、共通侵入領域に基づいてパターンデータ処理の内容に応じた影響範囲を容易に求めることが可能である。例えば、多くのパターンデータ処理内容の影響範囲は距離により規定でき、この場合共通侵入領域を一定距離拡大した領域を影響範囲とすることができる。また、外部パターンが接触や重複、包含など接続することでパターンデータ処理内容の結果が異なる場合、共通侵入領域が接触するパターン全体により影響範囲を規定することができる。このように、パターンデータ処理内容により影響範囲を規定する項目を明確化し、この項目が最大となる形状を共通侵入領域に含まれる外部パタ-ンの形状に仮定することで、影響範囲を求めることができる。影響範囲についてパターンデータ処理する場合、影響範囲内の処理結果を決定するために必要な範囲のセル内パターン以下、境界パターンと称す。を例えばデータ展開し、セル外のパターンとマージして個別処理することで、各参照点の個別のパターンデータ処理結果を得ることができる。尚、共通侵入領域からの影響と同様に、影響範囲内の処理結果は、影響範囲の近傍のパターンから演算内容に応じた影響を受ける。このため、前記境界パターンは影響範囲の外部のパターンを含む場合もある。この範囲を求める方法は、共通侵入領域から影響範囲を求める方法と同様である。このとき、境界パターンの形状により、セル内の処理結果に比べてパターンが追加される部分と削除される部分がある。パターンが追加される部分は、上位階層セルに処理結果のパターンとして追加すればよいことから、セル内の処理結果に影響はない。パターンが削除される部分は、上位階層セルで削除することができないため、削除される可能性のある部分をセル内の結果から予め削除しておき、セル内の該当部分と合わせた結果を上位階層セル内に作成する等の方法をとることになる。ここで、実際のパターンデータ処理方法は、必ずしも前記のように共通データ領域に対応する階層のパターンデータ処理と、展開された共通侵入領域に基づく影響範囲のパターンデータ処理とに限定するものではない。影響範囲のパターンデータ処理結果に対し、参照点ごとに新たなセルとしこれを参照することで、同一の処理結果を共通化する方法を採用することや、あるいは共通データ領域とあわせた新たなセルとする方法を採用することも可能である。また、共通侵入領域に基づく影響範囲は、参照点毎に個別処理が必要となるため、処理時間短縮のためにはできるだけ少ないことが望ましい。このため、パターンデータ処理の内容をより詳細に考慮して影響範囲を狭い範囲にするような算出方法を採用することは可能である。また、各セルにおいて、当該セル内の下位階層を含めた全てのデータを包含する領域データ存在領域は、当該セルにおいて全てのレイヤで共通であるようにしている。データ存在領域は、全てのデータを包含するXY軸方向に沿った長方形が基本であるが、データが存在しない大面積の領域がある場合、データが存在しない部分を除く距離に依存する処理に対して、その影響距離分拡張する領域の外部の重複関係が検出できない場合、外部を全て重複すると扱う等のバリエーションは可能である。以上により、重複領域に厳しい制約を設けることなく、正確で効率的な階層処理を実現することが可能となる。以下、本発明の実施の形態について、図面を参照しながら詳細に説明する。図1は、本発明の実施の形態の原理を説明するための説明図で、LSILargeScaleIntegrationcircuitの例を示している。パターンデータは、フォトリソグラフィで使用するマスクに対応した複数のレイヤ構造を持っており、パターンデータ処理もこのレイヤを基準に実行する。このため、パターンデータを構成する各セルのレイヤ毎に、セルの外部からパターン外部パターンが侵入した領域を共通侵入領域として保持する。共通侵入領域は、外部パターンが侵入した領域の個々の形状は不要であり、侵入した個々の領域を結合し、それを枠取りした形状でよい。即ち、階層セルの共通侵入領域は、外部パターンのうちの当該階層セルのデータ存在領域に侵入した部分をOR処理することによって得られる領域である。次に、パターンデータ処理の処理内容に応じて、共通侵入領域を基にして、外部パターンと一緒にパターンデータ処理する必要のある領域影響範囲を求める。影響範囲の処理は、階層セル内のパターンのうち影響範囲の処理に必要な範囲のパターンを、上位階層セルに展開する等して、外部パターンと一緒に個別処理する。セルのデータ存在領域から前記影響範囲を除いた部分は、セルの外部の処理とは無関係に独立して処理可能な部分共通データ領域である。この部分は、一度だけ処理しておけば、同一セルの共通データ領域に関する処理が、パターンデータにおける他の領域においても必要な場合には、当該処理結果を利用することができる。共通侵入領域が同じ場合でも、影響範囲の算出方法はパターンデータ処理の内容に応じた演算処理毎に異なるが、影響範囲は共通侵入領域を基準に求めることができる。したがって、共通侵入領域を一度求めておけば、階層処理を行う場合に、実際にパターンデータ処理に影響を与える影響範囲や共通データ領域を容易に求めることが可能になる。影響範囲については個別にパターンデータ処理すると共に、共通データ領域については一度だけパターンデータ処理することにより、厳しい制約を設けることなく、正確で効率的な階層処理を実現することが可能となる。図1iにおいて、セルa、セルbは階層構造を有しており、セルaは上位階層セル例えばトップTopセル、セルbは下位階層セルである。セルaは2つのセルbを参照点として有すると共に、配線等のパターン101、102を有している。パターン101、102は、セルbから見れば、外部からセルb内へ侵入する外部パターンである。尚、各セルに含まれるパターン等のデータは各セルのデータ存在領域内に存在するが、図1の例では、各セルa、セルbのデータ存在領域は実線の長方形枠で囲まれた領域である。以下の各図においても、セルのデータ存在領域は実線の長方形枠で囲まれた領域としているが、他の形状の枠をデータ存在領域とすることができる。図1iiに示すように、パターン101、102のうち各セルbに侵入する部分のOR処理を行うことにより、共通侵入領域103が得られる。共通侵入領域103は、参照点図1の例ではセルbのいずれかに外部のパターン101、102が侵入する領域である。共通侵入領域103を基に、パターンデータ処理の演算内容に応じたセルbの影響範囲が決定できる。影響範囲は、パターンデータ処理が例えばAND処理やOR処理等の論理演算処理の場合には、共通侵入領域103に含まれる領域となる。パターンデータ処理がサイジング処理や寸法チェック処理の場合には、影響範囲は、共通侵入領域を所定サイズ幅拡大した領域となる。また、パターンデータ処理が対象選択処理の場合には、影響範囲は、共通侵入領域内に外部パターンが存在することによってパターンデータ処理の結果選択又は非選択が変化するパターン全体の領域となる。影響範囲は、上位階層セルaの演算処理を行う際に上位階層セルaとマージして演算が必要な領域である。下位階層セルbのデータ存在領域から影響範囲を除いた部分は、他の処理から独立してパターンデータ処理可能な領域共通データ領域である。このように、本発明の実施の形態は、各セル毎に共通侵入領域103を求めておき、共通侵入領域103を用いて論理演算処理等の各種のパターンデータ処理を行うことを特徴とするものである。また、本発明の実施の形態は、各セル毎に求めた共通侵入領域を基に、パターンデータ処理の内容に応じた影響範囲を求め、影響範囲については上位に展開して個別にパターンデータ処理を行い、セルのデータ存在領域から影響範囲を除外した共通データ領域については一度だけパターンデータ処理を行うことにより、パターンデータ全体のパターンデータ処理を行うことを特徴とするものである。即ち、本発明の実施の形態では、セルの階層構造に着目して、各セルの参照点毎に、当該セルと前記当該セルの傘下にある全ての下位階層セルとを除外した残り全てのパターンから当該セルのデータ存在領域に侵入するパターンこれらのパターンを纏めて外部パターンと称す。を検出して、各セルに外部パターンが侵入する全ての領域の和を当該セルの共通侵入領域として関連付けて持たせておく。パターンデータ処理を行う際に、共通侵入領域及びパターンデータ処理の内容に応じて影響範囲及び共通データ領域を算出する。前記共通データ領域については一度のみのパターンデータ処理とすることにより、同一セルが複数使用されている場合にパターンデータ処理回数を低減する。また、前記影響範囲についてはセル毎に個別にパターンデータ処理を行う。これにより、パターンデータ処理全体に対する処理が可能になるため、厳しい設計制約を設けることなく、効率的に階層的パターンデータ処理を実現できる。以下、本発明の実施の形態に係るパターンデータ処理方法、パターンデータ処理装置、前記パターンデータ処理方法をコンピュータに実行させるためのパターンデータ処理用プログラム及び前記パターンデータ処理用プログラムを記録したコンピュータ読み取り可能な記録媒体について、図面に沿って詳細に説明する。尚、各図において、同一部分には同一符号を付している。図2は、本発明の実施の形態に係るパターンデータ処理装置200のブロック図である。図2において、パターンデータ処理装置200は、コンピュータによって構成することができ、CADComputerAidedDesignによって作成したパターンデータ217に対する論理演算等の各種処理を行う機能を有している。本実施の形態では、パターンデータとしてLSIのパターンデータ217の例を示している。パターンデータ217は、階層化された複数のセルから成るセルデータ211を有している。セルのデータセルデータはレイアウトデータとも称され、セルデータ211は複数のセルデータによって構成されている。各セルのセルデータは、配線パターンや電子回路素子等の構成要素レイアウト図形要素の多角形の図形データと当該多角形の座標データを有しており又、参照するセルのデータとして、セル名称、座標、反転回転繰り返し等のデータを有している。パターンデータ217は複数のセルデータによって構成され、セルデータ211の一部若しくは全部の複数のセルデータによって構成される。複数のセルデータ211の中から、LSIや表示装置のパターンデータ処理対象を表すのに必要な複数のセルデータが組み合わされてパターンデータ217が構成されている。パターンデータ処理装置200は、中央処理装置CPUによって構成されパターンデータ処理を行うパターンデータ処理部201、液晶表示装置LCD等によって構成された表示部202、マウスやキーボードを有する操作部203、パターンデータ処理部201が実行するプログラムや各種データを記憶する記憶部204を備えている。記憶部204は磁気ディスク等によって構成されている。記憶部204には、処理対象のパターンデータ217がパターンデータ処理を行う前に格納される。CD-ROMCompactDisc-ReadOnlyMemory等のコンピュータ読み取り可能な記録媒体213には、パターンデータ処理部201が実行するパターンデータ処理用プログラムが記録されている。記録媒体213に記録された前記パターンデータ処理用プログラムは、記憶部204のプログラム領域に記憶して利用される。パターンデータ処理部201は、記憶部204に記憶したパターンデータ処理用プログラムを実行することにより、共通侵入領域算出処理部205及び図形処理部206を構築する。共通侵入領域算出処理部205は、CADによって作成され記憶部204に記憶されたパターンデータ217を利用して共通侵入領域を算出する機能を有する。共通侵入領域算出処理部205は、セル間の重複領域を検出するセル間重複領域検出処理部216、セル間の重複パターンを抽出するセル間重複パターン抽出処理部207、及び、外部パターンから共通侵入領域を検出する共通侵入領域検出処理部208を有している。外部パターンは、セル間重複パターンと、上位階層セルのパターンの中の各セル内に侵入するパターンとを合わせたものである。セル間重複領域検出処理部216は、セル毎に、当該セルのセルゾーンと、他の全ての同位階層のセルのセルゾーンとが重複する領域セル間重複領域を検出する。ここで、前記他の全ての同位階層のセルは、前記当該セルの全ての上位階層セル前記当該セルよりも1階層上位の全てのセルによって直接参照されているセルである。セル間重複パターン抽出処理部207はセル間重複パターン抽出処理を行う。セル間重複領域検出処理部216によるセル間重複領域検出処理と、セル間重複パターン抽出処理部207によるセル間重複パターン抽出処理とによって、セル間重複パターン検出処理が行われる。セル間重複パターン検出処理は、セル毎に、前記セル間重複領域に存在する当該セルおよび当該セルの傘下にある最下位階層セルに至るまでの全ての下位階層セルのパターンを検出する処理である。ここで、セルゾーンはセルのデータ存在領域上位階層セルから見れば参照点であり、当該セルの全データを包含する領域である。セルゾーンは必ずしも長方形でなくてもよい。共通侵入領域検出処理部208は共通侵入領域検出処理を行う。共通侵入領域検出処理は、セルデータ211のセル毎に、当該セルに侵入する外部パターンの侵入部分をOR処理することによって得られる領域共通侵入領域を求める処理である。共通侵入領域検出処理部208は、求めた共通侵入領域の形状データを、当該セルの共通侵入領域データとして当該セルに対応付けて記憶する。セル間重複領域検出処理部216のセル間重複領域検出処理、セル間重複パターン抽出処理部207のセル間重複パターン抽出処理及び共通侵入領域検出処理部208の共通侵入領域検出処理によって共通侵入領域算出処理が行われる。尚、パターンデータ217を構成する全てのセルについて共通侵入領域検出処理を予め行うようにすれば、他のパターンデータに対するパターンデータ処理を行う場合に各セルの共通侵入領域を利用することができるが、処理を短時間で済ませる場合には、パターンデータ217を構成するセルについてのみ共通侵入領域検出処理を行うようにしてもよい。図形処理部206は、共通侵入領域データ212を用いて、パターンデータ217に対して所定のパターンデータ処理を行う処理部である。図形処理部206は、影響範囲算出処理部214、共通データ領域算出処理部215、共通データ領域処理部209及び影響範囲処理部210を備えている。影響範囲算出処理部214は、パターンデータ処理の内容に応じて、セルの共通侵入領域に基づいて当該セルの影響範囲を求める処理を行う。共通データ領域算出処理部215は、セルのデータ存在領域と当該セルの影響範囲から共通データ領域を求める処理を行う。共通データ領域処理部209は各セルの共通データ領域についてパターンデータ処理を行う。影響範囲処理部210は各セルの影響範囲についてパターンデータ処理を行う。図形処理部206は、共通データ領域処理部209と影響範囲処理部210が行ったパターンデータ処理の結果を統合することによって、パターンデータ217全体に対するパターンデータ処理結果を得る。図形処理部206は、このパターンデータ処理結果を記憶部204に記憶する。ここで、表示部202は表示手段を構成し、操作部203は操作手段を構成し、記憶部204は記憶手段を構成し、パターンデータ処理部201は処理手段を構成している。また、共通侵入領域算出処理部205は共通侵入領域算出手段を構成し、図形処理部206はデータ処理手段を構成している。また、セル間重複領域検出処理部216はセル間重複領域検出手段を構成し、セル間重複パターン抽出処理部207はセル間重複パターン抽出手段を構成し、共通侵入領域検出処理部208は共通侵入領域検出手段を構成している。また、セル間重複領域検出処理部216及びセル間重複パターン抽出処理部207はセル間重複パターン検出手段を構成している。また、影響範囲算出処理部214は影響範囲算出手段を構成し、共通データ領域算出処理部215は共通データ領域算出手段を構成している。また、共通データ領域処理部209は共通データ領域処理手段を構成し、影響範囲処理部210は影響範囲処理手段を構成している。また、図形処理部206から影響範囲算出処理部214及び共通データ領域算出処理部215を除いた部分はパターンデータ処理手段を構成している。図3は、本実施の形態におけるセル間重複パターン検出処理を示すフローチャートで、パターンデータ処理部201が記憶部204に記憶したパターンデータ処理用プログラムを実行することによって行う処理である。セル間重複パターン検出処理はパターンデータ処理部201のセル間重複領域検出処理部216及びセル間重複パターン抽出処理部207が行う。セル間重複パターン検出処理は、各セルのデータ存在領域が他の全ての同位階層のセルのデータ存在領域と重複する領域セル間重複領域を検出する処理であるセル間重複領域検出処理ステップS301~S305、S310と、セルの傘下にある最下位階層セルに至るまでの全ての下位階層セルのパターンのうち、当該セルのセル間重複領域に重複するパターンであるセル間重複パターンを抽出するセル間重複パターン抽出処理ステップS306~S309、S311を有している。図4は、本実施の形態における共通侵入領域検出処理を示すフローチャートで、パターンデータ処理部201が記憶部204に記憶したパターンデータ処理用プログラムを実行することによって行う処理である。共通侵入領域検出処理はパターンデータ処理部201の共通侵入領域検出処理部208が行う。図5は本発明の実施の形態で使用するセルを示す図で、図6は本実施の形態で使用する各セルの階層構造を示す図である。図5及び図6に示すように、図5iは最上位階層トップセルTop、図5iiはセルTopの1階層下位に位置しセルTopが参照する階層セルA、図5iiiはセルTopの1階層下位に位置しセルTopが参照する階層セルB、図5ivは階層セルAの下位階層に位置し階層セルAが参照する階層セルC、図5vは階層セルA及び階層セルBの下位階層に位置し階層セルA及び階層セルBが参照する階層セルDである。参照セルは、当該参照セルの一階層上のセルによって参照されるセルである。また、参照セルは、当該参照セルの一階層上のセルに直接含まれるセルである。セルCは、セルAを介して間接的にセルTopに含まれるため、セルTopの参照セルではない。セルDも、セルA、セルBを介して間接的にセルTopに含まれるため、セルTopの参照セルではない。セルTopは、LSI全体を表すパターンデータ217に相当し、2つのセルA及び1つのセルBを参照セルとして有すると共に、最上位階層のパターンとしてパターン501を有している。セルAは、1つのセルC及び1つのセルDを参照セルとして含むと共に、当該セルAの階層のパターンとしてパターン502を有している。セルBは、1つのセルDを参照セルとして含むと共に、当該セルBの階層のパターンとしてパターン503を有している。セルCは、最下位階層ボトムのセルであり、参照セルを含んでおらず、当該セルCの階層のパターンとしてパターン504を有している。セルDはセルCと同様に、最下位階層ボトムのセルであり、参照セルを含んでおらず、当該セルDの階層のパターンとしてパターン505を有している。セルA、B、C、Dは、セルTopの傘下にあるセルである。セルAの傘下にあるセルはセルC、Dである。セルBの傘下にあるセルはセルDのみである。セルCはセルAの傘下にある下位階層セルではあるが、セルBの下位階層セルではない。セルDはセルA、Bの傘下にある下位階層セルである。セルA、Bは同位階層のセル1階層上に同じ上位階層セルを有するセルである。セルC、Dは、セルAを基準にして見た場合、セルAの1階層下にあるため、セルC、DはセルAを基準とする場合には同位階層である。しかしながら、セルBを基準にして見た場合には、セルDはセルBの1階層下にあるが、セルBの1階層下には位置しないため、セルC、DはセルBを基準とする場合には同位階層ではない。セルゾーンはすべてのレイヤを対象としたものであるため、セルゾーンには当該セルの全てのレイヤのパターンが含まれる。しかし、パターンは共通侵入領域を求めるレイヤのパターンのみ記述しているため、セルゾーンの含まれるパターンの範囲とレイヤに含まれる範囲は必ずしも一致していない。図7~図13はセル間重複パターン検出処理の説明図で、図7~図10はセル間重複領域検出処理の説明図、図11~図13はセル間重複領域を用いて行うセル間重複パターン検出処理の説明図である。セル間重複領域検出処理と、セル間重複パターン抽出処理によってセル間重複パターン検出処理が行われる。また、図14~図17は共通侵入領域検出処理の説明図である。前述したように、前記セル間重複パターン検出処理及び共通侵入領域検出処理を行うことによって共通侵入領域が算出される。以下、図2~図17を用いて、セル間重複パターン検出処理及び共通侵入領域検出処理を含む共通侵入領域算出処理について説明する。共通侵入領域算出処理部205のセル間重複領域検出処理部216及びセル間重複パターン抽出処理部207は、記憶部204からパターンデータ処理の対象であるパターンデータ217を読み込んで、図3のセル間重複パターン検出処理を行う。セル間重複パターン検出処理では、セル間重複領域検出処理部216がセル間重複領域検出処理処理ステップS301~S305、S310を行い、セル間重複パターン抽出処理部207がセル間重複パターン抽出処理処理ステップS306~309、S311を行う。[セル間重複領域検出処理]セル間重複領域検出処理は、セル間重複領域検出処理部216が全セルに対してセル毎に、当該セルのセルゾーンが同位階層の他のセルのセルゾーンと重複するセル間重複領域を検出すると共に、当該セルから直接参照されている全てのセル換言すれば、当該セルが参照している1階層下位の全てのセルのセルゾーンのうち、当該セルのセル間重複領域に含まれる下位セルの領域を下位セルのパターンの展開が必要な領域以下、パターン展開必要領域と称する。として検出するために行う処理である。セル間重複領域に含まれる当該セルと各下位階層セルのパターンは、重複する相手セルに対する侵入パターンであり、これを求めるためには、セル間重複領域に含まれる最下位階層セルまでのパターンを展開する必要がある。これを効率的に行うため、セル間重複領域に含まれる一階層下位のセルのセルゾーンをパターン展開必要領域として検出して下位階層セルに登録し、順次最下位階層まで伝播させる。具体的には、最上位階層セルから最下位階層セルまでの全てのセル換言すればパターンデータ217として使用している全てのセルに対して、最上位階層セルから最下位階層セルへ順に、処理ステップS301~S305、S310の処理を行う。最上位階層セルから最下位階層セルまでの使用している全てのセルまで、当該セルに含まれる一階層下位のセル間のセル間重複領域の検出を行うと共に、当該セルが有するセル間重複領域と当該セルが有するパターン展開必要領域とのOR領域に対して一階層下位のセルのセルゾーンとの間の重複領域を当該下位階層セルのパターン展開必要領域として順次検出する。尚、パターン展開必要領域の分配処理ステップS302を行う前に当該セルのセル間重複領域が求められていればよく、パターン展開必要領域の分配処理ステップS302とセル間重複領域登録処理ステップS304は必ずしも同一セルに対し連続して行う必要は無い。ここで、上下階層間のように直接参照する関係にあるものや、あるいは他の階層を挟んで複数階層にまたがり引用関係にあるもの換言すれば、間接的に参照する関係にあるものは、セル間の重複としては扱わず、パターン展開あるいは後述するパターンの侵入の場合にのみ評価する。i下位階層セルのセルゾーン計算処理ステップステップS301処理ステップS301では、現時点でセル間重複領域作成の対象としているセルが参照している下位階層セルのセルゾーンを計算する。図7iは、最上位階層セルTopの例である。最上位階層セルTopは下位階層として、2つのセルAと1つのセルBを参照している。iiパターン展開必要領域の分配処理ステップS302処理ステップS302では、当該セルのセル間重複領域とパターン展開必要領域のOR領域を下位階層セルに分配する。前記分配処理は、下位階層セルと当該セルの前記OR領域の関係を抽出処理し、下位の各セルと重複するOR領域を下位セルのパターン展開必要領域として順次追加する処理である。図8iは最上位階層セルTopの例である。セルTopは上位階層セルや同位階層セルがないため、同位階層の他のセルとの重複が無く又上位から侵入するパターンも無く、セル間重複領域がない。したがって、セルTopのセル間重複領域に含まれる一階層下のセルA、Bのセル領域セルA、Bのパターン展開必要領域も無い。尚、当該セルのセル間重複領域は、当該セルの上位階層セルについて成された下位階層セルのセル間重複領域登録処理ステップS304によって得られたものを用い、当該セルのパターン展開必要領域は当該セルを直接参照している全てのセル換言すれば、当該セルを参照している1階層上位の全てのセルについてのパターン展開必要領域の分配処理ステップS302によって得られたものを用いる。例えばセルAの場合は、図8iiに示すように、処理ステップS304によって得られたもの図10i参照を用いる。セルAはハッチングで示すセル間重複領域を有しているが、パターン展開必要領域は有していない。セルAのセル間重複領域とセルAのパターン展開領域のOR領域ここでは、セルAはパターン展開必要領域は無い。と、下位階層セルCのセルゾーンとが重複しており、前記重複する領域がセルCのパターン展開必要領域となる。iii下位階層セルの重複領域検出処理ステップS303処理ステップS303では、上位階層セルにおいて、下位階層セルのセルゾーンの重複部分をセル間重複領域として抽出する。図9iのハッチング部分が、前記下位階層セルのセル間重複領域である。iv下位階層セルのセル間重複領域登録処理ステップS304処理ステップS304では、iiiで求めた下位階層セルのセル間重複領域を当該下位階層セルのセル間重複領域として重複相手セルのセル間重複領域と関連付けて追加登録する。相手セル、領域とも同一のものが既に登録されている場合、追加は行わない。図10i。ここで得られたセル間重複領域のデータは、前述したように次の下位階層セルのパターン展開必要領域の分配処理ステップS302で使用されるステップS310。前記処理を最上位階層セルから最下位階層セルまで順に終了するまで繰り返すステップS305。このとき処理するセルの順序は、上位階層セルについての処理が全て終了しているセルを処理対象として選択する。セルAに関して前記処理を行う場合、図7ii、図8ii、図9ii、図10iiの順で処理が行われ、図10iiに示すように、セルC、Dのセル間重複領域とパターン展開必要領域のOR領域が検出される。セルB~Dに関しても同様の処理が行われる。これにより、セル毎にセル間重複領域が検出される。セル間重複領域に存在する当該セルおよび最下位階層に至るまでの下位セルのパターンは、他のいずれかのセルへ侵入するものである。最上位階層セルから最下位階層セルまで全てのセルについて前記セル間重複領域検出処理が完了すると、次のセル間重複パターン抽出処理が行われる。[セル間重複パターン抽出処理]セル間重複パターン抽出処理部207は、セル毎に、前記のようにして検出したセル間重複領域においてセル間で重複するパターンセル間重複パターンを検出するためのセル間重複パターン検出処理を行う。セル間重複パターン検出処理では、全てのセルに対して、最下位階層セルから最上位階層セルへ順序に、処理ステップS306~S309、S311の処理を行う。i評価対象パターン検出処理ステップS306処理ステップS306では、現時点でセル間重複パターン検出処理の対象としているセルのパターンと、当該セルから直接参照されている全てのセル換言すれば、当該セルが参照している1階層下位のセルから展開された展開パターンのOR処理を行い、前記OR処理の結果得られたパターンを当該セルの評価対象パターンとする。評価対象パターンとは、当該セルとその下位階層セルのパターンのうち、当該セルおよび上位階層におけるセル間重複パターンであるか否かの評価の対象となるパターンである。図11iは、現時点のセル間重複パターン検出処理対象のセルが最下位階層セルC、Dの例である。最下位階層セルC、Dは参照点である下位階層セルを有しないため、下位から展開された展開パターン上位階層セル間重複パターンが無く、セル内のパターンのみが対象となる。尚、前記下位階層セルからの展開パターンは、当該セルから直接参照されている全てのセル換言すれば、当該セルが参照している1階層下位の全てのセルに関するパターン展開必要領域のパターン展開処理ステップS307によって得られたものを用いる。例えば、セルAの場合は、図12ii、ステップS307によって得られたものを用いる。以上のようにして、セル内のパターンと、当該セルが参照している1階層下位の全ての階層セルから展開された展開パターンとをOR処理することによって得られるパターンである評価対象パターンが、セル毎に得られる。iiパターン展開必要領域のパターン展開処理ステップS307処理ステップS307では、前記検出した評価対象パターンのうちパターン展開必要領域に存在するもの展開パターンを、当該セルを直接参照している全ての上位セル換言すれば、当該セルを参照している1階層上位の全てのセルにおける当該セルの参照点に展開する。図12iは、セルCからセルAへの展開パターンである。尚、セルAにはパターン展開必要領域が無いため図8参照、図12iiに示すように、セルAからセルTopへの展開パターンは無い。前述したように、ここで得られた展開パターンは、次の上位階層セルの評価対象パターン検出処理ステップS306で使用されるステップS311。ここでは、全ての当該セルの参照点に展開しているが、パターン展開必要領域の分配処理ステップS302において、分配元となった上位セル名と位置をパターン展開必要領域と合わせて登録することで、必要な参照点にのみ展開することも可能である。どちらの手順も処理効率の違いであり、共通侵入領域の算出結果は同一となる。iiiセル間重複パターン登録処理ステップS308処理ステップS308では、前記検出した評価対象パターンのうちセル間重複領域に存在するものを、セル間重複パターンとして重複相手セル名および重複位置に関連付けて記憶部204に記憶する。セルC、Dに関して得られたセル間重複パターンは、図13iのハッチングで示す領域となる。図13に示すように、自セル内のパターンのうち、セル間重複領域と重複するパターン部分が、セル間重複パターンとなる。セル間重複パターンは、同じセル間重複領域を有する他のセルへ侵入するパターンとなる。前記処理を最下位階層セルから最上位階層セルまで順に終了するまで繰り返すステップS309。このときの順序は、当該セルから直接参照されている全ての下位階層セル換言すれば、当該セルが参照している1階層下位のセルについてセル間重複パターン抽出処理が終了しているセルを、セル間重複パターン抽出処理の対象として選択する。セルAに関して前記処理を行う場合、図11ii、図12ii、図13iiとなる。セルAのセル間重複パターンは、図12iiの評価対象パターンとセル間重複領域とが重なる領域であり、図13iiのハッチングを付した領域となる。他のセルに関しても同様の処理が行われる。以上のようにしてセル間重複パターン検出処理が行われることにより、各セル毎に、同じセル間重複領域を有する他のセルへ侵入するセル間重複パターンが得られる。このように、本発明の実施の形態では、先ずセル間重複領域を検出しておき、次に、評価対象パターンのうち前記セル間重複領域に重複するパターンをセル間重複パターンとして求めるようにしているため、はじめから各セル内の全ての領域についてセル間重複パターンを求める方法に比べて、少ないデータ規模で求めることが可能になる。次に、共通侵入領域検出処理部208は、前述した処理によって記憶部204に記憶されたセル間重複パターンのデータを読み込んで、図4の共通侵入領域検出処理を行う。[共通侵入領域検出処理]共通侵入領域検出処理では、最上位階層セルから最下位層セルまでの全てのセルに対して、上位階層セルから下位階層セルへ順に、処理ステップS401~S406を行う。1セル間侵入領域作成処理ステップS401処理ステップS401では、現時点で共通侵入領域検出処理の対象としているセルと同位階層のセルを当該セルの重複相手セルとして、処理ステップS308で関連付けられた全てのセル間重複パターンを、当該セルの対応する位置当該セルと重複相手セルの重なる位置にセル間侵入領域として作成する。セル間侵入領域は、当該セルに関連付けられた他の全ての同位階層セル前記重複相手セルのセル間重複パターンを、当該セルのデータ存在領域内の対応する位置に配置したものである。図14iは最上位階層セルTopの例であり、セルTopには同位階層セルが存在しないため、最上位階層セルTopにはセル間侵入領域は無い。セルA、Bのセル間侵入領域は図14iに示すようになり又、セルC、Dのセル間侵入領域は図14iiのようになる。尚、このステップをここで行うのではなく、処理ステップS308でセル間重複パターンを登録する代わりに、このステップの処理とあわせ、重複相手セルへセル間侵入領域を登録することも同一の結果を得ることができる。2共通侵入領域完成処理ステップS402処理ステップS402では、当該セルを直接参照している全ての上位階層セル換言すれば、当該セルを参照している1階層上位の全てのセルから切り出した侵入領域即ち、1階層上位の全てのセルに含まれるパターンのうち、当該セルのデータ存在領域に重なる領域と前記セル間侵入領域のOR処理を行うことにより、セル毎に共通侵入領域算出処理が完了する。前記OR処理の結果得られる領域が共通侵入領域であり、これを図15に示す。図15iは最上位階層セルTopの例であり、セルTopには上位階層セルが存在しないため、上位階層セルから切り出した侵入領域図形は無く、したがって共通侵入領域は無い。セルAの場合には、最上位階層セルTopのパターン中のセルAと重なる領域が上位階層セルから切り出した侵入領域となり、図15iiのハッチングで示す共通侵入領域が得られる。尚、前記全ての上位階層セル即ち、当該セルを参照している1階層上位の全てのセルから切り出した侵入領域は、上位階層セルの下位階層侵入領域作成処理ステップS404によって得られたものを用いる。3下位階層侵入評価パターン作成処理ステップS403処理ステップS403では、当該セルの共通侵入領域と、前記共通侵入領域検出処理対象セルの対象レイヤのパターン下位階層のパターンは含まないとのOR処理を行うことにより、下位階層に対する侵入評価パターン下位階層侵入評価パターンを作成する。下位階層侵入評価パターンとは、上位階層セルから下位階層セルのデータ存在領域内に侵入するか否かの判定対象となるパターンである。図16iは最上位階層セルTopの例であり、最上位階層セルTopには上位階層セルが存在しないため、前記共通侵入領域は無く、したがって下位階層侵入評価パターンはセルTopの対象レイヤのパターンハッチング領域のみとなる。セルAの下位階層侵入評価パターンは図16iiのハッチング領域となる。4分配処理ステップS404処理ステップS404では、前記下位階層侵入評価パターンを参照点毎に下位階層のセルに分配する図17i。前記分配処理は、参照セルゾーンと下位階層侵入評価パターンの重なり領域を抽出処理し、抽出した領域を対応するセルに付与する処理である。前記分配された領域は図14に示したセル間侵入領域に追加処理されて図17i、図15の共通侵入領域が得られる。図17iでは、セルA、Bの侵入領域及び分配された下位階層侵入評価パターンにハッチングが付されており、これらが図15の共通侵入領域となる。このように、当該セルの共通侵入領域と当該セルのパターンとのOR処理の結果を下位階層セルに分配することで、下位セルにおける上位セルからの侵入領域を算出する。前述したように、ここで得られた侵入領域のデータは、下位階層セルの共通侵入領域の完成処理ステップS402で使用される。前記処理を最上位階層セルから最下位階層セルまで順に終了するまで繰り返すステップS405。このときの順序は、全ての上位階層セルの処理が終了したセルを対象として選択する。このときの順序は、その全ての上位階層セルについて共通侵入領域検出処理が終了しているセルを、共通侵入領域検出処理の対象として選択する。セルAに関して前記処理を行う場合、図14ii、図15ii、図16ii、図17iiとなる。セルC、Dの場合、共通侵入領域は、図17iiのハッチングを付した領域となる。他のセルに関しても同様の処理が行われ、共通侵入領域が得られる。共通侵入領域は、セル領域内で外部パターンが重複する可能性のある領域である。ここでは、セル間侵入領域ステップS401と上位セルパターンによる侵入領域ステップS404を別に求めているが、セルパターンと共通侵入領域の重複部分をドントケアとする場合、他の手順も可能である。たとえば、パターン展開必要領域とともにセル間重複領域に存在するパターンを上位階層セルに展開し、上位セルパターンによる侵入領域ステップS404にて一括して共通侵入領域を求めることができる。この場合も、共通侵入領域の計算方法が異なるが、セル間重複領域を求め、これをもとにセル間重複パターンを求めていることは同様である。次に、前述のようにして算出した共通侵入領域を用いて、パターンデータ217に対する所定の処理を行う例について説明する。パターンデータ217に対する処理としては、パターンデータ217の形状や配置が正しいか否かの検証処理やパターンデータ217の変更処理等がある。また、パターンデータ処理には、AND処理、OR処理等の論理演算処理、セルが有するパターンの寸法を変更するサイジング処理、スペースやパターンの寸法チェック処理、対象選択処理等、種々の処理がある。以下に、パターンデータ処理の具体例を説明する。図18は、パターンデータ処理部201の図形処理部206がパターンデータ処理としてAND処理を行う場合のフローチャートである。図19は、パターンデータ217を構成するセルデータ211の中の、下位階層セルXの構成を示す図である。セルXは複数のレイヤ本実施の形態では第1レイヤ及び第2レイヤを有するセルで、第1レイヤにパターン301を有し、第2レイヤにパターン302を有している。図20は、パターンデータとしての最上位階層セルTopの構成を示す図である。セルTopは、2つのセルXを参照セルとして有すると共に、第1レイヤにパターン303、304を有し又、第2レイヤにパターン305、306を有している。図21~図24は、パターンデータに対するAND処理の説明図であり、セルTopにおける第1レイヤの全パターンと第2レイヤの全パターンとのAND処理を行う動作の説明図である。以下、図2、図18~図24を用いて本実施の形態におけるパターンデータ処理の例として、異なるレイヤに存在するパターン同士のAND処理について説明する。共通侵入領域算出処理部208は、各階層セル毎に全ての参照点即ち、最上位階層セルTopに至るまでの全ての上位階層セルの中で当該セルを参照している箇所における外部パターンの侵入部分をレイヤ毎に求め、前記各レイヤ毎の侵入部分のOR領域を、各レイヤの共通侵入領域として当該セルに関連付けて記憶部204に格納する図18のステップS501。これにより、共通侵入領域として、図21に示すように、第1レイヤの共通侵入領域401及び第2レイヤの共通侵入領域402が得られる。この共通侵入領域401、402は全ての演算で共通に使用できるものであり、レイヤ毎に一度だけ求める。次に、影響範囲算出処理部214は、共通侵入領域401、402に基づいて、パターンデータ処理の内容ここではAND処理に応じて影響範囲を算出する。一般に、2つのレイヤを入力する処理では、第1レイヤの共通侵入領域による影響第1レイヤの影響と第2レイヤの共通侵入領域による影響第2レイヤの影響は内容が異なる。同様に、境界パターンについても、それぞれのレイヤの影響範囲によりそれぞれに入力レイヤに対する効果が異なる。このため、以下の4種を考慮する必要がある。第1レイヤの影響範囲による第1レイヤ境界パターン第1レイヤの影響範囲による第2レイヤ境界パターン第2レイヤの影響範囲による第1レイヤ境界パターン第2レイヤの影響範囲による第2レイヤ境界パターンパターンデータ処理がAND処理の場合は、演算自体が距離に依存せずパターンの重複関係のみでパターンデータ処理結果が決定される。また、セル内パターンと外部パターンの同じレイヤの重複部分はセル内の処理結果が使用可能であり、他階層の処理結果は考慮不要ドントケアDontCareとなる。このことから、各レイヤの影響範囲は第1レイヤの影響範囲は、第1レイヤの共通侵入領域から第1レイヤのセル内パターンを除いた領域第2レイヤの影響範囲は、第2レイヤの共通侵入領域から第2レイヤのセル内パターンを除いた領域となる。また、階層間にまたがって考慮が必要なケースは、セルのパターンと外部パターンので異なるレイヤのパターンが重複する部分のみであることから、AND処理の境界図形は、第1レイヤの影響範囲による第1レイヤ境界図形および第2レイヤの影響範囲による第2レイヤ境界図形は不要第1レイヤの影響範囲による第2レイヤ境界図形は、第1レイヤの影響範囲内に存在する、第2レイヤのセル内パターン第2レイヤの影響範囲による第1レイヤ境界図形は、第2レイヤの影響範囲内に存在する、第1レイヤのセル内パターンである。したがって、図形処理部206の影響範囲算出処理部214は、共通侵入領域401、402から、共通侵入領域401、402と同一レイヤのセル内パターンとの重複領域を除いた領域を、演算処理で使用する影響範囲として算出するステップS502。前記影響範囲は図22に示すように、第1レイヤの影響範囲307、第2レイヤの影響範囲308となる。共通データ領域算出処理部215は、セルのデータ存在領域から前記影響範囲を除いた領域を共通データ領域として算出し、当該セルに関連付けて記憶部204に格納するステップS503。ただし、AND処理の場合、第1レイヤの影響範囲、第2レイヤの影響範囲とも一方のレイヤのパターンしか存在せず、処理結果のパターンは存在しないため、前記影響範囲の削除は不要である。次に、共通データ領域処理部209は、記憶部204に記憶した前記セルの共通データ領域に対してAND処理を行う。この場合、共通データ領域処理部209は前記AND処理を当該セル単体で行い、当該セルの共通データ領域に対するパターンデータ処理結果として当該セルに関連付けて記憶部204に格納する。共通データ領域処理部209は、図23に示すように、下位階層セルXについて単独で、第1レイヤと第2レイヤのAND処理を行うことにより、共通データ領域に対するAND処理結果として、AND領域309が得られる。次に、上位階層の演算に影響するセル内パターンを抽出するため、影響範囲処理部210は、図24に示すように、第1レイヤのセル内パターン301と第2レイヤの影響範囲308との重複部分、第2レイヤのセル内パターン302と第1レイヤの影響範囲307との重複部分を各々第1レイヤ境界パターン310、第2レイヤ境界パターン311として算出し、全参照点に展開するステップS504。境界パターンは、セル内パターンのうち外部パターンと一緒に処理する必要のあるパターンであり、AND処理では影響範囲にある異なるレイヤのセル内パターンである。単なるAND処理に比べると手順は複雑となるが、演算対象データ量はセル単位であり非常に少なくなるため、全体としては演算処理時間の短縮が可能となる。影響範囲処理部210は、図25iに示すように、当該セルから直接参照されている全ての下位階層セル換言すれば、当該セルが参照している全ての1階層下位のセルから展開した境界パターンと上位階層セルのパターンを相互にマージし、図25iiに示すように上位階層セルの第1レイヤと第2レイヤのAND処理を実行するステップS505。これにより、領域601、602が得られる。図形処理部206は、図25iiに示すように、共通データ領域処理部209がAND処理を行うことによって算出した領域309と、影響範囲処理部210がAND処理を行うことによって算出した領域601、602との和を、パターンデータ処理の結果として算出する。図形処理部206は、前記パターンデータ処理の結果を記憶部204に記憶するステップS506。これにより、フラット処理と同じ演算結果を得ることができる。次に、パターンデータ処理としてSUB処理の例を、前記AND処理の例で使用したパターンデータを用いて説明する。SUB処理に特有の処理を図26~図29に示している。SUB処理も、前記AND処理と同様に、図2のパターンデータ処理装置200を用いて行われる。使用するパターンデータは、前述したAND処理で用いたものと同じため、共通侵入領域は前記AND処理のものと同じであり、共通侵入領域401、402である。SUB処理は、処理自体が距離に依存せずパターンの重複関係のみで結果が決定されることはAND処理と同様である。しかしながら、SUB処理は、セル内パターンと外部パターンの重複に関しては、第1レイヤから第2レイヤを除く演算であるため、2つのレイヤで扱いがAND処理の場合とは異なることになる。即ち、セル内の第2レイヤのパターンは、上位階層セルの第2レイヤのパターンが重複していても結果は変わらないが、第1レイヤのパターンが重複する場合、第2レイヤで削除するのはセル内のパターンだけではなく、上位のパターンも削除する必要がある。つまりセル内の第1レイヤの有無に拘わらず全てのセル外部の第1レイヤと重複する領域は一度のみの共通の処理とすることができず、個別処理が必要になる。このことから、SUB処理における各レイヤの影響範囲は第1レイヤの影響範囲は、第1レイヤの共通侵入領域全体第2レイヤの影響範囲は、第2レイヤの共通侵入領域から第2レイヤのセル内パターンを除いた領域となる。また、階層間にまたがって考慮が必要なケースは、各レイヤの影響範囲と異なるレイヤのパターンが重複する部分であることから、SUB処理の境界図形は、第1レイヤの影響範囲による第1レイヤ境界図形および第2レイヤの影響範囲による第2レイヤ境界図形は不要第1レイヤの影響範囲による第2レイヤ境界図形は、第1レイヤの影響範囲内に存在する、第2レイヤのセル内パターン第2レイヤの影響範囲による第1レイヤ境界図形は、第2レイヤの影響範囲内に存在する、第1レイヤのセル内パターンである。したがって、図形処理部206の影響範囲算出処理部214は、第1レイヤの共通侵入領域401全体と同一の領域と、第2レイヤの共通侵入領域402から第2レイヤのセル内パターンと重複する領域を除いた領域とを、パターンデータ処理で使用する影響範囲として算出する図18の処理ステップS502及び図21参照。その結果、図26に示すように、第1レイヤの共通侵入領域401全体と同一の領域として、第1レイヤの影響範囲312が得られる同図i。また、第2レイヤの共通侵入領域402から第2レイヤのセル内パターンと重複する領域を除いた領域として、第2レイヤの影響範囲313が得られる同図ii。SUB処理の場合、第1レイヤの影響範囲は、セル内のパターンに影響しないため共通データ領域に対して考慮不要ドントケアDontcareである。また、第2レイヤの影響範囲は、セル内パターンが削除される可能性がある領域に相当するため、共通データ領域から除く必要がある。共通データ領域算出処理部215は、セルのデータ存在領域から前記第2レイヤの影響範囲を除いた領域を共通データ領域として算出し、当該セルに関連付けて記憶部204に格納するステップS503。次に共通データ領域処理部209は、記憶部204に記憶した前記セルの共通データ領域に対してSUB処理を行う。この場合、共通データ領域処理部209は、セル内の共通データ領域の演算はセル単体で一度のみ演算を行い、共通データに関するセルの処理結果として各セルデータ211に関連付けて記憶部204に格納する。このため、セル内の演算処理共通データ領域についてのSUB処理は、図27に示すように下位階層セルXについて単独で、第1レイヤと第2レイヤのSUB処理を行い、さらに共通データ領域とAND処理することにより、SUB領域314が得られる。上位階層セルの処理に影響するセル内パターンを抽出するため、影響範囲処理部210は、図28に示すように、第1レイヤのセル内パターン301と第2レイヤの影響範囲313との重複部分及び第2レイヤのセル内パターン302と第1レイヤの影響範囲312との重複部分を、各々第1レイヤ境界パターン315、第2レイヤ境界パターン316として算出し、全参照点に展開するステップS504。次に影響範囲処理部210は、図29iに示すように当該セルから直接参照されている全ての下位階層セル換言すれば、当該セルが参照している全ての1階層下位のセルから展開した境界パターンと上位階層セルのパターンを相互にマージし、図29iiに示すように上位階層セルの第1レイヤと第2レイヤのSUB処理を実行するステップS504。これにより、領域317、318が得られる。図形処理部206は、図29iiに示すように、共通データ領域処理部209が算出した領域314と影響範囲処理部210が算出した領域317、318の和を、パターンデータ処理の結果として算出する。図形処理部206は、前記パターンデータ処理の結果を記憶部204に記憶するステップS506。これにより、フラット処理と同じ演算結果を得ることができる。他のパターンデータ処理の例としてOR処理の場合は、階層間で影響を及ぼさないため影響範囲はなく、各階層毎に独立にOR処理を行えばよい。その他のパターンデータ処理も演算処理の内容や演算実現手順は異なるが、1共通侵入領域を用いて、これにより結果が変化する範囲を影響範囲として入力レイヤごとに求め、2セル内の演算を行うと共に影響範囲内で結果が不正となる可能性があるパターンを削除し、3影響範囲に対する各参照点における個別処理に必要な境界パターンを作成して、上位階層の演算を順次実行することにより、所定の階層的演算処理が実現できる。ここで、1~3の実現手段は、これまでに例示したようにパターンデータ処理の内容により異なるが、いずれも共通侵入領域に基づいて決定可能である。以上述べたように、本発明の実施の形態に係るパターンデータ処理方法は、階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を行うパターンデータ処理方法において、セル毎に外部から当該セルに侵入する外部パターンを検出し、前記外部パターンが当該セルに侵入する領域を共通侵入領域として当該セルに関連付ける共通侵入領域算出ステップと、セルに関連付けられた前記共通侵入領域に基づいて、前記所定の処理の内容に応じて、当該セルの中で前記外部パターンとともに前記所定の処理を行う必要のある領域を当該セルの影響範囲として算出する影響範囲算出ステップと、セルのデータ存在領域から当該セルの影響範囲を除外した領域を当該セルの共通データ領域として算出する共通データ領域算出ステップと、前記各セルの共通データ領域については前記所定の処理を一度行うと共に前記影響範囲については当該セルに侵入する前記外部パターンとともに前記所定の処理を行うことにより、前記パターンデータに対する前記所定の処理を行うパターンデータ処理ステップとを備えて成ることを特徴としている。ここで、前記共通侵入領域算出ステップは、セルが同位階層の他のセルと重複する領域であるセル間重複領域を検出するセル間重複領域検出ステップと、各セルのパターンと各セルの最下位階層セルに至るまでの全ての下位階層セルのパターンの内、当該セルのセル間重複領域に重複するパターンであるセル間重複パターンを抽出するセル間重複パターン抽出ステップと、各セルに重複する同位階層の他のセルのセル間重複パターンと、当該セルの最上位階層に至るまでの全ての上位階層のセルのパターンのうち当該セルのデータ存在領域に重複するパターンとから成る前記共通侵入領域を算出する共通侵入領域検出ステップとを備えて成るように構成してもよい。また、前記セル間重複領域検出ステップは、各セルと同位階層セルとの間の重複領域をセル間重複領域として検出する処理と、最上位階層セルから最下位階層セルまで順に各セルのセル間重複領域と上位階層の処理で検出した当該セルのパターン展開必要領域のOR領域の内、一階層下位のセルのデータ存在領域と重複する領域を下位階層のセルのパターン展開必要領域として検出する処理であり、前記セル間重複パターン抽出ステップは、最下位階層セルから最上位階層セルまで順に、各セルのパターンと下位階層から展開された評価対象パターンを合わせたパターンを当該セルの評価対象パターンとし、当該セルのセル間重複領域に重複する評価対象パターンを当該セルのセル間重複パターンとして抽出すると共に、前記当該セルのパターン展開必要領域に存在する当該セルの評価対象パターンを上位階層に展開する処理であり、前記共通侵入領域検出ステップは、最上位階層セルから最下位階層セルまで順に、各セルに重複する同位階層のセルのセル間重複パターンと、当該セルに重複する一階層上位のセルのパターンと、当該セルに重複する一階層上位のセルの共通侵入領域とから成る前記共通侵入領域を算出する処理であるように構成してもよい。前記影響範囲算出ステップは、セルに関連付けられた前記共通侵入領域に基づいて、前記所定の処理の内容に応じて、当該セルのデータ存在領域の中で、当該セル単独で前記所定の処理を行うと前記外部パターンの影響を受けて誤った結果が得られるため前記外部パターンとともに前記所定の処理を行う必要のある領域を当該セルの影響範囲として算出する処理である。本発明の実施の形態に係るパターンデータ処理方法は、前記のように構成されているため、厳しい設計制約を設けることなく、階層化された複数のセルを有するパターンデータに対して論理演算処理等の所定の処理を効率的に行うことができる。また、レイアウト設計においては、階層間のパターン制約を考慮する必要がなく、従来と同じ設計条件のみを考慮しての設計が可能となるため、制約増加によるレイアウト面積の増加や設計工数、期間の増大が防止できる。パターンデータ処理においては、実際には重複がなくとも階層間のパターン制約によって展開されるパターン量より、実際階層間の重複による影響範囲のみのパターン量の方が一般に少なくできる。処理時間は、ほぼこの展開パターン量に依存するため、共通侵入領域作成にかかる時間以上に処理時間は短縮が可能となる。また、LSIやFPD等のためのレイアウトパターン設計にあたり、設計ルールを満たしていることの検証は、論理演算、サイジング、寸法チェック、対象選択処理などを組み合わせることで実現している。また、製造工程に受け渡すデータの作成も、同様にこれらの処理を組み合わせることで実現する。このような図形処理を、高速に実施するための階層処理の実現に用いることが可能である。また、本発明の実施の形態に係るパターンデータ処理装置200は、階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を行うパターンデータ処理装置において、各セル毎に外部から当該セルに侵入する外部パターンを検出し、前記外部パターンが当該セルに侵入する領域を共通侵入領域として当該セルに関連付ける共通侵入領域算出処理部205と、セルに関連付けられた前記共通侵入領域に基づいて、前記所定の処理の内容に応じて、当該セルの中で前記外部パターンとともに前記所定の処理を行う必要のある領域を当該セルの影響範囲として算出する影響範囲算出処理部214と、セルのデータ存在領域から当該セルの影響範囲を除外した領域を当該セルの共通データ領域として算出する共通データ領域算出処理部215と、前記各セルの共通データ領域については前記所定の処理を一度行うと共に前記影響範囲については当該セルに侵入する前記外部パターンとともに前記所定の処理を行うことにより、前記パターンデータに対する前記所定の処理を行うパターンデータ処理手段とを備えて成ることを特徴としている。ここで、共通侵入領域算出処理部205は、セルが同位階層の他のセルと重複する領域であるセル間重複領域を検出するセル間重複領域検出処理部216と、各セルのパターンと各セルの最下位階層に至るまでの全ての下位階層セルのパターンの内、当該セルのセル間重複領域に重複するパターンであるセル間重複パターンを抽出するセル間重複パターン抽出処理部207と、各セルに重複する同位階層の他のセルのセル間重複パターンと、当該セルの最上位階層に至るまでの全ての上位階層のセルのパターンのうち当該セルのデータ存在領域に重複するパターンとから成る前記共通侵入領域を算出する共通侵入領域検出処理部208とを備えて成るように構成することができる。セル間重複領域検出処理部216は、各セルと同位階層セルとの間の重複領域をセル間重複領域として検出すると共に、最上位階層セルから最下位階層セルまで順に各セルのセル間重複領域と上位階層の処理で検出した当該セルのパターン展開必要領域のOR領域の内、一階層下位のセルのデータ存在領域と重複する領域を下位階層のセルのパターン展開必要領域として検出し、セル間重複パターン抽出処理部207は、最下位階層セルから最上位階層セルまで順に、各セルのパターンと下位階層から展開された評価対象パターンを合わせたパターンを当該セルの評価対象パターンとし、当該セルのセル間重複領域に重複する評価対象パターンを当該セルのセル間重複パターンとして抽出すると共に、前記当該セルのパターン展開必要領域に存在する当該セルの評価対象パターンを上位階層に展開し、共通侵入領域検出処理部208は、最上位階層セルから最下位階層セルまで順に、各セルに重複する同位階層のセルのセル間重複パターンと、当該セルに重複する一階層上位のセルのパターンと、当該セルに重複する一階層上位のセルの共通侵入領域とから成る前記共通侵入領域を算出するように構成することができる。本発明の実施の形態に係るパターンデータ処理装置200は、前記のように構成されているため、厳しい設計制約を設けることなく、階層化された複数のセルを有するパターンデータに対して論理演算処理等の所定の処理を効率的に行うことができる等の効果を奏する。また、本発明の実施の形態によれば、コンピュータに階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を実行させるためのパターンデータ処理用プログラムにおいて、コンピュータに前述したパターンデータ処理方法を実行させることを特徴とするパターンデータ処理用プログラムが提供される。コンピュータは本実施の形態に係るパターンデータ処理用プログラムを実行することにより、階層化された複数のセルを有するパターンデータに対して、予め定めた所定の処理を実行させることができる。また、本発明の実施の形態に係るパターンデータ処理用プログラムをコンピュータに実行させることにより、パターンデータ処理装置200を構築することが可能になる。また、本発明の実施の形態によれば、コンピュータに前述したパターンデータ処理方法を実行させるためのパターンデータ処理用プログラムを記録したコンピュータ読み取り可能な記録媒体が提供できる。尚、本発明の実施の形態は種々の変更が可能である。例えば、本発明の実施の形態では、パターンデータ処理の例としてLSIの例で説明したが、FPDのパターンデータをはじめとして、階層化された複数のセルを有するパターンデータに所定の処理を行う場合に適用可能である。