(57)【特許請求の範囲】
【請求項１】
Ｘ軸方向を左右方向とし、かつ、Ｙ軸方向を上下方向とするＸ−Ｙ座標面上における２つの凸多角形の重なり合った部分に対応する図形を切り出す図形クリッピング装置であって、
それぞれの凸多角形の各辺のうち、それぞれの凸多角形の最上に位置する頂点である上端頂点から最下に位置する頂点である下端頂点までを右回りに辿ることができる辺である右辺についてそれぞれ設けられた属性フラグおよびそれぞれの凸多角形の前記上端頂点から前記下端頂点までを左回りに辿ることができる辺である左辺についてそれぞれ設けられた属性フラグと、
前記２つの凸多角形の前記上端頂点のうち、より下方に位置する上端頂点を初期頂点として選択し、前記初期頂点が当該初期頂点を含まない他方の凸多角形の前記左辺と前記右辺との間に位置するか否かを判定し、その判定の結果、前記初期頂点が前記他方の凸多角形の左辺と右辺との間に位置するときには、当該初期頂点の座標を出力し、かつ、前記初期頂点を含む方の凸多角形の前記右辺についての前記属性フラグおよび前記左辺についての前記属性フラグをそれぞれＯＮ状態にセットすると共に前記他方の凸多角形の前記右辺についての前記属性フラグおよび前記左辺についての前記属性フラグをそれぞれＯＦＦ状態にセットし、一方、前記初期頂点が前記他方の凸多角形の左辺と右辺との間に位置しないときには、前記初期頂点を含む方の凸多角形の前記右辺についての前記属性フラグおよび前記左辺についての前記属性フラグをそれぞれＯＦＦ状態にセットすると共に前記他方の凸多角形の前記右辺についての前記属性フラグおよび前記左辺についての前記属性フラグをそれぞれＯＦＦ状態にセットする初期設定手段と、
前記初期頂点の両隣にある２つの頂点と、当該初期頂点を通り、かつ、Ｘ軸に平行な線と交差する前記他方の凸多角形の２辺それぞれの端点である２つ頂点のうち、より下方に位置するそれぞれの頂点との４つの頂点、もしくは、前回の選択頂点に隣接し、かつ、当該選択頂点よりも下方に位置する頂点と、前記前回の選択頂点の候補である選択候補頂点から前記前回の選択頂点を除く３つの頂点との４つの頂点、のいずれか一方の４つの頂点を今回の選択候補頂点とし、当該選択候補頂点のうち最上に位置する頂点を今回の前記選択頂点として選択する頂点選択手段と、
前記選択頂点を含む方の凸多角形の各辺のうち、当該選択頂点と当該選択頂点よりも上方に位置する頂点とを端点とする辺を選択辺とし、当該選択頂点を含まない方の凸多角形の各辺のうち、前記選択候補頂点と当該選択候補頂よりも上方に位置する頂点とを端点とする２つの辺と前記選択辺とがそれぞれ交差するか否かを判定する交差判定手段と、
前記交差判定手段による判定の結果、前記選択辺が前記選択頂点を含まない方の凸多角形の辺と交差するときには、その度に、その交点の座標を出力すると共に、互いに交差する辺についての前記属性フラグをそれぞれ反転させる交点座標出力手段と、
前記属性フラグのうち、前記選択辺に対応する属性フラグがＯＮ状態か否かを判定する属性フラグ判定手段と、
前記属性フラグ判定手段によって属性フラグがＯＮ状態と判定されたときに、前記選択頂点の座標を出力する頂点座標出力手段と、
前記頂点座標出力手段によって出力された前記選択頂点の座標、前記初期設定手段によって前記初期頂点の座標が出力された場合にはその座標、および、前記交点座標出力手段によって前記交点の座標が出力された場合にはその座標に基づいて前記２つの凸多角形の重なり合った部分に対応する図形を切り出す切出手段と、
を備えてなる図形クリッピング装置。
【請求項２】
Ｘ軸方向を左右方向とし、かつ、Ｙ軸方向を上下方向とするＸ−Ｙ座標面上における２つの凸多角形の重なり合った部分に対応する図形を切り出す図形クリッピング方法であって、
制御手段が、前記２つの凸多角形それぞれの最上に位置する頂点である上端頂点のうち、より下方に位置する上端頂点を初期頂点として選択し、前記初期頂点が当該初期頂点を含まない他方の凸多角形の前記上端頂点から最下に位置する頂点である下端頂点までを左回りに辿ることができる辺である左辺と当該凸多角形の前記上端頂点から前記下端頂点までを右回りに辿ることができる辺である右辺との間に位置するか否かを判定し、その判定の結果、前記初期頂点が前記他方の凸多角形の左辺と右辺との間に位置するときには、前記２つの凸多角形それぞれの前記左辺についての属性フラグおよび前記右辺についての属性フラグと、前記２つの凸多角形の重なり合った部分に対応する図形の各頂点の座標と、を記憶する記憶手段に当該初期頂点の座標を出力し、かつ、前記初期頂点を含む方の凸多角形の前記右辺についての属性フラグおよび前記左辺についての属性フラグをそれぞれＯＮ状態にして前記記憶手段にセットすると共に前記他方の凸多角形の前記右辺についての属性フラグおよび前記左辺についての属性フラグをそれぞれＯＦＦ状態にして前記記憶手段にセットし、一方、前記初期頂点が前記他方の凸多角形の左辺と右辺との間に位置しないときには、前記初期頂点を含む方の凸多角形の前記右辺についての属性フラグおよび前記左辺についての属性フラグをそれぞれＯＦＦ状態にして前記記憶手段にセットすると共に前記初期頂点を含まない方の凸多角形の前記右辺についての属性フラグおよび前記左辺についての属性フラグをそれぞれＯＦＦ状態にして前記記憶手段にセットする初期設定ステップと、
前記制御手段が、前記初期頂点の両隣にある２つの頂点と、当該初期頂点を通り、かつ、Ｘ軸に平行な線と交差する前記他方の凸多角形の２辺それぞれの端点である２つ頂点のうち、より下方に位置するそれぞれの頂点との４つの頂点、もしくは、前回の選択頂点に隣接し、かつ、当該選択頂点よりも下方に位置する頂点と、前記前回の選択頂点の候補である選択候補頂点から前記前回の選択頂点を除く３つの頂点との４つの頂点、のいずれか一方の４つの頂点を今回の選択候補頂点とし、当該選択候補頂点のうち最上に位置する頂点を今回の前記選択頂点として選択する頂点選択ステップと、
前記制御手段が、前記選択頂点を含む方の凸多角形の各辺のうち、当該選択頂点と当該選択頂点よりも上方に位置する頂点とを端点とする辺を選択辺とし、当該選択頂点を含まない方の凸多角形各辺のうち、前記選択候補頂点と当該選択候補頂よりも上方に位置する頂点とを端点とする２つの辺と前記選択辺とがそれぞれ交差するか否かを判定する交差判定ステップと、
前記制御手段が、前記交差判定ステップにおける判定の結果、前記選択辺が前記選択頂点を含まない方の凸多角形の辺と交差するときには、その度に、その交点の座標を前記記憶手段に出力すると共に、互いに交差する辺について前記記憶手段にセットされている属性フラグをそれぞれ反転させる交点座標出力ステップと、
前記制御手段が、前記記憶手段にセットされている属性フラグのうち、前記選択辺に対応する属性フラグがＯＮ状態か否かを判定する属性フラグ判定ステップと、
前記制御手段が、前記属性フラグ判定ステップにおいて属性フラグがＯＮ状態と判定されたときに、前記選択頂点の座標を前記記憶手段に出力する頂点座標出力ステップと、
前記制御手段が、前記頂点選択ステップ、交差判定ステップ、交点座標出力ステップおよび頂点座標出力ステップを繰り返し実行し、前記頂点座標出力ステップにおいて出力された前記選択頂点の座標、前記初期設定ステップにおいて前記初期頂点の座標が出力された場合にはその座標、および、前記交点座標出力ステップにおいて前記交点の座標が出力された場合にはその座標に基づいて前記２つの凸多角形の重なり合った部分に対応する図形を切り出す切出ステップと、
を備えてなる図形クリッピング方法。
【請求項３】
Ｘ軸方向を左右方向とし、かつ、Ｙ軸方向を上下方向とするＸ−Ｙ座標面上における２つの凸多角形の重なり合った部分に対応する図形を切り出す図形クリッピング処理を実行するコンピュータを、
前記２つの凸多角形それぞれの最上に位置する頂点である上端頂点のうち、より下方に位置する上端頂点を初期頂点として選択し、前記初期頂点が当該初期頂点を含まない他方の凸多角形の前記上端頂点から最下に位置する頂点である下端頂点までを左回りに辿ることができる辺である左辺と当該凸多角形の前記上端頂点から前記下端頂点までを右回りに辿ることができる辺である右辺との間に位置するか否かを判定し、その判定の結果、前記初期頂点が前記他方の凸多角形の左辺と右辺との間に位置するときには、前記２つの凸多角形それぞれの前記左辺についての属性フラグおよび前記右辺についての属性フラグと、前記２つの凸多角形の重なり合った部分に対応する図形の各頂点の座標と、を記憶する記憶手段に当該初期頂点の座標を出力し、かつ、前記初期頂点を含む方の凸多角形の前記右辺についての属性フラグおよび前記左辺についての属性フラグをそれぞれＯＮ状態にして前記記憶手段にセットすると共に前記他方の凸多角形の前記右辺についての属性フラグおよび前記左辺についての属性フラグをそれぞれＯＦＦ状態にして前記記憶手段にセットし、一方、前記初期頂点が前記他方の凸多角形の左辺と右辺との間に位置しないときには、前記初期頂点を含む方の凸多角形の前記右辺についての属性フラグおよび前記左辺についての属性フラグをそれぞれＯＦＦ状態にして前記記憶手段にセットすると共に前記初期頂点を含まない方の凸多角形の前記右辺についての属性フラグおよび前記左辺についての属性フラグをそれぞれＯＦＦ状態にして前記記憶手段にセットする初期設定手段、
前記初期頂点の両隣にある２つの頂点と、当該初期頂点を通り、かつ、Ｘ軸に平行な線と交差する前記他方の凸多角形の２辺それぞれの端点である２つ頂点のうち、より下方に位置するそれぞれの頂点との４つの頂点、もしくは、前回の選択頂点に隣接し、かつ、当該選択頂点よりも下方に位置する頂点と、前記前回の選択頂点の候補である選択候補頂点から前記前回の選択頂点を除く３つの頂点との４つの頂点、のいずれか一方の４つの頂点を今回の選択候補頂点とし、当該選択候補頂点のうち最上に位置する頂点を今回の前記選択頂点として選択する頂点選択手段、
前記選択頂点を含む方の凸多角形の各辺のうち、当該選択頂点と当該選択頂点よりも上方に位置する頂点とを端点とする辺を選択辺とし、当該選択頂点を含まない方の凸多角形各辺のうち、前記選択候補頂点と当該選択候補頂よりも上方に位置する頂点とを端点とする２つの辺と前記選択辺とがそれぞれ交差するか否かを判定する交差判定手段、
前記交差判定手段による判定の結果、前記選択辺が前記選択頂点を含まない方の凸多角形の辺と交差するときには、その度に、その交点の座標を前記記憶手段に出力すると共に、互いに交差する辺について前記記憶手段にセットされている属性フラグをそれぞれ反転させる交点座標出力手段、
前記記憶手段にセットされている属性フラグのうち、前記選択辺に対応する属性フラグがＯＮ状態か否かを判定する属性フラグ判定手段、
前記属性フラグ判定手段によって属性フラグがＯＮ状態と判定されたときに、前記選択頂点の座標を前記記憶手段に出力する頂点座標出力手段、および、
前記頂点座標出力手段によって出力された前記選択頂点の座標、前記初期設定手段によって前記初期頂点の座標が出力された場合にはその座標、および、前記交点座標出力手段によって前記交点の座標が出力された場合にはその座標に基づいて前記２つの凸多角形の重なり合った部分に対応する図形を切り出す切出手段、
として機能させるプログラムがコンピュータ読み取り可能に記録されていることを特徴とする記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、例えば、画像処理装置、描画装置または図形編集装置等に用いられる図形クリッピング装置および図形クリッピング方法に関し、さらに詳しくは、複数の凸多角形の互いに重なり合った部分を抽出する図形クリッピング装置および図形クリッピング方法に関する。
【０００２】
【従来の技術】
例えば、コンピュータグラフィックス等の分野において、画像の作成または編集を行うときには、画像処理装置、描画装置または図形編集装置等が用いられる。これらの装置は、画像を構成する複数の図形に対応する図形データに対して演算処理を施し、図形の変形、移動、削除等の図形編集処理を行う。
【０００３】
ところで、このような図形編集処理の１つに、図形クリッピング処理がある。図形クリッピング処理とは、複数の図形の互いに重なり合った部分を切り出す（クリッピングする）処理である。この図形クリッピング処理には、スラブ法が用いられる。スラブ法は、一般に知られた方法であり、例えば、朝野哲夫「計算幾何学」，朝倉書店等に記載されている。
【０００４】
ここで、２つの凸多角形の互いに重なり合った部分を切り出す方法を図1１に従って説明する。
【０００５】
図１１において、Ｘ−Ｙ座標面上に配置された凸多角形Ｐと凸多角形Ｑとは、互いに重なり合っている。ここで、互いに重なり合った部分を重なり部分Ｒとする。また、凸多角形Ｐの各頂点のうち、最上に位置する頂点を上端点Ｐｕとし、最下に位置する頂点を下端点Ｐｂとし、凸多角形Ｐの各辺を、上端点Ｐｕから下端点Ｐｂに向けて反時計回りに辿ったときに通過する各頂点を、通過する順番にＰＬｉ（ｉ＝１，２，３，…）とし、凸多角形Ｐの各辺を、下端点Ｐｂから上端点Ｐｕに向けて反時計回りに辿ったときに通過する各頂点を、通過する順番にＰＲｊ（ｊ＝１，２，３，…）とする。同様に、凸多角形Ｑの各頂点のうち、最上に位置する頂点を上端点Ｑｕとし、最下に位置する頂点を下端点Ｑｂとし、凸多角形Ｑの各辺を、上端点Ｑｕから下端点Ｑｂに向けて反時計回りに辿ったときに通過する各頂点を、通過する順番にＱＬｍ（ｍ＝１，２，３，…）とし、凸多角形Ｑの各辺を、下端点Ｑｂから上端点Ｑｕに向けて反時計回りに辿ったときに通過する各頂点を、通過する順番にＱＲｎ（ｎ＝１，２，３，…）とする。さらに、図の左上端をＸ−Ｙ座標面の原点とし、例えば、凸多角形Ｐの上端点ＰｕのＹ座標をＹ（Ｐｕ）と表記する。その他の頂点Ｐｂ，ＰＬｉ，ＰＲｊ，Ｑｕ，Ｑｂ，ＱＬｍ，ＱＲｎのＹ座標についてもこれと同様に表記する。
【０００６】
以上のような条件の下で、例えば、凸多角形Ｑの各頂点ＱＲｎに着目し、以下のステップ(1)〜(3)を実行する。
【０００７】
(1)凸多角形Ｐの各頂点ＰＬｉ，ＰＲｊの中から、下記の数式１を満たす頂点ＰＬｉ，ＰＲｊを選択する。
【０００８】
【数１】
Ｙ（ＰＬｉ-1）＜Ｙ（ＱＲｎ）≦Ｙ（ＰＬｉ）
Ｙ（ＰＲｊ+1）＜Ｙ（ＱＲｎ）≦Ｙ（ＰＲｊ）
(2)凸多角形Ｑの辺（ＱＲｎ，ＱＲｎ+1）が、凸多角形Ｐのいずれかの辺と交わるか否かを判定し、交わるときには、その交点の座標を出力する。
【０００９】
(3)凸多角形Ｑの頂点ＱＲｎが、凸多角形Ｐの辺（ＰＬｉ-1，ＰＬｉ）と辺（ＰＲｊ，ＰＲｊ+1）との間に位置するか否かを判定し、頂点ＱＲｎがこれらの辺の間に位置するときには、頂点ＱＲｎの座標を出力する。
【００１０】
例えば、図１１中の凸多角形Ｑの頂点ＱＲ２に着目し、上記ステップ(1)〜(3)を実行した場合、上記数式１を満たす頂点ＰＬｉ，ＰＲｊは、ＰＬ３，Ｐｂ（ＰＱ０＝Ｐｂとする）である。そして、凸多角形Ｑの辺（ＱＲ２，ＱＲ３）は、凸多角形Ｐの辺（ＰＬ１，ＰＬ２）と交わるので、交点Ａの座標を出力する。さらに、頂点ＱＲ２は、辺（ＰＬ２，ＰＬ３）と辺（Ｐｂ，ＰＲ１）との間に位置するので、頂点ＱＲ２の座標を出力する。
【００１１】
上記ステップ(1)〜(3)を各凸多角形Ｐ，Ｑの各頂点ＰＬｉ，ＰＲｊ，ＱＬｍ，ＱＲｎ、上端点Ｐｕ，Ｑｕおよび下端点Ｐｂ，Ｑｂについて実行することによって、重なり部分Ｒを包囲する各点の座標が出力されることになる。なお、上端点Ｐｕ，Ｑｕについては、上記ステップ(1)および(3)のみを実行する。そして、出力された各点の座標に基づいて重なり部分Ｒに対応する図形を特定することができ、この重なり部分Ｒを切り出すことができる。
【００１２】
なお、スラブ法とは、凸多角形を複数の台形（スラブ）の集合と考え、異なる凸多角形に属するスラブの間に交差があるか否かを判定することによって、各凸多角形の重なり部分があるか否かを認識するものである。上述したステップ(1)〜(3)は、このスラブ法に基づいて図形クリッピング処理を実現したときの具体的な手順を示したものである。
【００１３】
【発明が解決しようとする課題】
ところで、上記ステップ(1)〜(3)を各凸多角形の各頂点について実行すれば、理論的には、各凸多角形の重なり部分を切り出すことができる。しかしながら、上記ステップ(1)〜(3)を実際に、画像処理装置、描画装置または図形編集装置に実行させて、図形クリッピング処理を行うと、演算処理に時間がかかるという問題がある。
【００１４】
特に、上記ステップ(3)では、一方の多角形の頂点が他方の多角形の２つの辺との間に位置するか否かの判定を行う。この判定には、頂点の座標および各辺の端点の座標等を用いて外積計算を行う必要があるため、演算処理に時間がかかるという問題がある。
【００１５】
例えば、図形クリッピング処理の対象となる凸多角形が、複雑な形状をなし、膨大な頂点および辺を有する場合、各凸多角形の重なり部分を切り出すには、外積計算を何度も実行しなければならない。また、図形クリッピング処理の対象となる図形が曲線を含む場合には、通常、曲線を多数の短い直線に近似して処理を行う。このような場合にも、頂点および辺の数が膨大となり、外積計算を行う回数が膨大となる。この結果、演算処理の時間が長くなり、画像の作成または編集の作業性が低下する場合があるという問題がある。
【００１６】
本発明は、上述した問題に鑑みなされたものであり、図形クリッピング処理を高速に実行することができ、図形クリッピング作業の作業性を向上させることができる図形クリッピング装置および図形クリッピング方法を提供することを目的としている。
【００１７】
【課題を解決するための手段】
上述した課題を解決するために、請求項１の発明は、Ｘ軸方向を左右方向とし、かつ、Ｙ軸方向を上下方向とするＸ−Ｙ座標面上における２つの凸多角形の重なり合った部分に対応する図形を切り出す図形クリッピング装置であって、それぞれの凸多角形の各辺のうち、それぞれの凸多角形の最上に位置する頂点である上端頂点から最下に位置する頂点である下端頂点までを右回りに辿ることができる辺である右辺についてそれぞれ設けられた属性フラグおよびそれぞれの凸多角形の前記上端頂点から前記下端頂点までを左回りに辿ることができる辺である左辺についてそれぞれ設けられた属性フラグと、前記２つの凸多角形の前記上端頂点のうち、より下方に位置する上端頂点を初期頂点として選択し、前記初期頂点が当該初期頂点を含まない他方の凸多角形の前記左辺と前記右辺との間に位置するか否かを判定し、その判定の結果、前記初期頂点が前記他方の凸多角形の左辺と右辺との間に位置するときには、当該初期頂点の座標を出力し、かつ、前記初期頂点を含む方の凸多角形の前記右辺についての前記属性フラグおよび前記左辺についての前記属性フラグをそれぞれＯＮ状態にセットすると共に前記他方の凸多角形の前記右辺についての前記属性フラグおよび前記左辺についての前記属性フラグをそれぞれＯＦＦ状態にセットし、一方、前記初期頂点が前記他方の凸多角形の左辺と右辺との間に位置しないときには、前記初期頂点を含む方の凸多角形の前記右辺についての前記属性フラグおよび前記左辺についての前記属性フラグをそれぞれＯＦＦ状態にセットすると共に前記他方の凸多角形の前記右辺についての前記属性フラグおよび前記左辺についての前記属性フラグをそれぞれＯＦＦ状態にセットする初期設定手段と、前記初期頂点の両隣にある２つの頂点と、当該初期頂点を通り、かつ、Ｘ軸に平行な線と交差する前記他方の凸多角形の２辺それぞれの端点である２つ頂点のうち、より下方に位置するそれぞれの頂点との４つの頂点、もしくは、前回の選択頂点に隣接し、かつ、当該選択頂点よりも下方に位置する頂点と、前記前回の選択頂点の候補である選択候補頂点から前記前回の選択頂点を除く３つの頂点との４つの頂点、のいずれか一方の４つの頂点を今回の選択候補頂点とし、当該選択候補頂点のうち最上に位置する頂点を今回の前記選択頂点として選択する頂点選択手段と、前記選択頂点を含む方の凸多角形の各辺のうち、当該選択頂点と当該選択頂点よりも上方に位置する頂点とを端点とする辺を選択辺とし、当該選択頂点を含まない方の凸多角形の各辺のうち、前記選択候補頂点と当該選択候補頂よりも上方に位置する頂点とを端点とする２つの辺と前記選択辺とがそれぞれ交差するか否かを判定する交差判定手段と、前記交差判定手段による判定の結果、前記選択辺が前記選択頂点を含まない方の凸多角形の辺と交差するときには、その度に、その交点の座標を出力すると共に、互いに交差する辺についての前記属性フラグをそれぞれ反転させる交点座標出力手段と、前記属性フラグのうち、前記選択辺に対応する属性フラグがＯＮ状態か否かを判定する属性フラグ判定手段と、前記属性フラグ判定手段によって属性フラグがＯＮ状態と判定されたときに、前記選択頂点の座標を出力する頂点座標出力手段と、前記頂点座標出力手段によって出力された前記選択頂点の座標、前記初期設定手段によって前記初期頂点の座標が出力された場合にはその座標、および、前記交点座標出力手段によって前記交点の座標が出力された場合にはその座標に基づいて前記２つの凸多角形の重なり合った部分に対応する図形を切り出す切出手段と、を備えている。
【００１８】
即ち、２つの凸多角形は、例えば、記憶回路内等に形成されたＸ−Ｙ座標平面上に配置されており、これらの凸多角形を所定の走査方向に走査することによって図形クリッピング処理を行う。つまり、Ｘ−Ｙ座標平面上における上方から下方に向けて、図形クリッピング処理は進行する。
【００１９】
また、２つの凸多角形のうち、一方の凸多角形について、最上に位置する頂点である上端頂点から最下に位置する頂点である下端頂点までを右回りに辿ることができる各辺（下端頂点から上端頂点に向けて反時計回りに辿ったときに通過する各辺）を一方の凸多角形の右辺と呼び、一方の凸多角形の各辺を、上端頂点から下端頂点までを左回りに辿ることができる各辺（上端頂点から下端頂点に向けて反時計回りに辿ったときに通過する各辺）を一方の凸多角形の左辺と呼ぶ。そして、一方の凸多角形の右辺についての属性フラグと、一方の凸多角形の左辺についての属性フラグをそれぞれ設ける。ここで、属性フラグとは、例えば、書き換え可能な記録回路上に設けられたフラグであり、ＯＮ状態とＯＦＦ状態の２種類の状態を記憶することができる。
【００２０】
これと同様に、他方の凸多角形についても、上端頂点から下端頂点までを右回りに辿ることができる辺を右辺と呼び、上端頂点から下端頂点までを左回りに辿ることができる辺を左辺と呼ぶ。そして、他方の凸多角形の右辺についての属性フラグと、一方の凸多角形の左辺についての属性フラグをそれぞれ設ける。
【００２１】
このように、４つの属性フラグを用いて図形クリッピング処理を行う。
【００２２】
次に、初期設定手段は、２つの凸多角形の上端頂点のうち、より下方に位置する上端頂点を初期頂点として選択する。さらに、初期設定手段は、初期頂点が当該初期頂点を含まない方の凸多角形の左辺と右辺との間に位置するか否かを判定する。
【００２３】
その判定の結果、初期頂点が当該初期頂点を含まない方の凸多角形の左辺と右辺との間に位置するときには、当該初期頂点の座標を出力し、かつ、初期頂点を含む方の凸多角形の右辺についての属性フラグおよび左辺についての属性フラグをそれぞれＯＮ状態にセットすると共に初期頂点を含まない方の凸多角形の右辺についての属性フラグおよび左辺についての属性フラグをそれぞれＯＦＦ状態にセットする。一方、初期頂点が当該初期頂点を含まない方の凸多角形の左辺と右辺との間に位置しないときには、当該初期頂点の座標を出力せず、初期頂点を含む方の凸多角形の右辺についての属性フラグおよび左辺についての属性フラグをそれぞれＯＦＦ状態にセットすると共に初期頂点を含まない方の凸多角形の右辺についての属性フラグおよび左辺についての属性フラグをそれぞれＯＦＦ状態にセットする。
【００２４】
次に、頂点選択手段は、各凸多角形の各頂点の中から、後述する交差判定手段、交点座標出力手段、属性フラグ判定手段および頂点座標出力手段による一連の処理の対象となる頂点を選択頂点として選択する。
【００２５】
即ち、頂点選択手段、交差判定手段、交点座標出力手段、属性フラグ判定手段および頂点座標出力手段による一連の処理は、繰り返し実行される。そして、この一連の処理が一巡する毎に、頂点選択手段は、各凸多角形の各頂点のうち、未処理の新たな頂点を選択頂点として次々に選択する。
【００２６】
さらに具体的に説明すると、初期設定手段による処理が終了した直後においては、頂点選択手段は、初期頂点の両隣にある２つの頂点と、当該初期頂点を通り、かつ、Ｘ軸に平行な線と交差する他方の凸多角形の２辺それぞれの端点である２つ頂点のうち、より下方に位置するそれぞれの頂点との合計４つの頂点を選択候補頂点として選択し、これら４つの選択候補頂点の中から最上に位置する頂点を選択頂点として選択する。また、頂点選択手段、交差判定手段、交点座標出力手段、属性フラグ判定手段および頂点座標出力手段による一連の処理が１回以上実行された後は、頂点選択手段は、前回の選択頂点に隣接し、かつ、当該選択頂点よりも下方に位置する頂点と、選択候補頂点（前回の選択候補頂点）から前記前回の選択頂点を除いた３つの頂点との合計４つの頂点を選択候補頂点とし、これら４つの選択候補頂点の中から最上に位置する頂点を選択頂点として選択する。
【００２７】
次に、交差判定手段は、選択頂点と当該選択頂点よりも上方に位置する頂点とを端点とする辺を選択辺とし、選択頂点を含まない方の凸多角形において選択候補頂点と当該選択候補頂よりも上方に位置する頂点とを端点とする２つの辺と選択辺とが交差するか否かを判定する。
【００２８】
次に交点座標出力手段は、前記交差判定手段による判定の結果、選択辺が選択頂点を含まない方の凸多角形の２辺のうちのいずれか一方と交差するときには、その交点の座標を出力すると共に、互いに交差する辺についての属性フラグをそれぞれ反転させる。即ち、属性フラグの状態がＯＦＦ状態のときには、それをＯＮ状態に切り換える。一方、属性フラグの状態がＯＮ状態のときには、それをＯＦＦ状態に切り換える。また、交点座標出力手段は、前記交差判定手段による判定の結果、選択辺が選択頂点を含まない方の凸多角形の２辺の双方とそれぞれ交差するときには、各交点の座標を出力すると共に、互いに交差する辺についての属性フラグをそれぞれ反転させる。なお、前記交差判定手段による判定の結果、選択辺が選択頂点を含まない方の凸多角形のいずれの辺とも交差しないときには、各属性フラグの状態は維持される。
【００２９】
次に、属性フラグ判定手段は、選択辺に対応する属性フラグがＯＮ状態か否かを判定する。続いて、頂点座標出力手段は、属性フラグ判定手段によって属性フラグがＯＮ状態と判定されたとき、選択頂点の座標を出力する。
【００３０】
そして、頂点選択手段、交差判定手段、交点座標出力手段、属性フラグ判定手段および頂点座標出力手段による一連の処理を繰り返し実行する。
【００３１】
次に、切出手段は、頂点座標出力手段によって出力された選択頂点の座標、初期設定手段において初期頂点の座標が出力された場合にはその座標、および、交点座標出力手段によって交点の座標が出力された場合にはその座標に基づいて２つの凸多角形の重なり合った部分に対応する図形を切り出す。
【００３２】
このように、上述した図形クリッピング装置では、選択頂点の座標を出力するか否かを、属性フラグの状態に基づいて決定している。そして、属性フラグは、一方の凸多角形の選択頂点が他方の凸多角形の内部にあるときに、ＯＮ状態となり、一方の凸多角形の選択頂点が他方の凸多角形の外部にあるときには、ＯＦＦ状態となるようにセットされる。
【００３３】
例えば、初期設定手段において、一方の凸多角形の初期頂点が他方の凸多角形の２つの辺の間に位置するとき、属性フラグはＯＮ状態にセットされる。一方の凸多角形の初期頂点が、他方の凸多角形の２つの辺の間に位置するということは、即ち、一方の凸多角形の初期頂点が、他方の凸多角形の内部に位置することを意味する。また、交点座標出力手段において、選択辺が他方の凸多角形のいずれかの辺と交差するとき、属性フラグの状態は反転する。選択辺が他方の凸多角形のいずれかの辺と交差したということは、一方の凸多角形の選択頂点が他方の凸多角形の内部に入ったこと、または、一方の凸多角形の選択頂点が他方の凸多角形の内部から外部に出たことを意味する。
【００３４】
このように、属性フラグは、一方の凸多角形の選択頂点が他方の凸多角形の内部に位置するときに、ＯＮ状態にセットされる。従って、属性フラグがＯＮ状態のときに、その選択頂点の座標を出力すれば、各凸多角形の重なり合った部分を包囲する各点の座標を抽出することができ、重なり合った部分に対応する図形を特定して切り出すことができる。
【００３５】
これにより、初期設定手段において、初期頂点が他方の凸多角形の２つの辺の間に位置するか否かを判定するときに、外積計算を１回だけ実行するものの、その後は、外積計算を一切行わずに、各凸多角形の互いに重なり合った部分を包囲する各点の座標を抽出することができ、この重なり合った部分を切り出すことができる。従って、図形クリッピング処理における演算処理の時間を減少させることができ、図形クリッピング作業の作業性を向上させることができる。
【００３６】
また、請求項２の発明による図形クリッピング方法によっても、上述した請求項１の発明による図形クリッピング装置と同様に、図形クリッピング処理における演算処理の時間を減少させることができ、図形クリッピング作業の作業性を向上させることができる。
【００３７】
さらに、請求項３の発明による記録媒体に記録されたプログラムをコンピュータに読み取らせ、このプログラムをコンピュータに実行させることにより、コンピュータを、上述した請求項１の発明による図形クリッピング装置として機能させることができる。
【００３８】
【発明の実施の形態】
以下、本発明の実施の形態を添付図面に従って説明する。
【００３９】
図１は、本発明の実施形態による図形クリッピング装置１０を示している。この図形クリッピング装置１０は、複数の図形の互いに重なり合った部分を切り出す処理、即ち、図形クリッピング処理を行うものである。
【００４０】
図１に示すように、図形クリッピング装置１０は、ＣＰＵ１，ＲＯＭ２，ＲＡＭ３，ディスプレイ４、マウス５、キーボード６を備えており、これらは、バス７を介して相互に接続されている。
【００４１】
ＣＰＵ１は、図形クリッピング装置１０の全体的な制御を行うものである。また、ＣＰＵ１は、図５ないし図１０に示す図形クリッピング処理プログラムを実行する。ＲＯＭ２には、図形クリッピング装置１０を制御するためのプログラムおよび図５ないし図１０に示す図形クリッピング処理プログラム等が記憶されている。ＲＡＭ３には、図２に示すような属性フラグ８が記録されている。また、ＲＡＭ３は、図形クリッピング処理を行うときの作業エリアとして使用される。ディスプレイ４は、図形クリッピング処理を行うときに、処理の対象となる図形等を表示するものであり、マウス５およびキーボード６は図形クリッピング装置１０に指令やデータを入力するものである。
【００４２】
次に、図形クリッピング処理について説明する。以下の説明では、図３に示す２つの凸多角形Ｐ，Ｑの重なり合った部分を切り出す場合を例に挙げる。
【００４３】
図３において、Ｘ−Ｙ座標面上に配置された凸多角形Ｐと凸多角形Ｑとは、互いに重なり合っている。ここで、互いに重なり合った部分を重なり部分Ｒとする。また、凸多角形Ｐの各頂点のうち、最上に位置する頂点（Ｙ座標が最も小さい頂点）を上端点Ｐｕとし、最下に位置する頂点（Ｙ座標が最も大きい頂点）を下端点Ｐｂとし、凸多角形Ｐの各辺を、上端点Ｐｕから下端点Ｐｂに向けて反時計回りに辿ったときに通過する各頂点を、通過する順番にＰＬｉ（ｉ＝１，２，３，…）とし、凸多角形Ｐの各辺を、下端点Ｐｂから上端点Ｐｕに向けて反時計回りに辿ったときに通過する各頂点を、通過する順番にＰＲｊ（ｊ＝１，２，３，…）とする。同様に、凸多角形Ｑの各頂点のうち、最上に位置する頂点を上端点Ｑｕとし、最下に位置する頂点を下端点Ｑｂとし、凸多角形Ｑの各辺を、上端点Ｑｕから下端点Ｑｂに向けて反時計回りに辿ったときに通過する各頂点を、通過する順番にＱＬｍ（ｍ＝１，２，３，…）とし、凸多角形Ｑの各辺を、下端点Ｑｂから上端点Ｑｕに向けて反時計回りに辿ったときに通過する各頂点を、通過する順番にＱＲｎ（ｎ＝１，２，３，…）とする。さらに、図の左上端をＸ−Ｙ座標面の原点とする。
【００４４】
また、説明の便宜上、例えば、凸多角形Ｐの上端点ＰｕのＹ座標をＹ（Ｐｕ）と表記する。その他の頂点Ｐｂ，ＰＬｉ，ＰＲｊ，Ｑｕ，Ｑｂ，ＱＬｍ，ＱＲｎのＹ座標についてもこれと同様に表記する。また、凸多角形Ｐの上端点Ｐｕから下端点Ｐｂに向けて反時計回りに辿ったときに通過する各辺を凸多角形Ｐの左辺と呼び、下端点Ｐｂから上端点Ｐｕに向けて反時計回りに辿ったときに通過する各辺を凸多角形Ｐの右辺と呼ぶ。同様に、凸多角形Ｑの上端点Ｑｕから下端点Ｑｂに向けて反時計回りに辿ったときに通過する各辺を凸多角形Ｑの左辺と呼び、下端点Ｑｂから上端点Ｑｕに向けて反時計回りに辿ったときに通過する各辺を凸多角形Ｑの右辺と呼ぶ。
【００４５】
また、図形クリッピング処理には、Ｘ−Ｙ座標面のＸ軸に平行な走査線を用いる。この走査線を、Ｙ座標値の小さい側から大きい側にＹ軸に沿って移動させることにより、後述する頂点出力処理等を行う。以下、走査線が移動する方向を走査方向と呼び、Ｙ座標値の小さい側を走査方向開始側と呼び、Ｙ座標値の大きい側を走査方向終了側または走査方向側と呼ぶ。
【００４６】
さらに、図形クリッピング処理には、図２に示す属性フラグ８が用いられる。属性フラグ８とは、凸多角形Ｐの左辺の状態、凸多角形Ｐの右辺の状態、凸多角形Ｑの左辺の状態および凸多角形Ｑの右辺の状態を示す４つのフラグから構成されている。これらのフラグは、図形クリッピング処理の中でＯＮ状態またはＯＦＦ状態にそれぞれセットされる。
【００４７】
それでは、図形クリッピング処理について図５ないし図１０のフローチャートに沿って説明する。
【００４８】
まず、作業者が、図３に示す凸多角形Ｐ，Ｑに対応する図形データと図形クリッピング処理を開始させるための指令を図形クリッピング装置１０に入力すると、ＣＰＵ１は、凸多角形Ｐ，Ｑに対応する図形データをＲＡＭ３の作業エリアに記憶し、図５に示す図形クリッピング処理のメインルーチンを実行する。
【００４９】
図５に示すように、まず、凸多角形Ｐ，Ｑに対応する図形データに基づいて、凸多角形Ｐ，Ｑの各頂点、各上端点および各下端点の座標を認識する（ステップ１）。このとき、図３に示すように、２つの凸多角形のうち、上端点のＹ座標の値が小さい方を凸多角形Ｐとし、上端点のＹ座標の値が大きい方を凸多角形Ｑとする。
【００５０】
次に、凸多角形Ｑの上端点ＱｕのＹ座標が、凸多角形Ｐの下端点ＰｂのＹ座標よりも大きいか否かを判定し（ステップ２）、大きいときには、図形クリッピング処理を終了する。凸多角形Ｑの上端点ＱｕのＹ座標が、凸多角形Ｐの下端点ＰｂのＹ座標よりも大きいときには、凸多角形Ｐと凸多角形Ｑは重なっていないと判断できるからである。一方、凸多角形Ｑの上端点ＱｕのＹ座標が、凸多角形Ｐの下端点ＰｂのＹ座標よりも大きくないときには、凸多角形Ｐと凸多角形Ｑは重なっている判断できる。そこで、まず初期設定処理を実行すべく、図６に示す初期設定処理プログラムを起動する（ステップ３）。
【００５１】
図６中の初期設定処理では、まず、下記の数式２を満たすＰＬｉ，ＰＲｊを求める（ステップ１１およびステップ１２）。
【００５２】
【数２】
Ｙ（ＰＬｉ-1）＜Ｙ（ＱＲｎ）≦Ｙ（ＰＬｉ）
Ｙ（ＰＲｊ+1）＜Ｙ（ＱＲｎ）≦Ｙ（ＰＲｊ）
次に、上記数式２を満たすＰＬｉ，ＰＲｊをそれぞれ含む凸多角形Ｐの左辺（ＰＬｉ-1，ＰＬｉ）と右辺（ＰＲｊ，ＰＲｊ+1）を求め、凸多角形Ｑの上端点Ｑｕ（初期頂点）が、これらの辺の間に位置するか否かを判定する（ステップ１３）。上端点Ｑｕがこれら２つの辺の間に位置するときには、上端点Ｑｕの座標をＲＡＭ３の記憶エリア中の所定の場所に出力すると共に、凸多角形Ｑの左辺および右辺の属性フラグをＯＮ状態にセットする（ステップ１４およびステップ１５）。一方、凸多角形Ｑの上端点Ｑｕが、これらの辺の間に位置しないときには、上端点Ｑｕの座標を出力せず、凸多角形Ｑの左辺および右辺の属性フラグをＯＦＦ状態にセットする（ステップ１６）。
【００５３】
次に、凸多角形Ｐの左辺および右辺の属性フラグをＯＦＦ状態にセットし（ステップ１７）、図５に示すメインルーチンのステップ４に移行する。
【００５４】
図５中のステップ４では、凸多角形Ｑの上端点Ｑｕの両隣にある２つの頂点ＱＬｍ，ＱＲｎと、当該凸多角形Ｑの上端点Ｑｕを通る走査線と交差する凸多角形Ｐの２辺が持つ走査方向側の２つの頂点ＰＬｉ，ＰＲｊとの合計４つの頂点を選択候補としてそれぞれ選択する。さらに、選択候補として選択された４つの頂点の中から、Ｙ座標の値が最小の頂点を選択頂点として選択する。そして、図７ないし図１０に示す頂点出力処理を起動する（ステップ５）。
【００５５】
頂点出力処理では、選択頂点が頂点ＰＬｉ，ＰＲｊ，ＱＬｍおよびＱＲｎのいずれかを判定する（図７中のステップ２１ないしステップ２３）。そして、選択頂点が頂点ＰＬｉのときには図８中のステップ４１へ移行する。
【００５６】
図８中のステップ４１では、凸多角形Ｐの各左辺の中から、走査方向側に選択頂点ＰＬｉを持つ左辺（ＰＬｉ-1，ＰＬｉ）を選択辺として設定する。さらに、凸多角形Ｑにおいて走査方向側に選択候補頂点を持つ２つの辺、即ち、右辺（ＱＲｎ，ＱＲｎ+1）および左辺（ＱＬｍ-1，ＱＬｍ）を処理対象辺として設定する。
【００５７】
次に、凸多角形Ｐの選択辺（ＰＬｉ-1，ＰＬｉ）が、処理対象辺として設定されている凸多角形Ｑの右辺（ＱＲｎ，ＱＲｎ+1）と交差するか否かを判定する（ステップ４２）。そして、凸多角形Ｐの選択辺（ＰＬｉ-1，ＰＬｉ）が、凸多角形Ｑの右辺（ＱＲｎ，ＱＲｎ+1）と交差するときには、その交点の座標を出力すると共に、互いに交差する２つの属性フラグ８を反転させる（ステップ４３およびステップ４４）。一方、凸多角形Ｐの選択辺（ＰＬｉ-1，ＰＬｉ）が、凸多角形Ｑの右辺（ＱＲｎ，ＱＲｎ+1）と交差しないときには、属性フラグ８を反転させない。
【００５８】
次に、凸多角形Ｐの選択辺（ＰＬｉ-1，ＰＬｉ）が、処理対象辺として設定されている凸多角形Ｑの左辺（ＱＬｍ-1，ＱＬｍ）と交差するか否かを判定する（ステップ４５）。そして、凸多角形Ｐの選択辺（ＰＬｉ-1，ＰＬｉ）が、凸多角形Ｑの左辺（ＱＬｍ-1，ＱＬｍ）と交差するときには、その交点の座標を出力すると共に、互いに交差する２つの属性フラグ８を反転させる（ステップ４６およびステップ４７）。一方、凸多角形Ｐの選択辺（ＰＬｉ-1，ＰＬｉ）が、凸多角形Ｑの左辺（ＱＬｍ-1，ＱＬｍ）と交差しないときには、属性フラグを反転させない。
【００５９】
次に、凸多角形Ｐの左辺の属性フラグ８がＯＮ状態か否かを判定し、ＯＮ状態のときには、選択頂点として選択されている頂点ＰＬｉの座標をＲＡＭ３の記憶エリア中の所定の場所に出力する（ステップ４８およびステップ４９）。一方、凸多角形Ｐの左辺の属性フラグ８がＯＦＦ状態のときには、頂点ＰＬｉの座標を出力しない。
【００６０】
一方、選択頂点が頂点ＰＲｊのときには図９中のステップ５１へ移行する。そして、図９中のステップ５１では、凸多角形Ｐの各右辺の中から、走査方向側に選択頂点ＰＲｊを持つ右辺（ＰＲｊ，ＰＲｊ+1）を選択辺として設定する。さらに、凸多角形Ｑにおいて走査方向側に選択候補頂点を持つ２つの辺、即ち、左辺（ＱＬｍ-1，ＱＬｍ）および右辺（ＱＲｎ，ＱＲｎ+1）を処理対象辺として設定する。
【００６１】
次に、凸多角形Ｐの選択辺（ＰＲｊ，ＰＲｊ+1）が、処理対象辺として設定されている凸多角形Ｑの左辺（ＱＬｍ-1，ＱＬｍ）と交差するか否かを判定する（ステップ５２）。そして、凸多角形Ｐの選択辺（ＰＲｊ，ＰＲｊ+1）が、凸多角形Ｑの左辺（ＱＬｍ-1，ＱＬｍ）と交差するときには、その交点の座標を出力すると共に、互いに交差する２つの属性フラグ８を反転させる（ステップ５３およびステップ５４）。一方、凸多角形Ｐの選択辺（ＰＲｊ，ＰＲｊ+1）が、凸多角形Ｑの左辺（ＱＬｍ-1，ＱＬｍ）と交差しないときには、属性フラグ８を反転させない。
【００６２】
次に、凸多角形Ｐの選択辺（ＰＲｊ，ＰＲｊ+1）が、処理対象辺として設定されている凸多角形Ｑの右辺（ＱＲｎ，ＱＲｎ+1）と交差するか否かを判定する（ステップ５５）。そして、凸多角形Ｐの選択辺（ＰＲｊ，ＰＲｊ+1）が、凸多角形Ｑの右辺（ＱＲｎ，ＱＲｎ+1）と交差するときには、その交点の座標を出力すると共に、互いに交差する２つの属性フラグ８を反転させる（ステップ５６およびステップ５７）。一方、凸多角形Ｐの選択辺（ＰＲｊ，ＰＲｊ+1）が、凸多角形Ｑの右辺（ＱＲｎ，ＱＲｎ+1）と交差しないときには、属性フラグを反転させない。
【００６３】
次に、凸多角形Ｐの右辺の属性フラグ８がＯＮ状態か否かを判定し、ＯＮ状態のときには、選択頂点として選択されている頂点ＰＲｊの座標をＲＡＭ３の記憶エリア中の所定の場所に出力する（ステップ５８およびステップ５９）。一方、凸多角形Ｐの右辺の属性フラグ８がＯＦＦ状態のときには、頂点ＰＲｊの座標を出力しない。
【００６４】
一方、選択頂点が頂点ＱＬｍのときには図１０中のステップ６１へ移行する。そして、図１０中のステップ６１では、凸多角形Ｑの各左辺の中から、走査方向側に選択頂点ＱＬｍを持つ左辺（ＱＬｍ-1，ＱＬｍ）を選択辺として設定する。さらに、凸多角形Ｐにおいて走査方向側に選択候補頂点を持つ２つの辺、即ち、右辺（ＰＲｊ，ＰＲｊ+1）および左辺（ＰＬｉ-1，ＰＬｉ）を処理対象辺として設定する。
【００６５】
次に、凸多角形Ｑの選択辺（ＱＬｍ-1，ＱＬｍ）が、処理対象辺として設定されている凸多角形Ｐの右辺（ＰＲｊ，ＰＲｊ+1）と交差するか否かを判定する（ステップ６２）。そして、凸多角形Ｑの選択辺（ＱＬｍ-1，ＱＬｍ）が、凸多角形Ｐの右辺（ＰＲｊ，ＰＲｊ+1）と交差するときには、その交点の座標を出力すると共に、互いに交差する２つの属性フラグ８を反転させる（ステップ６３およびステップ６４）。一方、凸多角形Ｑの選択辺（ＱＬｍ-1，ＱＬｍ）が、凸多角形Ｐの右辺（ＰＲｊ，ＰＲｊ+1）と交差しないときには、属性フラグ８を反転させない。
【００６６】
次に、凸多角形Ｑの選択辺（ＱＬｍ-1，ＱＬｍ）が、処理対象辺として設定されている凸多角形Ｐの左辺（ＰＬｉ-1，ＰＬｉ）と交差するか否かを判定する（ステップ６５）。そして、凸多角形Ｑの選択辺（ＱＬｍ-1，ＱＬｍ）が、凸多角形Ｐの左辺（ＰＬｉ-1，ＰＬｉ）と交差するときには、その交点の座標を出力すると共に、互いに交差する２つの属性フラグ８を反転させる（ステップ６６およびステップ６７）。一方、凸多角形Ｑの選択辺（ＱＬｍ-1，ＱＬｍ）が、凸多角形Ｐの左辺（ＰＬｉ-1，ＰＬｉ）と交差しないときには、属性フラグを反転させない。
【００６７】
次に、凸多角形Ｑの左辺の属性フラグ８がＯＮ状態か否かを判定し、ＯＮ状態のときには、選択頂点として選択されている頂点ＱＬｍの座標をＲＡＭ３の記憶エリア中の所定の場所に出力する（ステップ６８およびステップ６９）。一方、凸多角形Ｑの左辺の属性フラグ８がＯＦＦ状態のときには、頂点ＱＬｍの座標を出力しない。
【００６８】
一方、選択頂点が頂点ＱＲｎのときには図７中のステップ２４へ移行する。そして、図７中のステップ２４では、凸多角形Ｑの各右辺の中から、走査方向側に選択頂点ＱＲｎを持つ右辺（ＱＲｎ，ＱＲｎ+1）を選択辺として設定する。さらに、凸多角形Ｐにおいて走査方向側に選択候補頂点を持つ２つの辺、即ち、左辺（ＰＬｉ-1，ＰＬｉ）および右辺（ＰＲｊ，ＰＲｊ+1）を処理対象辺として設定する。
【００６９】
次に、凸多角形Ｑの選択辺（ＱＲｎ，ＱＲｎ+1）が、処理対象辺として設定されている凸多角形Ｐの左辺（ＰＬｉ-1，ＰＬｉ）と交差するか否かを判定する（ステップ２５）。そして、凸多角形Ｑの選択辺（ＱＲｎ，ＱＲｎ+1）が、凸多角形Ｐの左辺（ＰＬｉ-1，ＰＬｉ）と交差するときには、その交点の座標を出力すると共に、互いに交差する２つの属性フラグ８を反転させる（ステップ２６およびステップ２７）。一方、凸多角形Ｑの選択辺（ＱＲｎ，ＱＲｎ+1）が、凸多角形Ｐの左辺（ＰＬｉ-1，ＰＬｉ）と交差しないときには、属性フラグ８を反転させない。
【００７０】
次に、凸多角形Ｑの選択辺（ＱＲｎ，ＱＲｎ+1）が、処理対象辺として設定されている凸多角形Ｐの右辺（ＰＲｊ，ＰＲｊ+1）と交差するか否かを判定する（ステップ２８）。そして、凸多角形Ｑの選択辺（ＱＲｎ，ＱＲｎ+1）が、凸多角形Ｐの右辺（ＰＲｊ，ＰＲｊ+1）と交差するときには、その交点の座標を出力すると共に、互いに交差する２つの属性フラグ８を反転させる（ステップ２９およびステップ３０）。一方、凸多角形Ｑの選択辺（ＱＲｎ，ＱＲｎ+1）が、凸多角形Ｐの右辺（ＰＲｊ，ＰＲｊ+1）と交差しないときには、属性フラグを反転させない。
【００７１】
次に、凸多角形Ｑの右辺の属性フラグ８がＯＮ状態か否かを判定し、ＯＮ状態のときには、選択頂点として選択されている頂点ＱＲｎの座標をＲＡＭ３の記憶エリア中の所定の場所に出力する（ステップ３１およびステップ３２）。一方、凸多角形Ｑの右辺の属性フラグ８がＯＦＦ状態のときには、頂点ＱＲｎの座標を出力しない。
【００７２】
以上のような図７ないし図１０に示す頂点出力処理が終了したら、図５に示すメインルーチンのステップ６に移行する。
【００７３】
図６中のステップ６では、選択頂点が凸多角形Ｐの下端点Ｐｂまたは凸多角形Ｑの下端点Ｑｂか否かを判定する。そして、選択頂点が下端点Ｐｂまたは下端点Ｑｂでないときには、ステップ４に戻る。
【００７４】
そして、ステップ４では、今まで選択頂点として選択していた頂点を選択候補から外し、その代わりに、今まで選択頂点として選択していた頂点のＹ軸方向隣に位置する頂点を新たな選択候補に加える。即ち、今まで選択していた頂点が頂点ＰＬｉの場合には、その頂点ＰＬｉを選択候補から外し、頂点ＰＬｉ+1を新たに選択候補に加える。また、今まで選択していた頂点が頂点ＰＲｊの場合には、その頂点ＰＲｊを選択候補から外し、頂点ＰＲｊ-1を新たに選択候補に加える。さらに、今まで選択していた頂点が頂点ＱＬｍの場合には、その頂点ＱＬｍを選択候補から外し、頂点ＱＬｍ+1を新たに選択候補に加える。さらにまた、今まで選択していた頂点が頂点ＱＲｎの場合には、その頂点ＱＲｎを選択候補から外し、頂点ＱＲｎ-1を新たに選択候補に加える。さらに、ステップ４では、選択候補として選択された４つの頂点の中から、Ｙ座標の値が最小の頂点を選択頂点として新たに選択する。そして、図７ないし図１０に示す頂点出力処理を再び起動する（ステップ５）。
【００７５】
このように、ステップ４ないしステップ６の処理を繰り返すことにより、図３中の矢示に示すような走査方向に沿って処理の開始側から終了側に向けて頂点出力処理が進行する。即ち、図３に示す凸多角形Ｐ，Ｑの各頂点がＹ座標の値が小さい順に次々に選択頂点として選択され、頂点出力処理の対象となる。そして、選択頂点として下端点Ｐｂまたは下端点Ｑｂが選択されたときに、ステップ６で「ＹＥＳ」と判定され、ステップ７に移行する。この段階で、凸多角形Ｐと凸多角形Ｑとの重なり部分Ｒを包囲する各頂点の座標が、ＲＡＭ３の記憶エリア中の所定の場所に出力されている。
【００７６】
そして、ステップ７では、ＲＡＭ３の記憶エリア中の所定の場所に出力された上記各頂点の座標に基づいて、重なり部分Ｒの切出処理を行う。
【００７７】
次に、実際に図３に示す凸多角形Ｐ，Ｑの重なり部分Ｒを切り出す動作について図４に示す属性フラグの履歴を参照しつつ説明する。
【００７８】
まず、凸多角形Ｑの上端点ＱｕのＹ座標は、凸多角形Ｐの下端点ＰｂのＹ座標より大きくないため、初期設定処理が実行される（ステップ２およびステップ３）。そして、初期設定処理において、上端点Ｑｕ（初期頂点）が、上記数式２を満たすＰＬｉ，ＰＲｊ、即ち、ＰＬ２，ＰＲ２を含む凸多角形Ｐの左辺（ＰＬ１，ＰＬ２）と右辺（ＰＲ２，ＰＲ３）との間に位置するか否か判定される（ステップ１１ないしステップ１３）。この判定の結果、上端点Ｑｕは、左辺（ＰＬ１，ＰＬ２）と右辺（ＰＲ２，ＰＲ３）との間に位置しないため、上端点Ｑｕの座標は出力されず、凸多角形Ｐの左辺および右辺並びに凸多角形Ｑの左辺および右辺の各属性フラグ８は、図４に示すように、ＯＦＦ状態にセットされる（ステップ１６およびステップ１７）。
【００７９】
次に、凸多角形Ｑの上端点Ｑｕの両隣にある２つの頂点ＱＬ１，ＱＲ３と、凸多角形Ｑの上端点Ｑｕを通る走査線と交差する凸多角形Ｐの２辺が持つ走査方向側の２つの頂点ＰＬ２，ＰＲ２との合計４つの頂点が選択候補として選ばれる。さらに、この４つの頂点の中から頂点ＰＲ２が選択頂点として選択され、頂点ＰＲ２に対して頂点出力処理が実行される（ステップ４およびステップ５）。そして、頂点出力処理において、まず、選択辺として凸多角形Ｐの右辺（ＰＲ２，ＰＲ３）が設定され、処理対象辺として凸多角形Ｑの左辺（Ｑｕ，ＱＬ１）および右辺（ＱＲ３，Ｑｕ）が設定される（ステップ５１）。次に、凸多角形Ｐの選択辺（ＰＲ２，ＰＲ３）が、凸多角形Ｑの左辺（Ｑｕ，ＱＬ１）と交差するか否か判定される（ステップ５２）。図３に示すように、凸多角形Ｐの選択辺（ＰＲ２，ＰＲ３）は、凸多角形Ｑの左辺（Ｑｕ，ＱＬ１）と交差しないため、次に、凸多角形Ｐの選択辺（ＰＲ２，ＰＲ３）が、凸多角形Ｑの右辺（ＱＲ３，Ｑｕ）と交差するか否か判定される（ステップ５５）。図３に示すように、凸多角形Ｐの選択辺（ＰＲ２，ＰＲ３）は、凸多角形Ｑの右辺（ＱＲ３，Ｑｕ）と交差しないため、次に、凸多角形Ｐの右辺（選択辺）の属性フラグがＯＮ状態か否か判定される（ステップ５８）。図４に示すように、凸多角形Ｐの右辺の属性フラグ８はＯＦＦ状態であるため、当該頂点ＰＲ２の座標は出力されない。
【００８０】
次に、凸多角形Ｐ，Ｑの各頂点のうち、頂点ＰＬ２，ＰＲ１，ＱＬ１，ＱＲ３が選択候補として選ばれる。さらに、この４つの頂点の中から頂点ＱＲ３が選択頂点として選択され、頂点ＱＲ３に対して頂点出力処理が実行される（ステップ４およびステップ５）。そして、頂点出力処理において、まず、選択辺として凸多角形Ｑの右辺（ＱＲ３，Ｑｕ）が設定され、処理対象辺として凸多角形Ｐの左辺（ＰＬ１，ＰＬ２）および右辺（ＰＲ１，ＰＲ２）が設定される（ステップ２４）。次に、凸多角形Ｑの選択辺（ＱＲ３，Ｑｕ）が、凸多角形Ｐの左辺（ＰＬ１，ＰＬ２）と交差するか否か判定される（ステップ２５）。図３に示すように、凸多角形Ｑの選択辺（ＱＲ３，Ｑｕ）は、凸多角形Ｐの左辺（ＰＬ１，ＰＬ２）と交差しないため、次に、凸多角形Ｑの選択辺（ＱＲ３，Ｑｕ）が、凸多角形Ｐの右辺（ＰＲ１，ＰＲ２）と交差するか否か判定される（ステップ２８）。図３に示すように、凸多角形Ｑの選択辺（ＱＲ３，Ｑｕ）は、凸多角形Ｐの右辺（ＰＲ１，ＰＲ２）とも交差しないため、次に、凸多角形Ｑの右辺（選択辺）の属性フラグがＯＮ状態か否か判定される（ステップ３１）。図４に示すように、凸多角形Ｑの右辺の属性フラグ８はＯＦＦ状態であるため、当該頂点ＱＲ３の座標は出力されない。
【００８１】
次に、凸多角形Ｐ，Ｑの各頂点のうち、頂点ＰＬ２，ＰＲ１，ＱＬ１，ＱＲ２が選択候補として選ばれる。さらに、この４つの頂点の中から頂点ＱＬ１が選択頂点として選択され、頂点ＱＬ１に対して頂点出力処理が実行される（ステップ４およびステップ５）。そして、頂点出力処理において、まず、選択辺として凸多角形Ｑの左辺（Ｑｕ，ＱＬ１）が設定され、処理対象辺として凸多角形Ｐの右辺（ＰＲ１，ＰＲ２）および左辺（ＰＬ１，ＰＬ２）が設定される（ステップ６１）。次に、凸多角形Ｑの選択辺（Ｑｕ，ＱＬ１）が、凸多角形Ｐの右辺（ＰＲ１，ＰＲ２）と交差するか否か判定される（ステップ６２）。図３に示すように、凸多角形Ｑの選択辺（Ｑｕ，ＱＬ１）は、凸多角形Ｐの右辺（ＰＲ１，ＰＲ２）と交差しないため、次に、凸多角形Ｑの選択辺（Ｑｕ，ＱＬ１）が、凸多角形Ｐの左辺（ＰＬ１，ＰＬ２）と交差するか否か判定される（ステップ６５）。図３に示すように、凸多角形Ｑの選択辺（Ｑｕ，ＱＬ１）は、凸多角形Ｐの左辺（ＰＬ１，ＰＬ２）とも交差しないため、次に、凸多角形Ｑの左辺（選択辺）の属性フラグがＯＮ状態か否か判定される（ステップ６８）。図４に示すように、凸多角形Ｑの左辺の属性フラグ８はＯＦＦ状態であるため、当該頂点ＱＬ１の座標は出力されない。
【００８２】
次に、凸多角形Ｐ，Ｑの各頂点のうち、頂点ＰＬ２，ＰＲ１，ＱＬ２，ＱＲ２が選択候補として選ばれる。さらに、この４つの頂点の中から頂点ＰＬ２が選択頂点として選択され、頂点ＰＬ２に対して頂点出力処理が実行される（ステップ４およびステップ５）。そして、頂点出力処理において、まず、選択辺として凸多角形Ｐの左辺（ＰＬ１，ＰＬ２）が設定され、処理対象辺として凸多角形Ｑの右辺（ＱＲ２，ＱＲ３）および左辺（ＱＬ１，ＱＬ２）が設定される（ステップ４１）。次に、凸多角形Ｐの選択辺（ＰＬ１，ＰＬ２）が、凸多角形Ｑの右辺（ＱＲ２，ＱＲ３）と交差するか否か判定される（ステップ４２）。図３に示すように、凸多角形Ｐの選択辺（ＰＬ１，ＰＬ２）は、凸多角形Ｑの右辺（ＱＲ２，ＱＲ３）と交点Ａで交差しているため、交点Ａの座標が出力されると共に、凸多角形Ｐの左辺（選択辺）および凸多角形Ｑの右辺の属性フラグ８がそれぞれＯＮ状態に反転する（ステップ４３およびステップ４４）。次に、凸多角形Ｐの選択辺（ＰＬ１，ＰＬ２）が、凸多角形Ｑの左辺（ＱＬ１，ＱＬ２）と交差するか否か判定される（ステップ４５）。図３に示すように、凸多角形Ｐの選択辺（ＰＬ１，ＰＬ２）は、凸多角形Ｑの左辺（ＱＬ１，ＱＬ２）と交差しないため、次に、凸多角形Ｐの左辺（選択辺）の属性フラグがＯＮ状態か否か判定される（ステップ４８）。図４に示すように、凸多角形Ｑの左辺の属性フラグはＯＮ状態であるため、当該頂点ＰＬ２の座標が出力される（ステップ４９）。
【００８３】
同様にして、頂点ＰＲ１，ＱＬ２，ＱＲ２，ＰＬ３，ＰＬ４，ＱＲ１が、この順序で次々に選択頂点として選択され、頂点出力処理が繰り返し実行される。その過程において、頂点ＱＲ２の座標，頂点ＰＬ３の座標および凸多角形Ｐの左辺（ＰＬ３，ＰＬ４）と凸多角形Ｑの右辺（ＱＲ１，ＱＲ２）との交点Ｂの座標がそれぞれ出力される。その後、選択頂点として下端点Ｐｂが選択されたとき、ステップ６で「ＹＥＳ」と判定されてステップ７に移行し、ステップ７において切出処理が実行される。この段階で、ＲＡＭ３の記録エリア内の所定の場所には、重なり部分Ｒを包囲するすべての頂点の座標、即ち、頂点ＰＬ２，頂点ＰＬ３，頂点ＱＲ２，交点Ａおよび交点Ｂのそれぞれの座標が出力されているので、これらの座標に基づいて重なり部分Ｒを切り出す。
【００８４】
かくして、本実施形態による図形クリッピング装置１０によれば、選択頂点の座標を出力するか否かを、属性フラグ８の状態に基づいて決定している。そして、属性フラグ８は、一方の凸多角形の選択頂点が他方の凸多角形の内部にあるときに、ＯＮ状態となり、一方の凸多角形の選択頂点が他方の凸多角形の外部にあるときには、ＯＦＦ状態となるようにセットされる。
【００８５】
例えば、初期設定処理において、凸多角形Ｑの上端点Ｑｕが、上記数式２を満たす頂点ＰＬｉ，ＰＲｊをそれぞれ含む凸多角形Ｐの左辺と右辺との間に位置するとき、属性フラグ８はＯＮ状態にセットされる。凸多角形Ｑの上端点Ｑｕが、凸多角形Ｐの左辺と右辺との間に位置するということは、即ち、凸多角形Ｑの上端点Ｑｕが、凸多角形Ｐの内部に位置することを意味する。また、頂点出力処理において、選択頂点を含む一方の凸多角形の辺が、他方の凸多角形の左辺および右辺のうちいずれか一方の辺と交差するとき、属性フラグの状態は反転する。選択頂点を含む一方の凸多角形の辺が、他方の凸多角形の辺と交差したということは、一方の凸多角形の選択頂点が他方の凸多角形の内部に入ったこと、または、一方の凸多角形の選択頂点が他方の凸多角形の内部から外部に出たことを意味する。
【００８６】
このように、属性フラグ８は、一方の凸多角形の選択頂点が他方の凸多角形の内部に位置するときに、ＯＮ状態にセットされる。従って、属性フラグがＯＮ状態のときに、その選択頂点の座標を出力すれば、各凸多角形Ｐ，Ｑの重なり部分Ｒを包囲する各頂点の座標を抽出することができ、抽出した各点の座標に基づいて重なり部分Ｒを切り出すことができる。
【００８７】
これにより、初期設定処理において、凸多角形Ｑの上端点Ｑｕが凸多角形Ｐの左辺と右辺との間に位置するか否かを判定するときに、外積計算を１回だけ実行するものの、その後は、外積計算を一切行わずに、属性フラグ８を参照するだけで、各凸多角形Ｐ，Ｑの重なり部分Ｒを包囲する各点の座標を抽出することができ、重なり部分Ｒを切り出すことができる。従って、図形クリッピング処理における演算処理の時間を減少させることができ、図形クリッピング作業の作業性を向上させることができる。
【００８８】
なお、前記実施形態では、図形クリッピング処理を、凸多角形Ｑの上端点Ｑｕから凸多角形Ｐの下端点Ｐｂに向けてＹ軸方向に実行したが、本発明はこれに限らず、図形クリッピング処理を、凸多角形Ｐの下端点Ｐｂから凸多角形Ｑの上端点Ｑｕに向けてＹ軸方向に実行してもよく、さらに、図形クリッピング処理をＸ軸方向に実行してもよい。
【００８９】
また、前記実施形態では、図形クリッピング処理プログラムをＲＯＭ２に記憶するものとして述べたが、本発明はこれに限らず、図形クリッピング処理プログラムを外部から図形クリッピング装置１０に読み込ませ、ＲＡＭ３等に記憶させる構成としてもよい。さらに、図形クリッピング処理プログラムをＣＤ−ＲＯＭまたはフロッピーディスク等の記録媒体に記録し、この記録媒体を介して図形クリッピング処理プログラムをコンピュータに読み取らせ、コンピュータを図形クリッピング装置として機能させる構成としてもよい。
【００９０】
なお、図６中のステップ１１ないしステップ１７が初期設定手段の具体例である。図５中のステップ４が頂点選択手段の具体例であり、図７中のステップ２４，ステップ２５およびステップ２８、図８中のステップ４１，ステップ４２およびステップ４５、図９中のステップ５１，ステップ５２およびステップ５５、図１０中のステップ６１，ステップ６２およびステップ６５が交差判定手段の具体例である。図７中のステップ２６、ステップ２７、ステップ２９およびステップ３０，図８中のステップ４３、ステップ４４、ステップ４６およびステップ４７、図９中のステップ５３、ステップ５４、ステップ５６およびステップ５７、図１０中のステップ６３、ステップ６４、ステップ６６およびステップ６７が交点座標出力手段の具体例である。図７中のステップ３１、図８中のステップ４８、図９中のステップ５８、図１０中のステップ６８が属性フラグ判定手段の具体例であり、図７中のステップ３２、図８中のステップ４９、図９中のステップ５９、図１０中のステップ６９が頂点座標出力手段の具体例である。図５中のステップ７が切出手段の具体例である。
【００９１】
【発明の効果】
以上詳述したとおり、請求項１の発明の図形クリッピング装置によれば、一方の凸多角形の選択頂点が他方の凸多角形の内部に位置するときにＯＮ状態にセットされ、一方の凸多角形の選択頂点が他方の凸多角形の外部に位置するときにはＯＦＦ状態にセットされる属性フラグを設け、この属性フラグがＯＮ状態のときに、選択頂点の座標を出力する構成としたから、初期設定時において、初期頂点が他方の凸多角形の２つの辺の間に位置するか否かを判定するときに、外積計算を１回だけ実行するものの、その後は、外積計算を一切行わずに、各凸多角形の互いに重なり合った部分を包囲する各点の座標を抽出することができ、この重なり合った部分を切り出すことができる。従って、図形クリッピング処理における演算処理の時間を減少させることができ、図形クリッピング作業の作業性を向上させることができる。
【００９２】
特に、図形クリッピング処理の対象となる図形が曲線を含む場合には、通常、曲線を多数の短い直線に近似して処理を行うため、処理の対象となる頂点の数が膨大となる。このような場合には、図形クリッピング処理における演算処理の時間を大幅に短縮することができ、図形クリッピング処理の高速化を図ることができる。
【００９３】
また、請求項２の発明による図形クリッピング方法によっても、上述した請求項１の発明による図形クリッピング装置と同様に、図形クリッピング処理における演算処理の時間を減少させることができ、図形クリッピング作業の作業性を向上させることができる。
【００９４】
さらに、請求項３の発明による記録媒体に記録されたプログラムをコンピュータに読み取らせ、このプログラムをコンピュータに実行させることにより、コンピュータを、上述した請求項１の発明による図形クリッピング装置として機能させることができ、請求項１の発明による図形クリッピング装置と同様の効果を得ることができる。
【図面の簡単な説明】
【図１】  本発明の実施の形態による図形クリッピング装置の構成を示すブロック図である。
【図２】  本発明の実施の形態による属性フラグを示す説明図である。
【図３】  本発明の実施の形態による図形クリッピング処理の対象となる凸多角形を示す説明図である。
【図４】  本発明の実施の形態における属性フラグの履歴を示す説明図である。
【図５】  本発明の実施の形態における図形クリッピング処理のメインルーチンを示すフローチャートである。
【図６】  本発明の実施の形態における初期設定処理を示すフローチャートである。
【図７】  本発明の実施の形態における頂点出力処理を示すフローチャートである。
【図８】  本発明の実施の形態における頂点出力処理を示すフローチャートである。
【図９】  本発明の実施の形態における頂点出力処理を示すフローチャートである。
【図１０】  本発明の実施の形態における頂点出力処理を示すフローチャートである。
【図１１】  図形クリッピング処理の対象となる凸多角形を示す説明図である。
【符号の説明】
１  ＣＰＵ
２  ＲＯＭ
３  ＲＡＭ
８  属性フラグ
１０  図形クリッピング装置
Ｐ，Ｑ  凸多角形
【図１】
0004066103.tif 000002
【図２】
0004066103.tif 000003
【図３】
0004066103.tif 000004
【図４】
0004066103.tif 000005
【図５】
0004066103.tif 000006
【図６】
0004066103.tif 000007
【図７】
0004066103.tif 000008
【図８】
0004066103.tif 000009
【図９】
0004066103.tif 000010
【図１０】
0004066103.tif 000011
【図１１】
0004066103.tif 000012