(57)【特許請求の範囲】
【請求項１】
複数の辺で形成される第１の図形のデータ及び前記第１の図形のうち所定長を半径とする円によって塗り込みが行われる部分を表す第２の図形のデータを格納するデータ格納部に格納されている前記第１の図形のデータに係る前記第１の図形の各辺を当該第１の図形の内側方向に前記所定長移動し、前記第１の図形の頂点のうち角度が許容角度より大きい頂点を形成する複数の辺が移動後に交わる点を中心とし前記所定長を半径とする円を生成し、当該円と当該移動前の辺とにより囲まれる閉領域を特定することで、第３の図形を生成し、前記第３の図形のデータを前記データ格納部に格納するステップと、
前記データ格納部に格納されている前記第３の図形のデータに係る前記第３の図形のうち前記第１の図形内に含まれる前記第３の図形と、前記データ格納部に格納されている前記第２の図形のデータに係る前記第２の図形との、図形についての論理和演算を実施することによって、第４の図形を生成し、前記第４の図形のデータを前記データ格納部に格納するステップと、
前記データ格納部に格納されている前記第１の図形のデータに係る前記第１の図形から前記データ格納部に格納されている前記第４の図形のデータに係る前記第４の図形を除去する、図形についての差演算を実施することによって、第５の図形を生成し、前記第５の図形のデータを前記データ格納部に格納するステップと、
を、コンピュータに実行させるための図形処理プログラム。
【請求項２】
前記データ格納部に格納されている前記第１の図形のデータに係る前記第１の図形の各辺を当該第１の図形の内側方向に所定長移動し、移動後の辺及び当該移動後の辺の交点を所定の方向で辿ることで特定される第６の図形を生成し、前記第６の図形のデータを前記データ格納部に格納する図形生成ステップと、
前記データ格納部に格納されている前記第６の図形のデータに係る前記第６の図形の第１の辺の各々を両側に前記所定長だけ移動させた第２の辺の頂点を、前記第１の辺の頂点を中心として前記所定長を半径とする円弧で結ぶことで、第７の図形を生成し、前記第７の図形のデータを前記データ格納部に格納するステップと、
前記データ格納部に格納されている前記第６の図形のデータに係る前記第６の図形と、前記データ格納部に格納されている前記第７の図形のデータに係る前記第７の図形との、図形についての論理和演算を実施することによって、前記第２の図形を生成し、前記第２の図形のデータを前記データ格納部に格納するステップと、
をさらに前記コンピュータに実行させるための請求項１記載の図形処理プログラム。
【請求項３】
複数の辺で形成される第１の図形のデータ及び前記第１の図形のうち所定長を半径とする円によって塗り込みが行われる部分を表す第２の図形のデータを格納するデータ格納部に格納されている前記第１の図形のデータに係る前記第１の図形の各辺を当該第１の図形の内側方向に所定長移動し、前記第１の図形の頂点のうち角度が許容角度より大きい頂点を形成する複数の辺が移動後に交わる点を中心とし前記所定長を半径とする円を生成し、当該円と当該移動前の辺とにより囲まれる閉領域を特定することで、第３の図形を生成し、前記第３の図形のデータを前記データ格納部に格納するステップと、
前記データ格納部に格納されている前記第３の図形のデータに係る前記第３の図形のうち前記第１の図形内に含まれる前記第３の図形と、前記データ格納部に格納されている前記第２の図形のデータに係る前記第２の図形との、図形についての論理和演算を実施することによって、第４の図形を生成し、前記第４の図形のデータを前記データ格納部に格納するステップと、
前記データ格納部に格納されている前記第１の図形のデータに係る前記第１の図形から前記データ格納部に格納されている前記第４の図形のデータに係る前記第４の図形を除去する、図形についての差演算を実施することによって、第５の図形を生成し、前記第５の図形のデータを前記データ格納部に格納するステップと、
を含み、コンピュータにより実行される図形処理方法。
【請求項４】
前記データ格納部に格納されている前記第１の図形のデータに係る前記第１の図形の各辺を当該第１の図形の内側方向に所定長移動し、移動後の辺及び当該移動後の辺の交点を所定の方向で辿ることで特定される第６の図形を生成し、前記第６の図形のデータを前記データ格納部に格納する図形生成ステップと、
前記データ格納部に格納されている前記第６の図形のデータに係る前記第６の図形の第１の辺の各々を両側に前記所定長だけ移動させた第２の辺の頂点を、前記第１の辺の頂点を中心として前記所定長を半径とする円弧で結ぶことで、第７の図形を生成し、前記第７の図形のデータを前記データ格納部に格納するステップと、
前記データ格納部に格納されている前記第６の図形のデータに係る前記第６の図形と、前記データ格納部に格納されている前記第７の図形のデータに係る前記第７の図形との、図形についての論理和演算を実施することによって、前記第２の図形を生成し、前記第２の図形のデータを前記データ格納部に格納するステップと、
をさらに含む請求項３記載の図形処理方法。
【請求項５】
複数の辺で形成される第１の図形のデータ及び前記第１の図形のうち所定長を半径とする円によって塗り込みが行われる部分を表す第２の図形のデータを格納するデータ格納部と、
前記データ格納部に格納されているデータを用いて処理を実施する処理部と、
を有し、
前記処理部は、
データ格納部に格納されている前記第１の図形のデータに係る前記第１の図形の各辺を当該第１の図形の内側方向に前記所定長移動し、前記第１の図形の頂点のうち角度が許容角度より大きい頂点を形成する複数の辺が移動後に交わる点を中心とし前記所定長を半径とする円を生成し、当該円と当該移動前の辺とにより囲まれる閉領域を特定することで、第３の図形を生成し、前記第３の図形のデータを前記データ格納部に格納し、
前記データ格納部に格納されている前記第３の図形のデータに係る前記第３の図形のうち前記第１の図形内に含まれる前記第３の図形と、前記データ格納部に格納されている前記第２の図形のデータに係る前記第２の図形との、図形についての論理和演算を実施することによって、第４の図形を生成し、前記第４の図形のデータを前記データ格納部に格納し、
前記データ格納部に格納されている前記第１の図形のデータに係る前記第１の図形から前記データ格納部に格納されている前記第４の図形のデータに係る前記第４の図形を除去する、図形についての差演算を実施することによって、第５の図形を生成し、前記第５の図形のデータを前記データ格納部に格納する、
図形処理装置。
【請求項６】
前記処理部は、
前記データ格納部に格納されている前記第１の図形のデータに係る前記第１の図形の各辺を当該第１の図形の内側方向に所定長移動し、移動後の辺及び当該移動後の辺の交点を所定の方向で辿ることで特定される第６の図形を生成し、前記第６の図形のデータを前記データ格納部に格納し、
前記データ格納部に格納されている前記第６の図形のデータに係る前記第６の図形の第１の辺の各々を両側に前記所定長だけ移動させた第２の辺の頂点を、前記第１の辺の頂点を中心として前記所定長を半径とする円弧で結ぶことで、第７の図形を生成し、前記第７の図形のデータを前記データ格納部に格納し、
前記データ格納部に格納されている前記第６の図形のデータに係る前記第６の図形と、前記データ格納部に格納されている前記第７の図形のデータに係る前記第７の図形との、図形についての論理和演算を実施することによって、前記第２の図形を生成し、前記第２の図形のデータを前記データ格納部に格納する、
請求項５記載の図形処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、図形処理技術に関する。
【背景技術】
【０００２】
例えばプリント板を製造するため、プリント板の実装設計ＣＡＤ（Computer Aided Design）システムから製造データを出力する。この製造データには、アートワークフィルムを作成するためのガーバーデータが含まれる。ガーバーデータは面パターンなどの塗りつぶされるべき図形を所定半径の円の軌跡（円の直径幅の線）で表現する。ガーバーデータで表現できない部分が生じると実装設計ＣＡＤシステムからのデータとの間に矛盾が生じる。そのため、プリント板の実装設計ＣＡＤシステムでは面パターンに一定幅（ガーバーデータを表現するために用いる円の直径）の線で塗り込みを行い、塗り込みできない箇所（すなわち塗り込み幅違反箇所）を検出し、設計者にエラーとして表示したり、自動で修正したりしている。
【０００３】
塗り込み幅違反箇所を検出する従来技術の１つとして、図１において矢印で示すように面パターンを構成する多角形形状の辺同士の最短距離を求め、その距離と塗り込み幅を比較することで塗り込み幅違反箇所を検出する方法がある。この技術では、面パターンの辺同士の最短距離を求めるため、処理対象の面パターンの頂点が多くなると辺の数も増加し、辺と辺の組み合わせが膨大な数になり、処理時間が長くなる。具体的には、最悪ケースでは頂点数の２乗に比例した時間を要するため、頂点数が１００万を超える面パターンでは辺と辺の距離を算出する演算を１兆回行うことになってしまう。なお、塗り込み幅違反箇所を検出するだけではなく、ＥＭＣ（Electro-magnetic Compatibility）対策等で、一定角度以下の頂点を角取りするような処理も併せて実施することになる。なお、塗り込み違反は、塗り込み幅違反又は許容角度違反、若しくはその両方を表す。
【０００４】
別の従来技術としては、画像処理演算を行うことで、塗り込み幅違反箇所を検出する方法も存在している。この技術では、データを２次元メッシュデータとして扱うことになる。そのため、面パターンなどの図形データを１次元の頂点配列として保持する場合には、データを変換する処理を行うことになるため、余分な処理負荷がかかる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平５−２４２１９７号公報
【特許文献２】特開平６−２８４２５号公報
【特許文献３】特開２００５−３２１８４６号公報
【特許文献４】特開平７−５６９７８号公報
【非特許文献】
【０００６】
【非特許文献１】築添 明，小澤 時典，酒見 淳也，三浦 地平，石井 建基，”VLSIマスクデータに対する論理演算と交点計算を同時処理するパターン論理演算手法”，電子通信学会論文誌’86/6 Vol.J69-D No.6
【発明の概要】
【発明が解決しようとする課題】
【０００７】
従って、本技術の目的は、一側面においては、塗り込み違反箇所についての処理を高速実行できるようにするための技術を提供することである。
【課題を解決するための手段】
【０００８】
本図形処理方法は、（Ａ）複数の辺で形成される第１の図形のデータを格納するデータ格納部に格納されているデータに係る第１の図形の各辺を当該第１の図形の内側方向に所定長移動し、移動後の辺及び当該移動後の辺の交点を所定の方向で辿ることで特定される第２の図形を生成し、第２の図形のデータをデータ格納部に格納する図形生成ステップと、（Ｂ）データ格納部に格納されている上記データに係る第２の図形の第１の辺の各々を両側に所定長だけ移動させた第２の辺の頂点を、第１の辺の頂点を中心として所定長を半径とする円弧で結ぶことで、第３の図形を生成し、第３の図形のデータをデータ格納部に格納するステップと、（Ｃ）データ格納部に格納されている上記データに係る第２の図形と第３の図形との、図形についての論理和演算を実施することによって、第４の図形を生成し、第４の図形のデータをデータ格納部に格納するステップとを含む。
【発明の効果】
【０００９】
一側面において、塗り込み違反箇所についての処理を高速実行できるようになる。
【図面の簡単な説明】
【００１０】
【図１】図１は、従来の技術を説明するための図である。
【図２】図２は、本実施の形態に係る図形処理装置の機能ブロック図である。
【図３】図３は、図形データの保持の仕方を説明するための図である。
【図４】図４は、処理対象の図形の一例を示す図である。
【図５】図５は、修正図形生成処理の処理フローを示す図である。
【図６】図６は、第１図形処理の処理フローを示す図である。
【図７Ａ】図７Ａは、線分の辺の平行移動処理を説明するための図である。
【図７Ｂ】図７Ｂは、線分の辺の平行移動処理を説明するための図である。
【図７Ｃ】図７Ｃは、線分の辺の平行移動処理を説明するための図である。
【図７Ｄ】図７Ｄは、線分の辺の平行移動処理を説明するための図である。
【図８Ａ】図８Ａは、円弧の辺の平行移動処理を説明するための図である。
【図８Ｂ】図８Ｂは、円弧の辺の平行移動処理を説明するための図である。
【図８Ｃ】図８Ｃは、円弧の辺の平行移動処理を説明するための図である。
【図８Ｄ】図８Ｄは、円弧の辺の平行移動処理を説明するための図である。
【図９Ａ】図９Ａは、円弧の辺の平行移動処理を説明するための図である。
【図９Ｂ】図９Ｂは、円弧の辺の平行移動処理を説明するための図である。
【図９Ｃ】図９Ｃは、円弧の辺の平行移動処理を説明するための図である。
【図１０】図１０は、処理対象の図形に対して修正後図形生成における第１段階目の処理を実施した後の図形を示す図である。
【図１１】図１１は、処理対象の図形に対して修正後図形生成における第２段階目の処理を実施した後の図形を示す図である。
【図１２】図１２は、第２図形処理の概要を説明するための図である。
【図１３】図１３は、第２図形処理の概要を説明するための図である。
【図１４】図１４は、第２図形処理の処理フローを示す図である。
【図１５Ａ】図１５Ａは、線分の辺の膨張処理を説明するための図である。
【図１５Ｂ】図１５Ｂは、線分の辺の膨張処理を説明するための図である。
【図１５Ｃ】図１５Ｃは、線分の辺の膨張処理を説明するための図である。
【図１５Ｄ】図１５Ｄは、線分の辺の膨張処理を説明するための図である。
【図１５Ｅ】図１５Ｅは、線分の辺の膨張処理を説明するための図である。
【図１６Ａ】図１６Ａは、円弧の辺の膨張処理を説明するための図である。
【図１６Ｂ】図１６Ｂは、円弧の辺の膨張処理を説明するための図である。
【図１６Ｃ】図１６Ｃは、円弧の辺の膨張処理を説明するための図である。
【図１７】図１７は、処理対象の図形に対して修正後図形生成における第３段階目の処理を実施した後の図形を示す図である。
【図１８】図１８は、処理対象の図形に対して修正後図形生成における第４段階目の処理を実施した後の図形を示す図である。
【図１９】図１９は、塗り込み違反箇所検出の処理フローを示す図である。
【図２０】図２０は、第３図形処理の処理フローを示す図である。
【図２１】図２１は、処理対象の図形に対して塗り込み違反箇所検出における第１段階目の処理を実施した後の図形を示す図である。
【図２２】図２２は、第３図形処理の処理フローを示す図である。
【図２３】図２３は、平行移動後の辺の交点に円を発生する処理を説明するための図である。
【図２４】図２４は、処理対象の図形に対して塗り込み違反箇所検出における第２段階目の処理を実施した後の図形を示す図である。
【図２５】図２５は、円弧図形の生成を説明するための図である。
【図２６】図２６は、処理対象の図形に対して塗り込み違反箇所検出における第３段階目の処理を実施した後の図形を示す図である。
【図２７】図２７は、図２６の一部を拡大及び分解した図である。
【図２８】図２８は、第３図形処理の処理フローを示す図である。
【図２９】図２９は、第４図形処理を説明するための図である。
【図３０】図３０は、第４図形処理を説明するための図である。
【図３１】図３１は、第４図形処理を説明するための図である。
【図３２】図３２は、第４図形処理を説明するための図である。
【図３３】図３３は、円弧のなす角度を説明するための図である。
【図３４】図３４は、円弧のなす角度を説明するための図である。
【図３５】図３５は、図形テーブルの一例を示す図である。
【図３６】図３６は、第４図形処理を説明するための図である。
【図３７】図３７は、第４図形処理を説明するための図である。
【図３８】図３８は、第４図形処理の処理フローを示す図である。
【図３９】図３９は、包含判定処理の処理フローを示す図である。
【図４０】図４０は、処理対象の図形に対して塗り込み違反箇所検出における第４段階目の処理を実施した後の図形を示す図である。
【図４１】図４１は、図形のＯＲ演算を説明するための図である。
【図４２】図４２は、処理対象の図形に対して塗り込み違反箇所検出における第５段階目の処理を実施した後の図形を示す図である。
【図４３】図４３は、処理対象の図形に対して塗り込み違反箇所検出における第６段階目の処理を実施した後の図形を示す図である。
【図４４】図４４は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００１１】
本技術の実施の形態に係る図形処理装置１００の機能ブロック図を図２に示す。図形処理装置１００は、図形データ格納部１０１と、設定データ格納部１０２と、修正図形生成部１０３と、違反箇所検出部１０４と、データ格納部１０５と、出力部１０６とを有する。さらに、図形処理装置１００は、修正図形生成部１０３及び違反箇所検出部１０４と連携して処理を実施する個別の演算部として、辺移動処理部１１１と、円弧結合処理部１１２と、辺膨張処理部１１３と、円弧生成部１１４と、包含判定部１１５と、図形データ反転部１１６と、図形演算部１１７とを有する。
【００１２】
修正図形生成部１０３は、図形データ格納部１０１に格納されている処理対象の図形データを、設定データ格納部１０２に従って処理して、処理途中のデータ及び処理結果のデータをデータ格納部１０５に格納する。違反箇所検出部１０４は、図形データ格納部１０１及びデータ格納部１０５に格納されている図形データを、設定データ格納部１０２に従って処理して、処理途中のデータ及び処理結果のデータをデータ格納部１０５に格納する。出力部１０６は、例えば表示装置や印刷装置等の出力装置に、データ格納部１０５に格納されている図形データを表示する。
【００１３】
辺移動処理部１１１は、辺の平行移動処理を実施する。円弧結合処理部１１２は、平行移動した辺を連結する円弧を生成する。辺膨張処理部１１３は、辺を膨張させる長円図形を生成する。円弧生成部１１４は、平行移動後の辺の交点に円を生成する。包含判定部１１５は、ある図形に他の図形が包含されるかを判定するための処理を実施する。図形データ反転部１１６は、図形の頂点の保持方向を反転させる。図形演算部１１７は、ＯＲ演算など図形に対する演算を実施する。
【００１４】
本実施の形態では、図形データは、図３に示すような順序の頂点配列として図形データ格納部１０１及びデータ格納部１０５に保持される。各頂点は、ｘ軸及びｙ軸で張られる２次元平面上の座標値で定義される。そして、図形の外形は、反時計周りに頂点を保持することで規定される。図３において外形を表す矩形は、反時計回りで頂点番号１から５までの頂点で規定される。また、打ち抜きは、時計周りに頂点を保持することで規定される。図３において打ち抜きを表す三角形は、時計回りで頂点番号６から９までの頂点で規定される。さらに、辺である円弧は、円弧の始点、中間点及び終点の順番で頂点が保持される。また、円弧には円弧であるという情報を別途保持させ、線分と円弧の区別ができるようになっている。また、円弧が一周して円を形成する場合は、半円に分割された円弧として情報を保持する。図３において打ち抜きを表す円の上側の半円について、時計回りに始点、中間点及び終点が頂点番号１０乃至１２の頂点で規定される。下側の半円について、時計回りに始点、中間点及び終点が頂点番号１２乃至１４の頂点で規定される。
【００１５】
また、設定データ格納部１０２には、塗り込み円の半径及び違反と判定される頂点の角度（すなわち許容角度）の値が格納されている。なお、一般的に許容角度はｒ度以下ということになるので、この「ｒ」という値が設定データ格納部１０２に格納される。
【００１６】
次に、図４乃至図４３を用いて図形処理装置１００の処理内容を説明する。まず、処理対象の図形について塗り込み違反箇所を修正した後の図形のデータを生成する際の処理を図４乃至図１８を用いて説明する。
【００１７】
また、説明を分かりやすくするために、図４に示すような面パターンが処理対象の図形であるものとする。すなわち、図４に示すような図形のデータが、図形データ格納部１０１に格納されているものとする。
【００１８】
まず、修正図形生成部１０３は、図形データ格納部１０１から処理対象の図形データを読み出すと共に、設定データ格納部１０２から塗り込み円の半径を読み出す（図５：ステップＳ１）。次に、修正図形生成部１０３は、第１図形処理を実施する（ステップＳ３）。この第１図形処理は、辺を処理対象の図形の内側に移動させ、移動後の辺の端点を円弧で結ぶ処理である。この処理の詳細については、図６乃至図１０を用いて説明する。
【００１９】
まず、修正図形生成部１０３は、処理対象の図形の未処理の頂点を１つ特定する（図６：ステップＳ２１）。例えば、頂点番号の小さい順に処理を行うものとする。そして、修正図形生成部１０３は、特定された頂点を始点として含む辺を特定する（ステップＳ２３）。そして、修正図形生成部１０３は、辺移動処理部１１１に、特定された辺に対する処理を指示する。
【００２０】
辺移動処理部１１１は、特定された辺が線分であるか判断する（ステップＳ２５）。特定された辺が線分であれば、辺移動処理部１１１は、辺を図形の内側に塗り込み円の半径だけ平行移動させる処理を実施する（ステップＳ２７）。処理結果は、データ格納部１０５に格納される。その後処理はステップＳ３１に移行する。
【００２１】
本ステップの処理を図７Ａ乃至図７Ｄを用いて具体的に説明する。まず、図７Ａに示すような辺を、図７Ｂに示すように辺の始点を中心として、ｘ軸と辺とがなす角度が０となるように、辺を回転させる。そして、図７Ｃに示すように、回転移動後の辺を、ｙ軸の正方向に塗り込み円の半径（点線直線矢印の長さ）だけ平行移動する。最後に、図７Ｄに示すように、平行移動前の辺の始点を中心として、図７Ｂとは逆方向に同角度だけ、平行移動後の辺を回転させる。このようにすれば、図形の内側に塗り込み円の半径分平行移動させた辺を得ることができる。その後、処理はステップＳ３１に移行する。
【００２２】
一方、辺が円弧である場合には、辺移動処理部１１１は、特定された円弧に応じた円弧を生成し、配置することで、円弧の平行移動処理を実施する（ステップＳ２９）。処理結果はデータ格納部１０５に格納される。その後、処理はステップＳ３１に移行する。
【００２３】
本ステップの処理を図８Ａ乃至図８Ｄ及び図９Ａ乃至図９Ｃを用いて具体的に説明する。まず、図８Ａに示すような円弧を、図８Ｂに示すように円弧の始点を中心として、円弧の始点と終点とを結ぶ線とｘ軸とがなす角度が０となるように回転させる。そして図８Ｂの状態において、円弧の中間点が、円弧の始点と終点とを結んだ線の上側にあるのか（すなわちｙ軸の正方向）、下側にあるのか（すなわちｙ軸の負の方向）を判断する。図８Ｂの場合には下側に存在している。下側に存在している場合には、図８Ｃに示すように、円弧の半径を、塗り込み円の半径分（点線直線矢印の長さ分）短くした円弧を生成する。逆に、上側に存在している場合には、円弧の半径を、塗り込み円の半径分長くした円弧を生成する。生成された円弧の始点、中間点及び終点は、元の円弧の始点、中間点及び終点から算出することができるが、この方法はよく知られているので説明は省略する。最後に、図８Ｄに示すように、元の円弧の始点を中心として、図８Ｂとは逆方向に同角度だけ、生成した円弧を回転させる。
【００２４】
なお、円弧の半径が、塗り込み円の半径より短い場合もある。図９Ａは円弧を表しており、図９Ｂは円弧の半径より長い半径を有する塗り込み円を示している。このような場合、図９Ｃに示すように、塗り込み円の半径から円弧の半径を減算した長さの半径を有しており、ふくらみ方向が逆になる円弧を生成する。この際、生成した円弧の始点は、元の円弧の始点から中心点を介して交差した位置になり、生成した円弧の終点も、元の円弧の終点から中心点を介して交差した位置になる。
【００２５】
そして、修正図形生成部１０３は、特定された頂点が外形又は打ち抜きの始点であるか確認する（ステップＳ３１）。特定された頂点が外形又は打ち抜きの始点である場合にはステップＳ３９に移行する。一方、特定された頂点が外形又は打ち抜きの始点ではない場合には、修正図形生成部１０３は、平行移動後の辺の始点に対する処理を、円弧結合処理部１１２に指示する。
【００２６】
これに対して円弧結合処理部１１２は、第１の円弧結合処理を実施する（ステップＳ３３）。具体的には、今回の平行移動後の辺の始点を終点とし、直前に平行移動された辺の終点を始点とし、特定された頂点を中心とする時計回りの円弧を生成する。そして生成した円弧によって、今回の平行移動後の辺の始点と、直前に平行移動された辺の終点とを結合する。
【００２７】
また、修正図形生成部１０３は、特定された頂点が外形又は打ち抜きの終点であるか確認する（ステップＳ３５）。特定された頂点が外形又は打ち抜きの終点である場合には、修正図形生成部１０３は、円弧結合処理部１１２に、平行移動後の辺の終点に対する処理を指示する。
【００２８】
これに対して円弧結合処理部１１２は、第２の円弧結合処理を実施する（ステップＳ３７）。具体的には、外形又は打ち抜きの始点について実施した平行移動後の辺の始点を終点とし、今回平行移動された辺の終点を始点とし、外形又は打ち抜きの始点を中心とする時計回りの円弧を生成する。そして生成した円弧によって、外形又は打ち抜きの始点について実施した平行移動後の辺の始点と、今回の平行移動された辺の終点とを結合する。
【００２９】
特定された頂点が外形又は打ち抜きの終点である場合又はステップＳ３７の後に、修正図形生成部１０３は、未処理の頂点が存在しているか判断する（ステップＳ３９）。未処理の頂点が存在している場合には、ステップＳ２１に戻る。一方、未処理の頂点が存在していない場合には、元の処理に戻る。このように生成された図形のデータは、データ格納部１０５に格納される。
【００３０】
このような処理を実施することで、図４に示した処理対象の図形（図形Ａとする）から、図１０のような図形（図形Ｂとする）が生成される。図１０の図形において、細点線矢印は塗り込み円の半径を表しており、図形Ａの辺が塗り込み円の半径だけ内側に平行移動されていることが分かる。また、平行移動後の辺の端点は時計回りの円弧で結合されている。平行移動後の辺が交差する場合には、飛び出る形に円弧が生成されるが、円弧ａ１及びａ２のように、平行移動後の辺が交差しない場合には、円弧によって平行移動後の辺が繋がれる。打ち抜きの円弧については、図形の内側に平行移動させるため、打ち抜きの円弧よりも大きな円弧が生成されている。この例では、平行移動後の円弧は互いに交差しており、外形に近い方の円弧については平行移動後の円弧が、外形について平行移動させた後の辺とも交差するようになる。このような処理を実施することで、外形についての辺は、平行移動後も一筆書きできるようになっている。
【００３１】
図５の処理の説明に戻って、修正図形生成部１０３は、図形演算部１１７に指示して、第１図形処理により生成された図形Ｂから、打ち抜き部分を除き時計回りの頂点配列を除去した連続する外形の図形Ｃを生成させ、当該図形Ｃのデータをデータ格納部１０５に格納する（ステップＳ５）。
【００３２】
図形Ｂにおいて、平行移動後の辺及び当該平行移動後の辺の交点を反時計回りで辿ることで外形を特定し、時計回りで頂点が配置されている閉領域を削除する。なお、図形内部に、外形についての平行移動後の辺と交差しない平行移動後の辺が残っている場合には、時計回りの頂点配置であっても当該平行移動後の辺を残す。図１０のような図形Ｂからは、図１１のような図形Ｃが生成される。図１１から分かるように、時計回りで頂点が配置されている閉領域は削除されるため点線で表されており、平行移動後の辺及び当該平行移動後の辺の交点を反時計回りで辿ることで特定される外形は、実線で示されている。なお、本例では打ち抜きの辺は平行移動させると互いに交差してしまうので、打ち抜きは無くなってしまう。
【００３３】
このような処理は、例えば特開平２−１３２５６９号公報に開示されている手法を用いればよいので、詳細な説明については省略する。このような手法を採用する場合には、頂点数×頂点数の対数に比例する時間で処理できることが知られている。すなわち、処理速度が高速化される。
【００３４】
次に、修正図形生成部１０３は、データ格納部１０５に格納されている図形のデータを読み出し、第２図形処理を実施する（ステップＳ７）。この第２図形処理は、ステップＳ５で生成された図形Ｃの辺を膨張させる処理である。具体的には、図１２の左側に示すような線分の場合には、塗り込み円の半径分だけ上下に平行移動させた後、線分の両端を中心とし、塗り込み円の半径と同じ長さの半径を有する円弧で結ぶことで、図１２の右側に示すような長円図形を生成する。また、図１３の左側に示すような円弧の場合には、外側に塗り込み円の半径分長い半径を有する円弧と、内側に塗り込み円の半径分短い半径を有する円弧とを生成し、円弧の端点を中心とし、塗り込み円の半径と同じ半径を有する円弧で結ぶことで、図１３の右側に示すような長円図形を生成する。この処理の詳細については、図１４乃至図１７を用いて説明する。
【００３５】
まず、修正図形生成部１０３は、処理対象の図形の未処理の頂点を１つ特定する（図１４：ステップＳ４１）。例えば、頂点番号の小さい順に処理を行うものとする。そして、修正図形生成部１０３は、特定された頂点を始点として含む辺を特定する（ステップＳ４３）。そして、修正図形生成部１０３は、辺膨張処理部１１３に、特定された辺に対する処理を指示する。
【００３６】
これに対して辺膨張処理部１１３は、特定された辺が線分であるか判断する（ステップＳ４５）。特定された辺が線分であれば、辺膨張処理部１１３は、辺を上下に塗り込み円の半径だけ平行移動した辺を生成する処理を実施する（ステップＳ４７）。その後処理はステップＳ５１に移行する。
【００３７】
本ステップの処理を図１５Ａ乃至１５Ｅを用いて具体的に説明する。まず、図１５Ａに示すような辺を、図１５Ｂに示すように辺の始点を中心として、ｘ軸と辺とがなす角度が０となるように、辺を回転させる。そして、図１５Ｃに示すように、回転移動後の辺を、ｙ軸の正方向及び負方向に塗り込み円の半径（点線直線矢印の長さ）だけ平行移動した辺を生成する。そして、図１５Ｄに示すように、平行移動前の辺の始点を中心として、図１５Ｂとは逆方向に同角度だけ、平行移動後の辺を回転させる。なお、図１５Ｅで示すような、エッジを円弧で結合する処理は、ステップＳ５１で実施される。
【００３８】
一方、特定された辺が円弧であれば、辺膨張処理部１１３は、円弧の半径を塗り込み円の半径だけ伸縮させた円弧を生成する処理を実施する（ステップＳ４９）。処理結果はデータ格納部１０５に格納される。その後、処理はステップＳ５１に移行する。
【００３９】
本ステップの処理を図１６Ａ乃至１６Ｃを用いて具体的に説明する。まず、図１６Ａに示すような円弧を、図１６Ｂに示すように、円弧の半径を、塗り込み円の半径分（点線直線矢印の長さ分）短くした円弧と、塗り込み円の半径（点線直線矢印の長さ分）長くした円弧とを生成する。生成された円弧の始点、中間点及び終点は、元の円弧の始点、中間点及び終点から算出することができるが、この方法はよく知られているので説明は省略する。なお、図１６Ｃで示すような、エッジを円弧で結合する処理は、ステップＳ５１で実施される。
【００４０】
そして、辺膨張処理部１１３は、特定された辺の端点を中心とし、塗り込み円の半径を有する円弧で、生成した線分又は円弧の端点を結合し、長円図形を生成する（ステップＳ５１）。処理結果はデータ格納部１０５に格納される。
【００４１】
その後、修正図形生成部１０３は、未処理の頂点が存在しているか判断する（ステップＳ５３）。未処理の頂点が存在している場合には、ステップＳ４１に戻る。一方、未処理の頂点が存在していない場合には、元の処理に戻る。このように生成された図形のデータは、データ格納部１０５に格納される。
【００４２】
このような処理を実施すると、図１１に示すような図形Ｃから、図１７に示すような図形Ｄが生成される。長円図形が重なりつつ外形を辿るような形となる。但し、図形Ｃの内部で重ならない部分も出てくる。また、長円図形は角が丸くなるので、処理対象の図形Ａと重ねてみると、角が一部欠けるようになっている。
【００４３】
図５の処理の説明に戻って、修正図形生成部１０３は、図形演算部１１７に指示して、ステップＳ５で生成された図形ＣとステップＳ７で生成された図形Ｄとについて図形のＯＲ演算（論理和演算）を実施させ、塗り込み違反部分を修正した修正後図形Ｅを生成し、修正後図形Ｅのデータをデータ格納部１０５に格納する（ステップＳ９）。図形のＯＲ演算については、例えば特開平２−１３２５６９号公報に開示されている手法を用いればよいので、詳細な説明については省略する。
【００４４】
図１１の図形Ｃと図１７の図形ＤとのＯＲ演算を実施すると、図１８に示すような図形Ｅが生成される。図形Ｅは、塗り込み幅違反部分が除去され、許容角度違反部分が除去されている。
【００４５】
そして、出力部１０６は、データ格納部１０５に格納されている図形Ｅのデータを読み出し、表示装置等の出力装置に出力する（ステップＳ１１）。図１８に示すような図形が表示装置等に出力される。このようにすれば、設計者は、修正後の図形を自動的に得ることができ、修正の手間が少なくなる。
【００４６】
また、上で示した処理は頂点数×頂点数の対数に比例した処理量で済むため、処理速度が高速化される。
【００４７】
次に、処理対象図形の塗り込み幅違反箇所及び許容角度違反箇所を検出して表示する処理について図１９乃至図４３を用いて説明する。なお、図５の処理が完了しているものとする。
【００４８】
まず、違反箇所検出部１０４は、図形データ格納部１０１から処理対象の図形のデータを読み出し、設定データ格納部１０２から塗り込み円の半径及び許容角度の値を読み出す（図１９：ステップＳ１０１）。
【００４９】
そして、違反箇所検出部１０４は、第３図形処理を実施する（ステップＳ１０３）。第３図形処理は、辺の平行移動と、平行移動後の辺の交点について平行移動前の角度が許容角度以上であれば円を生成する処理である。詳細については、図２０乃至図２６を用いて説明する。
【００５０】
まず、違反箇所検出部１０４は、フラグｔを０にセットする（図２０：ステップＳ１２１）。フラグｔは、外形又は打ち抜き終点についての処理か否かを表すフラグであり、外形又は打ち抜き終点についての処理であれば「１」にセットされる。
【００５１】
そして、違反箇所検出部１０４は、処理対象の図形の未処理の頂点を１つ特定する（ステップＳ１２３）。例えば、頂点番号の小さい順に処理を行うものとする。また、違反箇所検出部１０４は、特定された頂点を始点として含む辺を特定する（ステップＳ１２５）。そして、違反箇所検出部１０４は、辺移動処理部１１１に、特定された辺に対する処理を指示する。
【００５２】
これに対して辺移動処理部１１１は、特定された辺が線分であるか判断する（ステップＳ１２７）。特定された辺が線分であれば、辺移動処理部１１１は、辺を図形の内側に塗り込み円の半径だけ平行移動させる処理を実施する（ステップＳ１２９）。この処理は、ステップＳ２７と同じであるので、詳細な説明は省略する。その後、処理はステップＳ１３３に移行する。
【００５３】
一方、辺が円弧である場合には、辺移動処理部１１１は、特定された円弧に応じた円弧を生成し、配置することで、円弧の平行移動処理を実施する（ステップＳ１３１）。この処理もステップＳ２９と同様であるから、詳細な説明を省略する。その後、処理はステップＳ１３３に移行する。
【００５４】
なお、図４に示した処理対象の図形に対してここまでの処理を全ての辺について実施すると、図２１に示すようになる。図２１の例では、以下で述べるように平行移動後の他の辺と交点を有しない場合には処理の対象から除外されるので、処理の対象から除外される辺について示されていない。また、図２１の例では、打ち抜きについては平行移動後の辺を示していないが、これは以下の処理で特に影響がなく、説明を簡略化するためであって、実際には打ち抜きについても処理する。
【００５５】
そして、違反箇所検出部１０４は、特定された頂点が、外形又は打ち抜きの始点であるか確認する（ステップＳ１３３）。特定された頂点が外形又は打ち抜きの始点である場合には端子Ａを介して図２８のステップＳ１５７に移行する。
【００５６】
一方、特定された頂点が外形又は打ち抜きの始点ではない場合には、違反箇所検出部１０４は、今回の平行移動後の辺が、直前に平行移動された辺と交点を有するか判断する（ステップＳ１３５）。今回の平行移動後の辺が、直前に平行移動された辺と交点を有する場合には、端子Ｂを介して図２２の処理に移行する。一方、今回の平行移動後の辺が、直前に平行移動された辺と交点を有しない場合には、端子Ｃを介して図２８の処理に移行する。
【００５７】
次に、端子Ｂを介して移行した後の処理を、図２２を用いて説明する。ここで、違反箇所検出部１０４は、この交点について平行移動前の辺の角度は許容角度以下であるか判断する（ステップＳ１３７）。図３３に示したように辺が円弧の場合は図３４のように円弧の接線を辺と考え角度を求める。平行移動前の辺の角度が許容角度以下である場合には、違反であるから以降の処理を実施せず、端子Ａを介して図２８のステップＳ１５７に移行する。一方、平行移動前の辺の角度が許容角度より大きい場合には、角度は問題ないので、違反箇所検出部１０４は、円弧生成部１１４に、この交点について円弧を発生させる処理を指示する。これに対して円弧生成部１１４は、この交点を中心に塗り込み円を生成する（ステップＳ１３９）。塗り込み円の半径は、設定データ格納部１０２に格納されている塗り込み円の半径と同じであるから、平行移動前の辺との接点が存在する可能性がある。例えば円弧生成部１１４は、生成した円と平行移動前の辺との接点を算出する（ステップＳ１４１）。図２３に示すように、平行移動後の辺（実線）の交点ｃに塗り込み円を生成すると、平行移動前の辺（点線）との接点ｄ及びｅが算出される。なお、平行移動前の辺の頂点ｆは、接点ｄ及びｅの間に存在している。
【００５８】
ここまでの処理を、図２１に示した図形に対して実施すると、図２４のような図形が得られる。図２４の例では、平行移動前の辺の頂点の角度が許容角度を超えている場合に、平行移動後の辺の交点に、塗り込み円が配置されている。この図形の左上の交点では、平行移動前の辺の頂点の角度αが許容角度以下であるため、塗り込み円は発生されない。
【００５９】
その後、円弧生成部１１４は、平行移動前の辺の頂点と、算出された接点と、生成した円（すなわち塗り込み円）とから、平行移動前の辺の頂点から接点までの辺と発生した円とで囲まれる円弧図形を生成する（ステップＳ１４３）。図２３の場合には、図２５に示すような円弧図形が生成される。すなわち、辺ｆｄ及び辺ｆｅと、交点Ｃを中心とする円とで囲まれる円弧図形を生成する。処理結果はデータ格納部１０５に格納される。
【００６０】
また、図２４に示した図形に対してステップＳ１４３を実施したとすると、図２６に示すような図形が生成される。図２６の例では、５つの交点に対して５つの円弧図形が生成される。左下の２つの円弧図形は、分離すると図２７に示すような２つの円弧図形が重なっているものである。図２６に示すような円弧図形が図形Ｆとして処理される。
【００６１】
図２２の処理の説明に戻って、違反箇所検出部１０４は、ｔが０であるか判断する（ステップＳ１４５）。ｔが０であれば、外形又は打ち抜きの終点についての処理ではないので、端子Ｃを介して図２８の処理に移行する。一方、ｔが１であれば、外形又は打ち抜き終点についての処理を実施したことになるので、違反箇所検出部１０４は、ｔを０に戻し（ステップＳ１４７）、端子Ａを介して図２８のステップＳ１５７に移行する。
【００６２】
次に、端子Ｃを介して移行した先の処理について図２８を用いて説明する。違反箇所検出部１０４は、特定された頂点が外形又は打ち抜きの終点であるか確認する（ステップＳ１４９）。特定された頂点が外形又は打ち抜きの終点ではない場合には、違反箇所検出部１０４は、未処理の頂点が存在しているか判断し（ステップＳ１５７）、未処理の頂点が存在している場合には、端子Ｄを介してステップＳ１２３に戻る。
【００６３】
一方、特定された頂点が外形又は打ち抜きの終点である場合には、違反箇所検出部１０４は、今回平行移動した辺が、この外形又は打ち抜きについて最初に平行移動した辺との交点を有するか判断する（ステップＳ１５１）。今回平行移動した辺が、この外形又は打ち抜きについて最初に平行移動した辺との交点を有していない場合には、ステップＳ１５７に移行する。一方、今回平行移動した辺が、この外形又は打ち抜きについて最初に平行移動した辺との交点を有する場合には、違反箇所検出部１０４は、平行移動前の辺の頂点の角度が許容角度以下であるか判断する（ステップＳ１５３）。角度が許容角度以下である場合には、円を発生させたりする処理は行わないのでステップＳ１５７に移行する。一方、角度が許容角度を超えている場合には、違反箇所検出部１０４は、フラグｔを１にセットし（ステップＳ１５５）、処理は端子Ｅを介して図２２のステップＳ１３９に移行する。これによって、円を発生させると共に円弧図形を生成する。
【００６４】
このような処理を実施することで、上でも述べたように、平行移動前の辺の頂点の角度が許容角度を超えている場合には、平行移動した辺の交点周辺に、図２６に示すように、円弧図形Ｆが生成されることになる。
【００６５】
図１９の処理の説明に戻って、違反箇所検出部１０４は、第４図形処理を実施する（ステップＳ１０５）。第４図形処理は、第３図形処理で生成された円弧図形Ｆのうち、処理対象の図形Ａに包含される円弧図形Ｆを特定する処理である。この処理の詳細については、図２９乃至図４３を用いて説明する。
【００６６】
例えば図２９に示すような図形（図形αと呼ぶ）に、図３０に示すような図形（図形β１乃至β３）が包含されるかを判定する場合を考える。図形αと図形β１乃至β３は、図３１に示すように配置されているものとする。そして、図３２に示すように、ｘ座標値の小さい順に、平面走査法を適用して、図形α及び図形β１乃至β３の各頂点において、周知のベントレーオットマン（Bentley-Ottman）の交差判定により、図形α及び図形β１乃至β３の各頂点を通る、ｙ軸に平行なスイープライン上の各辺間の交点を算出する。図形α及び図形β１乃至β３の交点についてもスイープラインが設定されて、同様にスイープライン上の交点が算出される。図３２の例では、スイープラインはＬ１乃至Ｌ１６が設定される。そして、各スイープライン上の交点については、ｙ座標が小さい順にソートされる。
【００６７】
なお、ｙ座標が同じ場合には、スイープラインとなす角が小さい順に並べる。円弧とスイープラインの交点のような場合には、円弧の接線とスイープラインとのなす角度を算出して判定する。
【００６８】
その後、図形αの外部か内部かをフラグｆで判定しつつ、図形αの外部で図形βを検出した場合には、図形βは包含されていないと判定する。
【００６９】
例えば、図３５に示すような図形βについての図形テーブルを用意しておく。そして、例えばスイープラインＬ３に着目して、ｙ座標値が小さい順にスイープラインＬ３と交差する辺をソートしておく。図３２から分かるように、図３６に示すような順番に辺がソートされる。すなわち、図形β１の辺、図形αの辺、図形β１の辺、図形αの辺の順番に並べられる。図形β１の辺と、図形αの辺との順番については、上で述べたようにスイープラインＬ３となす角度の小さい順で決定される。このスイープラインＬ３を処理する場合には、図形αの内部に入る前、すなわちフラグが０の状態で、図形β１の辺が出現することになるので、図形β１は、図形αの内部に包含されないことが分かる。すなわち、スイープラインＬ３を処理すると、図３７に示すように、図形テーブルにおいて図形β１に対して「１」がセットされ、図形β１が包含されないことが記録される。このような図形テーブル及び各スイープライン上の辺のソート結果については、図形処理装置１００のメインメモリなどの記憶装置に格納される。
【００７０】
以上の処理は、図３８及び図３９のような処理フローに従って行われる。まず、違反箇所検出部１０４は、包含判定部１１５に、処理対象の図形Ａに円弧図形Ｆが包含されるかを判定する包含判定処理を実施させる（図３８：ステップＳ１６１）。そして、違反箇所検出部１０４は、包含判定処理によって処理対象の図形Ａに包含されないと判定された円弧図形Ｆを削除する（ステップＳ１６３）。そして、元の処理に戻る。
【００７１】
次に、図３９を用いて、包含判定処理について説明する。まず、包含判定部１１５は、上で述べたように図形Ａと円弧図形Ｆとの頂点及び交点についてｘ座標値が小さい順にｙ軸に平行なスイープラインを設定すると共に、スイープライン毎に、交差する辺をｙ座標値でソートし、ソート結果を例えば図形処理装置１００のメインメモリなどの記憶装置に格納する（ステップＳ１７１）。
【００７２】
そして、包含判定部１１５は、未処理のスイープラインを１本特定する（ステップＳ１７３）。また、包含判定部１１５は、フラグｆを０にセットする（ステップＳ１７５）。フラグｆは、上でも述べたように、図形Ａの外側か内側かを設定するフラグであり、０は図形Ａの外側を表し、１は図形Ａの内側を表す。
【００７３】
そして、包含判定部１１５は、特定されたスイープラインについて、ソート結果の上位から未処理の辺を１つ特定する（ステップＳ１７７）。その後、包含判定部１１５は、特定された辺が図形α（処理対象の図形Ａ）の辺であるか判断する（ステップＳ１７９）。特定された辺が図形αの辺ではない場合には、包含判定部１１５は、フラグｆが０であるか判断する（ステップＳ１８１）。フラグｆが１であれば、ステップＳ１９１に移行する。一方、フラグｆが０であれば、図形αの外部で図形βが検出されたことになるので、包含判定部１１５は、図形テーブルにおいて、特定された辺の図形名に「１」を設定する（ステップＳ１８３）。すなわち、特定された辺の図形は、包含されていないと設定する。そして処理はステップＳ１９１に移行する。
【００７４】
一方、特定された辺が図形αの辺である場合には、包含判定部１１５は、フラグｆが０であるか判断する（ステップＳ１８５）。フラグｆが０であれば、包含判定部１１５は、フラグｆを１に設定する（ステップＳ１８７）。そして処理はステップＳ１９１に移行する。一方、フラグｆが１であれば、包含判定部１１５は、フラグｆを０に設定する（ステップＳ１８９）。そして処理はステップＳ１９１に移行する。すなわち、図形αの辺が検出され、既に図形αの内部であった場合には、図形αの外部に出たことを示すようにフラグｆを０に設定する。一方、図形αの外部であった場合には、図形αの内部に入ったことを示すようにフラグｆを１に設定する。
【００７５】
そして、包含判定部１１５は、全ての辺について処理したか判断し（ステップＳ１９１）、未処理の辺が存在する場合にはステップＳ１７７に戻る。一方、全ての辺について処理した場合には、包含判定部１１５は、全てのスイープラインについて処理したか判断する（ステップＳ１９３）。未処理のスイープラインが存在する場合にはステップＳ１７３に戻る。一方、全てのスイープラインを処理した場合には、元の処理に戻る。
【００７６】
このような処理を実施することで、図形テーブルに、包含されていないと判定された図形については「１」が設定され、包含されていると判定された図形については「０」が設定されている状態となる。
【００７７】
すなわち、図形テーブルにおいて「１」が設定されている円弧図形Ｆについては、図３８のステップＳ１６３で削除される。データ格納部１０５には、削除後の円弧図形Ｆが図形Ｇとして格納される。
【００７８】
図２６のような円弧図形の場合、左下の２つの円弧図形については、図４０に示すように、図形Ａに包含されていないので削除される。削除後の図形を図形Ｇとする。なお、ステップＳ１６３は、頂点数×頂点数の対数に比例する時間で処理することができる。
【００７９】
図１９の処理の説明に戻って、違反箇所検出部１０４は、データ格納部１０５に格納されている修正後図形Ｅと第４図形処理の処理結果である図形Ｇとに対してＯＲ演算（論理和演算）を実施させて図形Ｈを生成し、図形Ｈのデータをデータ格納部１０５に格納する（ステップＳ１０７）。
【００８０】
図４１に、これまでの処理で生成された図形Ｅと図形Ｇとを重ねて示す。重ねてみると、点線丸Ｇ1乃至Ｇ3で示すように、角の部分が図形Ｅでは丸くなっているが、図形Ｇではその角の部分が含まれる。従って、ＯＲ演算を実施すれば、図４２に示すように、図形Ｅに角の部分が足された図形Ｈが生成されることになる。
【００８１】
そして、違反箇所検出部１０４は、図形データ格納部１０１に格納されている図形Ａとデータ格納部１０５に格納されており且つステップＳ１０７のＯＲ演算で生成された図形Ｈとから、（図形Ａ−図形Ｈ）の図形演算を図形演算部１１７に実施させ、修正箇所を示すための図形Ｉを生成し、図形Ｉのデータをデータ格納部１０５に格納する（ステップＳ１０９）。
【００８２】
より具体的には、違反箇所検出部１０４は、図形データ反転部１１６に対して、図形Ｈの図形データを出力して、図形データにおける頂点の順番を反転させる。具体的には、外形についての頂点については時計回りに並べ替え、打ち抜きについては反時計回りに並び替える。そして、違反箇所検出部１０４は、図形Ｈの処理結果及び図形Ａのデータを、図形演算部１１７に出力する。そうすると、図形演算部１１７は、外形については時計回りの頂点についての辺を削除し、打ち抜きについては反時計回りの頂点についての辺を削除することで、（図形Ａ−図形Ｈ）という図形についての差演算を実施する。
【００８３】
図４２に示した図形Ａ−図形Ｈの結果は、図４３に示すような図形Ｉとなる。斜線部分が図形Ｉであり、塗り込み幅違反及び角度違反の箇所を示している。
【００８４】
出力部１０６は、データ格納部１０５に格納されており且つステップＳ１０９で生成された図形Ｉのデータを、表示装置等の出力装置に出力する（ステップＳ１１１）。このようにして、設計者は、問題箇所を容易に把握することができるようになる。
【００８５】
このように、面パターンの塗り込み違反箇所の修正（すなわち、塗り込み幅違反箇所を修正し、許容角度以下の部分の角取りをすること）を、図形の移動及び生成、図形演算処理で実施できるようになる。そして、辺の平行移動処理、辺を膨らませる処理がそれぞれ頂点数に比例する時間、図形演算が頂点数×頂点数の対数に比例する時間で行うことができるので、演算時間を頂点数×頂点数の対数に比例する時間に抑えることができるようになる。さらに、本実施の形態では同時に面パターンの角取りをも行えるので、角取り演算を別途行うこともない。
【００８６】
面パターンの塗り込み幅違反箇所及び許容角度違反箇所の検出についても、図形の移動及び生成、図形演算処理で実施できるようになる。そして、辺の平行移動処理、円弧図形を生成する処理が頂点数に比例する時間、包含判定処理が頂点数×頂点数の対数に比例する時間、図形演算が頂点数×頂点数の対数に比例する時間で行うことができるので、演算時間を頂点数×頂点数の対数に比例する時間に抑えることができるようになる。
【００８７】
以上本技術の実施の形態を説明したが、本技術はこれに限定されるものではない。例えば、図２の機能ブロック図は一例であって、必ずしも実際にプログラムモジュール構成と一致しない場合もある。また、処理フローについても、処理結果が変わらない限り、処理順番を入れ替えたり、並列実施するようにしても良い。
【００８８】
例えば、修正図形生成部１０３の処理と、違反箇所検出部１０４の処理の一部（修正後図形を使用するまでの処理）とは互いに並行して実施しても良い。
【００８９】
さらに、１台のコンピュータで実施するのではなく、複数台のコンピュータで上で述べた機能を実施するようにしても良い。
【００９０】
なお、上で述べた図形処理装置１００は、コンピュータ装置であって、図４４に示すように、メモリ２５０１とＣＰＵ２５０３とハードディスク・ドライブ（ＨＤＤ）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【００９１】
以上述べた本実施の形態をまとめると、以下のようになる。
【００９２】
本実施の形態に係る図形処理方法は、（Ａ）複数の辺で形成される第１の図形のデータを格納するデータ格納部に格納されているデータに係る第１の図形の各辺を当該第１の図形の内側方向に所定長移動し、移動後の辺及び当該移動後の辺の交点を所定の方向で辿ることで特定される第２の図形を生成し、第２の図形のデータをデータ格納部に格納する図形生成ステップと、（Ｂ）データ格納部に格納されている上記データに係る第２の図形の第１の辺の各々を両側に所定長だけ移動させた第２の辺の頂点を、第１の辺の頂点を中心として所定長を半径とする円弧で結ぶことで、第３の図形を生成し、第３の図形のデータをデータ格納部に格納するステップと、（Ｃ）データ格納部に格納されている上記データに係る第２の図形と第３の図形との、図形についての論理和演算を実施することによって、第４の図形を生成し、第４の図形のデータをデータ格納部に格納するステップとを含む。
【００９３】
このようにすれば、第１の図形における塗り込み幅違反箇所及び許容角度違反箇所を適切に修正した第４の図形が自動的に且つ高速に生成されることになる。
【００９４】
さらに、本図形処理方法は、（Ｄ）データ格納部に格納されている上記データに係る第１の図形の各辺を当該第１の図形の内側方向に所定長移動し、移動後の辺の交点のうち移動前の辺の角度が許容角度より大きい交点を中心とし所定長を半径とする円を生成し、当該円と当該移動前の辺とにより囲まれる閉領域を特定することで、第５の図形を生成し、第５の図形のデータをデータ格納部に格納するステップと、（Ｅ）データ格納部に格納されている上記データに係る第５の図形のうち第１の図形内に含まれる第５の図形と、データ格納部に格納されている上記データに係る第４の図形との、図形についての論理和演算を実施することによって、第６の図形を生成し、第６の図形のデータをデータ格納部に格納するステップと、（Ｆ）データ格納部に格納されている上記データに係る第１の図形からデータ格納部に格納されている上記データに係る第６の図形を除去する、図形についての差演算を実施することによって、第７の図形を生成し、第７のデータをデータ格納部に格納するステップとをさらに含むようにしても良い。
【００９５】
このようにすれば、第１の図形における塗り込み幅違反箇所及び許容角度違反箇所を表す第７の図形が自動的且つ高速に生成されることになる。
【００９６】
なお、上で述べた図形のデータが、第１の方向の順番で外形の頂点のデータを含み、第１の方向とは逆の第２の方向の順番で打ち抜きの頂点のデータを含む場合がある。この場合、上で述べた図形生成ステップが、移動後の辺の交点のうち外形についての交点及び当該交点を繋ぐ辺については、第１の方向で辿ることで特定される第２の図形を生成するステップを含む場合もある。このようにすれば、容易に第２の図形を生成することができる。
【００９７】
さらに、上で述べた図形生成ステップが、移動後の辺の端点を円弧で結ぶステップを含むようにしても良い。移動後の辺に交点がない場合には、このような円弧によって、移動後の外形又は打ち抜きの辺が適切に連結されるようになる。
【００９８】
なお、上で述べたような処理をコンピュータに実施させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭなどの光ディスク、光磁気ディスク、半導体メモリ（例えばＲＯＭ）、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。なお、処理途中のデータについては、ＲＡＭ等の記憶装置に一時保管される。
【００９９】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１００】
（付記１）
複数の辺で形成される第１の図形のデータを格納するデータ格納部に格納されている前記データに係る前記第１の図形の各辺を当該第１の図形の内側方向に所定長移動し、移動後の辺及び当該移動後の辺の交点を所定の方向で辿ることで特定される第２の図形を生成し、前記第２の図形のデータを前記データ格納部に格納する図形生成ステップと、
前記データ格納部に格納されている前記データに係る前記第２の図形の第１の辺の各々を両側に前記所定長だけ移動させた第２の辺の頂点を、前記第１の辺の頂点を中心として前記所定長を半径とする円弧で結ぶことで、第３の図形を生成し、前記第３の図形のデータを前記データ格納部に格納するステップと、
前記データ格納部に格納されている前記データに係る前記第２の図形と前記第３の図形との、図形についての論理和演算を実施することによって、第４の図形を生成し、前記第４の図形のデータを前記データ格納部に格納するステップと、
を、コンピュータに実行させるための図形処理プログラム。
【０１０１】
（付記２）
前記データ格納部に格納されている前記データに係る前記第１の図形の各辺を当該第１の図形の内側方向に前記所定長移動し、移動後の辺の交点のうち移動前の辺の角度が許容角度より大きい交点を中心とし前記所定長を半径とする円を生成し、当該円と当該移動前の辺とにより囲まれる閉領域を特定することで、第５の図形を生成し、前記第５の図形のデータを前記データ格納部に格納するステップと、
前記データ格納部に格納されている前記データに係る前記第５の図形のうち前記第１の図形内に含まれる前記第５の図形と、前記データ格納部に格納されている前記データに係る前記第４の図形との、図形についての論理和演算を実施することによって、第６の図形を生成し、前記第６の図形のデータを前記データ格納部に格納するステップと、
前記データ格納部に格納されている前記データに係る前記第１の図形から前記データ格納部に格納されている前記データに係る前記第６の図形を除去する、図形についての差演算を実施することによって、第７の図形を生成し、前記第７のデータを前記データ格納部に格納するステップと、
をさらに前記コンピュータに実行させるための付記１記載の図形処理プログラム。
【０１０２】
（付記３）
前記図形のデータが、第１の方向の順番で外形の頂点のデータを含み、前記第１の方向とは逆の第２の方向の順番で打ち抜きの頂点のデータを含み、
前記図形生成ステップが、
前記移動後の辺の交点のうち外形についての交点及び当該交点を繋ぐ辺については、前記第１の方向で辿ることで特定される前記第２の図形を生成するステップ
を含む付記１又は２記載の図形処理プログラム。
【０１０３】
（付記４）
前記図形生成ステップが、
前記移動後の辺の端点を円弧で結ぶステップ
を含む付記１乃至３のいずれか１つ記載の図形処理プログラム。
【０１０４】
（付記５）
複数の辺で形成される第１の図形のデータを格納するデータ格納部に格納されている前記データに係る前記第１の図形の各辺を当該第１の図形の内側方向に所定長移動し、移動後の辺及び当該移動後の辺の交点を所定の方向で辿ることで特定される第２の図形を生成し、前記第２の図形のデータを前記データ格納部に格納する第２図形生成ステップと、
前記データ格納部に格納されている前記データに係る前記第２の図形の第１の辺の各々を両側に前記所定長だけ移動させた第２の辺の頂点を、前記第１の辺の頂点を中心として前記所定長を半径とする円弧で結ぶことで、第３の図形を生成し、前記第３の図形のデータを前記データ格納部に格納するステップと、
前記データ格納部に格納されている前記データに係る前記第２の図形と前記第３の図形との、図形についての論理和演算を実施することによって、第４の図形を生成し、前記第４の図形のデータを前記データ格納部に格納するステップと、
を含み、コンピュータにより実行される図形処理方法。
【０１０５】
（付記６）
前記データ格納部に格納されている前記データに係る前記第１の図形の各辺を当該第１の図形の内側方向に前記所定長移動し、移動後の辺の交点のうち移動前の辺の角度が違反角度より大きい交点を中心とし前記所定長を半径とする円を生成し、当該円と当該移動前の辺とにより囲まれる閉領域を特定することで、第５の図形を生成し、前記第５の図形のデータを前記データ格納部に格納するステップと、
前記データ格納部に格納されている前記データに係る前記第５の図形のうち前記第１の図形内に含まれる前記第５の図形と、前記データ格納部に格納されている前記データに係る前記第４の図形との、図形についての論理和演算を実施することによって、第６の図形を生成し、前記第６の図形のデータを前記データ格納部に格納するステップと、
前記データ格納部に格納されている前記データに係る前記第１の図形から前記データ格納部に格納されている前記データに係る前記第６の図形を除去する、図形についての差演算を実施することによって、第７の図形を生成し、前記第７のデータを前記データ格納部に格納するステップと、
をさらに含む付記５記載の図形処理方法。
【０１０６】
（付記７）
複数の辺で形成される第１の図形のデータを格納するデータ格納部と、
前記データ格納部に格納されているデータを用いて処理を実施する処理部と、
を有し、
前記処理部は、
前記データ格納部に格納されている前記データに係る前記第１の図形の各辺を当該第１の図形の内側方向に所定長移動し、移動後の辺及び当該移動後の辺の交点を所定の方向で辿ることで特定される第２の図形を生成し、前記第２の図形のデータを前記データ格納部に格納し、
前記データ格納部に格納されている前記データに係る前記第２の図形の第１の辺の各々を両側に前記所定長だけ移動させた第２の辺の頂点を、前記第１の辺の頂点を中心として前記所定長を半径とする円弧で結ぶことで、第３の図形を生成し、前記第３の図形のデータを前記データ格納部に格納し、
前記データ格納部に格納されている前記データに係る前記第２の図形と前記第３の図形との、図形についての論理和演算を実施することによって、第４の図形を生成し、前記第４の図形のデータを前記データ格納部に格納する、
図形処理装置。
【０１０７】
（付記８）
前記処理部は、さらに、
前記データ格納部に格納されている前記データに係る前記第１の図形の各辺を当該第１の図形の内側方向に前記所定長移動し、移動後の辺の交点のうち移動前の辺の角度が許容角度より大きい交点を中心とし前記所定長を半径とする円を生成し、当該円と当該移動前の辺とにより囲まれる閉領域を特定することで、第５の図形を生成し、前記第５の図形のデータを前記データ格納部に格納し、
前記データ格納部に格納されている前記データに係る前記第５の図形のうち前記第１の図形内に含まれる前記第５の図形と、前記データ格納部に格納されている前記データに係る前記第４の図形との、図形についての論理和演算を実施することによって、第６の図形を生成し、前記第６の図形のデータを前記データ格納部に格納し、
前記データ格納部に格納されている前記データに係る前記第１の図形から前記データ格納部に格納されている前記データに係る前記第６の図形を除去する、図形についての差演算を実施することによって、第７の図形を生成し、前記第７のデータを前記データ格納部に格納する
付記７記載の図形処理装置。
【符号の説明】
【０１０８】
１００  図形処理装置
１０１  図形データ格納部
１０２  設定データ格納部
１０３  修正図形生成部
１０４  違反箇所検出部
１０５  データ格納部
１０６  出力部
１１１  辺移動処理部
１１２  円弧結合処理部
１１３  辺膨張処理部
１１４  円弧生成部
１１５  包含判定部
１１６  図形データ反転部
１１７  図形演算部
【図１】
0005672044.tif 000002
【図２】
0005672044.tif 000003
【図３】
0005672044.tif 000004
【図４】
0005672044.tif 000005
【図５】
0005672044.tif 000006
【図６】
0005672044.tif 000007
【図７Ａ】
0005672044.tif 000008
【図７Ｂ】
0005672044.tif 000009
【図７Ｃ】
0005672044.tif 000010
【図７Ｄ】
0005672044.tif 000011
【図８Ａ】
0005672044.tif 000012
【図８Ｂ】
0005672044.tif 000013
【図８Ｃ】
0005672044.tif 000014
【図８Ｄ】
0005672044.tif 000015
【図９Ａ】
0005672044.tif 000016
【図９Ｂ】
0005672044.tif 000017
【図９Ｃ】
0005672044.tif 000018
【図１０】
0005672044.tif 000019
【図１１】
0005672044.tif 000020
【図１２】
0005672044.tif 000021
【図１３】
0005672044.tif 000022
【図１４】
0005672044.tif 000023
【図１５Ａ】
0005672044.tif 000024
【図１５Ｂ】
0005672044.tif 000025
【図１５Ｃ】
0005672044.tif 000026
【図１５Ｄ】
0005672044.tif 000027
【図１５Ｅ】
0005672044.tif 000028
【図１６Ａ】
0005672044.tif 000029
【図１６Ｂ】
0005672044.tif 000030
【図１６Ｃ】
0005672044.tif 000031
【図１７】
0005672044.tif 000032
【図１８】
0005672044.tif 000033
【図１９】
0005672044.tif 000034
【図２０】
0005672044.tif 000035
【図２１】
0005672044.tif 000036
【図２２】
0005672044.tif 000037
【図２３】
0005672044.tif 000038
【図２４】
0005672044.tif 000039
【図２５】
0005672044.tif 000040
【図２６】
0005672044.tif 000041
【図２７】
0005672044.tif 000042
【図２８】
0005672044.tif 000043
【図２９】
0005672044.tif 000044
【図３０】
0005672044.tif 000045
【図３１】
0005672044.tif 000046
【図３２】
0005672044.tif 000047
【図３３】
0005672044.tif 000048
【図３４】
0005672044.tif 000049
【図３５】
0005672044.tif 000050
【図３６】
0005672044.tif 000051
【図３７】
0005672044.tif 000052
【図３８】
0005672044.tif 000053
【図３９】
0005672044.tif 000054
【図４０】
0005672044.tif 000055
【図４１】
0005672044.tif 000056
【図４２】
0005672044.tif 000057
【図４３】
0005672044.tif 000058
【図４４】
0005672044.tif 000059