(57)【特許請求の範囲】
【請求項１】
ＸＹ二次元座標系に定義された複数の図形についての図形演算を行う演算装置であって、
図形データファイルとして与えられた演算対象となる個々の図形データを、二辺がＸ軸に平行な台形の図形データに変換し、変換した図形データに、同一の台形を所定ピッチＰでＸ軸方向に複数ｎ個並べて配置した状態を示すデータが含まれていた場合には、この複数ｎ個の図形データを、代表となる１つの台形を示す図形データと、ピッチＰおよび個数ｎを示すデータと、によって構成される単一の圧縮図形データに置換する圧縮処理を行うことにより、圧縮台形形式の演算対象図形データファイルを作成するデータ圧縮部と、
前記圧縮台形形式の演算対象図形データファイル内の図形データを１つずつ抽出するデータ抽出部と、
このデータ抽出部から抽出された図形データを一時的に保持し、図形相互の演算を実行する演算部と、
前記演算部内の演算済みの図形データを排出して、圧縮台形形式の演算結果図形データファイルを作成するデータ排出部と、
前記圧縮台形形式の演算結果図形データファイルに含まれる圧縮図形データに対して、代表となる台形を複数ｎ個分だけピッチＰでＸ軸方向に並べた状態を示す複数の非圧縮図形データに置換する展開処理を施し、非圧縮図形データからなる演算結果図形データファイルを作成するデータ展開部と、
を備え、前記演算部は、抽出された図形データが非圧縮図形データの場合には、その図形をＸ軸上へ投影することによって得られるＸ軸投影像と、その図形をＹ軸上へ投影することによって得られるＹ軸投影像と、を求める機能を有し、抽出された図形データが圧縮図形データの場合には、展開処理によって得られる複数の図形の最小外接矩形をＸ軸上へ投影することによって得られるＸ軸投影像と、この最小外接矩形をＹ軸上へ投影することによって得られるＹ軸投影像と、を求める機能を有し、
前記データ抽出部によって１つの図形データが抽出されると、前記演算部は、この抽出された図形データと過去に抽出された図形データとの干渉の可能性を、それぞれの図形データについてのＸ軸投影像およびＹ軸投影像に基づいて判断する予備判断処理を行い、この予備判断処理において干渉の可能性有りと判断された場合には、圧縮図形データについては展開処理を施した上で、両図形データの干渉の有無を判断する本判断処理を行い、この本判断処理において干渉有りと判断された図形データについて所定の図形演算を実行する機能を有し、
前記データ抽出部は、圧縮台形形式の演算対象図形データファイル内の図形データを、台形の底辺のＹ座標値に基づいてソートし、ソート順に図形データを１つずつ抽出し、
前記データ抽出部によって１つの図形データが抽出されたら、前記演算部は、
(a)   抽出図形データについてＸ軸投影像を求め、このＸ軸投影像と、前記演算部に一時保持されている過去に抽出された図形データのＸ軸投影像との干渉の有無を判断するＸ軸に関する予備判断処理と、
(b)   抽出図形データについてＹ軸投影像を求め、このＹ軸投影像と、前記演算部に一時保持されている過去に抽出された図形データのＹ軸投影像との干渉の有無を判断するＹ軸に関する予備判断処理と、
(c)  (b) の予備判断処理で、抽出図形データに対して干渉無しと判断された図形データを、演算済みの図形データとして排出する処理と、
(d)  (a) および(b) の双方の予備判断処理で、抽出図形データに対して干渉有りと判断された図形データについて、圧縮図形データについては展開処理を施した上で、両図形データの二次元平面上での干渉の有無を判断する本判断処理と、
(e)  (d) の本判断処理で、抽出図形データに対して干渉有りと判断された図形データについて、所定の図形演算を実行する演算処理と、
を実行し、すべての抽出図形データについての処理が完了したときに、保持しているすべての図形データを演算済みの図形データとして排出する機能を有することを特徴とする図形演算装置。
【請求項２】
請求項１に記載の図形演算装置において、
(a) の予備判断処理において抽出図形データに対して干渉有りと判断された図形データに対してのみ、選択的に(b) の予備判断処理を実行するようにしたことを特徴とする図形演算装置。
【請求項３】
請求項１または２に記載の図形演算装置において、
演算部で求めたＸ軸投影像もしくはＹ軸投影像を登録する投影データ管理部を更に設け、演算部に一時保持されている過去の抽出図形データについてのＸ軸投影像もしくはＹ軸投影像を、前記投影データ管理部に登録することにより一時記憶することを特徴とする図形演算装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は図形演算装置に関し、特に、半導体集積回路のマスクパターンを構成する多数の図形についての論理演算を行う装置に関する。
【０００２】
【従来の技術】
半導体集積回路のレイアウト設計作業では、マスクパターンを構成する多数の図形間の論理演算処理が行われる。たとえば、レイアウトを検証する作業や、電子線描画装置用の図形データを作成する作業などでは、平面上で互いに重なり合う図形間における論理和演算（ＯＲ演算）や論理積演算（ＡＮＤ演算）などが行われる。このような図形演算処理は、基本的には、１つ１つの図形について、平面上で重なる他の図形があるか否かを調べ、他の図形と重なる場合には、両者について所定の演算処理を施して新たに別な図形を発生させる、という作業を、コンピュータを用いて繰り返し実行する処理となる。
【０００３】
【発明が解決しようとする課題】
半導体集積回路の集積度は年々向上してきており、マスクパターンを構成する図形の数も非常に膨大なものになってきている。たとえば、ＤＲＡＭに代表される超ＬＳＩのマスクパターンや遮光体パターンを生成するプロセスでは、１０億個を超える図形どうしの演算が必要になり、高機能のコンピュータを用いたとしても、膨大な演算時間を費やしているのが現状である。また、図形データのデータ量も膨大なものになり、演算に用いるコンピュータの内部メモリや外部記憶装置も、かなりの容量のものを確保しておかねばならない。
【０００４】
そこで本発明は、記憶容量のより小さなコンピュータを用いて、より短時間に演算処理を実行することができる図形演算装置を提供することを目的とする。
【０００５】
【課題を解決するための手段】
(1)   本発明の第１の態様は、ＸＹ二次元座標系に定義された複数の図形についての図形演算を行う演算装置において、
図形データファイルとして与えられた演算対象となる個々の図形データを、二辺がＸ軸に平行な台形の図形データに変換し、変換した図形データに、同一の台形を所定ピッチＰでＸ軸方向に複数ｎ個並べて配置した状態を示すデータが含まれていた場合には、この複数ｎ個の図形データを、代表となる１つの台形を示す図形データと、ピッチＰおよび個数ｎを示すデータと、によって構成される単一の圧縮図形データに置換する圧縮処理を行うことにより、圧縮台形形式の演算対象図形データファイルを作成するデータ圧縮部と、
圧縮台形形式の演算対象図形データファイル内の図形データを１つずつ抽出するデータ抽出部と、
このデータ抽出部から抽出された図形データを一時的に保持し、図形相互の演算を実行する演算部と、
演算部内の演算済みの図形データを排出して、圧縮台形形式の演算結果図形データファイルを作成するデータ排出部と、
圧縮台形形式の演算結果図形データファイルに含まれる圧縮図形データに対して、代表となる台形を複数ｎ個分だけピッチＰでＸ軸方向に並べた状態を示す複数の非圧縮図形データに置換する展開処理を施し、非圧縮図形データからなる演算結果図形データファイルを作成するデータ展開部と、
を設け、演算部が、抽出された図形データが非圧縮図形データの場合には、その図形をＸ軸上へ投影することによって得られるＸ軸投影像と、その図形をＹ軸上へ投影することによって得られるＹ軸投影像と、を求める機能を有し、抽出された図形データが圧縮図形データの場合には、展開処理によって得られる複数の図形の最小外接矩形をＸ軸上へ投影することによって得られるＸ軸投影像と、この最小外接矩形をＹ軸上へ投影することによって得られるＹ軸投影像と、を求める機能を有し、
データ抽出部によって１つの図形データが抽出されると、演算部が、この抽出された図形データと過去に抽出された図形データとの干渉の可能性を、それぞれの図形データについてのＸ軸投影像およびＹ軸投影像に基づいて判断する予備判断処理を行い、この予備判断処理において干渉の可能性有りと判断された場合には、圧縮図形データについては展開処理を施した上で、両図形データの干渉の有無を判断する本判断処理を行い、この本判断処理において干渉有りと判断された図形データについて所定の図形演算を実行するようにし、
データ抽出部は、圧縮台形形式の演算対象図形データファイル内の図形データを、台形の底辺のＹ座標値に基づいてソートし、ソート順に図形データを１つずつ抽出するようにし、
データ抽出部によって１つの図形データが抽出されたら、演算部が、
(a)   抽出図形データについてＸ軸投影像を求め、このＸ軸投影像と、演算部に一時保持されている過去に抽出された図形データのＸ軸投影像との干渉の有無を判断するＸ軸に関する予備判断処理と、
(b)   抽出図形データについてＹ軸投影像を求め、このＹ軸投影像と、演算部に一時保持されている過去に抽出された図形データのＹ軸投影像との干渉の有無を判断するＹ軸に関する予備判断処理と、
(c)  (b) の予備判断処理で、抽出図形データに対して干渉無しと判断された図形データを、演算済みの図形データとして排出する処理と、
(d)  (a) および(b) の双方の予備判断処理で、抽出図形データに対して干渉有りと判断された図形データについて、圧縮図形データについては展開処理を施した上で、両図形データの二次元平面上での干渉の有無を判断する本判断処理と、
(e)  (d) の本判断処理で、抽出図形データに対して干渉有りと判断された図形データについて、所定の図形演算を実行する演算処理と、
を実行し、すべての抽出図形データについての処理が完了したときに、保持しているすべての図形データを演算済みの図形データとして排出するようにしたものである。
【０００７】
(2)   本発明の第２の態様は、上述の第１の態様に係る図形演算装置において、
(a) の予備判断処理において抽出図形データに対して干渉有りと判断された図形データに対してのみ、選択的に(b) の予備判断処理を実行するようにしたものである。
【０００８】
(3)   本発明の第３の態様は、上述の第１または第２の態様に係る図形演算装置において、
演算部で求めたＸ軸投影像もしくはＹ軸投影像を登録する投影データ管理部を更に設け、演算部に一時保持されている過去の抽出図形データについてのＸ軸投影像もしくはＹ軸投影像を、この投影データ管理部に登録することにより一時記憶するようにしたものである。
【０００９】
【発明の実施の形態】
以下、本発明を図示する実施形態に基づいて説明する。
【００１０】
§１．  圧縮台形形式の図形データ
本発明の基本概念は、個々の図形を圧縮台形形式で表現し、この圧縮台形形式のデータに対して、図形演算処理を実行する点にある。ＤＲＡＭなどの半導体集積回路では、同一の素子が所定方向に規則正しく配列されていることが多い。このような集積回路のマスクパターンでは、形状および大きさの全く同じ図形が、一方向に一定のピッチで多数配列されることになる。最近のＤＲＡＭのマスクパターンには、１０億個以上の図形が含まれているが、実際には、これらの図形の大部分は、同一の図形を一定ピッチで配列した図形群から構成されており、個々の図形は所定の規則性をもって配置されている。従来は、このような規則性を考慮せずに、個々の図形すべてに対してそれぞれ個別の図形演算を行っていたため、膨大な図形データに対して類似した演算処理を繰り返し実行する必要があった。本発明では、個々の図形を、二辺がＸ軸に平行な台形の集合として表現し、かつ、規則性をもって配置されている台形については、これを圧縮形式の図形データで表現することにより全データ量を低減させている。このため、図形演算で取り扱うべきデータの全容量は、従来に比べて著しく減少する。しかも、個々の図形が干渉するか否か（二次元平面上において重なりを生じるか否か）を判断する作業は、圧縮図形データのままで判断を行う予備判断処理と、圧縮図形データを展開して非圧縮図形データの形で判断を行う本判断処理との二段階の処理で行うようにしたため、無駄な演算を省くことができ、演算時間も著しく短縮される。
【００１１】
本発明に係る図形演算装置は、演算対象となる複数の図形に関するデータを入力し、これら図形に対して所定の論理演算を施して新たな図形を発生させ、この新たな図形を示すデータを演算結果として出力する機能を有する。たとえば、図１に示すような４つの図形１１〜１４についての図形データを入力し、論理和演算（ＯＲ演算）を行えば、図２に示すような新たな図形１５を示す図形データが生成され、論理積演算（ＡＮＤ演算）を行えば、図３に示すような新たな図形１６〜１８を示す図形データが生成される。本発明の特徴は、このような図形演算を圧縮台形形式の図形データを用いて行う点にある。
【００１２】
図形データを台形形式で表現する手法は、従来からも利用されている。たとえば、電子線描画装置に与えるデータとしては、通常、台形形式の図形データが用いられている。ここで説明する実施形態では、演算対象となる個々の図形を、ＸＹ二次元座標系において二辺がＸ軸に平行な台形（本明細書では、少なくとも二辺が平行な四角形を台形と呼んでおり、長方形および正方形も台形に含まれる）の集合として表現することにより、台形形式の表現を行っている。たとえば、図４(a) に示すような図形２０がＸＹ座標系に定義されていた場合、図４(b) に示すように、この図形２０を４つの図形２１〜２４に分割して取り扱うことになる。図形２１〜２４は、いずれも上辺と底辺とがＸ軸に平行な台形である。
【００１３】
一方、台形形式で表現された図形データを圧縮して表現する手法も、従来から利用されている。たとえば、図５に示すような８個の図形３１〜３８からなるパターンを考える。このパターンは、一対の図形３１，３２を代表図形と考えれば、４個の代表図形を所定のピッチＰでＸ軸に沿って配置してなるパターンである。したがって、８個の図形すべてについての図形データを用意する代わりに、図６に示すように、実線で示す代表図形３１，３２についての図形データと、ピッチＰと繰り返し配置数４というデータを用いても表現することが可能である。図６に破線で示す図形については、実データは用意されていないが、代表図形３１，３２についての図形データ、ピッチＰ、繰り返し配置数４、という情報に基づいて、必要に応じて実データを生成することが可能である。このようにして、複数の図形データを単一の図形データで表現する手法は、一般に「図形データの圧縮」と呼ばれており、ここでは、圧縮前の図形データを非圧縮図形データ、圧縮後の図形データを圧縮図形データと呼ぶことにする。
【００１４】
ＤＲＡＭなどの半導体集積回路のマスクパターンでは、形状も大きさも同一の図形が所定のピッチで所定方向に多数配列されていることが多い。そこで、同一図形が所定ピッチＰでＸ軸方向に複数ｎ個並べて配置されていた場合には、ｎ個の図形についての図形データを圧縮して、代表となる１つの図形を示す図形データと、ピッチＰおよび個数ｎを示すデータと、によって構成される単一の圧縮図形データとして表現した方が効率的である。本発明では、演算対象となる個々の図形データを台形形式で表現するとともに、圧縮可能な図形データについては圧縮を行い、圧縮台形形式の図形データとして取り扱うことになる。
【００１５】
§２．  本発明に係る図形演算装置の構成
図７は本発明に係る図形演算装置の基本構成を示すブロック図である。図示のとおり、この図形演算装置は、データ圧縮部１、データ抽出部２、演算部３、投影データ管理部４、データ排出部５、データ展開部６の各要素から構成される。これらの各要素は、実際にはコンピュータのハードウエアおよびソフトウエアによって実現される要素であるが、ここでは、個々の処理機能に着目して、この図形演算装置が上述の６つの構成要素からなるものとして、以下の説明を行うことにする。
【００１６】
データ圧縮部１は、演算対象として与えられた一般形式（非圧縮図形データ）の図形データファイルαを、§１で述べた圧縮台形形式の図形データファイルβに変換する機能を有する。すなわち、まず、図形データファイルα内に含まれている演算対象となる個々の図形データを、二辺がＸ軸に平行な台形の集合として表現し、各台形を示す個々の図形データに変換する（図形データファイルαがもともと台形図形ファイルであった場合には、この変換処理は不要である）。続いて、この台形図形データ内の特定のｎ個の図形データが、同一の台形を所定ピッチＰでＸ軸方向に複数ｎ個並べて配置した状態を示すデータであった場合には、このｎ個の図形データを、代表となる１つの台形を示す図形データと、ピッチＰおよび個数ｎを示すデータと、によって構成される単一の圧縮図形データに置換する圧縮処理を行う。たとえば、図５に示す４個の図形データ３１，３３，３５，３７は、図６に示す図形データ３１とピッチＰおよび個数「４」を示すデータとによって構成される単一の圧縮図形データに置換され、図５に示す４個の図形データ３２，３４，３６，３８は、図６に示す図形データ３２とピッチＰおよび個数「４」を示すデータとによって構成される単一の圧縮図形データに置換されることになる。
【００１７】
こうして得られる圧縮台形形式の演算対象図形データファイルβは、もとの図形データファイルαに比べてかなり容量の小さなファイルになる。図６には、たかだか４個の図形データを圧縮した例を示したが、実際の集積回路のマスクパターンでは、数１０個あるいは数１００個もの図形データが単一の図形データに圧縮されることになり、圧縮の効率はかなり高いものになる。なお、このデータ圧縮部１において行われる図形データの台形形式への変換手法や、複数の図形データを単一の図形データに圧縮する手法は、既に種々の方法が公知であるため、ここでは具体的な方法についての説明は省略する。
【００１８】
データ抽出部２は、こうして準備された圧縮台形形式の演算対象図形データファイルβ内の図形データを１つずつ抽出して、これを演算部３に与える機能を有する。圧縮図形データの場合も、もとの図形データの数にかかわらず１つの図形データとして抽出される。ここに示す実施形態では、圧縮台形形式の演算対象図形データファイル内の図形データを、台形の底辺のＹ座標値に基づいてソートし、ソート順に図形データを１つずつ抽出するようにしている。
【００１９】
演算部３は、データ抽出部２から抽出された図形データを一時的に保持し、図形相互の演算を実行する。この演算の内容については後に詳述するが、できるだけ圧縮図形データのまま演算処理を行うようにし、演算処理の負担を軽減している。投影データ管理部４は、この演算部３における図形演算で利用される投影データを一時的に格納する機能を有する。詳細については後述するが、演算部３で生成された投影データは、この投影データ管理部４へ登録され、演算部３は必要に応じて、この投影データ管理部４内に登録されている投影データを検索しながら、図形演算処理を実行することになる。データ排出部５は、演算部３内の演算済みの図形データを排出して、圧縮台形形式の演算結果図形データファイルγを作成する機能を有する。最後に、データ展開部６によって、この図形データファイルγ内の圧縮図形データが展開され、一般形式の演算結果図形データファイルδが作成される。すなわち、このデータ展開部６は、圧縮台形形式の演算結果図形データファイルγ内に含まれる圧縮図形データを、代表となる台形を所定の個数分だけ所定ピッチでＸ軸方向に並べた状態を示す複数の非圧縮図形データに置換する展開処理を施し、非圧縮図形データからなる演算結果図形データファイルδを作成する処理を行うことになる。
【００２０】
§３．  本発明における基本的な演算手法
このように、データ抽出部２から演算部３へ与えられる個々の図形データは、圧縮形式の図形データであり、演算部３からデータ排出部５へ排出される個々の図形データも、圧縮形式の図形データである。したがって、演算部３では、圧縮形式の図形データを演算対象として取り扱う演算が行われることになる。
【００２１】
本発明の特徴は、この演算部３での図形演算を、できる限り圧縮形式の状態のままで実行する点にある。図形演算の基本は、相互に干渉する（二次元平面上で重なり合う）図形を、所定の論理演算規則に基づいて新たな図形に置き換える処理である。ただ、通常は、演算対象となる図形データファイルに含まれるすべての図形が相互に干渉しているわけではなく、そのうちの一部が干渉しているにすぎない。そこで、本発明では、圧縮形式の図形データについて、圧縮した状態のままで、干渉が生じている可能性を調べる予備判断処理を実施している。この予備判断処理において、干渉の可能性が無いと判断された図形データについては、圧縮した状態のまま、演算部３における処理は完了することになる。一方、予備判断処理において、干渉が生じている可能性のある図形データについては、展開処理を行って圧縮状態を解き、真に干渉が生じているか否かを調べる本判断処理を実行する。そして、真に干渉が生じていた場合には、展開した状態で図形演算を行い、新たな図形を発生させる更新処理を行い、必要に応じて、更新後の図形について圧縮処理を施す。こうすれば、できるだけ圧縮形式の状態のまま、演算処理を行うことが可能になる。
【００２２】
圧縮形式の図形データのまま干渉の有無を調べる予備判断処理は、Ｘ軸およびＹ軸への投影像を利用して行うことができる。演算部３は、抽出された図形データが非圧縮図形データ（データ圧縮部１において圧縮処理が施されなかったデータ、すなわち、１つだけ単独で配置されている図形についてのデータ）であった場合には、その図形をＸ軸上へ投影することによって得られるＸ軸投影像と、その図形をＹ軸上へ投影することによって得られるＹ軸投影像と、を求める機能を有する。たとえば、図６において、図形３２が単独で配置されている非圧縮図形であった場合には、この図形３２自身の投影像として、Ｘ軸投影像ＵとＹ軸投影像Ｖとが求められる（ここでは、各投影像を座標軸上の区間を示す矢印で表すことにする）。
【００２３】
これに対し、抽出された図形データが圧縮図形データの場合には、展開処理によって得られる複数の図形の最小外接矩形をＸ軸上へ投影することによって得られるＸ軸投影像と、この最小外接矩形をＹ軸上へ投影することによって得られるＹ軸投影像と、が演算部３において求められる。たとえば、図６において、図形３２が、ピッチＰと配置数４という情報を伴っており、図形３２，３４，３６，３８なる４つの図形の代表図形（圧縮図形）として与えられた場合には、これら４つの図形の最小外接矩形の投影像として、Ｘ軸投影像ＷとＹ軸投影像Ｖとが求められることになる（Ｙ軸投影像Ｖについては、圧縮図形も非圧縮図形も同じになる）。
【００２４】
このように、各図形データについてＸ軸投影像とＹ軸投影像とを求めておき、これら各投影像が干渉するか否か（一次元の軸上において重なり合うか否か）を判断する予備判断処理を行うようにすれば、二次元平面上で図形が真に干渉するか否かを判断する本判断処理を行う場合に比べて、演算負担は非常に軽いものになる。本発明では、Ｘ軸投影像に関して干渉が生じるか否かを判断する予備判断処理と、Ｙ軸投影像に関して干渉が生じるか否かを判断する予備判断処理と、の双方について、「相互に干渉有り」と判断された図形についてのみ、本判断処理を実行するようにして、全演算処理の負担を軽減するようにしている。
【００２５】
§４．  本発明に係る図形演算装置による処理手順
図８は、図７に示す図形演算装置を用いた基本的な図形演算処理手順を示す流れ図である。まず、ステップＳ１において、圧縮台形形式の演算対象図形データファイルβが用意される。すなわち、データ圧縮部１によって、一般形式の演算対象図形データファイルαを圧縮台形形式のファイルβに変換する処理が行われることになる。続いて、ステップＳ２において、このファイルβ内の複数の図形データを、底辺のＹ座標値の小さい順にソートし、これをソート順に１つずつ抽出する処理が行われる。すなわち、データ抽出部２によって、ファイルβ内の図形データが１つずつ抽出され、演算部３に与えられることになる。
【００２６】
続く、ステップＳ３〜Ｓ１２の手順は、データ抽出部２から抽出された１つの抽出図形データに着目して、演算部３で行われる処理である。まず、ステップＳ３において、Ｘ軸に関する予備判断処理が行われる。すなわち、抽出図形データについてＸ軸投影像を求め、このＸ軸投影像と、演算部３に一時保持されている過去に抽出された図形データのＸ軸投影像との干渉の有無を判断する処理が行われる。ここに示す実施形態では、過去に抽出された図形データのＸ軸投影像を、投影データ管理部４に登録することにしているので、この投影データ管理部４内に登録されているＸ軸投影像の中で、抽出図形データについてのＸ軸投影像に干渉するものがあるか否かを調べる処理が行われることになる。
【００２７】
続くステップＳ４では、Ｙ軸に関する予備判断処理が行われる。すなわち、抽出図形データについてＹ軸投影像を求め、このＹ軸投影像と、演算部に一時保持されている過去に抽出された図形データのＹ軸投影像との干渉の有無を判断する処理が行われる。なお、ここに示す実施形態では、過去に抽出された図形データのＸ軸投影像は、上述したように、投影データ管理部４に登録しているが、Ｙ軸投影像は登録を行っていない。これは、圧縮図形データについてのＸ軸投影像は、最小外接矩形を求める演算が必要であるのに対し、Ｙ軸投影像はそのような演算が不要であるためである（もちろん、Ｘ軸投影像とともにＹ軸投影像を投影データ管理部４へ登録するようにしてもかまわない）。
【００２８】
このステップＳ４におけるＹ軸に関する予備判断処理の結果、抽出図形データに対して干渉無しと判断された図形データ（過去に抽出され、演算部３内に一時保持された状態のままになっていた他の図形データ）は、ステップＳ５において、データ排出部５から排出される。これは、ステップＳ２において、底辺のＹ座標値の小さい順に抽出が行われていることを考慮すると、Ｙ軸投影像について、現在の抽出図形データに対して干渉しない図形データは、将来の抽出図形データに対しても干渉は生じないと判断できるためである。こうして演算部３から排出された図形データによって、演算結果図形データファイルγが構成されることになる。また、演算部３から排出された図形データは、もはや演算済みのデータであるから、この図形データについてのＸ軸投影像も、投影データ管理部４から登録が削除される。
【００２９】
かくして、ステップＳ３におけるＸ軸に関する予備判断処理と、ステップＳ４におけるＹ軸に関する予備判断処理と、の双方において、抽出図形データに対して干渉有りと判断された他の図形データが存在する場合には、この図形データは、抽出図形データに対して干渉する可能性があるので、ステップＳ６からステップＳ７へと進み、本判断処理が実行される。この本判断処理は、圧縮図形データについては展開処理を施した上で、両図形データ自身の干渉の有無を判断する処理であり、ＸＹ二次元平面上において、真に干渉が生じているか否かを判断する処理ということになる。このステップＳ７の本判断処理において、真に干渉する図形があると判断された場合には、ステップＳ９において、相互に干渉する図形（圧縮図形データの場合は展開した状態の複数の図形）相互について、所定の図形演算を実行し、新たな図形データを生成する処理が行われる。そして、続くステップＳ１０において、演算後の図形データに基づいて、投影データ管理部４内のＸ軸投影像の登録を更新する処理が行われる。
【００３０】
一方、ステップＳ３におけるＸ軸に関する予備判断処理と、ステップＳ４におけるＹ軸に関する予備判断処理と、の少なくともいずれか一方において、抽出図形データに対して干渉する図形データは全くなしと判断された場合には、この抽出図形データに真に干渉する他の図形データ（過去に抽出され、演算部３内に一時保持されている図形データ）は存在しないと判断できるので、この抽出図形データと演算部３内に一時保持されている過去に抽出された他の図形データとの間の図形演算は不要である。ただし、現在の抽出図形データと、将来抽出される図形データと、の間には、干渉が生じる可能性があるので、この現在の抽出図形データをそのまま演算部３内に一時保持した状態で残し、ステップＳ１１において、この現在の抽出図形データのＸ軸投影像を投影データ管理部４に登録しておく。
【００３１】
以上が、データ抽出部２によって抽出された１つの抽出図形データに着目した一連の処理である。この一連の処理が、順次抽出されるすべての図形データについて繰り返し実行される。すなわち、ステップＳ１２を経て、ステップＳ２からの処理が繰り返し実行されることになる。ステップＳ１２からステップＳ２へ戻ることにより、現在の抽出図形データは、過去の抽出図形データとなって演算部３内にそのまま残ることになり、そのＸ軸投影像は、投影データ管理部４内に登録される（ステップＳ１１）ことになる。
【００３２】
こうして、演算対象図形データファイルβ内のすべての図形データが抽出されたら、ステップＳ１２からステップＳ１３へと進み、最終的に演算部３内に残っている全図形データがデータ排出部５によって排出され、こうして排出された図形データによって、演算結果図形データファイルγが構成される。このデータファイルγは、圧縮台形形式の図形データファイルであるので、データ展開部６による展開処理を施すことにより、圧縮状態を解いた一般形式の演算結果図形データファイルδが得られる。
【００３３】
【実施例】
ここでは、図８に示す手順を、具体的な図形パターンに適用した実施例を述べる。いま、図９に示すような合計１４個の図形からなる図形パターンが演算対象図形データとして与えられ、これらの各図形について、論理和演算（ＯＲ演算）を行う場合を考える。図９の図形パターンを観察すればわかるとおり、図形ｃ２，ｂ５，ｄ１，ｂ６の４つについて干渉が生じており、実際には、これら４つの図形について論理和演算が実行されればよい。本発明に係る図形演算装置では、次のような手順によって、この図形演算が処理されることになる。
【００３４】
まず、図８のステップＳ１において、圧縮台形形式の演算対象図形データファイルβが用意される。図９に示す図形パターンにおいて、図形ａ１，ａ２，ａ３は所定ピッチＰａでＸ軸方向に並んだ同一形状の図形であり、これら３つの図形は、代表図形ａ１を示す図形データ「ａ１」に、「×３，Ｐａ」なる情報（同じ図形がピッチＰａで合計３個配置されていることを示す情報）を付加した圧縮図形データによって表現することができる。同様に、図形ｂ１〜ｂ８は所定ピッチＰｂでＸ軸方向に並んだ同一形状の図形であり、これら８つの図形は、代表図形ｂ１を示す図形データ「ｂ１」に、「×８，Ｐｂ」なる情報を付加した圧縮図形データによって表現することができ、図形ｃ１，ｃ２は所定ピッチＰｃでＸ軸方向に並んだ同一形状の図形であり、これら２つの図形は、代表図形ｃ１を示す図形データ「ｃ１」に、「×２，Ｐｃ」なる情報を付加した圧縮図形データによって表現することができる。かくして、図９に示す図形パターンは、図１０に示すように、４つの図形データ「ａ１（×３  Ｐａ）」，「ｂ１（×８  Ｐｂ）」，「ｃ１（×２  Ｐｃ）」，「ｄ１」によって表現されることになる。ここで、括弧内の情報を有する図形データは、いずれも圧縮図形データである。以下の説明では、便宜上、この圧縮図形データについては、括弧内の情報を省略し、単に、図形データ「ａ１」，「ｂ１」，「ｃ１」と呼ぶことにする。
【００３５】
ステップＳ２では、この４つの図形データを、底辺のＹ座標値の小さい順にソートし、ソート順に１つずつ抽出する処理が行われる。ここで、この４つの図形データの底辺のＹ座標値を調べると、図１１に示すように、図形データａ１，ｂ１，ｃ１，ｄ１の底辺のＹ座標値は、ｙａ，ｙｂ，ｙｃ，ｙｄの順となるので、４つの図形データは、ａ１，ｂ１，ｃ１，ｄ１の順にソートされ、この順に１つずつ抽出されることになる。したがって、ステップＳ２において最初に抽出される抽出図形データは、図形データａ１ということになる。
【００３６】
そこで、ステップＳ３では、この図形データａ１についてのＸ軸投影像が求められる。こうして求められたＸ軸投影像Ａを図１２に示す。既に述べたように、圧縮図形データのＸ軸投影像は、これを展開して得られる複数の図形の最小外接矩形のＸ軸投影像として定義されているので、図形データａ１についてのＸ軸投影像Ａは、図１２に示すように、展開して得られる合計３つの図形ａ１，ａ２，ａ３の最小外接矩形をＸ軸に投影した像となっている。結局、このＸ軸投影像Ａは、展開して得られる複数の図形のＸ軸方向に関する配置範囲を示すものであり、実際のデータとしては、図示するような２つのＸ座標値（ｘ１，ｘ２）を示すデータとなる。したがって、このＸ軸投影像Ａを求める演算は、単純な算術演算ですみ、二次元平面上に３つの図形ａ１，ａ２，ａ３を実際に展開する複雑な演算は不要である。同様に、ステップＳ４において、この図形データａ１についてのＹ軸投影像ＡＡを求める処理が行われる。
【００３７】
続く、ステップＳ５では、過去に抽出された他の図形データがまだ存在しないため、何の処理も行われない。また、ステップＳ６においても、図形データａ１に干渉する過去の図形データは存在しないので、ステップＳ１１へと進み、図形データａ１のＸ軸投影像Ａを投影データ管理部４に登録する処理が行われる。なお、この実施例では、Ｘ軸投影像のみを投影データ管理部４に登録しているが、Ｙ軸投影像の登録も行うようにしてもかまわない。
【００３８】
こうして、最初の抽出図形データａ１についての処理は完了する。図１３は、この時点における各部の保持内容を示す図である。演算部３には、最初の抽出図形データａ１がそのまま残っており、投影データ管理部４には、この図形データａ１についてのＸ軸投影像Ａが登録されている（ステップＳ１１の処理）。また、演算対象図形データファイルβ内には、これから抽出される予定の３つの図形データｂ１，ｃ１，ｄ１が残っており、演算結果図形データファイルγ内には、図形データは１つも排出されていない。
【００３９】
続いて、ステップＳ１２からステップＳ２へと戻り、２番目の抽出図形データとして、図形データｂ１が抽出される。そして、ステップＳ３では、図１４に示すように、この図形データｂ１についてのＸ軸投影像Ｂが求められ、Ｘ軸に関する予備判断処理が行われる。図１４に示すとおり、投影像Ｂは投影像Ａに干渉する。図１５は、この時点における各部の保持内容を示す図である。演算部３には、過去に抽出された図形データａ１、現時点での抽出図形データｂ１、そしてそのＸ軸投影像Ｂが保持されており、投影データ管理部４を検索することにより、投影像Ｂに干渉する投影像の有無を調べる。この例の場合、投影データ管理部４内に登録されている投影像Ａが干渉する投影像として検索されることになる。
【００４０】
次に、ステップＳ４において、図形データｂ１についてのＹ軸投影像ＢＢが求められ、過去に抽出された図形データのＹ軸投影像の中に干渉するものがあるか否かが調べられる。この例の場合、図１６に示すように、投影像ＢＢと投影像ＡＡとは干渉せず、ステップＳ４の予備判断処理では、干渉するもの無しと判断されることになる。なお、この実施例では、Ｙ軸投影像については、投影データ管理部４に登録することはせずに、演算部３内に保持されている個々の図形データからその都度Ｙ軸投影像を求めるようにしているが、Ｘ軸投影像とともにＹ軸投影像を投影データ管理部４に登録するようにした場合には、ステップＳ３の処理と同様に、投影データ管理部４内を検索して干渉するものがあるか否かを調べることになる。もっとも、Ｙ軸投影像は、その図形の底辺のＹ座標値と上辺のＹ座標値として一義的に与えられるので、実用上は、敢えて投影データ管理部４に登録しておく必要はない。
【００４１】
こうして、ステップＳ４のＹ軸に関する予備判断処理において、現在の抽出図形データｂ１に対して、過去に抽出された他の図形データａ１が干渉しないと判断されたので、続くステップＳ５では、この干渉しないと判断された図形データａ１の排出処理が行われ、そのＸ軸投影像Ａの登録を削除する処理が行われる。これは、図１６に示すように、図形ａ１と図形ｂ１とが、Ｙ軸に関して干渉しない以上、将来抽出される図形（底辺のＹ座標値は図形ｂ１のＹ座標値よりも大きい）についても、図形ａ１とは干渉する可能性がないと判断できるためである。
【００４２】
かくして、次のステップＳ６では、干渉するもの無しと判断されてステップＳ１１へと進み、図形データｂ１のＸ軸投影像Ｂを投影データ管理部４に登録する処理が行われる。こうして、２番目の抽出図形データｂ１についての処理は完了する。図１７は、この時点における各部の保持内容を示す図である。最初の抽出図形データａ１は、演算結果図形データファイルγ内に排出され、演算部３には、２番目の抽出図形データｂ１のみが残っている。また、投影データ管理部４には、この図形データｂ１についてのＸ軸投影像Ｂのみが登録されている。
【００４３】
再び、ステップＳ１２からステップＳ２へと戻り、今度は、３番目の抽出図形データとして、図形データｃ１が抽出される。そして、ステップＳ３では、図１８に示すように、この図形データｃ１についてのＸ軸投影像Ｃが求められ、Ｘ軸に関する予備判断処理が行われる。図１８に示すとおり、投影像Ｃは投影像Ｂに干渉する。図１９は、この時点における各部の保持内容を示す図である。演算部３には、過去に抽出された図形データｂ１、現時点での抽出図形データｃ１、そしてそのＸ軸投影像Ｃが保持されており、投影データ管理部４を検索することにより、投影像Ｃに干渉する投影像の有無を調べる。この例の場合、投影データ管理部４内に登録されている投影像Ｂが、干渉する投影像として検索されることになる。
【００４４】
次に、ステップＳ４において、図形データｃ１についてのＹ軸投影像ＣＣが求められ、過去に抽出された図形データのＹ軸投影像の中に干渉するものがあるか否かが調べられる。この例の場合、図２０に示すように、投影像ＣＣと投影像ＢＢとは干渉し、ステップＳ４の予備判断処理においても、図形データｃ１がｂ１と干渉するとの判断がなされることになる。そこで、続くステップＳ５では、図形データの排出は行われない。
【００４５】
こうして、ステップＳ６では、Ｘ軸，Ｙ軸の双方について、図形データｃ１と図形データｂ１とが干渉すると判断され、ステップＳ７の本判断処理が実行されることになる。すなわち、圧縮図形データｃ１とｂ１とに対して、はじめて展開処理が実行され、図２１に示すように、合計１０個の図形データｂ１〜ｂ８，ｃ１，ｃ２を二次元平面上に展開した状態が演算により求められ、真に干渉する図形があるか否かが判断される。この本判断処理によって、図形ｃ２と図形ｂ５とが真に干渉するとの判断が得られる。そこで、ステップＳ８からステップＳ９へと進み、この１０個の図形に対して、所定の図形演算が実行される。この例の場合は、論理和演算であるから、図形ｃ２と図形ｂ５との論理和に相当する図形が新たに発生されることになる。この新たな図形は、やはり台形形式で表現され、圧縮が可能な場合には圧縮が行われる。したがって、図２１に示す１０個の図形データｂ１〜ｂ８，ｃ１，ｃ２は、図２２に示すように、合計１１個の新たな図形データｅ１〜ｅ４，ｆ１〜ｆ３，ｇ１，ｈ１，ｉ１，ｊ１に置換される。更に、図形データｅ１〜ｅ４は単一の圧縮図形データｅ１に置換され、図形データｆ１〜ｆ３も単一の圧縮図形データｆ１に置換されるので、最終的には、図２３に示すように、合計６個の新たな図形データｅ１，ｆ１，ｇ１，ｈ１，ｉ１，ｊ１が得られることになる。
【００４６】
このように、演算部３内の図形データが新たな図形データに置換されると、投影データ管理部４内のＸ軸投影像について、登録を更新する処理がステップＳ１０で行われる。すなわち、新たな図形データｅ１，ｆ１，ｇ１，ｈ１，ｉ１，ｊ１についてのＸ軸投影像Ｅ，Ｆ，Ｇ，Ｈ，Ｉ，Ｊが、図２３に示すように求められ、投影データ管理部４の登録内容が更新されることになる。図２４は、この時点における各部の保持内容を示す図である。演算部３には、新たな図形データｅ１，ｆ１，ｇ１，ｈ１，ｉ１，ｊ１が残っており、投影データ管理部４内にも、この新たな図形データについてのＸ軸投影像Ｅ，Ｆ，Ｇ，Ｈ，Ｉ，Ｊが登録された状態になっている。
【００４７】
ここで、もう一度、ステップＳ１２からステップＳ２へと戻り、今度は、最後の抽出図形データとして、図形データｄ１が抽出される。そして、ステップＳ３では、図２５に示すように、この図形データｄ１についてのＸ軸投影像Ｄが求められ、Ｘ軸に関する予備判断処理が行われる。図２５に示すとおり、投影像Ｄは投影像Ｆ，Ｈ，Ｉ，Ｊに干渉する。図２６は、この時点における各部の保持内容を示す図である。投影データ管理部４を検索することにより、投影像Ｄに干渉する投影像の有無を調べれば、登録されている投影像Ｆ，Ｈ，Ｉ，Ｊが干渉する投影像として検索されることになる。
【００４８】
次に、ステップＳ４において、図形データｄ１についてのＹ軸投影像ＤＤが求められ、過去に抽出された図形データのＹ軸投影像の中に干渉するものがあるか否かが調べられる。この例の場合、図２７に示すように、投影像ＤＤと投影像ＥＥ，ＦＦ，ＪＪとが干渉し、投影像ＤＤと投影像ＧＧ，ＨＨ，ＩＩとは干渉しない、との予備判断がなされることになる。そこで、ステップＳ５において、Ｙ軸に関しては干渉しないと判断された図形データｇ１，ｈ１，ｉ１が演算結果図形データファイルγへと排出され、そのＸ軸投影像Ｇ，Ｈ，Ｉの登録が投影データ管理部４から削除される。図２８は、この時点における各部の保持内容を示す図である。
【００４９】
次のステップＳ６では、Ｘ軸，Ｙ軸の双方について、図形データｄ１と図形データｊ１，ｆ１とが干渉すると判断され、ステップＳ７の本判断処理が実行されることになる。すなわち、非圧縮図形データｄ１，ｊ１についてはそのまま、圧縮データｆ１については展開処理が実行され、図２９に示すように、合計５個の図形データｄ１，ｊ１，ｆ１〜ｆ３を二次元平面上に展開した状態が演算により求められ、真に干渉する図形があるか否かが判断される。この本判断処理によって、図形ｄ１，ｊ１，ｆ１が真に干渉するとの判断が得られる。そこで、ステップＳ８からステップＳ９へと進み、この３個の図形に対して、所定の図形演算が実行される。この例の場合は、論理和演算であるから、図形ｄ１，ｊ１，ｆ１の論理和に相当する図形が新たに発生されることになる。この新たな図形は、やはり台形形式で表現され、圧縮が可能な場合には圧縮が行われる。したがって、図２９に示す５個の図形データｄ１，ｊ１，ｆ１〜ｆ３は、図３０に示すように、合計６個の新たな図形データｋ１，ｌ１，ｍ１，ｎ１，ｏ１，ｏ２に置換される。更に、図形データｏ１，ｏ２は単一の圧縮図形データｏ１に置換されるので、最終的には、合計５個の新たな図形データｋ１，ｌ１，ｍ１，ｎ１，ｏ１に置換されることになる。
【００５０】
このように、演算部３内の図形データが新たな図形データに置換されると、投影データ管理部４内のＸ軸投影像について、登録を更新する処理がステップＳ１０で行われる。すなわち、新たな図形データｋ１，ｌ１，ｍ１，ｎ１，ｏ１についてのＸ軸投影像Ｋ，Ｌ，Ｍ，Ｎ，Ｏが、図３１に示すように求められ、投影データ管理部４の登録内容が更新されることになる。図３２は、この時点における各部の保持内容を示す図である。演算部３には、更新されなかった図形データｅ１，ｇ１に、新たな図形データｋ１，ｌ１，ｍ１，ｎ１，ｏ１が付加されており、投影データ管理部４内にも、これらの図形データについてのＸ軸投影像Ｅ，Ｇ，Ｋ，Ｌ，Ｍ，Ｎ，Ｏが登録された状態になっている。
【００５１】
以上で、すべての図形データについての抽出が完了したので、ステップＳ１２からステップＳ１３へと進むことになる。ここで、演算部３内に残っていた全図形データが演算結果図形データファイルγへと排出される。図３３は、この時点における各部の保持内容を示す図である。最終的な演算結果図形データファイルγ内には、図形データａ１，ｅ１，ｇ１，ｈ１，ｉ１，ｋ１，ｌ１，ｍ１，ｎ１，ｏ１が含まれており、これは、図３４に示すような図形パターンを示すものになる。必要に応じて、この圧縮台形形式のデータファイルγに対して展開処理を行えば、一般形式のデータファイルδを得ることができ、最終的な演算結果が得られる。
【００５２】
以上、本発明を図示する実施例に基づいて説明したが、本発明はこの実施例に限定されるものではなく、この他にも種々の態様で実施可能である。以下にいくつかの変形例を述べておく。
【００５３】
＜変形例１＞
図８に示す流れ図の手順では、抽出したすべての図形データについて、ステップＳ４のＹ軸に関する予備判断処理を実行しているが、ステップＳ３のＸ軸に関する予備判断処理によって、抽出図形データに対して干渉の可能性有りと判断された図形データに対してのみ、選択的にステップＳ４の予備判断処理を実行するようにしてもよい。そうすれば、Ｘ軸に関して干渉しないと判断された図形データについては、Ｙ軸に関する干渉判断を行う必要がなくなり、演算負担は更に軽減される。たとえば、図２５において、抽出図形データｄ１のＸ軸投影像Ｄに対して、投影像Ｅ，Ｇは干渉しないので、Ｙ軸に関する干渉判断処理では、図形データｅ１，ｇ１を検索対象からは外すことができる。すなわち、図２７に示すＹ軸に関する干渉判断処理では、図形データｅ１，ｇ１についてのＹ軸投影像ＥＥ，ＧＧは求める必要はなくなる。なお、この場合、ステップＳ５において、図形データｇ１が排出されなくなるが、最終的にステップＳ１３で全図形データが排出されることになるので、問題は生じない。
【００５４】
＜変形例２＞
上述の実施例では、ステップＳ２における抽出順を、底辺のＹ座標値の小さい順としているが、上辺のＹ座標値の大きい順とすることも可能である。
【００５５】
＜変形例３＞
上述の実施例では、二辺がＸ軸に平行な台形図形を用意し、Ｘ軸方向に一定ピッチで配置された複数の図形データに対して圧縮を行うようにしているが、逆に、二辺がＹ軸に平行な台形図形を用意し、Ｙ軸方向に一定ピッチで配置された複数の図形データに対して圧縮を行うようにしてもよい。この場合、ステップＳ２における抽出順は、Ｘ座標値の小さい順とすればよい。
【００５６】
＜変形例４＞
上述の実施例では、図形間の論理演算を論理和演算（ＯＲ演算）としているが、ステップＳ９において実行する論理演算は、この他にも論理積演算（ＡＮＤ演算）など、どのような図形演算を行うようにしてもかまわない。
【００５７】
【発明の効果】
以上のとおり本発明に係る図形演算装置によれば、図形データをできるだけ圧縮台形形式の状態のまま演算を行うようにしたため、記憶容量のより小さなコンピュータを用いて、より短時間に演算処理を実行することができるようになる。
【図面の簡単な説明】
【図１】図形演算の対象となる図形パターンの一例を示す図である。
【図２】図１の図形に対して論理和演算（ＯＲ演算）を実行した結果を示す図である。
【図３】図１の図形に対して論理積演算（ＡＮＤ演算）を実行した結果を示す図である。
【図４】本発明で用いる台形形式の図形表現を示す図である。
【図５】本発明で用いる圧縮処理の対象となる図形パターンの一例を示す図である。
【図６】図５に示す図形パターンに対して圧縮処理を施した状態を示す図である。
【図７】本発明に係る図形演算装置の基本構成を示すブロック図である。
【図８】図７に示す図形演算装置を用いた基本的な図形演算処理手順を示す流れ図である。
【図９】本発明に係る図形演算装置による演算対象となるパターンを構成する図形データの一例を示す図である。
【図１０】図９に示す図形データに対して、圧縮処理を施した状態を示す図である。
【図１１】図１０に示す４つの図形データについて、底辺のＹ座標値に基づくソートを行う処理を説明する図である。
【図１２】最初の抽出図形データａ１についてのＸ軸投影像Ａを示す図である。
【図１３】最初の抽出図形データａ１についての処理が完了した時点における各部の保持内容を示す図である。
【図１４】２番目の抽出図形データｂ１についてのＸ軸投影像Ｂを示す図である。
【図１５】２番目の抽出図形データｂ１についてのＸ軸に関する予備判断処理を行っている時点における保持内容を示す図である。
【図１６】２番目の抽出図形データｂ１についてのＹ軸投影像ＢＢを示す図である。
【図１７】２番目の抽出図形データｂ１についての処理が完了した時点における各部の保持内容を示す図である。
【図１８】３番目の抽出図形データｃ１についてのＸ軸投影像Ｃを示す図である。
【図１９】３番目の抽出図形データｃ１についてのＸ軸に関する予備判断処理を行っている時点における各部の保持内容を示す図である。
【図２０】３番目の抽出図形データｃ１についてのＹ軸投影像ＣＣを示す図である。
【図２１】２番目の抽出図形データｂ１と３番目の抽出図形データｃ１とを展開した状態を示す図である。
【図２２】図２１に示す各展開図形に対して、論理和演算を施すことにより新たに得られる図形データを示す図である。
【図２３】図２２に示す新たな図形データについてのＸ軸投影像を示す図である。
【図２４】図２３に示すＸ軸投影像に基づいて、投影データの登録内容が更新された時点における各部の保持内容を示す図である。
【図２５】最後の抽出図形データｄ１についてのＸ軸投影像Ｄを示す図である。
【図２６】最後の抽出図形データｄ１についてのＸ軸に関する予備判断処理を行っている時点における各部の保持内容を示す図である。
【図２７】最後の抽出図形データｄ１についてのＹ軸投影像ＤＤを示す図である。
【図２８】最後の抽出図形データｄ１に対して、Ｙ軸に関しては干渉しないと判断された図形データを排出した時点における各部の保持内容を示す図である。
【図２９】最後の抽出図形データｄ１およびこれに干渉する各図形データを展開した状態を示す図である。
【図３０】図２９に示す各展開図形に対して、論理和演算を施すことにより新たに得られる図形データを示す図である。
【図３１】図３０に示す新たな図形データについてのＸ軸投影像を示す図である。
【図３２】図３１に示すＸ軸投影像に基づいて、投影データの登録内容が更新された時点における各部の保持内容を示す図である。
【図３３】すべての処理が完了した時点における各部の保持内容を示す図である。
【図３４】最終的に得られる演算結果となるパターンを構成する図形データを示す図である。
【符号の説明】
１…データ圧縮部
２…データ抽出部
３…演算部
４…投影データ管理部
５…データ排出部
６…データ展開部
１１〜３８…図形データ
ａ１〜ａ３，ｂ１〜ｂ８，ｃ１，ｃ２，ｄ１，ｅ１〜ｅ４，ｆ１〜ｆ３，ｇ１，ｈ１，ｉ１，ｊ１，ｋ１，ｌ１，ｍ１，ｎ１，ｏ１，ｏ２…図形データ
Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ，Ｉ，Ｊ，Ｋ，Ｌ，Ｍ，Ｎ，Ｏ，Ｕ，Ｗ…Ｘ軸投影像
ＡＡ，ＢＢ，ＣＣ，ＤＤ，ＥＥ，ＦＦ，ＧＧ，ＨＨ，ＩＩ，ＪＪ，ＫＫ，ＬＬ，ＭＭ，ＮＮ，ＯＯ，Ｖ…Ｙ軸投影像
Ｐ，Ｐａ，Ｐｂ，Ｐｃ，Ｐｄ，Ｐｅ，Ｐｆ，Ｐｏ…ピッチ
α…一般形式の演算対象図形データファイル
β…圧縮台形形式の演算対象図形データファイル
γ…圧縮台形形式の演算結果図形データファイル
δ…一般形式の演算結果図形データファイル
【図１】
0003845477.tif 000002
【図２】
0003845477.tif 000003
【図３】
0003845477.tif 000004
【図４】
0003845477.tif 000005
【図５】
0003845477.tif 000006
【図６】
0003845477.tif 000007
【図７】
0003845477.tif 000008
【図８】
0003845477.tif 000009
【図９】
0003845477.tif 000010
【図１０】
0003845477.tif 000011
【図１１】
0003845477.tif 000012
【図１２】
0003845477.tif 000013
【図１３】
0003845477.tif 000014
【図１４】
0003845477.tif 000015
【図１５】
0003845477.tif 000016
【図１６】
0003845477.tif 000017
【図１７】
0003845477.tif 000018
【図１８】
0003845477.tif 000019
【図１９】
0003845477.tif 000020
【図２０】
0003845477.tif 000021
【図２１】
0003845477.tif 000022
【図２２】
0003845477.tif 000023
【図２３】
0003845477.tif 000024
【図２４】
0003845477.tif 000025
【図２５】
0003845477.tif 000026
【図２６】
0003845477.tif 000027
【図２７】
0003845477.tif 000028
【図２８】
0003845477.tif 000029
【図２９】
0003845477.tif 000030
【図３０】
0003845477.tif 000031
【図３１】
0003845477.tif 000032
【図３２】
0003845477.tif 000033
【図３３】
0003845477.tif 000034
【図３４】
0003845477.tif 000035