(57)【要約】【課題】計算負荷を低減することができる、あるいは処理時間を短縮することができる図形変形処理プログラム、図形変形処理方法、および図形変形処理装置を提供する。【解決手段】実施形態によれば、入力された第１のポリゴンから変形後の第２のポリゴンを生成する図形変形処理プログラムであって、頂点移動プログラムと、交点検出プログラムと、ループ除去プログラムと、を備えた図形変形処理プログラムが提供される。頂点移動プログラムは、第１のポリゴンを形成する複数の頂点のそれぞれを入力された重みに応じて独立して移動させる。交点検出プログラムは、第２のポリゴンを形成する複数の頂点のうちで隣接する２つの頂点同士を結ぶ複数の線分の交点を検出し、交点が第２のポリゴンにおいて無効な頂点であるか否かを判定する。ループ除去プログラムは、無効な頂点であると判定された交点を含む図形を除去する。【選択図】図１
2015060507.tif 000002
【特許請求の範囲】
【請求項１】
入力された第１のポリゴンから変形後の第２のポリゴンを生成する図形変形処理プログラムであって、
前記第１のポリゴンを形成する複数の頂点のそれぞれを入力された重みに応じて独立して移動させる頂点移動プログラムと、
前記第２のポリゴンを形成する複数の頂点のうちで隣接する２つの頂点同士を結ぶ複数の線分の交点を検出し、前記交点が前記第２のポリゴンにおいて無効な頂点であるか否かを判定する交点検出プログラムと、
前記無効な頂点であると判定された前記交点を含む図形を除去するループ除去プログラムと、
を備えた図形変形処理プログラム。
【請求項２】
前記頂点移動プログラムは、
第１の頂点の重みに応じた半径を有し前記第１の頂点を中心とした第１の円と、前記第１の頂点に隣接する第２の頂点の重みに応じた半径を有し前記第２の頂点を中心とした第２の円と、の間における接線を算出し、  
前記接線と、前記第１の頂点と前記第２の頂点とを通る直線と、の間の角度を算出し、
前記角度と、前記第１のポリゴンを形成する前記複数の頂点のそれぞれの重みと、により前記第１のポリゴンを形成する前記複数の頂点を移動させる請求項１記載の図形変形処理プログラム。
【請求項３】
前記交点検出プログラムは、
第１の頂点の重みに応じた半径を有し前記第１の頂点を中心とした第１の円と、前記第１の頂点に隣接する第２の頂点の重みに応じた半径を有し前記第２の頂点を中心とした第２の円と、の間における第１の接線と、
前記第２の円と、前記第２の頂点に隣接する第３の頂点の重みに応じた半径を有し前記第３の頂点を中心とした第３の円と、の間における第２の接線と、
が交差する交点を算出し、
前記第１の接線が前記第２の円と接する第１の接点から前記第２の接線が前記第２の円と接する第２の接点へ向かう方向であって、前記第２の円を中心とした回転の方向が所定の方向である場合に前記交点を前記無効な頂点であると判定する請求項１または２に記載の図形変形処理プログラム。
【請求項４】
前記隣接する２つの頂点の間の距離が所定の閾値以上である場合に、前記隣接する２つの頂点の少なくともいずれかの頂点を円弧上に存在する複数個の頂点列として移動させる補間プログラムをさらに備えた請求項１〜３のいずれか１つに記載の図形変形処理プログラム。
【請求項５】
入力された第１のポリゴンから変形後の第２のポリゴンを生成する図形変形処理方法であって、
前記第１のポリゴンを形成する複数の頂点のそれぞれを入力された重みに応じて独立して移動させる頂点移動工程と、
前記第２のポリゴンを形成する複数の頂点のうちで隣接する２つの頂点同士を結ぶ複数の線分の交点を検出し、前記交点が前記第２のポリゴンにおいて無効な頂点であるか否かを判定する交点検出工程と、
前記無効な頂点であると判定された前記交点を含む図形を除去するループ除去工程と、
を備えた図形変形処理方法。
【請求項６】
前記頂点移動工程は、
第１の頂点の重みに応じた半径を有し前記第１の頂点を中心とした第１の円と、前記第１の頂点に隣接する第２の頂点の重みに応じた半径を有し前記第２の頂点を中心とした第２の円と、の間における接線を算出し、  
前記接線と、前記第１の頂点と前記第２の頂点とを通る直線と、の間の角度を算出し、
前記角度と、前記第１のポリゴンを形成する前記複数の頂点のそれぞれの重みと、により前記第１のポリゴンを形成する前記複数の頂点を移動させる請求項５記載の図形変形処理方法。
【請求項７】
前記交点検出工程は、
第１の頂点の重みに応じた半径を有し前記第１の頂点を中心とした第１の円と、前記第１の頂点に隣接する第２の頂点の重みに応じた半径を有し前記第２の頂点を中心とした第２の円と、の間における第１の接線と、
前記第２の円と、前記第２の頂点に隣接する第３の頂点の重みに応じた半径を有し前記第３の頂点を中心とした第３の円と、の間における第２の接線と、
が交差する交点を算出し、
前記第１の接線が前記第２の円と接する第１の接点から前記第２の接線が前記第２の円と接する第２の接点へ向かう方向であって、前記第２の円を中心とした回転の方向が所定の方向である場合に前記交点を前記無効な頂点であると判定する請求項５または６に記載の図形変形処理方法。
【請求項８】
前記隣接する２つの頂点の間の距離が所定の閾値以上である場合に、前記隣接する２つの頂点の少なくともいずれかの頂点を円弧上に存在する複数個の頂点列として移動させる補間工程をさらに備えた請求項５〜７のいずれか１つに記載の図形変形処理方法。
【請求項９】
入力された第１のポリゴンから変形後の第２のポリゴンを生成する図形変形処理装置であって、
前記第１のポリゴンを形成する複数の頂点のそれぞれを入力された重みに応じて独立して移動させる頂点移動処理部と、
前記第２のポリゴンを形成する複数の頂点のうちで隣接する２つの頂点同士を結ぶ複数の線分の交点を検出し、前記交点が前記第２のポリゴンにおいて無効な頂点であるか否かを判定する交点検出部と、
前記無効な頂点であると判定された前記交点を含む図形を除去するループ除去部と、
を備えた図形変形処理装置。
【請求項１０】
前記頂点移動処理部は、
第１の頂点の重みに応じた半径を有し前記第１の頂点を中心とした第１の円と、前記第１の頂点に隣接する第２の頂点の重みに応じた半径を有し前記第２の頂点を中心とした第２の円と、の間における接線を算出し、  
前記接線と、前記第１の頂点と前記第２の頂点とを通る直線と、の間の角度を算出し、
前記角度と、前記第１のポリゴンを形成する前記複数の頂点のそれぞれの重みと、により前記第１のポリゴンを形成する前記複数の頂点を移動させる請求項９記載の図形変形処理装置。
【請求項１１】
前記交点検出部は、
第１の頂点の重みに応じた半径を有し前記第１の頂点を中心とした第１の円と、前記第１の頂点に隣接する第２の頂点の重みに応じた半径を有し前記第２の頂点を中心とした第２の円と、の間における第１の接線と、
前記第２の円と、前記第２の頂点に隣接する第３の頂点の重みに応じた半径を有し前記第３の頂点を中心とした第３の円と、の間における第２の接線と、
が交差する交点を算出し、
前記第１の接線が前記第２の円と接する第１の接点から前記第２の接線が前記第２の円と接する第２の接点へ向かう方向であって、前記第２の円を中心とした回転の方向が所定の方向である場合に前記交点を前記無効な頂点であると判定する請求項９または１０に記載の図形変形処理装置。
【請求項１２】
前記隣接する２つの頂点の間の距離が所定の閾値以上である場合に、前記隣接する２つの頂点の少なくともいずれかの頂点を円弧上に存在する複数個の頂点列として移動させる補間処理部をさらに備えた請求項９〜１１のいずれか１つに記載の図形変形処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、図形変形処理プログラム、図形変形処理方法、および図形変形処理装置に関する。
【背景技術】
【０００２】
例えば、半導体製造工程の中のリソグラフィ工程では、まずシミュレーションを行い、転写されるパターンを設定した上で、マスクの設計が行われる。このようなプロセスシミュレータの一部においては、輪郭情報から構成される二次元の図形形状（ポリゴン）を膨張または収縮させる手法として、図形形状を画像へ変換した後でその画像を処理する手法がある。しかし、この手法では、図形形状を膨張または収縮させる量（加工量）に比例して指数的に計算負荷が増大するという課題がある。図形変形処理において、計算負荷の低減あるいは処理時間の短縮が望まれている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１２−１６８７３０号公報
【特許文献２】特開２００７−２５６４０２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明が解決しようとする課題は、計算負荷を低減することができる、あるいは処理時間を短縮することができる図形変形処理プログラム、図形変形処理方法、および図形変形処理装置を提供することである。
【課題を解決するための手段】
【０００５】
実施形態によれば、入力された第１のポリゴンから変形後の第２のポリゴンを生成する図形変形処理プログラムであって、頂点移動プログラムと、交点検出プログラムと、ループ除去プログラムと、を備えた図形変形処理プログラムが提供される。前記頂点移動プログラムは、前記第１のポリゴンを形成する複数の頂点のそれぞれを入力された重みに応じて独立して移動させる。前記交点検出プログラムは、前記第２のポリゴンを形成する複数の頂点のうちで隣接する２つの頂点同士を結ぶ複数の線分の交点を検出し、前記交点が前記第２のポリゴンにおいて無効な頂点であるか否かを判定する。前記ループ除去プログラムは、前記無効な頂点であると判定された前記交点を含む図形を除去する。
【図面の簡単な説明】
【０００６】
【図１】本発明の実施の形態にかかる図形変形処理装置の要部構成を表すブロック図である。
【図２】本実施形態にかかる図形変形処理プログラムが実行する処理および図形変形処理方法を表すフローチャート図である。
【図３】本実施形態にかかる図形変形処理プログラムが実行する処理を説明する模式的平面図である。
【図４】比較例にかかる図形変形処理プログラムが実行する処理および図形変形処理方法を説明する模式図である。
【図５】頂点の移動処理を説明する模式的平面図である。
【図６】交点の検出および無効な図形の除去を説明する模式的平面図である。
【図７】頂点が無効か否かの判定方法を説明する模式的平面図である。
【図８】複数図形間の交点の検出および無効な図形の除去を説明する模式的平面図である。
【図９】複数図形間の交点の検出および無効な図形の除去を説明する模式的平面図である。
【図１０】本実施形態のコンピュータの一例を例示するブロック図である。
【発明を実施するための形態】
【０００７】
以下、本発明の実施の形態について図面を参照しつつ説明する。なお、各図面中、同様の構成要素には同一の符号を付して詳細な説明は適宜省略する。  
図１は、本発明の実施の形態にかかる図形変形処理装置の要部構成を表すブロック図である。
【０００８】
図１に表した図形変形処理装置１００は、演算部１１０と、データ格納部１２０と、入力部１３０と、出力部１４０と、を備える。  
演算部１１０は、頂点移動処理部１１１と、補間処理部１１３と、交点検出部１１５と、ループ除去部１１７と、を有する。演算部１１０が実行する動作あるいは処理の詳細については、後述する。
【０００９】
データ格納部１２０は、例えば、演算部１１０が実行している処理の途中のデータを格納したり、あるいは演算部１１０が実行した処理の結果のデータを格納する。  
入力部１３０は、例えば、キーボードやマウスなどの操作を介してオペレータから送信されたコマンドを入力する。  
出力部１４０は、例えば、データ格納部１２０に格納されている図形データなどを表示装置や印刷装置などの出力装置に表示する。
【００１０】
なお、図１に表したブロック図は、本実施形態にかかる図形変形処理装置１００の要部構成の一例であり、必ずしも実際のプログラムモジュールの構成とは一致しない場合がある。
【００１１】
図２は、本実施形態にかかる図形変形処理プログラムが実行する処理および図形変形処理方法を表すフローチャート図である。  
図３は、本実施形態にかかる図形変形処理プログラムが実行する処理を説明する模式的平面図である。  
図４は、比較例にかかる図形変形処理プログラムが実行する処理および図形変形処理方法を説明する模式図である。
【００１２】
図３（ａ）に表したように、本実施形態の演算部１１０には、輪郭情報から構成される二次元の図形形状（ポリゴン）が入力される。具体的には、例えば、ポリゴンの頂点のデータと、ポリゴンの頂点の移動に関する重み（変形量）と、が演算部１１０に入力される。また、図３（ａ）に表した矢印のように、演算部１１０に入力されるポリゴンの情報として、すべての頂点は、時計回りに接続されている。そのため、隣接する２つの頂点を接続する線分を図３（ａ）に表した矢印の方向にみると、右手側が図形形状の内側となる。
【００１３】
図３（ａ）に表した「３」や「−５」などの数値は、ポリゴンの頂点の移動に関する重みを例示している。ここで、正の数値（重み）は、その頂点が膨張することを表す。負の数値（重み）は、その頂点が収縮することを表す。このように、本実施形態にかかる図形変形処理プログラムおよび図形変形処理方法では、ポリゴン単位あるいは線分単位ではなく、複数の頂点がそれぞれ独立して移動する。
【００１４】
ここで、図４（ａ）〜図４（ｅ）を参照しつつ、比較例にかかる図形変形処理プログラムが実行する処理および図形変形処理方法について説明する。  
図４（ａ）に表したように、入力された第１の図形形状３１０が第２の図形形状３２０に膨張する場合を例に挙げて説明する。
【００１５】
図４（ｂ）に表したように、入力された第１の図形形状３１０のうちの第１の頂点３１１の重みが、「５」であるとする。入力された第１の図形形状３１０のうちの第２の頂点３１２の重みが、「１０」であるとする。
【００１６】
続いて、比較例では、図４（ｃ）に表したように、入力された第１の図形形状３１０の画像化が実行される。例えば、第１の図形形状３１０は、所定の画素を有する集合体として画像に変換される。
【００１７】
続いて、図４（ｄ）に表したように、各頂点に対応する画素において、各頂点の重みに対応する半径を有する円が描かれる。ここで、第１の頂点３１１と第２の頂点３１２との間の重みは、第１の頂点３１１の重みと、第２の頂点３１２の重みと、の間において線形補間を行うことで得られる。続いて、図４（ｄ）に表したように、すべての頂点において同様の処理を行い、描かれた円を含む画素の集合体が第２の図形形状３２０の画像となる。  
続いて、第２の図形形状３２０の画像が輪郭情報に変換される。
【００１８】
しかし、比較例にかかる図形変形処理プログラムが実行する処理および図形変形処理方法では、変形量（重み）が比較的大きい場合や、比較的高い分解能が必要な場合には、計算負荷がより高くなったり、処理時間がより長くなることがある。
【００１９】
これに対して、本実施形態にかかる図形変形処理プログラムが実行する処理および図形変形処理方法では、前述したように、輪郭情報から構成される二次元の図形形状（ポリゴン）が入力され、複数の頂点がそれぞれ独立して移動する。つまり、ポリゴンを画像化せずに、ポリゴンのままで複数の頂点をそれぞれ独立して移動させる。
【００２０】
具体的には、図２に表したように、頂点移動処理部１１１が複数の頂点のそれぞれを移動させる（ステップＳ１０１）。また、補間処理部１１３は、頂点の補間を行う（ステップＳ１０１）。すると、演算部１１０に入力されたポリゴン（図３（ａ）参照）は、図３（ｂ）に表したポリゴンのように変形する。つまり、複数の頂点のそれぞれが重みに応じて移動する。また、頂点の補間が必要な場合には、複数の頂点の少なくともいずれかが補間される。頂点の移動処理および頂点の補間処理の詳細については、後述する。
【００２１】
続いて、交点検出部１１５は、頂点の移動処理および頂点の補間処理が実行されたポリゴン（図３（ｂ）参照）の中から交点を検出する（ステップＳ１０３）。例えば、図３（ｃ）に表したように、交点検出部１１５は、交点２０１を検出し、交点２０１が無効な頂点か否かの判定を実行する。無効な頂点の検出の詳細については、後述する。
【００２２】
続いて、図３（ｃ）および図３（ｄ）に表したように、ループ除去部１１７は、交点検出部１１５が交点２０１を検出した後のポリゴンから無効な図形（ループ）２０３を除去する（ステップＳ１０５）。無効な図形（ループ）の除去の詳細については、後述する。なお、無効な頂点の検出については、交点検出部１１５ではなくループ除去部１１７が実行してもよい。
【００２３】
続いて、交点検出部１１５は、複数の図形の間の交点を検出する（ステップＳ１０７）。続いて、ループ除去部１１７は、交点検出部１１５が複数の図形の間の交点を検出した後のポリゴンから無形な図形（ループ）を除去する（ステップＳ１０９）。
【００２４】
このように、本実施形態では、ポリゴン（第１のポリゴン）として入力されたデータを画像化することなく、ポリゴンのデータのままで処理し、ポリゴン（第２のポリゴン）として出力する。  
これによれば、計算負荷を低減することができる。また、処理時間を短縮することができる。
【００２５】
次に、本実施形態にかかる図形変形処理プログラムが実行する処理および図形変形処理方法について、図面を参照しつつさらに説明する。  
図５は、頂点の移動処理を説明する模式的平面図である。
【００２６】
ここでは、図５（ａ）に表したように、第１の頂点２１１と、第２の頂点２１２と、を例に挙げて説明する。第２の頂点２１２は、第１の頂点２１１と隣接する。図２および図３に関して前述したように、ポリゴンの頂点の移動に関する重みが演算部１１０に入力される。頂点移動処理部１１１は、第１の頂点２１１の重みに応じた半径を有し第１の頂点２１１を中心とした第１の円２２１を描く。また、頂点移動処理部１１１は、第２の頂点２１２の重みに応じた半径を有し第２の頂点２１２を中心とした第２の円２２２を描く。
【００２７】
第１の頂点２１１と、第２の頂点２１２と、の間は、線形である。そのため、頂点移動処理部１１１は、第１の円２２１と、第２の円２２２と、の間に線形補間を行った円群を描く。頂点移動処理部１１１は、第１の円２２１と第２の円２２２とを含む円群から直線２３１を引く。つまり、頂点移動処理部１１１は、第１の円２２１の上の第１の接点２２５と、第２の円２２２の上の第２の接点２２６と、を通る直線（接線）２３１を引く。このように、移動後の第１の頂点２１１（第１の接点２２５）と、移動後の第２の頂点２１２（第２の接点２２６）と、の間の輪郭は、直線である。
【００２８】
図５（ａ）に表したように、第１の頂点２１１と第１の接点２２５とを通る直線２３３は、第１の頂点２１１と第２の頂点２１２とを通る直線２３９の第１の法線（垂線）２３４に対して角度θで傾いている。第１の頂点２１１は、第１の頂点２１１における第１の法線２３４に対して角度θで移動する。  
第２の頂点２１２と第２の接点２２６とを通る直線２３５は、第１の頂点２１１と第２の頂点２１２とを通る直線２３９の第２の法線（垂線）２３６に対して角度θで傾いている。第２の頂点２１２は、第２の頂点２１２における第２の法線２３６に対して角度θで移動する。
【００２９】
角度θは、第１の頂点２１１と第２の頂点２１２とを通る直線２３９あるいは直線２３９に平行な直線と、接線２３１と、の間の角度と同じである。頂点移動処理部１１１は、直線２３９あるいは直線２３９に平行な直線と、接線２３１と、の間の角度から角度θを求める。これにより、頂点移動処理部１１１は、角度θと各頂点の変形量の増減（重み）とにより、各頂点を移動させる。
【００３０】
次に、図５（ｂ）に表したように、第１の頂点２１１と、第３の頂点２１３と、の間の変形後の輪郭が凸になる場合を例に挙げて説明する。第３の頂点２１３は、第２の頂点２１２と隣接する。図５（ａ）に関して前述したように、頂点移動処理部１１１は、第１の円２２１と第２の円２２２とを描き、第１の接点２２５と第２の接点２２６とを通る接線２３１を引く。また、頂点移動処理部１１１は、第２の円２２２と第３の円２２３とを描き、第３の接点２２７と第４の接点２２８とを通る接線２３２を引く。
【００３１】
図５（ｃ）に表したように、第２の接点２２６と、第３の接点２２７と、の間については、補間処理部１１３が補間を行う。すなわち、補間処理部１１３は、第２の接点２２６と、第３の接点２２７と、の間の第２の円２２２の円周上に微小な線分を描く。言い換えれば、補間処理部１１３は、第２の接点２２６と、第３の接点２２７と、の間の第２の円２２２の円周上（円弧上）に存在する複数個の頂点列として第２の頂点２１２を移動させる。これにより、補間処理部１１３は、滑らかな輪郭形状を生成することができる。
【００３２】
なお、補間処理部１１３は、例えば隣接する２つの頂点同士の間の距離が所定の閾値以上である場合に、頂点の補間を行う必要があると判断する。
【００３３】
図６は、交点の検出および無効な図形の除去を説明する模式的平面図である。  
図７は、頂点が無効か否かの判定方法を説明する模式的平面図である。
【００３４】
交点検出部１１５は、頂点移動処理部１１１による頂点の移動処理および補間処理部１１３による頂点の補間処理が実行されたポリゴン（図６（ａ）参照）の中から交点を検出する。交点検出部１１５は、２つの線分が互いに交差するか否かを幾何的に判定することで交点を検出する。例えば、図６（ａ）に表したように、交点検出部１１５は、交点２５１、２５２、２５３を検出する。
【００３５】
続いて、交点検出部１１５は、交点２５１、２５２、２５３が無効な頂点か否かの判定を実行する。これについて、図７を参照しつつ、交点２５１を例に挙げてさらに説明する。なお、交点２５１、２５２、２５３が無効な頂点か否かの判定については、ループ除去部１１７が実行してもよい。
【００３６】
図７に表した例では、補間処理部１１３は、第１の接点２６１と、第２の接点２６２と、の間の第１の円２２１の円弧上に存在する複数個の頂点列として第１の頂点２１１を移動させる。補間処理部１１３は、第３の接点２６３と、第４の接点２６４と、の間の第２の円２２２の円弧上に存在する複数個の頂点列として第２の頂点２１２を移動させる。補間処理部１１３は、第５の接点２６５と、第６の接点２６６と、の間の第３の円２２３の円弧上に存在する複数個の頂点列として第３の頂点２１３を移動させる。
【００３７】
交点検出部１１５は、補間処理部１１３が円弧上に存在する複数個の頂点列として各頂点（例えば第１の頂点２１１）を置き換える（移動させる）ときの情報を流用する。すなわち、図７に矢印Ａ１〜Ａ３で表したように、補間処理部１１３は、円弧上に存在する複数個の頂点列として各頂点を置き換えるときに、相対的に小さい番号の接点から相対的に大きい番号の接点へ向かう回転方向の情報を付帯情報として交点検出部１１５およびループ除去部１１７の少なくともいずれかに与える。
【００３８】
交点検出部１１５は、補間処理部１１３から与えられた回転方向の情報に基づいて、交点２５１が無効な頂点か否かの判定を実行する。すなわち、交点検出部１１５は、図７に表した矢印Ａ２のように、回転方向が反時計回りの場合には、第２の接点２６２と第３の接点２６３とを通る接線２３１と、第４の接点２６４と第５の接点２６５とを通る接線２３２と、の交点２５１が無効な頂点であると判断する。一方で、交点検出部１１５は、回転方向が時計回りの場合には、２つの接線の交点が有効な頂点であると判断する。
【００３９】
なお、回転方向が反時計回りおよび時計回りのいずれの場合に、交点検出部１１５が交点を無効な頂点であると判断するか否かについては、これだけに限定されない。例えば、交点検出部１１５は、回転方向が時計回りの場合に、２つの接線の交点が無効な頂点であると判断してもよい。
【００４０】
続いて、図６（ｂ）に表したように、ループ除去部１１７は、交点検出部１１５が無効な頂点であると判断した交点２５１を含む無効な図形（ループ）２５６を除去する。続いて、図６（ｂ）および図６（ｃ）に表したように、ループ除去部１１７は、無効な図形（ループ）２５６を除去した後に残った頂点として新たな頂点２５１ａを作成する。
【００４１】
交点検出部１１５およびループ除去部１１７は、交点２５２、２５３についても同様の処理を実行する。すなわち、交点検出部１１５は、交点２５２、２５３が無効な頂点であるか否かを判定する。ループ除去部１１７は、無効な図形２５７、２５８を除去し、新たな頂点２５２ａ、２５３ａを作成する。
【００４２】
このように、本実施形態では、頂点移動処理部１１１による頂点の移動処理および補間処理部１１３による頂点の補間処理の少なくともいずれかの処理が実行されたときの情報を後段の処理へ継承し、不要な補間処理を省略することができる。これにより、処理の効率化を図ることができる。そのため、計算負荷を低減することができる。また、処理時間を短縮することができる。
【００４３】
図８および図９は、複数図形間の交点の検出および無効な図形の除去を説明する模式的平面図である。  
図８（ａ）〜図９（ｂ）は、例えば図５（ａ）〜図５（ｃ）に関して前述した図形変形処理プログラムが実行する処理および図形変形処理方法に基づいて、頂点移動処理部１１１および補間処理部１１３が各頂点を移動させた後の図形を表す。
【００４４】
図２および図３に関して前述したように、例えば、すべての頂点は、時計回りに接続されている。交点検出部１１５は、交点以外の頂点からスタートし、時計回りに輪郭をトレースする。ここで、例えばすべての頂点が時計回りに接続されているため、交点検出部１１５は、輪郭を形成する複数の線分のうちの各線分の方向を認識することができる。そのため、交点検出部１１５は、例えば時計回りに輪郭をトレースすることで、複数の図形の間の交点を検出することができる。例えば、図８（ａ）に表したように、交点検出部１１５は、複数の図形の間の交点２７１、２７２を検出することができる。
【００４５】
ここで、図９（ａ）および図９（ｂ）に表したように、交点検出部１１５は、複数の図形のそれぞれに外接する複数の長方形を求め、複数の長方形のうちで重なる図形同士の間において、複数の図形の間の交点を検出してもよい。例えば、図９（ａ）に表した例では、交点検出部１１５は、第１の図形２７６と、第２の図形２７７と、第３の図形２７８と、の間において交点を検出する。例えば、図９（ｂ）に表した例では、交点検出部１１５は、第１の図形２７６と、第２の図形２７７と、の間において交点を検出し、一方で、第３の図形２７７と、第４の図形２７９と、の間において交点を検出する。
【００４６】
これにより、無駄な判定処理を削減することができる。そのため、計算負荷を低減することができる。また、処理時間を短縮することができる。
【００４７】
続いて、図８（ａ）に表したように、ループ除去部１１７は、交点検出部１１５が検出した交点２７１、２７２を含む無効な図形（ループ）２７５を除去する。続いて、図８（ｂ）に表したように、ループ除去部１１７は、無効な図形（ループ）２７５を除去した後に残った頂点として新たな頂点２７１ａ、２７２ａを作成する。
【００４８】
図１０は、本実施形態のコンピュータの一例を例示するブロック図である。  
本実施形態にかかる図形変形処理装置１００は、例えばコンピュータ装置である。例えば、図１０に表したように、メモリ１６１と、ＣＰＵ（Central Processing Unit）１６３と、ハードディスク・ドライブ（ＨＤＤ）１６５と、表示制御部１６７と、表示装置１６９と、ドライブ装置１７３と、入力装置１７５と、通信制御部１７７と、がバス１７９で接続されている。
【００４９】
表示装置１６９は、表示制御部１６７を介してバス１７９に接続されている。ドライブ装置１７３は、例えばリムーバブル・ディスク１７１用の装置である。通信制御部１７７は、ネットワークに接続される。
【００５０】
オペレーティング・システム（ＯＳ：Operating System）及び本実施形態にかかる図形変形処理プログラムは、ＨＤＤ１６５に格納されている。図形変形処理プログラムは、ＣＰＵ１６３により実行される際には、ＨＤＤ１６５からメモリ１６１に読み出される。ＣＰＵ１６３は、図形変形処理プログラムプログラムの処理内容に応じて表示制御部１６７、通信制御部１７７およびドライブ装置１７３の少なくともいずれかを制御し、所定の動作を実行する。処理途中のデータは、主としてメモリ１６１に格納される。但し、処理途中のデータは、ＨＤＤ１６５に格納されてもよい。
【００５１】
例えば、本実施形態にかかる図形変形処理プログラムは、コンピュータで読み取り可能なリムーバブル・ディスク１７１に格納されて頒布され、ドライブ装置１７３からＨＤＤ１６５にインストールされる。例えば、本実施形態にかかる図形変形処理プログラムは、インターネットなどのネットワーク及び通信制御部１７７を経由して、ＨＤＤ１６５にインストールされてもよい。このようなコンピュータ装置は、ＣＰＵ１６３およびメモリ１６１などのハードウエアと、ＯＳ及びアプリケーション・プログラム（例えば本実施形態にかかる図形変形処理プログラム）などのプログラムと、が有機的に協働することにより、前述したような各種機能を実現する。
【００５２】
なお、本実施形態にかかる図形変形処理プログラムは、１台のコンピュータではなく２台のコンピュータにより実行されてもよい。
【００５３】
以上の実施形態では、輪郭情報から構成される二次元の図形形状（ポリゴン）が膨張する場合を例に挙げて説明した。ポリゴンが収縮する場合については、ポリゴンが膨張する場合として前述した手法を用いることができる。ポリゴンが収縮するか、あるいはポリゴンが膨張するかについては、ポリゴンの頂点の移動に関する重み（変形量）を表す数値の符号により判断することができる。ポリゴンの頂点の膨張およびポリゴンの頂点の収縮が単一のポリゴンの中に混在する場合においても、本実施形態にかかる図形変形処理プログラム、図形変形処理方法および図形変形処理装置により複数の頂点をそれぞれ独立して移動させることができる。
【００５４】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００５５】
１００ 図形変形処理装置、  １１０ 演算部、  １１１ 頂点移動処理部、  １１３ 補間処理部、  １１５ 交点検出部、  １１７ ループ除去部、  １２０ データ格納部、  １３０ 入力部、  １４０ 出力部、  １６１ メモリ、  １６３ ＣＰＵ、  １６５ ハードディスク・ドライブ、  １６７ 表示制御部、  １６９ 表示装置、  １７１ リムーバブル・ディスク、  １７３ ドライブ装置、  １７５ 入力装置、  １７７ 通信制御部、  １７９ バス、  ２０１ 交点、  ２０３ 図形（ループ）、  ２１１ 第１の頂点、  ２１２ 第２の頂点、  ２１３ 第３の頂点、  ２２１ 第１の円、  ２２２ 第２の円、  ２２３ 第３の円、  ２２５ 第１の接点、  ２２６ 第２の接点、  ２２７ 第３の接点、  ２２８ 第４の接点、  ２３１ 直線（接線）、  ２３２ 接線、  ２３３ 直線、  ２３４ 法線、  ２３５ 直線、  ２３６ 法線、  ２３９ 直線、  ２５１ 交点、  ２５１ａ 頂点、  ２５２ 交点、  ２５２ａ 頂点、  ２５３ 交点、  ２５６、２５７、２５８ 図形（ループ）、  ２６１ 第１の接点、  ２６２ 第２の接点、  ２６３ 第３の接点、  ２６４ 第４の接点、  ２６５ 第５の接点、  ２６６ 第６の接点、  ２７１ 交点、  ２７１ａ 頂点、  ２７２ 交点、  ２７２ａ 頂点、  ２７６ 第１の図形、  ２７７ 第２の図形、  ２７８ 第３の図形、  ２７９ 第４の図形、  ３１０ 第１の図形形状、  ３１１ 第１の頂点、  ３１２ 第２の頂点、  ３２０ 第２の図形形状
【図１】
2015060507.tif 000003
【図２】
2015060507.tif 000004
【図３】
2015060507.tif 000005
【図４】
2015060507.tif 000006
【図５】
2015060507.tif 000007
【図６】
2015060507.tif 000008
【図７】
2015060507.tif 000009
【図８】
2015060507.tif 000010
【図９】
2015060507.tif 000011
【図１０】
2015060507.tif 000012