(57)【要約】【課題】ＣＡＤ／ＣＡＭシステムにおける図形間の演算において、図形を高速に作成するとともに、多くの種類の図形を取り扱うことができるようにする。【解決手段】図形を制限することなく、演算対象の図形間の交点種別を算出し、交点を挟む前後の要素の位置及び演算種別から交点を選択するようにし、選択した交点のいずれかをスタート位置として目的とする図形を高速に作成できるようにする。また、新たなループを生成する際に不要な交点のみが存在するループに対し、交点種別から位置関係を判定することにより、演算種別に応じたループを高速に取り出すことができるようにする。【選択図】図１
2009259048.tif 000002
【特許請求の範囲】
【請求項１】
２つの図形から、論理和、論理差及び論理積のうち少なくとも１つの論理演算を行う図形処理装置であって、
前記２つの図形が互いに交差する交点での交差状態を表す交点種別を判定する交点種別判定手段と、
前記交点種別判定手段によって判定された交点種別の情報を記憶部に記憶する記憶手段と、
前記記憶部に記憶されている交点種別の情報と前記論理演算の種類とをもとに、新たな図形を生成するために必要な交点を選択する選択手段と、
前記選択手段によって選択された交点を用いて前記新たな図形を生成する図形生成手段とを有することを特徴とする図形処理装置。
【請求項２】
前記交点種別判定手段は、
前記交点を挟む前後の線の位置関係を算出する位置関係算出手段と、
前記図形の領域に属する側を定義する前記交点を挟む前後の線の進行方向が、他方の図形の外部へ進行する方向であるか、または他方の図形の内部へ進行する方向であるか、もしくは他方の図形を構成する線と一致する方向であるかを前記位置関係算出手段によって算出された位置関係に基づいて判定する進行方向判定手段とを有し、
前記記憶手段は、前記進行方向判定手段によって判定された進行方向についての情報を前記交点種別の情報として前記記憶部に記憶することを特徴とする請求項１に記載の図形処理装置。
【請求項３】
前記記憶手段は、前記交点種別の情報として、前記交点を挟む前後の線、前記図形を構成する線の位置関係、前記図形の領域に属する側を定義する前記交点を挟む前後の線の進行方向、及び他方の図形と交差する前記図形の領域の境界を示すループについての情報を前記記憶部に記憶することを特徴とする請求項１または２に記載の図形処理装置。
【請求項４】
前記図形生成手段は、
前記選択手段によって選択された交点を用いて、前記新たな図形の領域の境界を示す新たなループを生成するループ生成手段と、
前記選択手段によって選択された交点を用いて、前記２つの図形のうち少なくとも何れか１つの図形の領域の境界を示すループを抽出するループ抽出手段とを有し、
前記ループ生成手段によって生成された新たなループと、前記ループ抽出手段によって抽出されたループとを用いて前記新たな図形を生成することを特徴とする請求項１〜３の何れか１項に記載の図形処理装置。
【請求項５】
２つの図形から、論理和、論理差及び論理積のうち少なくとも１つの論理演算を行う図形処理方法であって、
前記２つの図形が互いに交差する交点での交差状態を表す交点種別を判定する交点種別判定工程と、
前記交点種別判定工程において判定した交点種別の情報を記憶部に記憶する記憶工程と、
前記記憶部に記憶されている交点種別の情報と前記論理演算の種類とをもとに、新たな図形を生成するために必要な交点を選択する選択工程と、
前記選択工程において選択した交点を用いて前記新たな図形を生成する図形生成工程とを有することを特徴とする図形処理方法。
【請求項６】
前記交点種別判定工程においては、
前記交点を挟む前後の線の位置関係を算出する位置関係算出工程と、
前記図形の領域に属する側を定義する前記交点を挟む前後の線の進行方向が、他方の図形の外部へ進行する方向であるか、または他方の図形の内部へ進行する方向であるか、もしくは他方の図形を構成する線と一致する方向であるかを前記位置関係算出工程において算出した位置関係に基づいて判定する進行方向判定工程とを有し、
前記記憶工程においては、前記進行方向判定工程において判定した進行方向についての情報を前記交点種別の情報として前記記憶部に記憶することを特徴とする請求項５に記載の図形処理方法。
【請求項７】
前記記憶工程においては、前記交点種別の情報として、前記交点を挟む前後の線、前記図形を構成する線の位置関係、前記図形の領域に属する側を定義する前記交点を挟む前後の線の進行方向、及び他方の図形と交差する前記図形の領域の境界を示すループについての情報を前記記憶部に記憶することを特徴とする請求項５または６に記載の図形処理方法。
【請求項８】
前記図形生成工程においては、
前記選択工程において選択した交点を用いて、前記新たな図形の領域の境界を示す新たなループを生成するループ生成工程と、
前記選択工程において選択した交点を用いて、前記２つの図形のうち少なくとも何れか１つの図形の領域の境界を示すループを抽出するループ抽出工程とを有し、
前記ループ生成工程において生成した新たなループと、前記ループ抽出工程において抽出したループとを用いて前記新たな図形を生成することを特徴とする請求項５〜７の何れか１項に記載の図形処理方法。
【請求項９】
２つの図形から、論理和、論理差及び論理積のうち少なくとも１つの論理演算を行う図形処理装置においてコンピュータに実行させるプログラムであって、
前記２つの図形が互いに交差する交点での交差状態を表す交点種別を判定する交点種別判定工程と、
前記交点種別判定工程において判定した交点種別の情報を記憶部に記憶する記憶工程と、
前記記憶部に記憶されている交点種別の情報と前記論理演算の種類とをもとに、新たな図形を生成するために必要な交点を選択する選択工程と、
前記選択工程において選択した交点を用いて前記新たな図形を生成する図形生成工程とをコンピュータに実行させることを特徴とするプログラム。
【請求項１０】
請求項９に記載のプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は図形処理装置、図形処理方法、プログラム及び記録媒体に関し、特に、ＣＡＤ／ＣＡＭシステムにおける図形間の演算に用いて好適な技術に関する。
【背景技術】
【０００２】
従来、コンピュータを利用して設計を行い、生産準備の全般を行うＣＡＤ（Computer Aided Design）／ＣＡＭ（Computer Aided Manufacturing）システムがある。このＣＡＤ／ＣＡＭシステムにおいて、複数の閉領域で構成される図形間の論理和、論理差及び論理積を論理演算する方法として、まず、図形を構成する要素を取り出し、それぞれの図形の要素間で交点を算出する。そして、算出した交点によって要素を分割し、分割した要素が相手図形に対して内部なのか外部なのかを判定して、演算の種類に対応した要素を取り出し、目的とする図形を生成するものが知られている。
【０００３】
また、幾何計算を用いずに図形処理を行う技術として、各図形を構成する線分の始点終点座標から処理対象の図形の座標値を順番に並べ、その並べた番号に置換して疑似座標図形を作成する。そして、疑似座標を単位とする疑似座標系の格子間に、作成した疑似座標図形をマトリクス上に展開して、このマトリクスを操作することにより幾何計算を用いずに図形処理を行う技術が知られている（例えば、特許文献１参照）。
【０００４】
【特許文献１】特開平０５−２５７９９８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
前述した従来例では、複雑で大量のデータを扱うＣＡＤ／ＣＡＭシステムにおいては、目的とする図形を得るために、演算処理を多く行い、さらにその演算処理の中における内外判定にも膨大な処理時間を要してしまうという問題点があった。
【０００６】
そこで、前記問題点を解消するために、前記特許文献１に記載の方法では、幾何計算を用いずに目的とする図形を得ることができ、図形処理を高速化できるという効果がある。ところが、扱える図形が制限されているため、汎用的に扱うことができないという問題点があった。
【０００７】
本発明は前述の問題点に鑑み、ＣＡＤ／ＣＡＭシステムにおける図形間の演算において、図形を高速に作成するとともに、多くの種類の図形を取り扱うことができるようにすることを目的としている。
【課題を解決するための手段】
【０００８】
本発明の図形処理装置は、２つの図形から、論理和、論理差及び論理積のうち少なくとも１つの論理演算を行う図形処理装置であって、前記２つの図形が互いに交差する交点での交差状況を表す交点種別を判定する交点種別判定手段と、前記交点種別判定手段によって判定された交点種別の情報を記憶部に記憶する記憶手段と、前記記憶部に記憶されている交点種別の情報と前記論理演算の種類とをもとに、新たな図形を生成するために必要な交点を選択する選択手段と、前記選択手段によって選択された交点を用いて前記新たな図形を生成する図形生成手段とを有することを特徴とする。
【０００９】
本発明の図形処理方法は、２つの図形から、論理和、論理差及び論理積のうち少なくとも１つの論理演算を行う図形処理方法であって、前記２つの図形が互いに交差する交点での交差状況を表す交点種別を判定する交点種別判定工程と、前記交点種別判定工程において判定した交点種別の情報を記憶部に記憶する記憶工程と、前記記憶部に記憶されている交点種別の情報と前記論理演算の種類とをもとに、新たな図形を生成するために必要な交点を選択する選択工程と、前記選択工程において選択した交点を用いて前記新たな図形を生成する図形生成工程とを有することを特徴とする。
【００１０】
本発明のプログラムは、２つの図形から、論理和、論理差及び論理積のうち少なくとも１つの論理演算を行う図形処理装置においてコンピュータに実行させるプログラムであって、前記２つの図形が互いに交差する交点での交差状況を表す交点種別を判定する交点種別判定工程と、前記交点種別判定工程において判定した交点種別の情報を記憶部に記憶する記憶工程と、前記記憶部に記憶されている交点種別の情報と前記論理演算の種類とをもとに、新たな図形を生成するために必要な交点を選択する選択工程と、前記選択工程において選択した交点を用いて前記新たな図形を生成する図形生成工程とをコンピュータに実行させることを特徴とする。
【００１１】
本発明の記録媒体は、前記に記載のプログラムを記録したことを特徴とする。
【発明の効果】
【００１２】
本発明によれば、交点種別の情報と論理演算の種類とをもとに選択した交点に基づいて図形を生成するため、演算量を抑えることができる。したがって、図形を高速に作成するとともに、多くの種類の図形を取り扱うことができる。
【発明を実施するための最良の形態】
【００１３】
（第１の実施形態）
以下、本発明の実施形態について図面に基づいて詳細に説明する。
図２は、本実施形態において、等高線作成処理を行う図形処理装置の構成例を示すブロック図である。
図２に示すように、図形処理装置１０は、中央処理部１、入力部２、表示部３、記憶部４、入出力制御部５、通信インターフェイス７及びバスライン８を備えている。そして、外部記憶媒体６が入出力制御部５と接続されている。なお、本実施形態の図形処理装置１０の構成は一例であり、図２に示された構成に限定されるものではない。
【００１４】
次に、前述した各部の構成について詳細に説明する。中央処理部１は、バスライン８を介して各部を制御するとともに、記憶部４に格納されたプログラムに従って図形処理を行う。この図形処理を行うためのプログラム及びパラメータは、入出力制御部５を介して外部記憶媒体６から記憶部４に格納される。入力部２は、ユーザの操作によりデータやパラメータ等を入力するためのキーボード及びマウス等として構成されている。
【００１５】
表示部３は、中央処理部１の制御によりデータやパラメータ等の表示を行うためのものであり、例えば、液晶ディスプレイから構成されている。記憶部４は、半導体メモリや磁気ディスク等から構成されており、制御プログラムや本実施形態の図形処理を行うプログラムを格納する。また、幾何形状を表す図形要素や、要素属性、演算種別（論理積（以下、ＡＮＤ）、論理和（以下、ＯＲ）、論理差（以下、ＮＯＴ））、同一点とみなすための許容誤差値、同一角度とみなす許容角度値といった計算用のパラメータを記憶する。さらには、後述する交点種別、交点の要不要、交点の探索有無といった交点の処理に関する情報も記憶する。
【００１６】
外部記憶媒体６は、例えば、磁気テープ、磁気ディスク、光磁気ディスク等である。通信インターフェイス７は、例えばＬＡＮに接続され、他の処理装置と接続されている。また、バスライン８は、前述した各部の共通信号路として構成されている。
【００１７】
図１は、本実施形態の図形処理の全体の動作手順の一例を示すフローチャートである。なお、図１に示す各処理は、中央処理部１の制御によって行われる。
最初に、ステップＳ１１０１において、中央処理部１は、演算の対象となる図形及び演算種別（ＡＮＤ／ＯＲ／ＮＯＴ）についての情報を入力データとして、記憶部４に記憶する。この時、外部記憶媒体６から入力データを入力してもよく、通信インターフェイス７を介して外部装置から入力データを入力してもよい。さらに、同一点とみなす許容誤差値、同一角度とみなす許容角度値などの計算用のパラメータを入力し、記憶部４に記憶する。
【００１８】
ここで、図形に関して説明する。図形は、１つ以上の領域で構成される。１つの領域は、外側の境界を示す反時計周りのループと、内側の境界を示す０個以上の時計周りのループとにより表現され、ループを境界とする範囲で領域が示される。すなわち、ループの進行方向の左手側が領域内部となる。
【００１９】
さらにループは、線分、曲線を近似した線分、及び円弧の要素で構成され、各要素が連結されて最初の要素始点の座標と最後の要素終点の座標とが一致する閉じた境界形状を形成する。また、各要素の情報には、始点、終点及び中心を表す座標情報と、要素種別、要素を識別するための番号、要素長、接線ベクトル、方向ベクトル、存在範囲、円弧半径などの要素の特徴、位置を示す情報とを含む属性情報が付随している。なお、入力データには、この属性情報は必ずしも含まれている必要はなく、中央処理部１により図形情報から算出するようにしてもよい。
【００２０】
本実施形態では、２つの図形について演算を行うために、それぞれを図形Ａ、図形Ｂと定義する。そして、演算結果として得られる図形を図形Ｃと定義する。すなわち、図形Ａと図形ＢとのＯＲ結果、図形Ａと図形ＢとのＡＮＤ結果、図形Ａと図形ＢとのＮＯＴ結果（図形Ａから図形ＢをＮＯＴした結果）が図形Ｃとなる。ステップＳ１１０１では、図形Ａ及び図形Ｂの情報がそれぞれ記憶部４に記憶される。
【００２１】
次に、ステップＳ１１０２において、ステップＳ１１０１で記憶された図形Ａ及び図形Ｂの情報を記憶部４から読み出し、図形Ａと図形Ｂとのラフチェックを行う。なお、ステップＳ１１０２の処理は、必ずしも行わなくてもよい処理であるが、ラフチェックを行うことにより、より高速に計算することが可能となる。
【００２２】
ラフチェックでは、図形Ａと図形Ｂとを配置した場合に、ループ同士を参照して、それぞれのループが互いに明らかに交差のしないループがあるかどうかを、ループによって形成される形状から識別する。交差する可能性のあるループに対しては、さらにループを構成する要素の単位でラフチェックを行うための情報（各要素から形成される形状の座標の最小値及び最大値）を算出し、算出した情報を記憶部４に記憶する。
【００２３】
このチェックの結果、各図形を構成する反時計回りのループを包含する形状に重なりがなく、図形Ａと図形Ｂとが交差しない場合は、ステップＳ１１０３〜Ｓ１１０７をスキップして、ステップＳ１１０８へ進む。一方、ステップＳ１１０２のチェックの結果、それぞれのループが交差し、図形Ａと図形Ｂとが交差する場合は、次のステップＳ１１０３へ進む。
【００２４】
次に、ステップＳ１１０３において、図形Ａと図形Ｂとの交点計算を行い、交点の情報及びその付随情報を記憶部４に記憶する。具体的にはまず、図形Ａを構成するループのうち、交差の可能性のあるループを順次取り出し、交差の可能性のある図形Ｂを構成するループに対して、交点計算を行う。そして、交点が求まったら、各交点に対し、図形Ａ及び図形Ｂのそれぞれの要素、ループを識別するための要素番号、ループ番号などの情報を付随情報として付加する。
【００２５】
なお、詳細については後述するが、交差する位置以外に、計算対象となっている要素の始点が、他方の要素との距離が許容誤差値以下である場合に同一点（交点）とみなし、要素の始点を交点として追加処理する。
【００２６】
次に、ステップＳ１１０４において、中央処理部１は交点種別判定手段として機能し、記憶部４に記憶されている交点の情報を読み出し、交点における交差状態及び接触状態を識別するための情報（以下、交点種別）を判定する処理を行う。交点種別では、図形Ａ及び図形Ｂそれぞれの要素の中から交点を挟む前後の要素を抽出し、抽出した要素の位置関係から交点における交差状態及び接触状態を識別するための情報を抽出する。なお、抽出した要素の途中で別の交点を有している場合は、一時的にその交点の位置で要素を分解して情報の抽出を行う。さらに、中央処理部１は進行方向判定手段として機能し、各図形のループの進行方向が相手図形に対して内部へ進む方向であるのか、もしくは外部へ進む方向であるのかを判定する。これらの情報は、図形Ａ及び図形Ｂの要素に対しそれぞれ抽出され、対象となる交点に関連付けされて交点種別の情報として記憶部４に記憶される。
【００２７】
なお、各要素の位置関係については、円弧の要素を含む場合は、交点における各要素の接線ベクトルと要素の位置フラグとを用いて計算する。この時、要素は、交点を始点となるように始点及び終点を入れ換える。そして、円弧の場合、半径（＝ｒ）が位置関係に関与するため、時計まわりの円弧の位置フラグは−１／ｒ、反時計まわりの円弧の位置フラグを１／ｒとする。また、線分の位置フラグは０とする。
【００２８】
図３は、交点を挟む前後の要素の位置関係の一例を説明する図である。
図３において、１６１は図形Ａにおける交点の前要素であり、１６２は図形Ａにおける交点の後要素である。一方、２６１は図形Ｂにおける交点の前要素であり、２６２は図形Ｂにおける交点の後要素である。
【００２９】
また、９６１は図形Ｂにおける交点の後要素２６２を基準にして図形Ａにおける交点の後要素１６２とのなす角度（α）である。この時、交点における接線のなす角度を反時計回りに算出する。同様に、９６２は図形Ｂにおける交点の前要素２６１とのなす角度（β）であり、９６３は図形Ａにおける交点の前要素１６１とのなす角度（γ）である。
【００３０】
図３に示す例では、図形Ｂにおける交点の後要素２６２を基準要素として計算した角度によって、配置順を決定する。この場合、図形Ｂにおける交点の後要素２６２から反時計回りの角度は、α＜β＜γである。したがって、図形Ａにおける交点の後要素１６２、図形Ｂにおける交点の前要素２６１、図形Ａにおける交点の前要素１６１の順に配置順を決定する。
【００３１】
また、図形Ａにおける交点の前要素１６１は、図形Ｂのループの進行方向の右側から交点に進むので、図形Ｂに対して外部に位置する要素であると判定する。一方、図形Ａにおける交点の後要素１６２は、交点から図形Ｂのループの進行方向の左側へ進むので、図形Ｂに対して内部に位置する要素であると判定する。同様に、図形Ｂにおける交点の前要素２６１は、図形Ａのループの進行方向の左側から交点へ進むので、図形Ａに対して内部に位置する要素であると判定する。そして、図形Ｂにおける交点の後要素２６２は、交点から図形Ａのループの進行方向の右側へ進むので、図形Ａに対して外部に位置する要素であると判定する。以上より、図形Ａのループは、図形Ｂに対して外部から内部へ進み、図形Ｂのループは、図形Ａに対して内部から外部へ進むと算出される。このように中央処理部１が位置関係算出手段及び進行方向判定手段として機能することにより、各要素の位置関係を算出し、各ループの進行方向を判定する。
【００３２】
前述したように基準の方向から反時計回りで角度を算出した際に、２つの要素間の角度が許容角度値以下の場合、一致判定処理を行う。図４は、一致判定処理を説明する図である。判定手順については、図４に示す第１の円弧１７１及び第２の円弧１７２を例に説明する。
【００３３】
図４において、第１の円弧１７１と第２の円弧１７２とが交差する交点において、第１の円弧１７１に接するベクトルを第１の接線ベクトル８７１とし、第２の円弧１７２に接するベクトルを第２の接線ベクトル８７２とする。第１の接線ベクトル８７１と第２の接線ベクトル８７２と間でなす角度ｗが許容角度値以下である場合、第１の円弧１７１と第２の円弧１７２との着目している交点以外に別の交点が存在するかどうかについて交点計算を行う。この時、要素の終点で交差する場合も交点とする。
【００３４】
この計算の結果、交点が存在する場合には、さらに、着目している交点及び別に存在する交点の中間位置で、各要素間の距離ｔを計算し、この距離ｔが許容誤差値以下である場合は、第１の円弧１７１と第２の円弧１７２とは一致と判定する。一方、着目している交点以外に交点が存在しない場合は、不一致と判定する。
【００３５】
角度ｗが許容角度値以下でありながら不一致と判定される場合のうち、特に角度差が０となるような２要素が交点で接する位置関係にある場合は、位置フラグの大小関係を用いることにより判定を行う。例えば、図５に示す位置関係の場合、要素１８１ａは交点を始点とする時計回りの円弧なので、要素の位置フラグは−１／ｒとなり、要素１８１ｂは線分なので、位置フラグは０となる。したがって、位置フラグの大小関係は、−１／ｒ（要素１８１ａ）＜０（要素１８１ｂ）であるので、反時計回りの各要素の配置順は、基準線に対して要素１８１ａ、要素１８１ｂの順となる。
【００３６】
以上の処理によって算出される交点種別の例を図６に示す。
図６（ａ）は、各ループが互いに交差するケース（以下、クロス）の一例を示す図である。図６（ａ）に示すように、図形Ａにおける前要素１１１及び後要素１１２を含むループと図形Ｂにおける前要素２１１及び後要素２１２を含むループとが交点３１１で交差している。すなわち、図形Ａのループは図形Ｂの内部へ進行し、図形Ｂのループは図形Ａの外部へ進行している。図６（ａ）に示す例以外に、図形Ａのループが外部へ進行し、図形Ｂのループが内部へ進行するパターンも同様にクロスである。
【００３７】
図６（ｂ）は、交点３２１の前または後で２つの要素が一致する組み合わせのケース（以下、１要素一致）の一例を示す図である。
図６（ｂ）に示すように、図形Ａにおける前要素１２１と図形Ｂにおける前要素２２１とが一致している。さらに、図形Ａにおける後要素１２２は、交点３２１から図形Ｂの外部へ進行し、図形Ｂにおける後要素２２２は、交点３２１から図形Ａの内部へ進行している。
【００３８】
図６（ｂ）に示す例以外にも、図形Ａ及び図形Ｂそれぞれのループが相手図形に対し、「外部から一致、内部から一致」、「一致から内部、一致から外部」及び「内部から一致、外部から一致」の３つのパターンも同様に１要素一致である。さらに、一致している２つの要素の進行方向が互いに異なる場合も存在する。この場合、図形Ａ及び図形Ｂそれぞれのループが相手図形に対し、「一致から外部、外部から一致」、「一致から内部、内部から一致」、「内部から一致、一致から内部」及び「外部から一致、一致から外部」の４つのパターンがある。この４つのパターンも同様に１要素一致であり、全部で８つのパターンに分類される。
【００３９】
図６（ｃ）は、２つの図形が接するケース（以下、跳ね返り）の一例を示す図である。
図６（ｃ）に示すように、図形Ａにおける前要素１３１及び後要素１３２を含むループと図形Ｂにおける前要素２３１及び後要素２３２を含むループとが交点３３１で接している。図６（ｃ）に示す例は、図形Ａが図形Ｂの外部側に位置し、図形Ｂが図形Ａの内部側に位置する例である。なお、図６（ｃ）に示す例以外に、図形Ａ及び図形Ｂそれぞれが相手図形に対し、「外部側、外部側」、「内部側、外部側」及び「内部側、内部側」の３つのパターンがある。この３つのパターンも跳ね返りであり、全部で４パターンに分類される。
【００４０】
図６（ｄ）は、２つの要素が交点３４１の前後でそれぞれ一致するケース（以下、２要素一致）の一例を示す図である。
図６に示すように、図形Ａにおける前要素１４１と図形Ｂにおける前要素２４１とが一致し、図形Ａにおける後要素１４２と図形Ｂにおける後要素２４２とが一致している。また、図６（ｄ）に示す例以外に、図形Ａのループの方向と図形Ｂのループの方向とが逆向きであるパターンも２要素一致である。
【００４１】
図６（ｅ）は、１つの要素に対して相手図形の２つの要素が一致するケース（以下、先端交点）の一例を示す図である。この先端交点は、突起した先端形状部や切欠き部に発生するパターンである。
図６（ｅ）に示す例では、図形Ｂにおける前要素２５１及び後要素２５２が交点３５１で突起した先端形状部を構成し、図形Ａにおける後要素１５２と、図形Ｂにおける前要素２５１及び後要素２５２とが一致している。また、図形Ａにおける前要素１５１は、図形Ｂの内部側に位置している。
【００４２】
この先端交点では、少なくとも一方の図形が微小幅の先端形状を形成している。詳細については後述するが、このケースでは、１要素一致の交点がこの微小幅の先端形状部に存在するかどうかを検出し、先端形状部に対する位置判定を行い、交点種別の更新を行う。交点種別が更新された場合には、先端部の交点の交点種別も先端形状部に対して再判定し、先端部の交点の交点種別を更新する。
【００４３】
この更新処理について、図７を参照しながら具体的に説明する。
図７において、図形Ａには第１の要素１０１と第２の要素１０２とが含まれている。また、図形Ｂには第１の要素２０１と第２の要素２０２とが含まれている。そして、図形Ａと図形Ｂとでは、第１の交点３０１、第２の交点３０２及び第３の交点３０３で交差している。
【００４４】
まず、図形Ａを構成する第１の要素１０１と、図形Ｂを構成する第１の要素２０１及び第２の要素２０２とが交差する第１の交点３０１が先端交点として算出される。なお、図形Ｂを構成する第２の要素２０２の始点は第１の交点３０１となっている。さらに、図形Ａを構成する第１の要素１０１と図形Ｂを構成する第２の要素２０２とにより、第２の交点３０２が算出される。この第２の交点３０２は、「内部から一致、一致から内部」のパターンであり、１要素一致である。
【００４５】
この第２の交点３０２は、第１の交点３０１に対して図形Ｂを構成する第２の要素２０２の前要素である第１の要素２０１上に位置する。すなわち、第２の交点３０２と図形Ｂを構成する第１の要素２０１との距離が許容誤差値以内と判定される。これにより、図形Ｂを構成する第１の要素２０１及び第２の要素２０２で先端形状部を形成していると判断することができる。
【００４６】
そして、図形Ａを構成する第１の要素１０１は、図形Ｂを構成する第１の要素２０１と一致することから、第２の交点３０２の交点種別を、「内部から一致、一致から内部の１要素一致」ではなく、「逆向きの２要素一致」に更新する。さらに、第１の交点３０１は、図形Ａを構成する第１の要素１０１が相手ループに対し一致から図形Ｂの外部に進行すると判定され、第１の交点３０１の交点種別を「一致から外部、一致から内部の１要素一致」に更新する。
【００４７】
図１の説明に戻り、次のステップＳ１１０５において、記憶部４に記憶されている演算種別及びステップＳ１１０４で算出された交点種別の情報から、それぞれの交点について必要であるかどうかを判定し、ループの生成に必要な交点と不要な交点とに分類する。この分類処理について図８のフローチャートを参照しながら説明する。
【００４８】
図８は、本実施形態における交点の分類処理手順の一例を示すフローチャートである。
まず、ステップＳ１２０１において、記憶部４に記憶されている交点の情報から１つの交点の情報を読み出し、読み出した情報からその交点の交点種別を参照する。次に、ステップＳ１２０２において、その交点の交点種別がクロスであるか否かを判定する。この判定の結果、交点種別がクロスである場合は、ステップＳ１２０５へ進む。一方、ステップＳ１２０２の判定の結果、交点種別がクロス以外である場合は、ステップＳ１２０３へ進む。
【００４９】
次に、ステップＳ１２０３において、その交点の交点種別が１要素一致であるか否かを判定する。この判定の結果、交点種別が１要素一致である場合は、ステップＳ１２０４へ進む。一方、ステップＳ１２０２の判定の結果、交点種別が１要素一致以外の場合は、ステップＳ１２０６へ進む。
【００５０】
次に、ステップＳ１２０４において、図形Ａが「一致から内部または内部から一致」のパターンでかつ演算種別が「ＡＮＤ」を満たすか、もしくは、図形Ａが「一致から外部または外部から一致」のパターンでかつ演算種別が「ＯＲ」を満たすか否かを判定する。この判定の結果、前述した要件の何れかを満たす場合は、対象となる交点は新たなループを生成するために必要な交点であると判定し、ステップＳ１２０５へ進む。一方、ステップＳ１２０４の判定の結果、前述した要件をいずれも満たさない場合は、対象となる交点は新たなループを生成するために必要な交点ではないと判定し、ステップＳ１２０６へ進む。なお、ステップＳ１２０４の判定処理は、交点種別の図形Ａの情報のみを用いて行う。
【００５１】
次に、ステップＳ１２０５において、ステップＳ１２０１で読み出した交点の情報は新たなループを生成するために必要な交点情報として記憶部４に記憶する。一方、ステップＳ１２０６においては、ステップＳ１２０１で読み出した交点の情報は新たなループを生成する際に不要な交点情報として記憶部４に記憶する。なお、ステップＳ１２０５において、新たなループを生成するために必要な交点であることを識別できるフラグを交点情報に追加するようにしてもよい。また、ステップＳ１２０６において、新たなループを生成する際に不要な交点であることを識別するフラグを交点情報に追加するようにしてもよい。
【００５２】
次に、ステップＳ１２０７において、交点種別を参照していない交点が存在するかどうかを判定する。この判定の結果、交点種別を参照していない交点が存在する場合は、ステップＳ１２０１へ戻る。一方、ステップＳ１２０７の判定の結果、交点種別を参照していない交点がない場合は、ステップＳ１２０８へ進み、交点の分類処理を終了する。
【００５３】
また、図１のステップＳ１１０５においては、交点の分類処理を行った後に、図形Ａ及び図形Ｂの構成要素に対し、新たなループを生成するために必要と判定された交点によって要素分解を行う。要素分解を行う時、要素種別を継承する場合、属性情報を保持している場合には属性情報の更新を行い、以下の処理により生成した図形の情報を、付随情報も含めて記憶部４にそれぞれ記憶しておく。さらに、交点種別での要素情報も要素分解後の図形に対応できるよう更新し、記憶部４に記憶する。
【００５４】
詳細な説明は後述するが、以降の処理では、中央処理部１は図形生成手段として機能し、新たな図形Ｃを得るために必要な処理を行う。まず、次のステップＳ１１０６〜ステップＳ１１０８において、演算目的のループを生成する処理及びループを取り出す処理を行い、生成したループの情報を、記憶部４に記憶する。この処理では、ステップＳ１１０５で要素分解して更新された情報に基づいて行う。なお、ループの進行方向は、後述するステップＳ１１０９にて決定される。
【００５５】
まず、ステップＳ１１０６では、中央処理部１は選択手段として機能し、ステップＳ１１０５で分類した、新たなループを生成するために必要な交点を選択する。そして、中央処理部１はループ生成手段として機能し、選択した交点を用いてループの生成処理を行う。具体的には、演算種別が「ＡＮＤ」の場合は、相手図形に対して内部に進む交点をスタート位置として、それに続く要素を探索する。そして、新たなループを生成するために必要と判定された交点に達したら、順次相手図形の要素に乗り移る処理（以下、乗り移り処理）を行う。すなわち、交点を境目に図形Ａから図形Ｂへ、あるいは、図形Ｂから図形Ａへ探索要素を変更する処理を行う。そして、スタート位置の交点に到達するまで、要素を探索し、探索順に要素を連結してループを構成する。
【００５６】
一方、演算種別が「ＯＲ」の場合は、相手図形に対して外部に進む交点をスタート位置として、「ＡＮＤ」の場合と同様に要素を探索し、探索順に要素を連結してループを構成する。なお、通過した交点には、処理済と認識できるフラグを登録し、処理対象となっているすべての交点が処理済となるまで、この処理を繰り返す。これによって、新たなループを生成するために必要と判定された交点によるループ生成処理が完了する。このステップＳ１１０６におけるループの生成処理について図９〜図１１を参照しながら説明する。
【００５７】
図９（ａ）は、図形Ａと図形Ｂとの間で交差する交点の分布を示す図である。
図形Ａは、図９（ｂ）に示すように、反時計回りのループ４０１と時計回りのループ４０２とにより１つの領域として構成されている。一方、図形Ｂは、図９（ｃ）に示すように、反時計回りのループ５０１と時計回りのループ５０２とにより１つの領域として構成されている。図９（ａ）に示すように、それぞれのループが交差して、第１の交点６０１〜第９の交点６０９が算出されている。なお、図９（ａ）に示す矢印は、要素の進行向きを示したものである。
【００５８】
図９（ａ）に示す例では、第１の交点６０１〜第４の交点６０４の交点種別はクロスと判定され、第６の交点６０６〜第９の交点６０９の交点種別は１要素一致と判定される。また、第５の交点６０５の交点種別は、逆向きの２要素一致と判定される。
【００５９】
図１０は、演算種別が「ＯＲ」の場合におけるループの生成処理手順の一例を示す図である。
演算種別が「ＯＲ」の場合は、ステップＳ１１０５において、第１の交点６０１、第２の交点６０２、第３の交点６０３及び第４の交点６０４が新たなループを生成するために必要な交点と判定され、図１０（ａ）に示すように交点が選択される。そして、これらの第１の交点６０１〜第４の交点６０４の中から、図形Ａの要素が図形Ｂの外部に進む交点に着目する。
【００６０】
図１０（ａ）に示す例では、第１の交点６０１に着目し、第１の交点６０１を演算結果として求めたいループのスタート位置として決定する。そして、図形Ａの要素を順次探索し、第３の交点６０３にて乗り移り処理を行い、図形Ｂの要素を探索し、スタート位置である第１の交点６０１に到達するまで要素を探索する。そして、探索した要素を連結することにより、図１０（ｂ）に示す図形Ｃの反時計回りのループ７０１を生成する。ここで、第１の交点６０１及び第３の交点６０３は、処理済の交点となる。
【００６１】
次に、残りの交点から交点種別における図形Ａの情報を参照し、図形Ｂの外部に進む第４の交点６０４に着目し、この第４の交点６０４をスタート位置として決定する。そして、同様に図形Ａの要素を順次探索し、第２の交点６０２にて乗り移り処理を行い、図形Ｂの要素を探索し、スタート位置である第４の交点６０４に到達するまで要素を探索する。そして、探索された要素を連結することにより、図１０（ｃ）に示す図Ｃの時計回りのループ７０２を生成する。
【００６２】
図１１は、演算種別が「ＡＮＤ」の場合におけるループの生成処理手順の一例を示す図である。
演算種別が「ＡＮＤ」の場合は、ステップＳ１１０５において、図１１（ａ）に示すように、第１の交点６０１〜第４の交点６０４と、第６の交点６０６〜第９の交点６０９とが新たなループを生成するために必要な交点と判定される。ＡＮＤ演算では、図形Ａが図形Ｂに対して内部へ進む第２の交点６０２及び第３の交点６０３に着目し、各交点をスタート位置として決定する。ＯＲ演算同様に要素探索及び交点での乗り移り処理を行い、図１１（ｂ）に示すように１つ目の反時計回りのループ８０１を生成し、図１１（ｃ）に示すように２つ目の反時計回りのループ８０２を生成する。
【００６３】
なお、ステップＳ１２０４で新たなループの生成に必要と判定された交点のうち、演算種別が「ＡＮＤ」の場合で、図形Ａの１つのループにおいて図形Ａ側の交点種別が「内部から一致もしくは一致から内部」のパターンの１要素一致しか存在しないものもある。この様なループでは、互いに領域が重なる場合はこれらの交点を新たなループを生成する際に不要な交点として取り扱う。また、演算種別が「ＯＲ」の場合、図形Ａの１つのループにおいて交点種別の図形Ａ側の交点種別が、「外部から一致もしくは一致から外部」のパターンの１要素一致しか存在しない場合も同様である。すなわち、互いに領域が重ならない場合はこれらの交点を新たなループを生成する際に不要な交点として取り扱う。続いて、新たなループを生成する際に不要とされた交点を含むループの取り出し処理について、以下に説明する。
【００６４】
次に、図１のステップＳ１１０７において、中央処理部１はループ抽出手段として機能し、ステップＳ１１０５でループを生成する際に不要と判定された交点を用いてループの取り出し処理を行う。まず、中央処理部１は選択手段として機能し、新たなループを生成する際に不要な交点のみからなるループが存在する場合に、これらの交点を選択する。そして、各交点の交点種別からそのループが相手図形に対して内部であるか、外部であるかを判定する。この判定は、図形Ａのループに対しては、交点種別の図形Ａの情報を用い、図形Ｂのループに対しては、交点種別の図形Ｂの情報を用いる。なお、ループに含まれる全ての交点の交点種別が２要素一致である場合には、２つのループが一致する。この場合は、ループの進行方向が同じであるか逆向きであるかを判定する。
【００６５】
演算種別が「ＡＮＤ」もしくは「ＮＯＴ」の場合には、相手図形に対して内部と判定されたループ、及び２つのループが同じ進行方向で一致しているループを取り出す。また、演算種別が「ＯＲ」の場合には、相手図形に対して外部と判定されたループ、及び２つのループが同じ進行方向で一致しているループを取り出す。そして、取り出したループについての情報を、演算結果として記憶部４に記憶する。
【００６６】
なお、演算種別が「ＮＯＴ」の場合は、図形Ａを構成するループに対してのみ、取り出し処理を行う。また、２つのループが同じ進行方向で一致している場合は、図形Ａあるいは図形Ｂいずれかから１ループのみを取り出す。
【００６７】
図１２は、新たなループの生成で不要な交点により、斜線で示した相手図形に対し、各ループが、内部、外部、一致で同じ向き、一致で逆向きとなる例を示した図である。図１２（ａ）には、相手図形に対して内部に位置する例、及び外部に位置する例を示している。また、図１２（ｂ）は、相手図形に対してループが一致しているが進行方向が逆である例を示しており、図１２（ｃ）は、相手図形に対してループが一致して、かつ進行方向も同じである例を示している。この情報により、要素探索をすることなく、目的としたループを直接取得することができる。
【００６８】
次に、ステップＳ１１０８において、交点が存在しないループに対して、ループを構成する要素に着目し、着目要素の始点あるいは中点に対し、相手図形の内部か外部かを判定する。そして、演算種別に応じて、ループを取り出し、出力結果に追加する。すなわち、ＡＮＤ演算またはＮＯＴ演算の場合は、内部となるループを取り出し、ＯＲ演算の場合は、外部となるループを取り出す。ここで、ＮＯＴ演算は、図形Ａのループからのみ取り出す。
【００６９】
次に、ステップＳ１１０９において、出力結果として得られた各ループの回り向きを、要素の向きを考慮した面積計算などを利用して決定し、各ループの包含関係から領域化し、図形Ｃとして生成する。そして、生成した図形Ｃについての情報を記憶部４に記憶する。この際、中央処理部１により、処理前の各ループに対し、微小要素の削除処理、「ぶら下がり稜線形状」と呼ばれる要素が折り返す許容誤差以下の幅部のカット処理、及び微小面積の領域の削除処理を行う。
【００７０】
次に、ステップＳ１１１０において、図形Ｃについての情報を指定のデータ形式に変換して、出力データとして通信インターフェイス７を介して外部装置に出力する。あるいは、入出力制御部５により外部記憶媒体６にファイルとして出力する。そして、処理を終了する。
【００７１】
以上のように本実施形態においては、図形を制限することなく、演算対象の図形間の交点種別を算出し、交点を挟む前後の要素の位置及び演算種別から交点を選択するようにした。これにより、選択した交点のいずれかをスタート位置として目的とする図形を高速に作成することができ、膨大な計算時間を要するといった問題が解決される。また、新たなループを生成する際に不要な交点のみが存在するループに対し、交点種別から位置関係を判定するようにしたので、演算種別に応じたループを高速に取り出すことができる。
【００７２】
（本発明に係る他の実施形態）
前述した本発明の実施形態における図形処理装置を構成する各手段、並びに図形処理方法の各工程は、コンピュータのＲＡＭやＲＯＭなどに記憶されたプログラムが動作することによって実現できる。このプログラム及び前記プログラムを記録したコンピュータ読み取り可能な記録媒体は本発明に含まれる。
【００７３】
また、本発明は、例えば、システム、装置、方法、プログラムもしくは記録媒体等としての実施形態も可能であり、具体的には、複数の機器から構成されるシステムに適用してもよいし、また、一つの機器からなる装置に適用してもよい。
【００７４】
なお、本発明は、前述した実施形態の機能を実現するソフトウェアのプログラム（実施形態では図１、８に示すフローチャートに対応したプログラム）を、システムまたは装置に直接、または遠隔から供給する場合も含む。そして、そのシステムまたは装置のコンピュータが前記供給されたプログラムコードを読み出して実行することによっても達成される場合を含む。
【００７５】
したがって、本発明の機能処理をコンピュータで実現するために、前記コンピュータにインストールされるプログラムコード自体も本発明を実現するものである。つまり、本発明は、本発明の機能処理を実現するためのコンピュータプログラム自体も含まれる。
【００７６】
その場合、プログラムの機能を有していれば、オブジェクトコード、インタプリタにより実行されるプログラム、ＯＳに供給するスクリプトデータ等の形態であってもよい。
【００７７】
プログラムを供給するための記録媒体としては、例えば、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスクなどがある。さらに、ＭＯ、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、磁気テープ、不揮発性のメモリカード、ＲＯＭ、ＤＶＤ（ＤＶＤ−ＲＯＭ、ＤＶＤ−Ｒ）などもある。
【００７８】
その他、プログラムの供給方法としては、クライアントコンピュータのブラウザを用いてインターネットのホームページに接続する方法がある。そして、前記ホームページから本発明のコンピュータプログラムそのもの、もしくは圧縮され自動インストール機能を含むファイルをハードディスク等の記録媒体にダウンロードすることによっても供給できる。
【００７９】
また、本発明のプログラムを構成するプログラムコードを複数のファイルに分割し、それぞれのファイルを異なるホームページからダウンロードすることによっても実現可能である。つまり、本発明の機能処理をコンピュータで実現するためのプログラムファイルを複数のユーザに対してダウンロードさせるＷＷＷサーバも、本発明に含まれるものである。
【００８０】
また、その他の方法として、本発明のプログラムを暗号化してＣＤ−ＲＯＭ等の記録媒体に格納してユーザに配布し、所定の条件をクリアしたユーザに対し、インターネットを介してホームページから暗号化を解く鍵情報をダウンロードさせる。そして、その鍵情報を使用することにより暗号化されたプログラムを実行してコンピュータにインストールさせて実現することも可能である。
【００８１】
また、コンピュータが、読み出したプログラムを実行することによって、前述した実施形態の機能が実現される。さらに、そのプログラムの指示に基づき、コンピュータ上で稼動しているＯＳなどが、実際の処理の一部または全部を行い、その処理によっても前述した実施形態の機能が実現され得る。
【００８２】
さらに、その他の方法として、まず記録媒体から読み出されたプログラムが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれる。そして、そのプログラムの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行い、その処理によっても前述した実施形態の機能が実現される。
【図面の簡単な説明】
【００８３】
【図１】本発明の実施形態における図形処理の動作手順の一例を示すフローチャートである。
【図２】本発明の実施形態における図形処理装置の構成例を示すブロック図である。
【図３】本発明の実施形態において、交点を挟む要素の位置関係の一例を示す図である。
【図４】本発明の実施形態における要素の一致判定の一例を示す図である。
【図５】角度差が０となる２要素が交点で接する位置関係の一例を示す図である。
【図６】本発明の実施形態における交点種別の例を示す図である。
【図７】本発明の実施形態における交点種別の先端交点の一例を示す図である。
【図８】本発明の実施形態において、必要な交点か不要な交点かを判定する処理手順の一例を示すフローチャートである。
【図９】演算処理時の交点の分布の一例を示す図である。
【図１０】本発明の実施形態において、演算種別が「ＯＲ」の場合におけるループの生成処理手順の一例を示す図である。
【図１１】本発明の実施形態において、演算種別が「ＡＮＤ」の場合におけるループの生成処理手順の一例を示す図である。
【図１２】本発明の実施形態において、不要な交点によるループの位置情報の例を示す図である。
【符号の説明】
【００８４】
１  中央演算部
２  入力部
３  表示部
４  記憶部
５  入出力制御部
６  外部記憶媒体
７  通信インターフェイス
８  バスライン
１０  図形処理装置
【図１】
2009259048.tif 000003
【図２】
2009259048.tif 000004
【図３】
2009259048.tif 000005
【図４】
2009259048.tif 000006
【図５】
2009259048.tif 000007
【図６】
2009259048.tif 000008
【図７】
2009259048.tif 000009
【図８】
2009259048.tif 000010
【図９】
2009259048.tif 000011
【図１０】
2009259048.tif 000012
【図１１】
2009259048.tif 000013
【図１２】
2009259048.tif 000014