(57)【特許請求の範囲】
【請求項１】
プロセッサと、プログラムが格納された記憶手段とを備え、前記プログラムは前記プロセッサに対し、色属性を持つ第１図形の上層に、色属性として透明度を持つ第２図形が重畳し、前記第１図形と前記第２図形とがそれぞれベクターオブジェクトで記述された印刷データについて、
ステップ（ａ）：前記第１図形及び前記第２図形を、相互に重畳する部分と、相互に重畳しない部分とに分割させ、
ステップ（ｂ）：重畳部分の色属性を少なくとも両図形の色属性に基づいて決定させ、
ステップ（ｃ）：前記重畳部分とそれ以外の部分のそれぞれをビットマップ展開させて画像を形成させる画像形成装置において、前記第１図形及び前記第２図形のそれぞれの境界線が３次ベジエ曲線又は直線で表され、前記プログラムは前記プロセッサに対しさらにステップ（ａ）で、
３次ベジエ曲線上に交点が存在すれば、前記３次ベジエ曲線を、その各端点及び前記交点での位置で分割させ、
ｘ−ｙ直交座標系での前記ベジエ曲線上の任意の点の座標を（ｆ（ｔ），ｇ（ｔ））を表す下記の式（１），（２）：
ｆ（ｔ）＝（１−ｔ）３ｘ１＋３（１−ｔ）２ｔｘ２＋３（１−ｔ）ｔ２ｘ３＋ｔ３ｘ４  ・・・（１）、及び
ｇ（ｔ）＝（１−ｔ）３ｙ１＋３（１−ｔ）２ｔｙ２＋３（１−ｔ）ｔ２ｙ３＋ｔ３ｙ４  ・・・（２）、
（ここで、前記分割されたベジエ曲線の制御点Ｑｉの座標を（ｘｉ，ｙｉ）、ｉを整数１〜ｎ（ｎは制御点の数）とする。）
及び、
パラメータ値ｔの区域が［０，１］の前記分割されたベジエ曲線上の任意の点の座標（ｕ（ｔ），ｖ（ｔ））のｕ及びｖを表す下記の式（３），（４）：
ｕ（ｔ）＝ａ１・ｔ３＋ｂ１・ｔ２＋ｃ１・ｔ＋ｄ１  ・・・（３）、及び
ｖ（ｔ）＝ａ２・ｔ３＋ｂ２・ｔ２＋ｃ２・ｔ＋ｄ２  ・・・（４）、
を用いて、
前記式（３），（４）中の８つの未知数ａ１、ｂ１、ｃ１、ｄ１、ａ２、ｂ２、ｃ２、ｄ２を以下の８つの条件式：
（ｆ（０），ｇ（０））＝（ｕ（０），ｖ（０））・・・条件式（１），（２）、
（ｆ（ｔ１），ｇ（ｔ１））＝（ｕ（１），ｖ（１））・・・条件式（３），（４）、
（ｔ＝０でのｆ’（ｔ）／ｇ’（ｔ）の値）＝（ｔ＝０でのｕ’（ｔ）／ｖ’（ｔ）の値）・・・条件式（５）、
（ｔ＝ｔ１でのｆ’（ｔ）／ｇ’（ｔ）の値）＝（ｔ＝１でのｕ’（ｔ）／ｖ’（ｔ）の値）・・・条件式（６）、
（ｔ＝０での（ｆ’（ｔ）／ｇ’（ｔ））’／ｇ’（ｔ）の値）＝（ｔ＝０での（ｕ’（ｔ）／ｖ’（ｔ））’／ｖ’（ｔ）の値）・・・条件式（７）、及び
（ｔ＝ｔ１での（ｆ’（ｔ）／ｇ’（ｔ））’／ｇ’（ｔ）の値）＝（ｔ＝１での（ｕ’（ｔ）／ｖ’（ｔ））’／ｖ’（ｔ）の値）・・・条件式（８）、
（ここで、交点のｔの値をｔ１、’はｔでの微分記号とする。）
の連立方程式の解として求めることで、前記分割されたベジエ曲線の近似式をそれぞれ定めることを特徴とする画像形成装置。
【請求項２】
前記条件式（７），（８）の替わりに、下記の条件式（９）〜（１１）：
ｆ（ｔ２）＝ｕ（０．５）・・・条件式（９）、
ｇ（ｔ２）＝ｖ（０．５）・・・条件式（１０）、及び
（ｔ＝ｔ２での(ｆ’（ｔ）／ｇ’（ｔ）)’／ｇ’（ｔ）の値）＝（ｔ＝０．５での（ｕ’（ｔ）／ｖ’（ｔ））’／ｖ’（ｔ）の値）・・・条件式（１１）、
を用いて、
前記８つの未知数ａ１、ｂ１、ｃ１、ｄ１、ａ２、ｂ２、ｃ２、ｄ２に新たな未知数ｔ２を加えた９つの未知数を、前記条件式（１）〜（６），（９）〜（１１）の連立方程式の解として求めることで、前記分割されたベジエ曲線の近似式をそれぞれ定める
ことを特徴とする請求項１に記載の画像形成装置。
【請求項３】
前記プログラムは前記プロセッサに対しステップ（ａ）においてさらに、
（ａ１）前記第１図形及び前記第２図形のそれぞれについて、境界線上を一方向に回るように境界線に方向情報を付加させておき、
（ａ２）前記交点で境界線の線分を分割した際に、分割後の線分の方向情報を、分割前の線分の方向情報と一致させ、
（ａ３）交点毎に、前記交点を始点とし前記一方向が前記始端から離れる方向である方向情報を持つ線分を１つ選択させ、移動方向を前記一方向と決定させ、
（ａ４）前記線分上を論理的に次の交点まで前記決定した方向へ移動させ、
（ａ５）移動後の交点が前記始点でなければ、前記交点で他方の図形の対応する点に移らせ、移動方向をステップ（ａ４）での方向と逆方向に決定させ、次いでステップ（ａ４）へ戻らさせ、前記始点であれば、一巡した閉曲線を前記相互に重畳しない部分の閉曲線と決定させる、
ことを特徴とする請求項１乃至２に記載の画像形成装置。
【請求項４】
前記プログラムは前記プロセッサに対しステップ（ａ）において、１つの交点及び一方向に関し、
（ａ６）前記交点を始点とする前記一方向の線分を１つ選択させ、
（ａ７）前記線分上を論理的に次の交点まで前記一方向へ移動させ、
（ａ８）移動後の交点が前記始点でなければ、前記交点で他方の図形の対応する点に移らせ、次いでステップ（ａ７）へ戻らさせ、前記始点であれば、一巡した閉曲線を保存させ、ステップ（ａ６）〜（ａ８）の処理により保存された閉曲線が１つであればステップ（ａ６）に戻らさせ、２つであれば両閉曲線の一方に包含される他方の閉曲線を前記相互に重畳する部分の閉曲線と決定させ、
前記一方向は、線分の方向情報が示す方向又はこれと逆方向のいずれか一方であることを特徴とする請求項１乃至３のいずれか１つに記載の画像形成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、色属性を持つ図形同士が重畳する場合に、ベクターオブジェクトの段階で、相互に重畳する部分と重畳しない部分とに図形を分割し、重畳部分の色属性を決定する処理を印刷処理の一部として行う画像形成装置に関する。
【背景技術】
【０００２】
プリンタ機能を備えた画像形成装置において、ベクターオブジェクトで表された２つのカラー図形が互いに重なり、上の図形が透明度を持っている場合、これら２つの図形の各々をラスタライズしてビットマップデータに変換した後に重畳部分の色を決定するという処理を行うと、ワークエリアのメモリサイズが増大するとともに処理時間が長くなるという問題点が生ずる。
【０００３】
そこで、発明者が本発明者と同一の下記特許文献１では、ベクターオブジェクトの段階で重畳部分とそれ以外の部分とに図形を分割し、各図形の色を決定した後にラスタライズすることにより、上記問題点を解決している。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第３９３５１２７号
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記特許文献１で例示されている図形は矩形であり、ベジエ曲線を用いて表される図形が重なり合っている場合において、図形分割後の数式による図形表現については開示されていない。曲線図形は一般に３次ベジエ曲線で表されるが、分割の前後で同一のベジエ曲線を用いると、そのパラメータの区域がベジエ曲線毎に異なるので、ラスタライズ処理を今までと同様に統一的に行うことができず、既存のラスタライズ処理を利用できなくなり、これを変更するとラスタライズ処理が複雑になる。
【０００６】
本発明の目的は、このような問題点に鑑み、ベジエ曲線を含む図形が重畳する場合、分割前後で図形表現を統一することにより、既存のラスタライズ処理を変更する必要がない画像形成装置を提供することにある。
【課題を解決するための手段】
【０００７】
本発明による画像形成装置の第１態様では、プロセッサと、プログラムが格納された記憶手段とを備え、前記プログラムは前記プロセッサに対し、色属性を持つ第１図形の上層に、色属性として透明度を持つ第２図形が重畳し、前記第１図形と前記第２図形とがそれぞれベクターオブジェクトで記述された印刷データについて、ステップ（ａ）：前記第１図形及び前記第２図形を、相互に重畳する部分と、相互に重畳しない部分とに分割させ、ステップ（ｂ）：重畳部分の色属性を少なくとも両図形の色属性に基づいて決定させ、ステップ（ｃ）：前記重畳部分とそれ以外の部分のそれぞれをビットマップ展開させて画像を形成させる画像形成装置において、前記第１図形及び前記第２図形のそれぞれの境界線が３次ベジエ曲線又は直線で表され、前記プログラムは前記プロセッサに対しさらにステップ（ａ）で、３次ベジエ曲線上に交点が存在すれば、前記３次ベジエ曲線を、その各端点及び前記交点での位置で分割させ、ｘ−ｙ直交座標系での前記ベジエ曲線上の任意の点の座標を（ｆ（ｔ），ｇ（ｔ））を表す下記の式（１），（２）：
ｆ（ｔ）＝（１−ｔ）３ｘ１＋３（１−ｔ）２ｔｘ２＋３（１−ｔ）ｔ２ｘ３＋ｔ３ｘ４  ・・・（１）、及び
ｇ（ｔ）＝（１−ｔ）３ｙ１＋３（１−ｔ）２ｔｙ２＋３（１−ｔ）ｔ２ｙ３＋ｔ３ｙ４  ・・・（２）、（ここで、前記分割されたベジエ曲線の制御点Ｑｉの座標を（ｘｉ，ｙｉ）、ｉを整数１〜ｎ（ｎは制御点の数）とする。）及び、パラメータ値ｔの区域が［０，１］の前記分割されたベジエ曲線上の任意の点の座標（ｕ（ｔ），ｖ（ｔ））のｕ及びｖを表す下記の式（３），（４）：
ｕ（ｔ）＝ａ１・ｔ３＋ｂ１・ｔ２＋ｃ１・ｔ＋ｄ１  ・・・（３）、及び
ｖ（ｔ）＝ａ２・ｔ３＋ｂ２・ｔ２＋ｃ２・ｔ＋ｄ２  ・・・（４）、を用いて、前記式（３），（４）中の８つの未知数ａ１、ｂ１、ｃ１、ｄ１、ａ２、ｂ２、ｃ２、ｄ２を以下の８つの条件式：
（ｆ（０），ｇ（０））＝（ｕ（０），ｖ（０））・・・条件式（１），（２）、
（ｆ（ｔ１），ｇ（ｔ１））＝（ｕ（１），ｖ（１））・・・条件式（３），（４）、
（ｔ＝０でのｆ’（ｔ）／ｇ’（ｔ）の値）＝（ｔ＝０でのｕ’（ｔ）／ｖ’（ｔ）の値）・・・条件式（５）、
（ｔ＝ｔ１でのｆ’（ｔ）／ｇ’（ｔ）の値）＝（ｔ＝１でのｕ’（ｔ）／ｖ’（ｔ）の値）・・・条件式（６）、
（ｔ＝０での（ｆ’（ｔ）／ｇ’（ｔ））’／ｇ’（ｔ）の値）＝（ｔ＝０での（ｕ’（ｔ）／ｖ’（ｔ））’／ｖ’（ｔ）の値）・・・条件式（７）、及び
（ｔ＝ｔ１での（ｆ’（ｔ）／ｇ’（ｔ））’／ｇ’（ｔ）の値）＝（ｔ＝１での（ｕ’（ｔ）／ｖ’（ｔ））’／ｖ’（ｔ）の値）・・・条件式（８）、（ここで、交点のｔの値をｔ１、’はｔでの微分記号とする。）の連立方程式の解として求めることで、前記分割されたベジエ曲線の前記近似式をそれぞれ定める。
【０００９】
本発明による画像形成装置の第２態様では、第１態様において、前記条件式（７），（８）の替わりに、下記の条件式（９）〜（１１）：
ｆ（ｔ２）＝ｕ（０．５）・・・条件式（９）、
ｇ（ｔ２）＝ｖ（０．５）・・・条件式（１０）、及び
（ｔ＝ｔ２での(ｆ’（ｔ）／ｇ’（ｔ）)’／ｇ’（ｔ）の値）＝（ｔ＝０．５での（ｕ’（ｔ）／ｖ’（ｔ））’／ｖ’（ｔ）の値）・・・条件式（１１）、を用いて、前記８つの未知数ａ１、ｂ１、ｃ１、ｄ１、ａ２、ｂ２、ｃ２、ｄ２に新たな未知数ｔ２を加えた９つの未知数を、前記条件式（１）〜（６），（９）〜（１１）の連立方程式の解として求めることで、前記分割されたベジエ曲線の近似式をそれぞれ定める。
【００１０】
本発明による画像形成装置の第３態様では、第１又は２態様において、前記プログラムは前記プロセッサに対しステップ（ａ）においてさらに、
（ａ１）前記第１図形及び前記第２図形のそれぞれについて、境界線上を一方向に回るように境界線に方向情報を付加させておき、
（ａ２）前記交点で境界線の線分を分割した際に、分割後の線分の方向情報を、分割前の線分の方向情報と一致させ、
（ａ３）交点毎に、前記交点を始点とし前記一方向が前記始端から離れる方向である方向情報を持つ線分を１つ選択させ、移動方向を前記一方向と決定させ、
（ａ４）前記線分上を論理的に次の交点まで前記決定した方向へ移動させ、
（ａ５）移動後の交点が前記始点でなければ、前記交点で他方の図形の対応する点に移らせ、移動方向をステップ（ａ４）での方向と逆方向に決定させ、次いでステップ（ａ４）へ戻らさせ、前記始点であれば、一巡した閉曲線を前記相互に重畳しない部分の閉曲線と決定させる。
【００１１】
本発明による画像形成装置の第４態様では、第１乃至３態様のいずれか１つにおいて、前記プログラムは前記プロセッサに対しステップ（ａ）において、１つの交点及び一方向に関し、
（ａ６）前記交点を始点とする前記一方向の線分を１つ選択させ、
（ａ７）前記線分上を論理的に次の交点まで前記一方向へ移動させ、
（ａ８）移動後の交点が前記始点でなければ、前記交点で他方の図形の対応する点に移らせ、次いでステップ（ａ７）へ戻らさせ、前記始点であれば、一巡した閉曲線を保存させ、ステップ（ａ６）〜（ａ８）の処理により保存された閉曲線が１つであればステップ（ａ６）に戻らさせ、２つであれば両閉曲線の一方に包含される他方の閉曲線を前記相互に重畳する部分の閉曲線と決定させ、前記一方向は、線分の方向情報が示す方向又はこれと逆方向のいずれか一方である。
【発明の効果】
【００１２】
上記第１態様の構成によれば、２図形の境界線の一部である３次ベジエ曲線上に交点が存在するとき、該３次ベジエ曲線を、その各端点及び該交点での位置で分割し、分割された各線分をパラメータの区域が［０，１］である３次ベジエ曲線で近似し、これを用いて、２図形の分割された部分の閉曲線を記述するので、分割前後で図形表現が統一されて、既存のラスタライズ処理を変更せずに用いることができるという効果を奏する。
【００１３】
また、前記分割されたベジエ曲線のパラメータ値が０及び１の位置のそれぞれで前記位置、前記位置でのｘ−ｙ直交座標系におけるｙに対するｘの１回微分値及び２回微分値が、分割前のベジエ曲線の対応する点でのそれらと一致するように、前記分割されたベジエ曲線の、前記分割前のベジエ曲線に対する近似式を定めるので、分割されたベジエ曲線の式を効率よく求めることができるという効果を奏する。
【００１４】
上記第２態様の構成によれば、前記分割されたベジエ曲線のパラメータ値が０、０．５及び１の位置のそれぞれで前記位置、前記位置でのｘ−ｙ直交座標系におけるｙに対するｘの１回微分値が、分割前のベジエ曲線の対応する点でのそれらと一致するように、前記分割されたベジエ曲線の、前記分割前のベジエ曲線に対する近似式を定めるので、前記同様に、分割されたベジエ曲線の式を効率よく求めることができるという効果を奏する。
【００１５】
上記第３態様の構成によれば、図形の境界線の方向付けを行ってから、上記簡単な処理で、相互に重畳しない図形の部分を求めることができるという効果を奏する。
【００１６】
上記第４態様の構成によれば、図形の境界線の方向付けを行ってから、上記簡単な処理で、相互に重畳する図形の部分を求めることができるという効果を奏する。
【００１７】
本発明の他の目的、特徴的な構成及び効果は、以下の説明を特許請求の範囲及び図面の記載と関係づけて読むことにより明らかになる。 
【図面の簡単な説明】
【００１８】
【図１】本発明が適用された実施例１に係る画像形成システムの概略図である。
【図２】主に画像形成装置のハードウェア構成を示す概略ブロック図である。
【図３】ＰＤＬデータに含まれるベクターオブジェクトをラスタライズする前の重畳図形分割処理を示す概略フローチャートである。
【図４】（Ａ）及び（Ｂ）はいずれも、閉曲線トレース方向判定説明図である。
【図５】図３のステップＳ１の詳細フローチャートである。
【図６】処理対象の２つの図形の説明図である。
【図７】図６の図形の各線分の時計回り方向付説明図である。
【図８】図３のステップＳ１７の大きい方の閉曲線判定説明図である。
【図９】（Ａ）〜（Ｃ）はそれぞれ２つの図形が包含関係にある場合の例外的処理説明図である。
【図１０】２つの図形の交点が４つである場合の処理対象説明図である。
【図１１】図１０の図形の各線分の時計回り方向付説明図である。
【実施例１】
【００１９】
図１は、本発明が適用された実施例１に係る画像形成システムの概略図である。
【００２０】
このシステムでは、画像形成装置１０とＰＣ（Personal Computer）２０とがネットワーク３０で結合されている。ユーザが、ＰＣ２０でアプリケーションを起動させて文書を作成し、印刷開始の指示を与えと、このアプリケーションは、プリンタドライバを介して文書をＰＤＬ（Page Description Language）データに変換し、これを、ＯＳ（Operating System）のスプーラ機能及び通信機能を介してプリンタに送信する。
【００２１】
図２は、主に画像形成装置１０のハードウェア構成を示す概略ブロック図である。
【００２２】
この画像形成装置１０では、ＣＰＵ１１がインターフェイス１２を介してＰＲＯＭ１３、ＤＲＡＭ１４、補助記憶装置１５、ネットワークインターフェイス１６、操作パネル１７、スキャナ１８、プリンタ１９及びファックスモデム１Ａに結合されている。図５では、簡単化の為に、複数種のインターフェイスを１つのブロック１２で表している。
【００２３】
ＰＲＯＭ１３は、例えばフラッシュメモリであり、ＢＩＯＳ（Basic Input/Output System）、ＯＳ、各種ドライバ、及び、画像形成装置として機能させるための各種アプリケーションが格納されている。
【００２４】
このアプリケーションには、ＰＤＬデータをラスタライズしてＤＲＡＭ１４上のビットマップデータに変換し、プリンタ１９に供給することにより画像を用紙上に転移する印刷処理プログラムが含まれる。
【００２５】
ＤＲＡＭ１４は、主記憶装置として用いられる。補助記憶装置１５には、印刷用データ、スキャナ１８で読み取った画像データ及びファクシミリ受信データが保存される。ネットワークインターフェイス１６は、ネットワーク３０に結合され、ＰＤＬデータの送信等に用いられる。操作パネル１７は、入力部及び表示部を供えている。スキャナ１８は、画像ファイル生成のために用いられ、このファイルは印刷、ファクシミリ送信又はファイル送信のために用いられる。プリンタ１９は、プリントエンジン並びに用紙の給紙部、搬送部及び排紙部を備え、ＤＲＡＭ１４に生成されたビットマップデータが供給され、このデータに基づいて感光ドラムに静電潜像を形成し、この像をトナーで現像し、トナー像を用紙に転移し定着させ、排紙する。
【００２６】
図３は、上記印刷処理プログラムにおいて、印刷データとしてのＰＤＬデータに含まれるベクターオブジェクトをラスタライズする前の重畳図形分割処理を示す概略フローチャートである。以下、括弧内は図中のステップ識別符号である。
【００２７】
（Ｓ０）後で閉曲線のトレース方向を利用するので、ここで各図形境界線の一方向回り、例えば時計回りの方向付けを行う。
【００２８】
例えば図４（Ａ）に示すような直線Ｐ１Ｐ２と曲線Ｐ２Ｐ１とを境界線とする図形４０について、Ｘ−Ｙ直交座標系の定義域と値域とから定まる外接矩形Ｒ１を求め、座標原点Ｏを（矩形Ｒ１の定義域の中点，矩形Ｒ１の値域の中点）とする。接点の１つ、例えば点Ｐ１から図形４０上を一方向へ回り、順に通過する接点列（Ｐ１、Ｐ２、Ｐ８、Ｐ７）の象限値（第１〜４象限の値１〜４）を記述していくと、（３，２，４，４）となり、これが時計回りのパターンであると判定できる。
【００２９】
この場合、直線Ｐ１Ｐ２は直線の端点Ｐ１から端点Ｐ２への方向が時計回りであり、曲線Ｐ２Ｐ１は曲線の端点Ｐ２から端点Ｐ１への方向が時計回りであると、境界線の線分を方向付ける。象限値順のパターンから反時計回りであると判定した場合には、その逆方向で線分を方向付ける。
【００３０】
この方向付けは、図４（Ｂ）のようにして行ってもよい。すなわち、図形４０上の同一直線上に無い３点、例えば点Ｐ１、Ｐ２、Ｐ９の三角形Ｐ１Ｐ２Ｐ９が内接する矩形Ｒ２について、上記同様に、Ｘ−Ｙ直交座標系の座標原点Ｏを（矩形Ｒ２の定義域の中点，矩形Ｒ２の値域の中点）とする。三角形Ｐ１Ｐ２Ｐ９の１つ、例えば点Ｐ１から図形４０上を一方向へ回り、順に通過する点（Ｐ１、Ｐ２、Ｐ９）の象限値を記述していくと、（３，２，１）となり、これが時計回りのパターンであると判定でき、上記同様に線分を方向付ける。
【００３１】
（Ｓ１）一方の図形と他方の図形との交点処理を行う。図５は、この交点処理の詳細フローチャートである。
【００３２】
交点処理には、交点座標を求める処理と、線分を交点で分割して分割後の各線分を表す式を求める処理とがあり、前者は以下のステップＳ３１〜Ｓ３７で行われ、後者は以下のステップＳ３９〜Ｓ４４で行われる。上記方向付けの結果は、後者のステップＳ４２、Ｓ４３で考慮する。線分は、３次ベジエ曲線又は直線であるとする。
【００３３】
（Ｓ３０）交点カウンタＮcpに初期値０を代入する。
【００３４】
一方の図形の線分毎に、以下のステップＳ３１からステップＳ３７までの処理を行う。例えば図６において、図形４０を一方の図形とすると、図形４０の線分である直線Ｐ１Ｐ２及び曲線Ｐ２Ｐ１のそれぞれについて、以下の処理を行う。
【００３５】
（Ｓ３１）該一方の図形の１つの線分を選択する。
【００３６】
他方の図形の線分毎に、以下のステップＳ３２〜Ｓ３６の処理を行う。例えば図６の図形４１の直線Ｐ３Ｐ４及び曲線Ｐ４Ｐ３のそれぞれについて、以下の処理を行う。
【００３７】
（Ｓ３２）該他方の図形の１つの線分を選択する。
【００３８】
（Ｓ３３）ステップＳ３１とステップＳ３２で選択した線分間に交点が存在すればステップＳ３４へ進み、そうでなければステップＳ３６へ進む。図６の場合、直線Ｐ１Ｐ２と、直線Ｐ３Ｐ４及び曲線Ｐ４Ｐ３のそれぞれとの間には交点が存在しないので、ステップＳ３３で否定判定され、曲線Ｐ２Ｐ１と、直線Ｐ３Ｐ４及び曲線Ｐ４Ｐ３とのそれぞれの間には交点が存在するので、ステップＳ３４へ進む。
【００３９】
（Ｓ３４）選択されている線分間の交点の座標を、例えば２分法で方程式を解くことにより求める。
【００４０】
（Ｓ３５）交点カウンタＮcpを１だけインクリメントする。
【００４１】
（Ｓ３６）該他方の図形について、未選択の線分が有ればステップＳ３２へ戻り、無ければステップＳ３７へ進む。
【００４２】
（Ｓ３７）該一方の図形について、未選択の線分が有ればステップＳ３１へ戻り、無ければステップＳ３８へ進む。
【００４３】
（Ｓ３８）交点カウンタＮcpが正であればステップＳ３９へ進み、そうでなければ図５の処理を終了する。
【００４４】
以下、各図形の線分毎、ステップＳ３９〜Ｓ４４の処理を行う。
【００４５】
（Ｓ３９）１つの線分を選択する。
【００４６】
（Ｓ４０）この線分上に、ステップＳ３４で求めた交点座標が存在すればステップＳ４１へ進み、そうでなければステップＳ４４へ進む。
【００４７】
（Ｓ４１）この線分がベジエ曲線であればステップＳ４２へ進み、直線であればステップＳ４３へ進む。
【００４８】
（Ｓ４２）ベジエ曲線を交点で分割し、分割された各ベジエ曲線の近似式を求める。
【００４９】
例えば図６の曲線Ｐ２Ｐ１については、交点Ｐ５、Ｐ６が存在するので、パラメータｔの区域が［０，１］のベジエ曲線Ｐ２Ｐ５の式と、パラメータｔの区域が［０，１］のベジエ曲線Ｐ５Ｐ６の式と、パラメータｔの区域が［０，１］のベジエ曲線Ｐ６Ｐ１の式とを求める。
【００５０】
より具体的には、ｘ−ｙ直交座標系での曲線Ｐ２Ｐ１上の任意の点の座標を（ｆ（ｔ），ｇ（ｔ））、曲線Ｐ２Ｐ１の制御点Ｑiの座標を（ｘi，ｙi）、ｉを１〜４の範囲の整数とすると、
ｆ（ｔ）＝（１−ｔ）3ｘ１＋３（１−ｔ）2ｔｘ２＋３（１−ｔ）ｔ2ｘ３＋ｔ3ｘ４  ・・・（１）
ｇ（ｔ）＝（１−ｔ）3ｙ１＋３（１−ｔ）2ｔｙ２＋３（１−ｔ）ｔ2ｙ３＋ｔ3ｙ４  ・・・（２）
と表される。ここにパラメータｔの区域は［０，１］であり、ｔ＝０で始点Ｐ２＝Ｑ１＝（ｘ１，ｙ１）、ｔ＝１で終点Ｐ１＝Ｑ５＝（ｘ４，ｙ４）となる。交点Ｐ５のｔの値をｔ１と表す。
【００５１】
パラメータｔの区域が［０，１］のベジエ曲線Ｐ２Ｐ５上の任意の点の座標（ｕ（ｔ），ｖ（ｔ））のｕ及びｖを、
ｕ（ｔ）＝ａ１・ｔ3＋ｂ１・ｔ2＋ｃ１・ｔ＋ｄ１  ・・・（３）
ｖ（ｔ）＝ａ２・ｔ3＋ｂ２・ｔ2＋ｃ２・ｔ＋ｄ２  ・・・（４）
と表し、８つの未知数ａ１、ｂ１、ｃ１、ｄ１、ａ２、ｂ２、ｃ２、ｄ２を以下の８つの条件式である連立方程式の解として求めることで、ベジエ曲線Ｐ２Ｐ５の式を決定する。
【００５２】
（ａ）始点Ｐ２及び交点Ｐ５の座標が両曲線で等しいことから、
（ｆ（０），ｇ（０））＝（ｕ（０），ｖ（０））
（ｆ（ｔ１），ｇ（ｔ１））＝（ｕ（１），ｖ（１））
という４つの条件式が得られる。
【００５３】
（ｂ）始点Ｐ２及び交点Ｐ５での傾きが両曲線で等しいという条件を与える。’をｔでの微分記号とすると、この条件は、ｔ＝０でのｆ'（ｔ）／ｇ'（ｔ）の値と、ｔ＝０でのｕ'（ｔ）／ｖ'（ｔ）の値とが互いに等しくなり、ｔ＝ｔ１でのｆ'（ｔ）／ｇ'（ｔ）の値と、ｔ＝１でのｕ'（ｔ）／ｖ'（ｔ）の値とが互いに等しくなるという式で表され、さらに２つの条件式が得られる。
【００５４】
（ｃ）また、始点Ｐ２及び交点Ｐ５での傾きの変化率が両曲線で等しいという条件を与える。この条件は、ｔ＝０での(ｆ'（ｔ）／ｇ'（ｔ）)'／ｇ'（ｔ）の値と、ｔ＝０での（ｕ'（ｔ）／ｖ'（ｔ））'／ｖ'（ｔ）の値とが互いに等しくなり、ｔ＝ｔ１での（ｆ'（ｔ）／ｇ'（ｔ））'／ｇ'（ｔ）の値と、ｔ＝１での（ｕ'（ｔ）／ｖ'（ｔ））'／ｖ'（ｔ）の値とが互いに等しくなるという式で表され、さらに２つの条件式が得られる。
【００５５】
上記８つの未知数は、以上の８つの条件式により定まる。
【００５６】
このような処理により、分割後のベジエ曲線の制御点を決定することなく該ベジエ曲線を求めることができるので、分割されたベジエ曲線の式を効率よく求めることができるという効果を奏する。
【００５７】
条件（ｃ）の替わりに、次のような条件を与えて近似してもよい。すなわち、ベジエ曲線Ｐ２Ｐ１がベジエ曲線Ｐ２Ｐ５上のパラメータ中点ｔ＝０．５での座標（ｕ（０．５），ｖ（０．５））を通るように定める。すなわち、ｆ（ｔ２）＝ｕ（０．５）、ｇ（ｔ２）＝ｖ（０．５）という拘束条件を与える。新たな未知数ｔ２を導入したので、この座標での両傾きが互いに等しいという条件を与える。すなわち、ｔ＝ｔ２での(ｆ'（ｔ）／ｇ'（ｔ）)'／ｇ'（ｔ）の値と、ｔ＝０．５での（ｕ'（ｔ）／ｖ'（ｔ））'／ｖ'（ｔ）の値とが互いに等しくなるという条件を与える。
【００５８】
この場合も、上記同様の効果を奏する。
【００５９】
なお、上式（３）、（４）を式（１）、（２）のように変形して制御点で表すことにより、制御点の座標列でベジエ曲線を表して、ラスタライザに受け渡すようにしてもよい。
【００６０】
次に、交点で分割されたそれぞれのベジエ曲線を、図７に示すように分割前のベジエ曲線Ｐ２Ｐ１と同じ方向（時計回り方向）に方向付ける。この方向付けは、線分に方向情報を付加することにより行う。例えば、パラメータｔが０から１に変化するとき座標が時計回り方向へ移動するようにした場合、この方向情報はパラメータｔに付加されていることになる。パラメータｔが０から１に変化するとき座標が反時計回り方向へ移動する場合には、パラメータを１次変換することにより、パラメータｔが０から１に変化するとき座標が時計回り方向へ移動するようにする。方向情報は、パラメータｔが０から１又は１から０のどちらに変化するときに座標が時計回り方向へ移動するかを示すフラグであってもよい。
【００６１】
次にステップＳ４４へ進む。
【００６２】
（Ｓ３３）直線を交点で分割し、分割されたそれぞれの定義域を求め、それぞれの直線の式は分割前のものと同一にする。また、それぞれの直線を、図７に示すように分割前の直線と同じ方向に方向付ける。図６の直線Ｐ３Ｐ４については、交点Ｐ５が存在するので、直線Ｐ３Ｐ４を、線分Ｐ３Ｐ５と線分Ｐ５Ｐ４とに分割し、それぞれの定義域を求め、また、それぞれの線分を図７に示すように、分割前の直線Ｐ３Ｐ４と同じ時計回り方向に方向付ける。
【００６３】
なお、直線についてもパラメータｔを用いて表し、いずれの直線もｔの区域が［０,１］となるようにして、ベジエ曲線の場合と同様に表現することにより、その後のラスタライザでの処理を統一して行えるようにしてもよい。
【００６４】
（Ｓ３４）全図形について、未選択の線分が有ればステップＳ３９へ戻り、無ければ図３のステップＳ２へ進む。
【００６５】
（Ｓ２）交点カウンタＮcpが正であればステップＳ３へ進み、そうでなければステップＳ１９へ進む。
【００６６】
以下、ステップＳ１で求めた交点毎に、ステップＳ３〜Ｓ９の、重畳しない部分の図形分割・登録処理を行う。
【００６７】
（Ｓ３）交点の１つを選択する。
【００６８】
（Ｓ４）この交点を始点とする時計回り方向の線分を１つ選択し、移動方向を時計回り方向と決める。
【００６９】
（Ｓ５）この線分上を、決められた方向へ移動し、次の交点まで移動する。「移動」は、線分の端点のみを追っていけばよい（以下同様）。
【００７０】
図７において、例えばステップＳ３で交点Ｐ５が選択され、ステップＳ４で線分Ｐ５Ｐ４が選択された場合、点Ｐ４から曲線Ｐ４Ｐ６の点Ｐ６まで移動する。
【００７１】
（Ｓ６）この交点が始点でなければステップＳ７へ進み、始点であればステップＳ８へ進む。
【００７２】
（Ｓ７）この交点から、他方の図形の同一点へ移る。移動方向は、移る前と逆方向と決め、ステップＳ５へ戻る。
【００７３】
前記の場合、図形４１の曲線Ｐ４Ｐ６の点Ｐ６から図形４０の曲線Ｐ５Ｐ６の点Ｐ６へ移り、移動方向を反時計回りと決定する。次にステップＳ５では、曲線Ｐ５Ｐ６の交点Ｐ６から交点Ｐ５へ移動し、ステップＳ６で交点Ｐ５が始点であると判定されてステップＳ８へ進む。
【００７４】
（Ｓ８）始点まで戻った閉曲線を、分割閉曲線として登録する。この分割閉曲線の色属性は、図形重畳部分ではないので、該分割閉曲線を含む分割前の図形の色属性と同じにする。
【００７５】
（Ｓ９）未選択の交点が有ればステップＳ３へ戻り、無ければステップＳ１０へ進む。
【００７６】
ステップＳ３で図７の交点Ｐ６を選択し、ステップＳ４で曲線Ｐ６Ｐ１を選択した場合には、ステップＳ５で点Ｐ１からＰ２、Ｐ５と移動し、ステップＳ６で否定判定されてステップＳ７へ進み、図形４０の交点Ｐ５から図形４１の点Ｐ５、Ｐ３、Ｐ６と移動し、ステップＳ６で肯定判定されてステップＳ８で閉曲線Ｐ６Ｐ１Ｐ２Ｐ５Ｐ３Ｐ６を登録し、その色属性を上記同様にして定める。
【００７７】
以下のステップＳ１０〜Ｓ１７は、図形論理積と図形論理和とを見つけて一端登録しておき、いずれが図形論理和であるかを判定してこれを削除することにより、図形論理積を重畳部分の分割図形として求める処理である。
【００７８】
（Ｓ１０）交点の１つを選択する。
【００７９】
（Ｓ１１）この交点を始点とする時計回り方向の線分を１つ選択し、移動方向を時計回り方向と決める。
【００８０】
（Ｓ１２）この線分上を、該方向へ移動し、次の交点まで移動する。
【００８１】
図７において、例えばステップＳ１０で交点Ｐ５が選択され、ステップＳ１１で曲線Ｐ５Ｐ６が選択された場合、交点Ｐ５から曲線Ｐ５Ｐ６の交点Ｐ６まで移動する。
【００８２】
（Ｓ１３）この交点が始点でなければステップＳ１４へ進み、始点であればステップＳ１５へ進む。
【００８３】
（Ｓ１４）この交点から、他方の図形の時計回り方向の線分の同一点へ移り、移動方向を前回と同じ時計回り方向と決め、ステップＳ１２へ戻る。
【００８４】
前記の場合、図形４０の曲線Ｐ５Ｐ６の交点Ｐ６から図形４１の曲線Ｐ６Ｐ３の交点Ｐ６へ移る。次にステップＳ１２では、交点Ｐ６から点Ｐ３、交点Ｐ５へと移動し、ステップＳ１３で交点Ｐ５が始点であると判定されてステップＳ１５へ進む。
【００８５】
（Ｓ１５）始点まで戻った閉曲線を分割閉曲線として登録する。
【００８６】
（Ｓ１６）始点で未選択の時計回り線分があればステップＳ１１へ戻り、無ければステップＳ１７へ進む。
【００８７】
ステップＳ１１で図７の曲線Ｐ５Ｐ４を選択した場合には、ステップＳ１２で交点Ｐ５から点Ｐ４、Ｐ６と移動し、ステップＳ１３で否定判定されてステップＳ１４へ進み、図形４１の交点Ｐ６から図形４０の交点Ｐ６、点Ｐ１、Ｐ２、Ｐ５と移動し、ステップＳ１３で肯定判定されてステップＳ１５で閉曲線Ｐ５Ｐ４Ｐ６Ｐ１Ｐ２Ｐ５を登録する。
【００８８】
（Ｓ１７）ステップＳ１５で登録された２つの閉曲線のうち、大きい方（図形論理和の閉曲線）を削除する。どちらが大きいかは、例えば図８に点線矩形で示すように、２つの閉曲線のそれぞれについて、定義域と値域とから定まる外接矩形Ｒ３、Ｒ４を求め、包含関係に基づいて決定する。
【００８９】
（Ｓ１８）ステップＳ１５で登録された２つの閉曲線のうち、小さい方（図形論理積の閉曲線）が分割前の２図形の重畳部分であり、その色属性を、該２図形のそれぞれの色属性及び予め設定されたブレンドモードに基づいて決定する。
【００９０】
例えば図８において図形４０の上に図形４１が重なり、図形４１の色属性が透明度を持っている場合、閉曲線Ｐ５Ｐ６Ｐ３Ｐ５について、図形４０の色属性である塗り色と、図形４１の色属性である塗り色及び透明度と、既定値又はユーザが設定したブレンドモードとに基づいて、ブレンドカラーを決定する。この透明度が０（不透明）であれば、図形４１の色属性である塗り色を該閉曲線の色属性と決定する。
【００９１】
以上で図３の処理を終了する。
【００９２】
（Ｓ１９）図９（Ａ）に示すように、図形４０と図形４１Ａとの関係が包含関係、即ち一方の図形に他方の図形が含まれているという関係がある場合には、ステップＳ２０へ進み、そうでなければステップＳ２２へ進む。
【００９３】
包含関係があるか否かは、図形４１Ａ内の任意の点、例えば点Ｐ３を通る任意の直線、例えば横方向の直線が、点Ｐ３の両側のそれぞれについて図形４０と交差するか否かで判定することができる。
【００９４】
（Ｓ２０）内側の閉曲線と、内側を刳り抜いた外側の閉曲線とに分割して、それぞれを分割閉曲線として登録する。
【００９５】
（Ｓ２１）内側の閉曲線についてはステップＳ１８と同様にしてブレンドカラーを決定し、図３の処理を終了する。
【００９６】
（Ｓ２２）それぞれの閉曲線４０、４１を登録し、図３の処理を終了する。
【００９７】
なお、図９（Ｂ）に示すように図形４１Ｂの一辺が図形４０の辺と重なり交点（交差点）を有しない場合や、図９（Ｃ）に示すように図形４１Ｃの１点Ｐ４が図形４１の辺上に存在し交点を有しない場合は、図８に関し述べたことと同様にして包含関係を決定し、図９（Ａ）の場合と同様に処理する。
【００９８】
図１０は、図形４０と図形４１とが重なって交点を４個有する場合を示す。
【００９９】
この場合、図５の処理により図１１に示すような方向付線分が得られる。また、図３のステップＳ３〜Ｓ９の繰り返し処理により、重畳しない閉曲線Ｐ５Ｐ４Ｐ６Ｐ５、閉曲線Ｐ６Ｐ７Ｐ６、閉曲線Ｐ７Ｐ８Ｐ７及び閉曲線Ｐ８Ｐ１Ｐ２Ｐ５Ｐ３Ｐ８が得られる。また、図３のステップＳ１０〜Ｓ１６の処理により、図形論理和の閉曲線Ｐ５Ｐ４Ｐ６Ｐ７Ｐ８Ｐ１Ｐ２Ｐ５及び図形論理積の閉曲線Ｐ５Ｐ６Ｐ７Ｐ８Ｐ３Ｐ５が得られる。
【０１００】
本実施例１によれば、２図形４０、４１の境界線の一部である３次ベジエ曲線上に交点が存在するとき、この３次ベジエ曲線を、その各端点及び該交点での位置で分割し、分割された各線分をパラメータの区域が［０，１］である３次ベジエ曲線で近似し、これを用いて、２図形４０、４１の分割された部分の閉曲線を記述するので、分割前後で図形表現が統一されて、既存のラスタライズ処理を変更せずに用いることができるという効果を奏する。
【０１０１】
また、図３のステップＳ０で図形境界線の方向付けを行ってから、ステップＳ３〜Ｓ９の簡単な処理で、相互に重畳しない図形の部分を求めることができるという効果を奏する。
【０１０２】
さらに、この方向付けを行ってから、ステップＳ１０〜Ｓ１８の簡単な処理で、相互に重畳する図形の部分を求めることができるという効果を奏する。
【０１０３】
以上において、本発明の好適な実施例を説明したが、本発明には他にも種々の変形例が含まれ、上記実施例で述べた各構成要素の機能を実現する他の構成を用いたもの、当業者であればこれらの構成又は機能から想到するであろう他の構成も、本発明に含まれる。
【０１０４】
例えば、図３のステップＳ１１及びＳ１４での一方向は、方向情報が示す方向と逆の方向であってもよい。
【０１０５】
また、ステップＳ４２において、分割された各ベジエ曲線のｔ＝０．５で分割前のベジエ曲線の対応する点（ｘ座標が両者で同一の点）での近似誤差（両者のｙ座標の差の絶対値）がしきい値、例えば１画素以上であれば、この点でさらにベジエ曲線を同様に分割することにより、近似精度を向上させてもよい。この２分割処理は、誤差がしきい値未満になるまで、分割点の両側のそれぞれについて続けてもよい。
【０１０６】
さらに、３図形以上の場合には、レイヤーが下の方からまず２図形を取り出して上記実施例で述べた処理を行い、ついで３図形目を取り出して、これと、登録されている分割図形の各々について順に、上記実施例で述べた処理を行い、その後４図形目以降も同様に処理するようにしてもよい。本発明は、少なくとも２図形について適用することにより、上記効果が得られる。
【符号の説明】
【０１０７】
１０  画像形成装置
１１  ＣＰＵ
１２  インターフェイス
１３  ＰＲＯＭ
１４  ＤＲＡＭ
１５  補助記憶装置
１６  ネットワークインターフェイス
１７  操作パネル
１８  スキャナ
１９  プリンタ
１Ａ  ファックスモデム
２０  ＰＣ
３０  ネットワーク
４０、４１、４１Ａ〜４１Ｃ  図形
Ｐ１〜Ｐ４  点
Ｐ５〜Ｐ８  交点
【図１】
0005687612.tif 000002
【図２】
0005687612.tif 000003
【図３】
0005687612.tif 000004
【図４】
0005687612.tif 000005
【図５】
0005687612.tif 000006
【図６】
0005687612.tif 000007
【図７】
0005687612.tif 000008
【図８】
0005687612.tif 000009
【図９】
0005687612.tif 000010
【図１０】
0005687612.tif 000011
【図１１】
0005687612.tif 000012