領域分割装置及び領域分割プログラム
【課題】従来の方法に比べて簡単に、重なりを持つ複数の領域を重ならない領域へ分割する領域分割装置を提供する。
【解決手段】領域断片取得部１３は、読出部１２で読み出した基点から閉領域Ａの境界線を時計回り方向にたどって次の交点である第１の交点を求め、その第１の交点から閉領域Ｂの境界線を時計方向と反時計方向にたどって、２つの領域断片をそれぞれ求める。判定部１４は、得られた領域断片の始点が既に登録されている分割領域の終点か否か、及び、その分割領域の境界線をたどった方向と領域断片が閉領域Ｂをたどった方向が同じか否かを判定する。この条件が満たされれば、登録されている分割領域の境界線として領域断片を追加し、そのほかの場合には領域断片を新たな分割領域の境界線として、包含関係を示す領域種別を付加して登録する。この処理を、閉領域Ａを周回するまで、各交点について順に行う。
【解決手段】領域断片取得部１３は、読出部１２で読み出した基点から閉領域Ａの境界線を時計回り方向にたどって次の交点である第１の交点を求め、その第１の交点から閉領域Ｂの境界線を時計方向と反時計方向にたどって、２つの領域断片をそれぞれ求める。判定部１４は、得られた領域断片の始点が既に登録されている分割領域の終点か否か、及び、その分割領域の境界線をたどった方向と領域断片が閉領域Ｂをたどった方向が同じか否かを判定する。この条件が満たされれば、登録されている分割領域の境界線として領域断片を追加し、そのほかの場合には領域断片を新たな分割領域の境界線として、包含関係を示す領域種別を付加して登録する。この処理を、閉領域Ａを周回するまで、各交点について順に行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、領域分割装置及び領域分割プログラムに関するものである。
【背景技術】
【０００２】
従来より画像処理分野においては、処理領域を分割する領域分割処理がしばしば用いられる。特に、それぞれが重なる処理領域に対して処理を行う場合があり、このような場合には重なり方の関係に従って各処理領域を分割することが行われている。図１７は、領域分割の一例の説明図である。例えば図１７（Ａ）に示すように実線で示した領域Ａと、領域Ａよりも太い線で示した領域Ｂとが重なり合っている場合を考える。この場合、図１７（Ｂ）に示すように、重ならない各領域に分割する。図１７（Ａ）において、Ａｃは領域Ａ外を示し、Ｂｃは領域Ｂ外を示している。すなわち、Ａ∩Ｂは領域Ａと領域Ｂが重なっていた分割領域、Ａ∩Ｂｃは領域Ａ内であるが領域Ｂ外の分割領域、Ａｃ∩Ｂは領域Ｂ内であるが領域Ａ外の分割領域、Ａｃ∩Ｂｃは領域Ａにも領域Ｂにも含まれない領域を示している。図１７（Ｂ）においては、領域Ａにも領域Ｂにも含まれない領域については示していない。
【０００３】
このような領域分割を必要とする処理の一例としては、特許文献１に記載されているように複数の図形を一部重ねて半透明処理により描画する場合が挙げられる。例えば図形１と図形２を描画する際に、図形１のうち図形２と重ならない部分（図１７（Ｂ）におけるＡ∩Ｂｃの領域に対応）と、図形２のうち図形１と重ならない部分（図１７（Ｂ）におけるＡｃ∩Ｂの領域に対応）については、図形１及び図形２の描画をそのまま行えばよい。図形１と図形２が重なる部分（例えば図１７（Ｂ）におけるＡ∩Ｂの領域に対応）については、両者を考慮した描画処理が必要となる。そのため、図形１のうち図形２と重ならない部分と、図形２のうち図形１と重ならない部分と、図形１と図形２が重なる部分とに領域を分割し、それぞれの領域についての描画処理を行っている。もちろん、このほかにも領域分割が必要な場合は多い。
【０００４】
このような複数の図形が重なりを持つ場合に、それぞれ重ならない領域へ分割する一つの方法として、２重連結辺リストを用いた平面走査方式がある。この方法では、複数の図形の境界線となる辺をそれぞれ線分とし、ある特定の方向に走査して線分との交点をもとに線分同士の交点を求める。この交点で線分を分割するとともに、交点を中心に例えば時計回りで隣接する線分を結合してゆく。結合の際に、一方の線分については交点へ向かう方向の線分ベクトルとし、もう一方は交点を始点とする方向の線分ベクトルとする。分割した各線分は２回ずつ用いられ、方向が異なる２つの線分ベクトルとして別々の線分ベクトルと結合されることになる。得られた連結された線分ベクトルにより囲まれた領域が、分割された領域を示すことになる。
【０００５】
【特許文献１】特開平１１−３２７５３４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明は、従来の方法に比べて簡単に、重なりを持つ複数の領域を重ならない領域へ分割することができる領域分割装置及び領域分割プログラムを提供することを目的とするものである。
【課題を解決するための手段】
【０００７】
本願請求項１に記載の発明は、第１の閉領域の境界線の情報を記憶する第１の記憶手段と、前記第１の閉領域と境界線が交差する第２の閉領域の境界線の情報を記憶する第２の記憶手段と、分割領域の境界線の情報を記憶する第３の記憶手段と、前記第１の記憶手段から前記第２の閉領域との交点を所定の方向に前記第１の閉領域を周回するまで順に基点として読み出す読出手段と、前記読出手段で読み出した基点から前記第１の閉領域の境界線を所定の方向にたどって次の第２の閉領域の境界線との交点である第１の交点から第２の閉領域の境界線を時計方向と反時計方向にたどってそれぞれ基点から第１の交点を通り第２の交点を終点とする領域断片と基点から第１の交点を通り第３の交点を終点とする領域断片をそれぞれ求める領域断片取得手段と、前記領域断片取得手段で求めた２つの領域断片について前記領域断片の始点が前記第３の記憶手段に記憶されている分割領域の境界線のその時点での終点として登録されているか否か及び登録されている場合に該登録されている分割領域の境界線をたどった方向と前記領域断片が前記第２の閉領域をたどった方向が同じか否かを判定する判定手段と、前記判定手段によって基点が既に登録されていると判定され領域断片がたどった方向が分割領域の境界線がたどった方向であると判定された場合には該登録されている分割領域の境界線として前記領域断片を追加しそのほかの場合には前記領域断片を新たな分割領域の境界線として前記第３の記憶手段に登録する登録手段を有することを特徴とする領域分割装置である。
【０００８】
本願請求項２に記載の発明は、請求項１に記載の領域分割装置の前記登録手段が、前記領域断片を新たな分割領域の境界線として前記第３の記憶手段に登録する際に、前記領域断片の基点から第１の交点までの前記第１の閉領域の境界線が前記第２の閉領域の内部か否か及び第１の交点から前記第２の閉領域の境界線をたどった方向により、当該分割領域が前記第１の閉領域と前記第２の閉領域との集合演算により定められる領域のいずれに属するかを示す領域種別を決定し、該領域種別を前記新たな分割領域に付加して登録することを特徴とする領域分割装置である。
【０００９】
本願請求項３に記載の発明は、請求項１または請求項２に記載の領域分割装置の構成に加えて、さらに、前記第１の閉領域と前記第２の閉領域の交点を検出して前記第１の記憶手段及び第２の記憶手段に境界線の情報として記憶させる交点検出手段を有することを特徴とする領域分割装置である。
【００１０】
本願請求項４に記載の発明は、請求項１ないし請求項３のいずれか１項に記載の領域分割装置の構成に加えて、さらに、前記第１の閉領域と前記第２の閉領域が交点を有するか否かを判定する交点判定手段と、前記交点判定手段が交点を有しないと判定した場合に包含処理を行う包含処理手段を有し、前記判定手段が交点を有すると判定した場合に前記読出手段、領域断片取得手段、判定手段、登録手段による処理を行い、前記包含処理手段は、前記第１の閉領域と前記第２の閉領域に重なりがない場合には前記第１の閉領域及び前記第２の閉領域を処理結果とし、一方の閉領域が内部に他方の閉領域を包含する場合には、前記一方の閉領域の前記他方の閉領域を除く領域を分割して、分割した各領域と前記他方の閉領域を処理結果とすることを特徴とする領域分割装置である。
【００１１】
本願請求項５に記載の発明は、請求項１ないし請求項４のいずれか１項に記載の領域分割装置の構成に加えて、さらに、前記第３の記憶手段に登録された分割領域が接触点または接触線を含む場合に接触する点で分割領域を分割する接触点分割手段をさらに有することを特徴とする領域分割装置である。
【００１２】
本願請求項６に記載の発明は、請求項１ないし請求項４のいずれか１項に記載の領域分割装置の構成に加えて、さらに、前記第１の閉領域と前記第２の閉領域が接触点を有する場合に２つの交点となるように前記第１の記憶手段に記憶されている前記第１の閉領域の境界線の情報または前記第２の記憶手段に記憶されている前記第２の閉領域の境界線の情報を変更する変更手段を有することを特徴とする領域分割装置である。
【００１３】
本願請求項７に記載の発明は、コンピュータに、請求項１ないし請求項６のいずれか１項に記載の領域分割装置の機能を実行させることを特徴とする領域分割プログラムである。
【発明の効果】
【００１４】
本願請求項１に記載の発明によれば、本発明の構成を用いない場合に比べて、簡単に、重なりを持つ複数の領域を、重なりのない複数の領域へ分割することができる。
【００１５】
本願請求項２に記載の発明によれば、分割した各領域に対して第１の閉領域と第２の閉領域との集合演算により定められる領域のいずれに属するかを示す領域種別を簡単に付与することができる。
【００１６】
本願請求項３に記載の発明によれば、本構成を有しない場合に比べて処理を高速化することができる。
【００１７】
本願請求項４に記載の発明によれば、一方の閉領域が他方の閉領域に含まれている場合でも領域の分割を行うことができ、両者の重なりがない場合についても対応することができる。
【００１８】
本願請求項５及び請求項６に記載の発明によれば、２つの閉領域の境界が接している場合についても、重なりのない複数の領域へ分割することができる。
【００１９】
本願請求項７に記載の発明は、本願請求項１ないし請求項６のいずれか１項に記載の発明の効果と同等の効果を得ることができる。
【発明を実施するための最良の形態】
【００２０】
図１は、本発明の第１の実施の形態を示すブロック図である。図中、１１は記憶部、１２は読出部、１３は領域断片取得部、１４は判定部、１５は登録部である。ここでは、第１の閉領域Ａと第２の閉領域Ｂとが重なりを有している場合に、閉領域Ａと閉領域Ｂとの集合演算により定められる領域、すなわち、閉領域Ａと閉領域Ｂの両方に含まれる領域、閉領域Ａには含まれるが閉領域Ｂには含まれない領域、閉領域Ｂには含まれるが閉領域Ａには含まれない領域に、それぞれが重ならないように分割する。３以上の閉領域が重なる場合には、２つの閉領域について分割した後、分割した各領域と別の閉領域との重なりをもとに分割処理を行ってゆけばよい。従って、２つの閉領域についての説明を行う。
【００２１】
なお、閉領域Ａと閉領域Ｂの一方が他方に完全に包含されることはないものとする。また、各閉領域の境界線がそれぞれ自分自身と途中で交差したり、内部に当該閉領域に含まれない領域が存在していないものとする。さらに、閉領域Ａと閉領域Ｂの境界線が接する箇所はないものとする。これらの場合のいくつかについての対処は、別の実施の形態で述べる。
【００２２】
記憶部１１は、閉領域Ａと閉領域Ｂの境界線の情報と、分割領域の境界線の情報を記憶する。各領域の境界線の情報は、境界線上のいくつかの点の情報により与えられる。点の間は、例えば直線や曲線で結ばれて境界線を構成する。なお、閉領域Ａ及び閉領域Ｂの境界線の情報として、両者の境界線の交点の情報が与えられていると、後述するように境界線をたどって次の交点を見つける際に有用である。
【００２３】
読出部１２は、記憶部１１から閉領域Ａまたは閉領域Ｂのいずれか一方について、交点を所定の方向に周回するまで順に基点として読み出し、領域断片取得部１３に渡す。ここでは閉領域Ａについて、交点を時計回り方向に順に読み出して基点とする。最初の基点としては、ここでは閉領域Ｂ外に存在する閉領域Ａの境界線が、閉領域Ｂと交差する２つの交点のうちの一方とする。このとき、他方の交点が、一方の交点から時計回り方向に存在する交点となるようにする。なお、確実にこのような条件を満たす最初の交点を見つけるため、例えば２つの閉領域のうち、特定の軸に関する座標値が最小あるいは最大となる点を特定し、その点を有する閉領域を閉領域Ａ、もう一方の閉領域を閉領域Ｂとし、特定した点から閉領域Ａの境界線を反時計回り方向にたどって得られる閉領域Ｂとの交点を最初の基点とすればよい。もちろん、この方法に限らず、最初の基点を決定してもよい。
【００２４】
領域断片取得部１３は、読出部１２で読み出した基点から、ここでは閉領域Ａの境界線を所定の方向にたどって次の第２の閉領域の境界線との交点である第１の交点を求め、さらにその第１の交点から閉領域Ｂの境界線を時計回り方向と反時計回り方向にたどって、それぞれ基点から第１の交点を通り第２の交点を終点とする領域断片と、基点から第１の交点を通り第３の交点を終点とする領域断片をそれぞれ求める。
【００２５】
判定部１４は、領域断片取得部１３で求めた２つの領域断片について、領域断片の始点が記憶部１１に分割領域境界線情報として記憶されている分割領域の境界線のその時点での終点として登録されているか否か、及び、登録されている場合には、その登録されている分割領域の境界線をたどった方向と、領域断片が閉領域Ｂをたどった方向が同じか否かを判定する。
【００２６】
登録部１５は、判定部１４によって領域断片の始点が既に登録されていると判定され、領域断片が閉領域Ｂをたどった方向が分割領域の境界線がたどった方向であると判定された場合には、その登録されている分割領域の境界線として、分割領域境界線情報に領域断片を追加する。また、そのほかの場合には、領域断片を新たな分割領域の境界線として、分割領域境界線情報を記憶部１１に登録する。新たな分割領域の登録を行う際には、当該分割領域が閉領域Ａと閉領域Ｂとの集合演算により定められる領域のいずれに属するかを示す領域種別を付加する。この領域種別は、当該分割領域が閉領域Ａ及び閉領域Ｂの両方に含まれるのか、閉領域Ａに含まれるが閉領域Ｂには含まれないのか、閉領域Ｂに含まれるが閉領域Ａには含まれないのか、あるいは閉領域Ａにも閉領域Ｂにも含まれないのかを示すものである。付加する領域種別の決定は、分割領域の境界線として登録する領域断片の基点から第１の交点までの閉領域Ａの境界線が閉領域Ｂの内部か否か、及び、第１の交点から閉領域Ｂの境界線をたどった方向により決定される。
【００２７】
図２は、本発明の第１の実施の形態における動作の一例を示す流れ図である。なお、予め閉領域Ａ境界線情報及び閉領域Ｂ境界線情報が記憶部１１に記憶されているものとする。また、閉領域Ａ境界線情報及び閉領域Ｂ境界線情報には、互いの交点が予め検出されているものとする。ここでは交点をａ（ｉ）とする。上述のように、交点ａ（ｉ）は閉領域Ａの時計回り方向に順に存在するものとする。また、最初の基点となる交点ａ（１）は、例えば２つの閉領域のうち、座標値が最小あるいは最大となる点を特定し、その点を有する閉領域を閉領域Ａ、もう一方の閉領域を閉領域Ｂとし、特定した点から閉領域Ａの境界線を反時計回り方向にたどって得られる閉領域Ｂとの交点をａ（１）とすればよい。ここではこの交点ａ（１）から次の交点ａ（２）までの閉領域Ａの境界線は閉領域Ｂの外部であるものとする。
【００２８】
Ｓ３１において、基点となる交点を指定する変数ｉを１とし、交点ａ（１）を最初の基点とする。読出部１２は、この交点ａ（１）の情報を記憶部１１から読み出して領域断片取得部１３に渡す。
【００２９】
Ｓ３２において、領域断片取得部１３は基点ａ（ｉ）から閉領域Ａの境界線を時計回り方向にたどって次の第２の閉領域の境界線との交点である第１の交点を求める。上述のように交点の情報が境界線情報として予め記憶されていれば、次の交点の情報は簡単に取得される。すなわち、基点ａ（ｉ）の次の交点である第１の交点は、交点ａ（ｉ＋１）である。さらに領域断片取得部１３は、その第１の交点ａ（ｉ＋１）から閉領域Ｂの境界線を時計回り方向と反時計回り方向にたどって、２つの領域断片を求める。基点から第１の交点を通り時計回り方向に閉領域Ｂの境界線をたどった領域断片をＣＲ（ｉ）、基点から第１の交点を通り反時計回り方向に閉領域Ｂの境界線をたどった領域断片をＣＬ（ｉ）とする。
【００３０】
Ｓ３３において、領域断片ＣＲ（ｉ）、ＣＬ（ｉ）の始点である基点ａ（ｉ）が、分割領域の境界線のここまでの処理における終点として登録されているか否か、及び、登録されている場合にはその分割領域の境界線が閉領域Ｂをたどっている方向と領域断片が閉領域Ｂをたどっている方向が一致するか否かを判定部１４で判定する。この条件を満たす領域断片については、Ｓ３４において、登録部１５は登録済みの分割領域の境界線の終点の後に、条件を満たす領域断片を追加して登録する。これにより、当該分割領域の終点は、追加された領域断片の終点である第２または第３の交点となるか、あるいは分割領域として境界線が周回する。
【００３１】
Ｓ３３の条件を満たさない場合には２つの領域断片について、あるいは一方の領域断片は条件を満たしてＳ３４の処理を行った場合の他方の領域断片については、Ｓ３５において登録部１５は新たな分割領域の境界線の一部として各領域断片を新規登録する。登録の際には、対応する領域種別を付加する。
【００３２】
図３は、領域種別の一例の説明図である。図３において、Ａｃは閉領域Ａ外を示し、Ｂｃは閉領域Ｂ外を示している。すなわち、Ａ∩Ｂは閉領域Ａと閉領域Ｂの両方に含まれることを示し、Ａ∩Ｂｃは閉領域Ａ内であるが閉領域Ｂ外であることを示し、Ａｃ∩Ｂは閉領域Ｂ内であるが閉領域Ａ外であることを示し、Ａｃ∩Ｂｃは閉領域Ａにも閉領域Ｂにも含まれないことを示している。
【００３３】
上述のように交点ａ（１）からａ（２）までの閉領域Ａの境界線が閉領域Ｂの外部であり、時計回り方向に閉領域Ａの交点をたどって順に基点とする場合には、変数ｉの値と領域断片がＣＬ（ｉ）かＣＲ（ｉ）かにより、図３に示すような領域種別を付加する。すなわち、変数ｉが奇数のときの領域断片ＣＬ（ｉ）については、閉領域Ａに含まれるが閉領域Ｂには含まれない（Ａ∩Ｂｃ）領域種別を付加し、領域断片ＣＲ（ｉ）については、閉領域Ａにも閉領域Ｂにも含まれない（Ａｃ∩Ｂｃ）領域種別を付加する。また、変数ｉが偶数のときの領域断片ＣＬ（ｉ）については、閉領域Ｂに含まれるが閉領域Ａには含まれない（Ａｃ∩Ｂ）領域種別を付加し、領域断片ＣＲ（ｉ）については、閉領域Ａと閉領域Ｂの両方に含まれる（Ａ∩Ｂ）領域種別を付加する。
【００３４】
ここでは交点ａ（１）からａ（２）までの閉領域Ａの境界線が閉領域Ｂの外部であるとしていることから、変数ｉが奇数であれば閉領域Ｂ外であり、変数ｉが偶数であれば、閉領域Ｂ内であると判定すればよい。これは、交点を通過すれば閉領域Ｂの内外が反転するからである。もちろん、最初の交点ａ（１）が閉領域Ｂの内部であれば変数ｉの値によって付加する領域種別は変わるし、閉領域Ａの交点をたどる方向が違う場合も、付加する領域種別は変わる。しかし、これらの条件が決まれば、閉領域Ｂの内外と領域断片がＣＬ（ｉ）かＣＲ（ｉ）かによって付加する領域種別は決定される。
【００３５】
図２に戻り、Ｓ３６において、読出部１２は次の交点ａ（ｉ＋１）が最初の基点ａ（１）であるか否かを判定し、交点ａ（ｉ＋１）が交点ａ（１）でない場合には、Ｓ３７において変数ｉを１だけ増加させ、次の交点ａ（ｉ）を基点として領域断片取得部１３に渡し、Ｓ３２へ戻って処理を続ける。
【００３６】
このような処理を繰り返して行い、Ｓ３６で交点ａ（ｉ＋１）が交点ａ（１）である場合には周回したものとして処理を終える。これまでの処理によって、分割領域の境界線の情報が記憶部１１に分割領域境界線情報として登録されている。また、各分割領域には分割前の閉領域Ａ，Ｂとの集合演算により定められる領域を示す領域種別が付加されている。例えば領域の重なりを考慮した描画処理を行う場合には、各分割領域について領域種別に従った描画処理を行えばよい。
【００３７】
図４は、本発明の第１の実施の形態における動作の具体例の説明図、図５、図６は、分割領域境界線情報の変化の一例の説明図である。図４において、閉領域Ａの境界線を実線で示し、閉領域Ｂの境界線を閉領域Ａの境界線よりも太い線で示している。また、ここでは最初の基点を得るため閉領域Ａの境界線上の点Ｐを求め、点Ｐから反時計回り方向に閉領域Ａの境界線をたっどって最初に現れる閉領域Ｂとの交点をａ（１）としている。この交点ａ（１）から閉領域Ａの境界線を時計回り方向にたどって出現する閉領域Ｂとの交点をそれぞれａ（２）〜ａ（６）としている。また、図５において時計回り方向をＲ、反時計回り方向をＬとして示している。
【００３８】
まず、交点ａ（１）を基点とする。そして、次の交点ａ（２）を第１の交点とし、この交点ａ（２）から閉領域Ｂを時計回り方向にたどって交点ａ（３）に至る領域断片ＣＲ（１）と、交点ａ（２）から閉領域Ｂを反時計回り方向にたどって交点ａ（５）に至る領域断片ＣＬ（１）を得る。まだ分割領域境界線情報は記憶部１１に記憶されていないので、登録部１５はこれらの領域断片ＣＲ（１）、ＣＬ（１）を新たな分割領域の境界線の一部として登録する。それぞれの新たな分割領域の領域種別は、図３に従って付与する。領域断片ＣＲ（１）を新たな分割領域の境界線の一部として登録した場合には領域種別としてＡｃ∩Ｂｃが、領域断片ＣＬ（１）を新たな分割領域の境界線の一部として登録した場合には領域種別としてＡ∩Ｂｃが、それぞれ付加される。ここまでで登録された分割領域境界線情報の一例を図５（Ａ）に示している。
【００３９】
次に交点ａ（２）を基点とする。そして、次の交点ａ（３）を第１の交点とし、この交点ａ（３）から閉領域Ｂを時計回り方向にたどって交点ａ（４）に至る領域断片ＣＲ（２）と、交点ａ（３）から閉領域Ｂを反時計回り方向にたどって交点ａ（２）に至る領域断片ＣＬ（２）を得る。基点である交点ａ（２）を終点とする分割領域境界線情報は記憶部１１に記憶されていないので、登録部１５はこれらの領域断片ＣＲ（２）、ＣＬ（２）を新たな分割領域の境界線の一部として登録する。領域断片ＣＲ（２）を新たな分割領域の境界線の一部として登録した場合には領域種別としてＡ∩Ｂが、領域断片ＣＬ（２）を新たな分割領域の境界線の一部として登録した場合には領域種別としてＡｃ∩Ｂが、それぞれ付加される。ここまでで登録された分割領域境界線情報の一例を図５（Ｂ）に示している。
【００４０】
次に交点ａ（３）を基点とする。そして、次の交点ａ（４）を第１の交点とし、この交点ａ（４）から閉領域Ｂを時計回り方向にたどって交点ａ（１）に至る領域断片ＣＲ（３）と、交点ａ（４）から閉領域Ｂを反時計回り方向にたどって交点ａ（３）に至る領域断片ＣＬ（３）を得る。図５（Ｂ）の１行目に示すように、基点である交点ａ（３）を終点とする分割領域境界線情報が記憶部１１に記憶されており、この方向は時計回り方向である。従って、領域断片ＣＲ（３）を１行目の分割領域境界線情報に追加する。これにより、図５（Ｃ）の１行目のようになる。また、領域断片ＣＬ（３）は方向が異なるので新たな分割領域の境界線の一部として登録する。領域種別は図３からＡ∩Ｂｃが付加される。ここまでで登録された分割領域境界線情報の一例を図５（Ｃ）に示している。
【００４１】
次に交点ａ（４）を基点とする。そして、次の交点ａ（５）を第１の交点とし、この交点ａ（５）から閉領域Ｂを時計回り方向にたどって交点ａ（２）に至る領域断片ＣＲ（４）と、交点ａ（５）から閉領域Ｂを反時計回り方向にたどって交点ａ（６）に至る領域断片ＣＬ（４）を得る。図５（Ｃ）の３行目に示すように、基点である交点ａ（４）を終点とする分割領域境界線情報が記憶部１１に記憶されており、この方向は時計回り方向である。従って、領域断片ＣＲ（４）を図５（Ｃ）の３行目の分割領域境界線情報に追加する。これにより、図５（Ｄ）の３行目のようになる。また、領域断片ＣＬ（４）は方向が異なるので新たな分割領域の境界線の一部として登録する。領域種別は図３からＡｃ∩Ｂが付加される。ここまでで登録された分割領域境界線情報の一例を図５（Ｄ）に示している。
【００４２】
次に交点ａ（５）を基点とする。そして、次の交点ａ（６）を第１の交点とし、この交点ａ（６）から閉領域Ｂを時計回り方向にたどって交点ａ（５）に至る領域断片ＣＲ（５）と、交点ａ（６）から閉領域Ｂを反時計回り方向にたどって交点ａ（１）に至る領域断片ＣＬ（５）を得る。図５（Ｄ）の２行目に示すように、基点である交点ａ（５）を終点とする分割領域境界線情報が記憶部１１に記憶されており、この方向は反時計回り方向である。従って、領域断片ＣＬ（５）を図５（Ｄ）の２行目の分割領域境界線情報に追加する。これにより、図６（Ａ）の２行目のようになる。また、領域断片ＣＲ（５）は方向が異なるので新たな分割領域の境界線の一部として登録する。領域種別は図３からＡｃ∩Ｂｃが付加される。ここまでで登録された分割領域境界線情報の一例を図６（Ａ）に示している。
【００４３】
次に交点ａ（６）を基点とする。そして、次の交点ａ（１）を第１の交点とし、この交点ａ（１）から閉領域Ｂを時計回り方向にたどって交点ａ（６）に至る領域断片ＣＲ（６）と、交点ａ（１）から閉領域Ｂを反時計回り方向にたどって交点ａ（４）に至る領域断片ＣＬ（６）を得る。図６（Ａ）の６行目に示すように、基点である交点ａ（６）を終点とする分割領域境界線情報が記憶部１１に記憶されており、この方向は反時計回り方向である。従って、領域断片ＣＬ（６）を図６（Ａ）の６行目の分割領域境界線情報に追加する。これにより、図６（Ｂ）の６行目のようになる。また、領域断片ＣＲ（６）は方向が異なるので新たな分割領域の境界線の一部として登録する。領域種別は図３からＡ∩Ｂが付加される。ここまでで登録された分割領域境界線情報の一例を図６（Ｂ）に示している。
【００４４】
次の交点は交点ａ（１）である。閉領域Ａを周回したので処理を終える。ここまでの処理で記憶部１１に記憶されている分割領域境界線情報は図６（Ｂ）に示されており、それぞれが分割領域である。また、各分割領域には閉領域Ａと閉領域Ｂとの集合演算により定められる領域を示す領域種別が付加されている。
【００４５】
図７は、本発明の第２の実施の形態を示すブロック図である。図中、２１は交点検出部、２２は交点判定部、２３は包含処理部、２４は回転方向判定部、２５は領域分割部、２６は接触点分割部である。この第２の実施の形態では、上述の第１の実施の形態で示した構成により領域分割の処理を実行するための前処理と、一方の閉領域が他方の閉領域の内部に含まれている場合の処理を追加したものである。
【００４６】
交点検出部２１は、閉領域Ａの境界線と閉領域Ｂの境界線の交点を検出して、その交点の情報を閉領域Ａ境界線情報及び閉領域Ｂ境界線情報として追加して記憶部１１に記憶させる。上述の第１の実施の形態における動作の一例の説明では、交点が閉領域Ａ境界線情報及び閉領域Ｂ境界線情報に含まれているものとして説明しているが、交点検出部２１はこの交点に関する情報を閉領域Ａ境界線情報及び閉領域Ｂ境界線情報に追加するものである。
【００４７】
交点判定部２２は、閉領域Ａと閉領域Ｂが交点を有するか否かを判定する。与えられた閉領域Ａと閉領域Ｂとは、例えば重なる部分がない場合あるいは一方が他方の内部に存在する場合には交点を有しない。交点判定部２２は、このような場合については後述する包含処理部２３により分割の処理を行わせるためのものである。この交点判定部２２が交点を有すると判定した場合に、領域分割部２５による上述の第１の実施の形態で説明した領域分割の処理を行う。
【００４８】
包含処理部２３は、交点判定部２２で閉領域Ａと閉領域Ｂが交点を有しないと判定した場合に、包含処理を行う。閉領域Ａと閉領域Ｂが交点を有しない場合としては、閉領域Ａと閉領域Ｂに重なりがない場合と、いずれか一方の閉領域が内部に他方の閉領域を包含する場合である。閉領域Ａと閉領域Ｂに重なりがない場合には、領域を分割する必要がないので、閉領域Ａおよび閉領域Ｂのデータをそのまま処理結果とすればよい。一方の閉領域が内部に他方の閉領域を包含する場合には、一方の閉領域の他方の閉領域を除く領域を分割して、分割した各領域と他方の閉領域を処理結果とする。なお、包含処理部２３で処理する場合には領域分割部２５による分割処理は行わず、処理を効率化する。
【００４９】
回転方向判定部２４は、閉領域Ａおよび閉領域Ｂの境界線を示す点列が時計回り方向に並べられているのか、あるいは反時計回り方向に並べられているのかを判定する。第１の実施の形態における動作の一例でも説明したように、いずれの方向に境界線をたどるかによって、新たに部分領域を登録する際に付加する領域種別が異なってくる。そのため、この回転方向判定部２４において閉領域Ａおよび閉領域Ｂの回転方向を判定しておく。あるいはさらに、所定の方向、例えば時計回り方向となるように点列を並べ直しておけばよい。
【００５０】
領域分割部２５は、上述の第１の実施の形態で示した読出部１２、領域断片取得部１３、判定部１４、登録部１５を有し、領域分割処理を行う。
【００５１】
接触点分割部２６は、領域分割部２５で領域分割処理を行ったことにより得られた記憶部１１に分割領域境界線情報として記憶されている各分割領域について、境界線が接触点または接触線を含む場合に、接触する点で分割領域をさらに分割する。あるいは、接触点または接触線を微少な距離だけ離した点または線を設定し、分割領域が接触点または接触線を含まないように変更してもよい。
【００５２】
本発明の第２の実施の形態における動作の一例について説明してゆく。閉領域Ａおよび閉領域Ｂの境界線を示す点列のデータが与えられると、このデータを閉領域Ａ境界線情報および閉領域Ｂ境界線情報として記憶部１１に記憶する。ここでは閉領域Ａ境界線情報の一例として、例えば境界線上のｎ番目の点について、その点の参照用座標ＰＸＡ０（ｎ）、ＰＹＡ０（ｎ）、その点が交点かそれ以外の点かを示すフラグＶＴＡ（ｎ）、交点の場合には閉領域Ｂの点と対応づける情報ＶＮＡ（ｎ）などを含んでいるものとする。閉領域Ｂ境界線情報についても、例えば境界線上のｎ番目の点について、その点の参照用座標ＰＸＢ０（ｎ）、ＰＹＢ０（ｎ）、その点が交点かそれ以外の点かを示す情報ＶＴＢ（ｎ）、交点の場合には閉領域Ａの点と対応づける情報ＶＮＢ（ｎ）などを含んでいるものとする。
【００５３】
図８は、交点検出部による交点検出処理の一例を示す流れ図である。ここでは、閉領域Ａの境界線上の点列としてｎＡ個の点が与えられ、また閉領域Ｂの境界線上の点列としてｎＢ個の点が与えられているものとする。つまり、ＰＸＡ０（ｎ）、ＰＹＡ０（ｎ）（ｎ＝０，…，ｎＡ−１）及び、ＰＸＢ０（ｎ）、ＰＹＢ０（ｎ）（ｎ＝０，…，ｎＢ−１）が与えられているとする。これらの与えられた参照用座標をもとに、交点を加えてゆくための更新用座標ＰＸＡ（ｎ）、ＰＹＡ（ｎ）及び更新用座標ＰＸＢ（ｎ）、ＰＹＢ（ｎ）を用いる。なお、処理前はＶＴＡ（ｎ）、ＶＴＢ（ｎ）は交点以外を示す情報が設定され、ＶＮＡ（ｎ）、ＶＮＢ（ｎ）には情報が設定されていない状態になっているものとし、交点の追加などにより更新用座標ＰＸＡ（ｎ）、ＰＹＡ（ｎ）及び更新用座標ＰＸＢ（ｎ）、ＰＹＢ（ｎ）を更新するのに合わせて、ＶＴＡ（ｎ）、ＶＮＡ（ｎ）、ＶＴＢ（ｎ），ＶＮＢ（ｎ）も更新してゆくものとする。
【００５４】
Ｓ４１において、閉領域Ａの点列を選択するための変数ｎを初期値０に設定する。また、ｎＡ０＝ｎＡ、ｎＢ０＝ｎＢとしてｎＡとｎＢの値をｎＡ０，ｎＢ０に退避しておく。さらに、
ＰＸＡ（ｉ）＝ＰＸＡ０（ｉ） （ｉ＝０，…，ｎＡ−１）
ＰＹＡ（ｉ）＝ＰＹＡ０（ｉ） （ｉ＝０，…，ｎＡ−１）
ＰＸＢ（ｉ）＝ＰＸＢ０（ｉ） （ｉ＝０，…，ｎＢ−１）
ＰＹＢ（ｉ）＝ＰＹＢ０（ｉ） （ｉ＝０，…，ｎＢ−１）
で更新用座標を初期化する。更にまた、閉領域Ａ上の点列更新用のカウンタｃＡを０で初期化し、閉領域Ｂ上の点列更新用のカウンタｃＢ（ｉ）をｃＢ（ｉ）＝１（ｉ＝０，…，ｎＢ−１）で初期化する。
【００５５】
Ｓ４２において、閉領域Ａの境界線上で変数ｎで示されるｎ番目の点（ＰＸＡ０（ｎ），ＰＹＡ０（ｎ））とｎ＋１番目の点（ＰＸＡ０（ｎ＋１），ＰＹＡ０（ｎ＋１））とをつなぐ線分Ｃと、閉領域Ｂの境界線を示す各線分、すなわちｍ＝０，…，ｎＢ０−１についてｍ番目の点（ＰＸＢ０（ｍ），ＰＹＢ０（ｍ））とｍ＋１番目の点（ＰＸＢ０（ｍ＋１），ＰＹＢ０（ｍ＋１））とをつなぐ線分Ｄｍとの交点を全て計算し、線分Ｃ上でｎ番目の点（ＰＸＡ０（ｎ），ＰＹＡ０（ｎ））に近い方から順に並べ替える。交点の数をｋ個とし、ｊ番目（ｊ＝１，…，ｋ）の交点の座標をＣＸ（ｊ）、ＣＹ（ｊ）とし、閉領域Ｂにおいて交点が得られた線分Ｄｍを特定するための情報をＣＮ（ｊ）＝ｍとする。
【００５６】
Ｓ４３において、Ｓ４２で交点が見つかったか否かを判定し、交点がない場合にはＳ５０に進み、交点がｋ個（ｋ≧１）ある場合にはＳ４４〜Ｓ４９の処理を行う。
【００５７】
Ｓ４４において、交点を特定する変数ｊを１に初期化した後、ｊ番目の交点についての境界線情報を追加すべく、Ｓ４５において閉領域Ａ境界線情報を更新し、Ｓ４６において閉領域Ｂ境界線情報を更新する。これらの閉領域Ａ境界線情報及び閉領域Ｂ境界線情報の更新のため、まず、線分Ｃ上でＰＸＡ０（ｎ）、ＰＹＡ０（ｎ）に近い側からｊ番目の交点が、それぞれ閉領域Ａ、Ｂの境界線上において現状で何番目の点であるかを示す変数ａと変数ｂを定める。具体的には、変数ａにはｃＡ＋ｊを、また変数ｂにはΣi=1CN(j)+1ｃＢ（ｉ）を設定する。なお、ａは閉領域Ａの境界線上で順に更新されていった番号でよいが、ｂは閉領域Ａの境界線との交わりが発見されるごとに追加されるため、上記のような和の形で定義される。ここで求める変数ｂの値は、閉領域Ｂにおいて１番目からＣＮ（ｊ）＋１番目までの、もともとの閉領域Ｂの点列の数と、既に得られている交点の数の合計値となる。これにより、当該交点が閉領域Ｂ上で他の交点を含めて何番目であるかがわかる。
【００５８】
更に、ｃＢ（ＣＮ（ｊ））＞１の場合、つまり、閉領域Ｂの境界線上で（ＰＸＢ０（ＣＮ（ｊ）），ＰＹＢ０（ＣＮ（ｊ）））と（ＰＸＢ０（ＣＮ（ｊ）＋１），ＰＹＢ０（ＣＮ（ｊ）＋１））との間の交点が既に登録されている場合には、ｊ番目の交点と既に登録されている交点が閉領域Ｂの境界線上でどの順番で現れるかによってｂの値を変動させる。具体的には、ｌ＝ｂとして、（ＰＸＢ０（ＣＮ（ｊ）），ＰＹＢ０（ＣＮ（ｊ）））と（ＰＸＢ（ｌ），ＰＹＢ（ｌ））との閉領域Ｂの境界線上での長さと、（ＰＸＢ０（ＣＮ（ｊ）），ＰＹＢ０（ＣＮ（ｊ）））と（ＣＸ（ｊ），ＣＹ（ｊ））との閉領域Ｂの境界線上での長さとを比較し、前者の長さが後者の長さより小さくなるまでｌから１を引いて再び比較を繰り返す。このようにして閉領域Ｂの境界線上でｂ番目の交点から交点を１つずつ戻りながら、閉領域Ｂの境界線上での交点が存在する位置（どの点の間にあるか）を特定する。その後に、ｂにｌ＋１を代入しなおす。
【００５９】
そしてＳ４５における閉領域Ａ境界線情報の更新においては、ａ番目以降の境界線の点列の情報を１つ分シフトするため、
ＰＸＡ（ｉ）＝ＰＸＡ（ｉ−１） （ｉ＝ａ＋１，…，ｎＡ＋ｊ）
ＰＹＡ（ｉ）＝ＰＹＡ（ｉ−１） （ｉ＝ａ＋１，…，ｎＡ＋ｊ）
ＶＴＡ（ｉ）＝ＶＴＡ（ｉ−１） （ｉ＝ａ＋１，…，ｎＡ＋ｊ）
ＶＮＡ（ｉ）＝ＶＮＡ（ｉ−１）＋ｐ （ｉ＝ａ＋１，…，ｎＡ＋ｊ）
を行う。ここでｐは、ＶＮＡ（ｉ−１）＜ｂならば０とし、ＶＮＡ（ｉ−１）≧ｂならば１とする。なお、後者は閉領域Ａの境界線上においてａ番目に新しい交点を加える際に、閉領域Ｂの境界線上でより後段側にある点の参照番号が１つ後ろにずれることを意味している。
【００６０】
そして、ａ番目に交点の情報を追加挿入する。すなわち、
ＰＸＡ（ａ）＝ＣＸ（ｊ）
ＰＹＡ（ａ）＝ＣＹ（ｊ）
ＶＴＡ（ａ）＝１（交点を示す）
ＶＮＡ（ａ）＝ｂ（閉領域Ｂのｂ番目の交点と対応することを示す）
を行う。更に、ｃＢ（ＣＮ（ｊ））に１を加える。
【００６１】
また、Ｓ４６における閉領域Ｂ境界線情報の更新においては、ｂ番目以降の境界線の点列の情報を１つ分シフトするため、
ＰＸＢ（ｉ）＝ＰＸＢ（ｉ−１） （ｉ＝ｂ＋１，…，ｎＢ＋ｊ）
ＰＹＢ（ｉ）＝ＰＹＢ（ｉ−１） （ｉ＝ｂ＋１，…，ｎＢ＋ｊ）
ＶＴＢ（ｉ）＝ＶＴＢ（ｉ−１） （ｉ＝ｂ＋１，…，ｎＢ＋ｊ）
ＶＮＢ（ｉ）＝ＶＮＢ（ｉ−１）＋ｐ （ｉ＝ｂ＋１，…，ｎＢ＋ｊ）
を行う。ここでｐは、ＶＮＢ（ｉ−１）＜ａならば０とし、ＶＮＢ（ｉ−１）≧ａならば１とする。なお、後者は閉領域Ｂの境界線上においてｂ番目に新しい交点を加える際に、閉領域Ａの境界線上でより後段側にある点の参照番号が１つ後ろにずれることを意味している。
【００６２】
そして、ｂ番目に交点の情報を追加挿入する。すなわち、
ＰＸＢ（ｂ）＝ＣＸ（ｊ）
ＰＹＢ（ｂ）＝ＣＹ（ｊ）
ＶＴＢ（ｂ）＝１（交点を示す）
ＶＮＢ（ｂ）＝ａ（閉領域Ａのａ番目の交点と対応することを示す）
を行う。これにより、１つの交点の情報が各境界線情報に追加される。
【００６３】
Ｓ４７において、変数ｊに１を加え、Ｓ４８において、ｊがｋを超えたか否かを判定する。変数ｊの値がｋを超えていなければ、未処理の交点が残っているのでＳ４５へ戻って次の交点を追加する処理を行う。変数ｊの値がｋを超えたら、交点の追加が終了しているのでＳ４９に進む。
【００６４】
Ｓ４９において、交点を加えたことによる点列の数の更新を行う。すなわち、ｎＡ及びｎＢにｋを加えるとともに、点列更新用のカウンタｃＡにｋ＋１を加える。
【００６５】
Ｓ５０において、変数ｎに１を加え、Ｓ５１において、閉領域Ａを周回したか否かを判定する。Ｓ５１の判定は、変数ｎの値がｎＡ０に達したか否かを判定すればよい。変数ｎの値がｎＡ０に達していなければ、Ｓ４２へ戻って閉領域Ａの境界線を構成する次の線分と閉領域Ｂとの交点を見つける処理を行う。変数ｎがｎＡ０に達していれば、閉領域Ａを周回したので、処理を終了する。この処理によって、閉領域Ａ境界線情報及び閉領域Ｂ境界線情報として、両者の交点を含めた点列の情報が記憶されることになる。
【００６６】
なお、閉領域Ａ及び閉領域Ｂの境界線は直線による折れ線で構成されていなくてもよく、例えばベジエ曲線などの曲線で構成されていてもよい。境界線が曲線で構成されている場合には、曲線間の近似交点を求めてもよいし、あるいは、曲線を直線による折れ線で近似して交点を求め、近似してもよい。
【００６７】
交点判定部２２では、上述の交点検出部２１による処理の際に、交点を検出したか否かを示す情報を受け取って、閉領域Ａと閉領域Ｂとが交点を有するか否かを判定すればよい。あるいは、記憶部１１に記憶されている閉領域Ａ境界線情報あるいは閉領域Ｂ境界線情報を順に読み出して交点として登録されている点があるか否かを判定してもよい。
【００６８】
交点判定部２２で交点がないと判定された場合には、領域分割部２５が分割処理を行わずに、処理が簡単な包含処理部２３による包含処理を行う。図９は、包含処理部における包含処理の一例を示す流れ図、図１０は、包含処理部における包含処理の具体例の説明図である。まずＳ６１において、閉領域Ａと閉領域Ｂとの包含関係を判定するため、ある特定の点を閉領域Ａ及び閉領域Ｂから求める。特定の点としては、例えば最小の点や最大の点などを求めるとよい。ここでは一例としてｘ座標が最小の点をそれぞれ求めることとし、閉領域Ａのｘ座標が最小の点をａ、閉領域Ｂのｘ座標が最小の点をｂとする。
【００６９】
Ｓ６２において、直線ｘ＝ａと閉領域Ｂとの交点が、直線ｘ＝ａにおいて点ａを挟んで両側に存在するか否かを判定する。両側に存在する場合には、閉領域Ｂが閉領域Ａを内部に含むことを示している。この場合には、Ｓ６３において、閉領域Ｂのうち閉領域Ａに含まれない部分を分割し、分割した複数の領域と閉領域Ａを処理結果とする。分割する位置は閉領域Ａの境界線を含むように分割するとよい。例えば直線ｘ＝ａあるいは直線ｘ＝ａ＋αで分割すると簡単である。
【００７０】
Ｓ６２で直線ｘ＝ａと閉領域Ｂの交点がない場合や、交点があっても点ａを挟むように存在しない場合には、さらにＳ６４において、直線ｘ＝ｂと閉領域Ａとの交点が、直線ｘ＝ｂにおいて点ｂを挟んで両側に存在するか否かを判定する。両側に存在する場合には、閉領域Ａが閉領域Ｂを内部に含むことを示している。この場合には、Ｓ６５において、閉領域Ａのうち閉領域Ｂに含まれない部分を分割し、分割した複数の領域と閉領域Ｂを処理結果とする。分割する位置は閉領域Ｂの境界線を含むように分割するとよい。例えば直線ｘ＝ｂあるいは直線ｘ＝ｂ＋αで分割すると簡単である。
【００７１】
Ｓ６４でも直線ｘ＝ｂと閉領域Ａの交点がない場合や、交点があっても点ｂを挟むように存在しない場合には、いずれか一方が他方を含む関係にはないものと判断できる。この場合には、閉領域Ａと閉領域Ｂをそのまま処理結果とすればよい。
【００７２】
例えば図１０（Ａ）に示した例では、直線ｘ＝ａは交点を持たないためＳ６２からＳ６４へ移り、直線ｘ＝ｂと閉領域Ａとの交点を求めると、点ｂを挟んで両側に交点を有している。従って、閉領域Ａが閉領域Ｂを内部に含むと判断し、Ｓ６５において、閉領域Ａの閉領域Ｂ以外の部分を分割する。この例では、直線ｘ＝ｂ＋αで分割した例を図１０（Ｂ）に示している。このように分割しておけば、分割領域はそれぞれ数学的に同位相の閉領域となるため、さらに他の閉領域との重なりに応じた分割処理を行う場合でも支障はない。
【００７３】
交点判定部２２で交点がないと判定された場合には、領域分割部２５が分割処理を行うが、上述のように新たに部分領域を登録する際に付加する領域種別を決定する際に、各閉領域の境界線を示す点列の回転方向を求めておくとよい。その判定を回転方向判定部２４で行っておく。なお、領域種別を付加せずに領域分割を行う場合には、回転方向判定部２４は不要である。
【００７４】
図１１は、回転方向判定部における回転方向の判定処理の一例を示す流れ図、図１２は、同じく具体例の説明図である。Ｓ７１において、閉領域の境界線上の特定の点を選択する。特定の点としては、ここではｘ座標の値が最も小さい点のうち、ｙ座標の値が最も小さい点ａを選択する。Ｓ７２において、閉領域の境界線を構成する点列から点ａの一つ後の点ｂを取得する。またＳ７３において、閉領域の境界線を構成する点列から点ａの一つ前の点ｃを取得する。
【００７５】
Ｓ７４において、点ａと点ｂを通る直線上で点ａから点ｂに向かう方向から見て右側に点ｃが存在するのか、左側に点ｃが存在するのかを判定する。点ａから点ｂへ向かう方向から見て右側に点ｃが存在する場合には、Ｓ７５において、当該閉領域は時計回り方向と判定する。また、点ａから点ｂへ向かう方向から見て左側に点ｃが存在する場合には、Ｓ７６において、当該閉領域は反時計回り方向と判定する。
【００７６】
図１２（Ａ）に示す例では、点ａから点ｂへ向かう方向から見て左側に点ｃが存在するので、反時計回り方向と判定される。図１２（Ｂ）に示す場合にも、点ａから点ｂへ向かう方向から見て左側に点ｃが存在するが、実際には時計回り方向である。この場合、Ｓ７１において点ａを選択する際のｘ座標値が最小であるという条件を満たしていないので、図１２（Ｂ）に示すような不都合は生じない。
【００７７】
このようにして回転方向判定部２４によって各閉領域の境界線を示す点列の回転方向がわかる。この回転方向に従って領域分割部２５による分割処理により各分割領域に付加する領域種別を変更したり、あるいは、回転方向を統一して点列を並べ替えてから領域分割部２５による分割処理を行えばよい。領域分割部２５による分割処理は第１の実施の形態において説明した通りである。
【００７８】
領域分割部２５による分割処理では、接触点や接触線は交点ではないため境界線上の１点として扱われる。そのため、領域分割部２５で分割された分割領域では、接触点や接触線がそのまま残った状態となっている。もちろんこのまま処理結果としてもよいが、例えば領域分割後に半透明処理を行う場合などでは、接触点あるいは接触線では塗りつぶしを行う面積がないため、不具合を生じかねない。そのため、ここでは接触点分割部２６によって接触点または接触線で分割領域をさらに分割する。
【００７９】
図１３は、接触点分割部２６による分割処理の一例を示す流れ図である。この処理は、処理結果として得られている各領域について、それぞれを処理対象として行う。Ｓ８１において、処理対象の領域は接触点あるいは接触線を含むか否かを判定し、含まなければその処理対象の領域に対する接触点分割部２６の処理は終了する。
【００８０】
接触点あるいは接触線を含んでいる場合には、Ｓ８２において、処理対象の領域の境界線上の点ｐを特定する。この点ｐは任意に特定すればよいが、ここではｘ座標の値が最小となる点を点ｐとする。
【００８１】
Ｓ８３において、処理対象の領域の境界線上にある接触点のうち、点ｐを挟む接触点を点ａ（１）、点ａ（２）とし、この点ａ（１）から点ａ（２）の方向に処理対象の領域の境界線をたどって接触点に番号を付与し、番号ｉにより特定される接触点を点ａ（ｉ）とする。接触点では、境界線をたどると行きと帰りで２回の番号付けがなされることになる。なお、接触線では、その始点と終点を接触点とする。
【００８２】
Ｓ８４において、変数ｉを１に初期化し、Ｓ８５において、点ａ（ｉ）と次の点ａ（ｉ＋１）とが１つの接触点に番号付けしたものであるか否かを判定する。１つの接触点に番号付けした点である場合には、Ｓ８６において、点ａ（ｉ）から点ａ（ｉ＋１）までにより境界線が構成される領域を１つの分割領域とする。
【００８３】
また、点ａ（ｉ）と点ａ（ｉ＋１）が異なる接触点のものである場合には、Ｓ８７において、点ａ（ｉ）から点ａ（ｉ＋１）までと、１つの接触点に点ａ（ｉ＋１）とともに付与されている番号を有する点ａ（ｔ）から次の点ａ（ｔ＋１）までにより境界線が構成される領域を１つの分割領域とする。なお、接触線の部分については分割領域とはしない。
【００８４】
Ｓ８６あるいはＳ８７の処理の後、Ｓ８８において、点ａ（ｉ）と次の点ａ（ｉ＋１）とが１つの接触点に番号付けしたものとの判定が２回行われたか否かを判定し、２回行われた場合には処理を終了する。０回または１回であればＳ８９において、変数ｉに１を加えてＳ８５へ戻り、次の点についての処理を行う。
【００８５】
図１４は、接触点における分割処理の具体例の説明図である。例えば図１４（Ａ）に示すような閉領域Ａ及び閉領域Ｂが与えられた場合には、領域分割部２５によって図１４（Ｂ）に示すような分割領域ａ，ｂ，ｃ，ｄが得られる。このうち分割領域ａは接触点を有している。そのため、接触点分割部２６によって図１４（Ｃ）に示すように分割領域ａを分割領域ｅ，ｆに分割する。
【００８６】
図１５は、接触点における分割処理の別の具体例の説明図である。図１４では接触点を有する簡単な例を示したが、図１３に示す処理では、より複雑な例に対応している。図１５（Ａ）に示した分割領域の例では、接触点が２つと接触線が１つ含まれている。このような場合に、図１３の処理に従いＳ８２で点ｐを特定し、Ｓ８３で各接触点に番号を付与してゆく。これによって図１５（Ｂ）に示すように点ｐ及び各点ａ（ｉ）（ｉ＝１，…，８）が得られる。
【００８７】
まずｉ＝１とし、点ａ（１）と点ａ（２）は１つの接触点に対して番号が付与された点であるから、Ｓ８６において、点ａ（１）から点ａ（２）へ至る境界線で構成される領域を１つの分割領域とする。これを図１５（Ｃ）に示している。
【００８８】
次にｉ＝２とし、点ａ（２）と点ａ（３）を参照すると、異なる接触点であるので、Ｓ８７において、点（２）から点ａ（３）までと、１つの接触点に点ａ（３）とともに付与されている番号を有する点ａ（８）から次の点ａ（１）までにより境界線が構成される領域を１つの分割領域とする。これを図１５（Ｄ）に示している。
【００８９】
さらにｉ＝３とし、点ａ（３）と点ａ（４）を参照すると、異なる接触点であるので、Ｓ８７における処理を行うが、この部分は接触線の部分であるので分割領域とはせずに次に進む。
【００９０】
ｉ＝４とし、点ａ（４）と点ａ（５）を参照すると、異なる接触点であるので、Ｓ８７において、点（４）から点ａ（５）までと、１つの接触点に点ａ（５）とともに付与されている番号を有する点ａ（６）から次の点ａ（７）までにより境界線が構成される領域を１つの分割領域とする。これを図１５（Ｅ）に示している。
【００９１】
ｉ＝５として点ａ（５）と点ａ（６）を参照すると、点ａ（５）と点ａ（６）は１つの接触点に対して番号が付与された点であるから、Ｓ８６において、点ａ（５）から点ａ（６）へ至る境界線で構成される領域を１つの分割領域とする。これを図１５（Ｆ）に示している。
【００９２】
このｉ＝５において、点ａ（ｉ）と次の点ａ（ｉ＋１）とが１つの接触点に番号付けしたものとの判定が２回（ｉ＝１とｉ＝５の場合）行われたので、これで接触点に関する分割処理を終える。この処理によって、図１５（Ａ）に示した接触点及び接触線を含む分割領域は、図１５（Ｃ）、（Ｄ）、（Ｅ）、（Ｆ）に示した４つの領域に分割される。
【００９３】
上述のように、この接触点及び接触線における分割処理は行わなくてもよい。あるいは、分割する代わりに接触点及び接触線で接触しないように境界線を構成することも可能である。すなわち、接触点を微少な距離だけ離した複数の点で近似したり、接触線を微少な間隔を有する複数の線で近似すればよい。
【００９４】
あるいは、交点検出部２１で交点を検出する際に、１つの接触点を微少な間隔を有する２つの交点として登録し、また接触線については両端を交点として登録すれば、領域分割部２５において接触点の部分で分割された分割領域が得られる。なお、この場合には接触点を２つ交点としたことにより微少な分割領域が生成されるが、この微少な分割領域は後で削除すればよい。
【００９５】
図１６は、本発明の各実施の形態の機能をコンピュータプログラムで実現した場合におけるコンピュータプログラム及びそのコンピュータプログラムを格納した記憶媒体とコンピュータの一例の説明図である。図中、１０１はプログラム、１０２はコンピュータ、１１１は光磁気ディスク、１１２は光ディスク、１１３は磁気ディスク、１１４はメモリ、１２１はＣＰＵ、１２２は内部メモリ、１２３は読取部、１２４はハードディスク、１２５はインタフェース、１２６は通信部である。
【００９６】
上述の本発明の各実施の形態で説明した各部の機能の一部または全部を、コンピュータにより実行可能なプログラム１０１によって実現してもよい。その場合、そのプログラム１０１およびそのプログラムが用いるデータなどは、コンピュータが読み取り可能な記憶媒体に記憶させておいてもよい。記憶媒体とは、コンピュータのハードウェア資源に備えられている読取部１２３に対して、プログラムの記述内容に応じて、磁気、光、電気等のエネルギーの変化状態を引き起こして、それに対応する信号の形式で、読取部１２３にプログラムの記述内容を伝達できるものである。例えば、光磁気ディスク１１１，光ディスク１１２（ＣＤやＤＶＤなどを含む）、磁気ディスク１１３，メモリ１１４（ＩＣカード、メモリカードなどを含む）等である。もちろんこれらの記憶媒体は、可搬型に限られるものではない。
【００９７】
これらの記憶媒体にプログラム１０１を格納しておき、例えばコンピュータ１０２の読取部１２３あるいはインタフェース１２５にこれらの記憶媒体を装着することによって、コンピュータからプログラム１０１を読み出し、内部メモリ１２２またはハードディスク１２４に記憶し、ＣＰＵ１２１によってプログラム１０１を実行することによって、各実施の形態で説明した機能が実現される。あるいは、ネットワークなどを介してプログラム１０１をコンピュータ１０２に転送し、コンピュータ１０２では通信部１２６でプログラム１０１を受信して内部メモリ１２２またはハードディスク１２４に記憶し、ＣＰＵ１２１によってプログラム１０１を実行することによって、各実施の形態で説明した機能を実現してもよい。なお、コンピュータ１０２には、このほかインタフェース１２５を介して様々な装置と接続してもよい。また、例えば記憶部１１はハードディスク１２４や内部メモリ１２２により構成すればよい。
【００９８】
もちろん、一部の機能についてハードウェアによって構成してもよいし、すべてをハードウェアで構成してもよい。あるいは、他の構成とともに本発明も含めたプログラムとして構成してもよい。例えば描画処理を行うプログラムとともに構成し、画像形成装置や表示装置に対して描画した画像を出力するように構成してもよい。もちろん、他の用途に適用する場合には、その用途におけるプログラムと一体化してもよい。
【図面の簡単な説明】
【００９９】
【図１】本発明の第１の実施の形態を示すブロック図である。
【図２】本発明の第１の実施の形態における動作の一例を示す流れ図である。
【図３】領域種別の一例の説明図である。
【図４】本発明の第１の実施の形態における動作の具体例の説明図である。
【図５】分割領域境界線情報の変化の一例の説明図である。
【図６】分割領域境界線情報の変化の一例の説明図（続き）である。
【図７】本発明の第２の実施の形態を示すブロック図である。
【図８】交点検出部による交点検出処理の一例を示す流れ図である。
【図９】包含処理部における包含処理の一例を示す流れ図である。
【図１０】包含処理部における包含処理の具体例の説明図である。
【図１１】回転方向判定部における回転方向の判定処理の一例を示す流れ図である。
【図１２】回転方向判定部における回転方向の判定処理の具体例の説明図である。
【図１３】回転方向判定部における回転方向の判定処理の具体例の説明図である。
【図１４】接触点における分割処理の具体例の説明図である。
【図１５】接触点における分割処理の別の具体例の説明図である。
【図１６】本発明の各実施の形態の機能をコンピュータプログラムで実現した場合におけるコンピュータプログラム及びそのコンピュータプログラムを格納した記憶媒体とコンピュータの一例の説明図である。
【図１７】領域分割の一例の説明図である。
【符号の説明】
【０１００】
１１…記憶部、１２…読出部、１３…領域断片取得部、１４…判定部、１５…登録部、２１…交点検出部、２２…交点判定部、２３…包含処理部、２４…回転方向判定部、２５…領域分割部、２６…接触点分割部、１０１…プログラム、１０２…コンピュータ、１１１…光磁気ディスク、１１２…光ディスク、１１３…磁気ディスク、１１４…メモリ、１２１…ＣＰＵ、１２２…内部メモリ、１２３…読取部、１２４…ハードディスク、１２５…インタフェース、１２６…通信部。
【技術分野】
【０００１】
本発明は、領域分割装置及び領域分割プログラムに関するものである。
【背景技術】
【０００２】
従来より画像処理分野においては、処理領域を分割する領域分割処理がしばしば用いられる。特に、それぞれが重なる処理領域に対して処理を行う場合があり、このような場合には重なり方の関係に従って各処理領域を分割することが行われている。図１７は、領域分割の一例の説明図である。例えば図１７（Ａ）に示すように実線で示した領域Ａと、領域Ａよりも太い線で示した領域Ｂとが重なり合っている場合を考える。この場合、図１７（Ｂ）に示すように、重ならない各領域に分割する。図１７（Ａ）において、Ａｃは領域Ａ外を示し、Ｂｃは領域Ｂ外を示している。すなわち、Ａ∩Ｂは領域Ａと領域Ｂが重なっていた分割領域、Ａ∩Ｂｃは領域Ａ内であるが領域Ｂ外の分割領域、Ａｃ∩Ｂは領域Ｂ内であるが領域Ａ外の分割領域、Ａｃ∩Ｂｃは領域Ａにも領域Ｂにも含まれない領域を示している。図１７（Ｂ）においては、領域Ａにも領域Ｂにも含まれない領域については示していない。
【０００３】
このような領域分割を必要とする処理の一例としては、特許文献１に記載されているように複数の図形を一部重ねて半透明処理により描画する場合が挙げられる。例えば図形１と図形２を描画する際に、図形１のうち図形２と重ならない部分（図１７（Ｂ）におけるＡ∩Ｂｃの領域に対応）と、図形２のうち図形１と重ならない部分（図１７（Ｂ）におけるＡｃ∩Ｂの領域に対応）については、図形１及び図形２の描画をそのまま行えばよい。図形１と図形２が重なる部分（例えば図１７（Ｂ）におけるＡ∩Ｂの領域に対応）については、両者を考慮した描画処理が必要となる。そのため、図形１のうち図形２と重ならない部分と、図形２のうち図形１と重ならない部分と、図形１と図形２が重なる部分とに領域を分割し、それぞれの領域についての描画処理を行っている。もちろん、このほかにも領域分割が必要な場合は多い。
【０００４】
このような複数の図形が重なりを持つ場合に、それぞれ重ならない領域へ分割する一つの方法として、２重連結辺リストを用いた平面走査方式がある。この方法では、複数の図形の境界線となる辺をそれぞれ線分とし、ある特定の方向に走査して線分との交点をもとに線分同士の交点を求める。この交点で線分を分割するとともに、交点を中心に例えば時計回りで隣接する線分を結合してゆく。結合の際に、一方の線分については交点へ向かう方向の線分ベクトルとし、もう一方は交点を始点とする方向の線分ベクトルとする。分割した各線分は２回ずつ用いられ、方向が異なる２つの線分ベクトルとして別々の線分ベクトルと結合されることになる。得られた連結された線分ベクトルにより囲まれた領域が、分割された領域を示すことになる。
【０００５】
【特許文献１】特開平１１−３２７５３４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明は、従来の方法に比べて簡単に、重なりを持つ複数の領域を重ならない領域へ分割することができる領域分割装置及び領域分割プログラムを提供することを目的とするものである。
【課題を解決するための手段】
【０００７】
本願請求項１に記載の発明は、第１の閉領域の境界線の情報を記憶する第１の記憶手段と、前記第１の閉領域と境界線が交差する第２の閉領域の境界線の情報を記憶する第２の記憶手段と、分割領域の境界線の情報を記憶する第３の記憶手段と、前記第１の記憶手段から前記第２の閉領域との交点を所定の方向に前記第１の閉領域を周回するまで順に基点として読み出す読出手段と、前記読出手段で読み出した基点から前記第１の閉領域の境界線を所定の方向にたどって次の第２の閉領域の境界線との交点である第１の交点から第２の閉領域の境界線を時計方向と反時計方向にたどってそれぞれ基点から第１の交点を通り第２の交点を終点とする領域断片と基点から第１の交点を通り第３の交点を終点とする領域断片をそれぞれ求める領域断片取得手段と、前記領域断片取得手段で求めた２つの領域断片について前記領域断片の始点が前記第３の記憶手段に記憶されている分割領域の境界線のその時点での終点として登録されているか否か及び登録されている場合に該登録されている分割領域の境界線をたどった方向と前記領域断片が前記第２の閉領域をたどった方向が同じか否かを判定する判定手段と、前記判定手段によって基点が既に登録されていると判定され領域断片がたどった方向が分割領域の境界線がたどった方向であると判定された場合には該登録されている分割領域の境界線として前記領域断片を追加しそのほかの場合には前記領域断片を新たな分割領域の境界線として前記第３の記憶手段に登録する登録手段を有することを特徴とする領域分割装置である。
【０００８】
本願請求項２に記載の発明は、請求項１に記載の領域分割装置の前記登録手段が、前記領域断片を新たな分割領域の境界線として前記第３の記憶手段に登録する際に、前記領域断片の基点から第１の交点までの前記第１の閉領域の境界線が前記第２の閉領域の内部か否か及び第１の交点から前記第２の閉領域の境界線をたどった方向により、当該分割領域が前記第１の閉領域と前記第２の閉領域との集合演算により定められる領域のいずれに属するかを示す領域種別を決定し、該領域種別を前記新たな分割領域に付加して登録することを特徴とする領域分割装置である。
【０００９】
本願請求項３に記載の発明は、請求項１または請求項２に記載の領域分割装置の構成に加えて、さらに、前記第１の閉領域と前記第２の閉領域の交点を検出して前記第１の記憶手段及び第２の記憶手段に境界線の情報として記憶させる交点検出手段を有することを特徴とする領域分割装置である。
【００１０】
本願請求項４に記載の発明は、請求項１ないし請求項３のいずれか１項に記載の領域分割装置の構成に加えて、さらに、前記第１の閉領域と前記第２の閉領域が交点を有するか否かを判定する交点判定手段と、前記交点判定手段が交点を有しないと判定した場合に包含処理を行う包含処理手段を有し、前記判定手段が交点を有すると判定した場合に前記読出手段、領域断片取得手段、判定手段、登録手段による処理を行い、前記包含処理手段は、前記第１の閉領域と前記第２の閉領域に重なりがない場合には前記第１の閉領域及び前記第２の閉領域を処理結果とし、一方の閉領域が内部に他方の閉領域を包含する場合には、前記一方の閉領域の前記他方の閉領域を除く領域を分割して、分割した各領域と前記他方の閉領域を処理結果とすることを特徴とする領域分割装置である。
【００１１】
本願請求項５に記載の発明は、請求項１ないし請求項４のいずれか１項に記載の領域分割装置の構成に加えて、さらに、前記第３の記憶手段に登録された分割領域が接触点または接触線を含む場合に接触する点で分割領域を分割する接触点分割手段をさらに有することを特徴とする領域分割装置である。
【００１２】
本願請求項６に記載の発明は、請求項１ないし請求項４のいずれか１項に記載の領域分割装置の構成に加えて、さらに、前記第１の閉領域と前記第２の閉領域が接触点を有する場合に２つの交点となるように前記第１の記憶手段に記憶されている前記第１の閉領域の境界線の情報または前記第２の記憶手段に記憶されている前記第２の閉領域の境界線の情報を変更する変更手段を有することを特徴とする領域分割装置である。
【００１３】
本願請求項７に記載の発明は、コンピュータに、請求項１ないし請求項６のいずれか１項に記載の領域分割装置の機能を実行させることを特徴とする領域分割プログラムである。
【発明の効果】
【００１４】
本願請求項１に記載の発明によれば、本発明の構成を用いない場合に比べて、簡単に、重なりを持つ複数の領域を、重なりのない複数の領域へ分割することができる。
【００１５】
本願請求項２に記載の発明によれば、分割した各領域に対して第１の閉領域と第２の閉領域との集合演算により定められる領域のいずれに属するかを示す領域種別を簡単に付与することができる。
【００１６】
本願請求項３に記載の発明によれば、本構成を有しない場合に比べて処理を高速化することができる。
【００１７】
本願請求項４に記載の発明によれば、一方の閉領域が他方の閉領域に含まれている場合でも領域の分割を行うことができ、両者の重なりがない場合についても対応することができる。
【００１８】
本願請求項５及び請求項６に記載の発明によれば、２つの閉領域の境界が接している場合についても、重なりのない複数の領域へ分割することができる。
【００１９】
本願請求項７に記載の発明は、本願請求項１ないし請求項６のいずれか１項に記載の発明の効果と同等の効果を得ることができる。
【発明を実施するための最良の形態】
【００２０】
図１は、本発明の第１の実施の形態を示すブロック図である。図中、１１は記憶部、１２は読出部、１３は領域断片取得部、１４は判定部、１５は登録部である。ここでは、第１の閉領域Ａと第２の閉領域Ｂとが重なりを有している場合に、閉領域Ａと閉領域Ｂとの集合演算により定められる領域、すなわち、閉領域Ａと閉領域Ｂの両方に含まれる領域、閉領域Ａには含まれるが閉領域Ｂには含まれない領域、閉領域Ｂには含まれるが閉領域Ａには含まれない領域に、それぞれが重ならないように分割する。３以上の閉領域が重なる場合には、２つの閉領域について分割した後、分割した各領域と別の閉領域との重なりをもとに分割処理を行ってゆけばよい。従って、２つの閉領域についての説明を行う。
【００２１】
なお、閉領域Ａと閉領域Ｂの一方が他方に完全に包含されることはないものとする。また、各閉領域の境界線がそれぞれ自分自身と途中で交差したり、内部に当該閉領域に含まれない領域が存在していないものとする。さらに、閉領域Ａと閉領域Ｂの境界線が接する箇所はないものとする。これらの場合のいくつかについての対処は、別の実施の形態で述べる。
【００２２】
記憶部１１は、閉領域Ａと閉領域Ｂの境界線の情報と、分割領域の境界線の情報を記憶する。各領域の境界線の情報は、境界線上のいくつかの点の情報により与えられる。点の間は、例えば直線や曲線で結ばれて境界線を構成する。なお、閉領域Ａ及び閉領域Ｂの境界線の情報として、両者の境界線の交点の情報が与えられていると、後述するように境界線をたどって次の交点を見つける際に有用である。
【００２３】
読出部１２は、記憶部１１から閉領域Ａまたは閉領域Ｂのいずれか一方について、交点を所定の方向に周回するまで順に基点として読み出し、領域断片取得部１３に渡す。ここでは閉領域Ａについて、交点を時計回り方向に順に読み出して基点とする。最初の基点としては、ここでは閉領域Ｂ外に存在する閉領域Ａの境界線が、閉領域Ｂと交差する２つの交点のうちの一方とする。このとき、他方の交点が、一方の交点から時計回り方向に存在する交点となるようにする。なお、確実にこのような条件を満たす最初の交点を見つけるため、例えば２つの閉領域のうち、特定の軸に関する座標値が最小あるいは最大となる点を特定し、その点を有する閉領域を閉領域Ａ、もう一方の閉領域を閉領域Ｂとし、特定した点から閉領域Ａの境界線を反時計回り方向にたどって得られる閉領域Ｂとの交点を最初の基点とすればよい。もちろん、この方法に限らず、最初の基点を決定してもよい。
【００２４】
領域断片取得部１３は、読出部１２で読み出した基点から、ここでは閉領域Ａの境界線を所定の方向にたどって次の第２の閉領域の境界線との交点である第１の交点を求め、さらにその第１の交点から閉領域Ｂの境界線を時計回り方向と反時計回り方向にたどって、それぞれ基点から第１の交点を通り第２の交点を終点とする領域断片と、基点から第１の交点を通り第３の交点を終点とする領域断片をそれぞれ求める。
【００２５】
判定部１４は、領域断片取得部１３で求めた２つの領域断片について、領域断片の始点が記憶部１１に分割領域境界線情報として記憶されている分割領域の境界線のその時点での終点として登録されているか否か、及び、登録されている場合には、その登録されている分割領域の境界線をたどった方向と、領域断片が閉領域Ｂをたどった方向が同じか否かを判定する。
【００２６】
登録部１５は、判定部１４によって領域断片の始点が既に登録されていると判定され、領域断片が閉領域Ｂをたどった方向が分割領域の境界線がたどった方向であると判定された場合には、その登録されている分割領域の境界線として、分割領域境界線情報に領域断片を追加する。また、そのほかの場合には、領域断片を新たな分割領域の境界線として、分割領域境界線情報を記憶部１１に登録する。新たな分割領域の登録を行う際には、当該分割領域が閉領域Ａと閉領域Ｂとの集合演算により定められる領域のいずれに属するかを示す領域種別を付加する。この領域種別は、当該分割領域が閉領域Ａ及び閉領域Ｂの両方に含まれるのか、閉領域Ａに含まれるが閉領域Ｂには含まれないのか、閉領域Ｂに含まれるが閉領域Ａには含まれないのか、あるいは閉領域Ａにも閉領域Ｂにも含まれないのかを示すものである。付加する領域種別の決定は、分割領域の境界線として登録する領域断片の基点から第１の交点までの閉領域Ａの境界線が閉領域Ｂの内部か否か、及び、第１の交点から閉領域Ｂの境界線をたどった方向により決定される。
【００２７】
図２は、本発明の第１の実施の形態における動作の一例を示す流れ図である。なお、予め閉領域Ａ境界線情報及び閉領域Ｂ境界線情報が記憶部１１に記憶されているものとする。また、閉領域Ａ境界線情報及び閉領域Ｂ境界線情報には、互いの交点が予め検出されているものとする。ここでは交点をａ（ｉ）とする。上述のように、交点ａ（ｉ）は閉領域Ａの時計回り方向に順に存在するものとする。また、最初の基点となる交点ａ（１）は、例えば２つの閉領域のうち、座標値が最小あるいは最大となる点を特定し、その点を有する閉領域を閉領域Ａ、もう一方の閉領域を閉領域Ｂとし、特定した点から閉領域Ａの境界線を反時計回り方向にたどって得られる閉領域Ｂとの交点をａ（１）とすればよい。ここではこの交点ａ（１）から次の交点ａ（２）までの閉領域Ａの境界線は閉領域Ｂの外部であるものとする。
【００２８】
Ｓ３１において、基点となる交点を指定する変数ｉを１とし、交点ａ（１）を最初の基点とする。読出部１２は、この交点ａ（１）の情報を記憶部１１から読み出して領域断片取得部１３に渡す。
【００２９】
Ｓ３２において、領域断片取得部１３は基点ａ（ｉ）から閉領域Ａの境界線を時計回り方向にたどって次の第２の閉領域の境界線との交点である第１の交点を求める。上述のように交点の情報が境界線情報として予め記憶されていれば、次の交点の情報は簡単に取得される。すなわち、基点ａ（ｉ）の次の交点である第１の交点は、交点ａ（ｉ＋１）である。さらに領域断片取得部１３は、その第１の交点ａ（ｉ＋１）から閉領域Ｂの境界線を時計回り方向と反時計回り方向にたどって、２つの領域断片を求める。基点から第１の交点を通り時計回り方向に閉領域Ｂの境界線をたどった領域断片をＣＲ（ｉ）、基点から第１の交点を通り反時計回り方向に閉領域Ｂの境界線をたどった領域断片をＣＬ（ｉ）とする。
【００３０】
Ｓ３３において、領域断片ＣＲ（ｉ）、ＣＬ（ｉ）の始点である基点ａ（ｉ）が、分割領域の境界線のここまでの処理における終点として登録されているか否か、及び、登録されている場合にはその分割領域の境界線が閉領域Ｂをたどっている方向と領域断片が閉領域Ｂをたどっている方向が一致するか否かを判定部１４で判定する。この条件を満たす領域断片については、Ｓ３４において、登録部１５は登録済みの分割領域の境界線の終点の後に、条件を満たす領域断片を追加して登録する。これにより、当該分割領域の終点は、追加された領域断片の終点である第２または第３の交点となるか、あるいは分割領域として境界線が周回する。
【００３１】
Ｓ３３の条件を満たさない場合には２つの領域断片について、あるいは一方の領域断片は条件を満たしてＳ３４の処理を行った場合の他方の領域断片については、Ｓ３５において登録部１５は新たな分割領域の境界線の一部として各領域断片を新規登録する。登録の際には、対応する領域種別を付加する。
【００３２】
図３は、領域種別の一例の説明図である。図３において、Ａｃは閉領域Ａ外を示し、Ｂｃは閉領域Ｂ外を示している。すなわち、Ａ∩Ｂは閉領域Ａと閉領域Ｂの両方に含まれることを示し、Ａ∩Ｂｃは閉領域Ａ内であるが閉領域Ｂ外であることを示し、Ａｃ∩Ｂは閉領域Ｂ内であるが閉領域Ａ外であることを示し、Ａｃ∩Ｂｃは閉領域Ａにも閉領域Ｂにも含まれないことを示している。
【００３３】
上述のように交点ａ（１）からａ（２）までの閉領域Ａの境界線が閉領域Ｂの外部であり、時計回り方向に閉領域Ａの交点をたどって順に基点とする場合には、変数ｉの値と領域断片がＣＬ（ｉ）かＣＲ（ｉ）かにより、図３に示すような領域種別を付加する。すなわち、変数ｉが奇数のときの領域断片ＣＬ（ｉ）については、閉領域Ａに含まれるが閉領域Ｂには含まれない（Ａ∩Ｂｃ）領域種別を付加し、領域断片ＣＲ（ｉ）については、閉領域Ａにも閉領域Ｂにも含まれない（Ａｃ∩Ｂｃ）領域種別を付加する。また、変数ｉが偶数のときの領域断片ＣＬ（ｉ）については、閉領域Ｂに含まれるが閉領域Ａには含まれない（Ａｃ∩Ｂ）領域種別を付加し、領域断片ＣＲ（ｉ）については、閉領域Ａと閉領域Ｂの両方に含まれる（Ａ∩Ｂ）領域種別を付加する。
【００３４】
ここでは交点ａ（１）からａ（２）までの閉領域Ａの境界線が閉領域Ｂの外部であるとしていることから、変数ｉが奇数であれば閉領域Ｂ外であり、変数ｉが偶数であれば、閉領域Ｂ内であると判定すればよい。これは、交点を通過すれば閉領域Ｂの内外が反転するからである。もちろん、最初の交点ａ（１）が閉領域Ｂの内部であれば変数ｉの値によって付加する領域種別は変わるし、閉領域Ａの交点をたどる方向が違う場合も、付加する領域種別は変わる。しかし、これらの条件が決まれば、閉領域Ｂの内外と領域断片がＣＬ（ｉ）かＣＲ（ｉ）かによって付加する領域種別は決定される。
【００３５】
図２に戻り、Ｓ３６において、読出部１２は次の交点ａ（ｉ＋１）が最初の基点ａ（１）であるか否かを判定し、交点ａ（ｉ＋１）が交点ａ（１）でない場合には、Ｓ３７において変数ｉを１だけ増加させ、次の交点ａ（ｉ）を基点として領域断片取得部１３に渡し、Ｓ３２へ戻って処理を続ける。
【００３６】
このような処理を繰り返して行い、Ｓ３６で交点ａ（ｉ＋１）が交点ａ（１）である場合には周回したものとして処理を終える。これまでの処理によって、分割領域の境界線の情報が記憶部１１に分割領域境界線情報として登録されている。また、各分割領域には分割前の閉領域Ａ，Ｂとの集合演算により定められる領域を示す領域種別が付加されている。例えば領域の重なりを考慮した描画処理を行う場合には、各分割領域について領域種別に従った描画処理を行えばよい。
【００３７】
図４は、本発明の第１の実施の形態における動作の具体例の説明図、図５、図６は、分割領域境界線情報の変化の一例の説明図である。図４において、閉領域Ａの境界線を実線で示し、閉領域Ｂの境界線を閉領域Ａの境界線よりも太い線で示している。また、ここでは最初の基点を得るため閉領域Ａの境界線上の点Ｐを求め、点Ｐから反時計回り方向に閉領域Ａの境界線をたっどって最初に現れる閉領域Ｂとの交点をａ（１）としている。この交点ａ（１）から閉領域Ａの境界線を時計回り方向にたどって出現する閉領域Ｂとの交点をそれぞれａ（２）〜ａ（６）としている。また、図５において時計回り方向をＲ、反時計回り方向をＬとして示している。
【００３８】
まず、交点ａ（１）を基点とする。そして、次の交点ａ（２）を第１の交点とし、この交点ａ（２）から閉領域Ｂを時計回り方向にたどって交点ａ（３）に至る領域断片ＣＲ（１）と、交点ａ（２）から閉領域Ｂを反時計回り方向にたどって交点ａ（５）に至る領域断片ＣＬ（１）を得る。まだ分割領域境界線情報は記憶部１１に記憶されていないので、登録部１５はこれらの領域断片ＣＲ（１）、ＣＬ（１）を新たな分割領域の境界線の一部として登録する。それぞれの新たな分割領域の領域種別は、図３に従って付与する。領域断片ＣＲ（１）を新たな分割領域の境界線の一部として登録した場合には領域種別としてＡｃ∩Ｂｃが、領域断片ＣＬ（１）を新たな分割領域の境界線の一部として登録した場合には領域種別としてＡ∩Ｂｃが、それぞれ付加される。ここまでで登録された分割領域境界線情報の一例を図５（Ａ）に示している。
【００３９】
次に交点ａ（２）を基点とする。そして、次の交点ａ（３）を第１の交点とし、この交点ａ（３）から閉領域Ｂを時計回り方向にたどって交点ａ（４）に至る領域断片ＣＲ（２）と、交点ａ（３）から閉領域Ｂを反時計回り方向にたどって交点ａ（２）に至る領域断片ＣＬ（２）を得る。基点である交点ａ（２）を終点とする分割領域境界線情報は記憶部１１に記憶されていないので、登録部１５はこれらの領域断片ＣＲ（２）、ＣＬ（２）を新たな分割領域の境界線の一部として登録する。領域断片ＣＲ（２）を新たな分割領域の境界線の一部として登録した場合には領域種別としてＡ∩Ｂが、領域断片ＣＬ（２）を新たな分割領域の境界線の一部として登録した場合には領域種別としてＡｃ∩Ｂが、それぞれ付加される。ここまでで登録された分割領域境界線情報の一例を図５（Ｂ）に示している。
【００４０】
次に交点ａ（３）を基点とする。そして、次の交点ａ（４）を第１の交点とし、この交点ａ（４）から閉領域Ｂを時計回り方向にたどって交点ａ（１）に至る領域断片ＣＲ（３）と、交点ａ（４）から閉領域Ｂを反時計回り方向にたどって交点ａ（３）に至る領域断片ＣＬ（３）を得る。図５（Ｂ）の１行目に示すように、基点である交点ａ（３）を終点とする分割領域境界線情報が記憶部１１に記憶されており、この方向は時計回り方向である。従って、領域断片ＣＲ（３）を１行目の分割領域境界線情報に追加する。これにより、図５（Ｃ）の１行目のようになる。また、領域断片ＣＬ（３）は方向が異なるので新たな分割領域の境界線の一部として登録する。領域種別は図３からＡ∩Ｂｃが付加される。ここまでで登録された分割領域境界線情報の一例を図５（Ｃ）に示している。
【００４１】
次に交点ａ（４）を基点とする。そして、次の交点ａ（５）を第１の交点とし、この交点ａ（５）から閉領域Ｂを時計回り方向にたどって交点ａ（２）に至る領域断片ＣＲ（４）と、交点ａ（５）から閉領域Ｂを反時計回り方向にたどって交点ａ（６）に至る領域断片ＣＬ（４）を得る。図５（Ｃ）の３行目に示すように、基点である交点ａ（４）を終点とする分割領域境界線情報が記憶部１１に記憶されており、この方向は時計回り方向である。従って、領域断片ＣＲ（４）を図５（Ｃ）の３行目の分割領域境界線情報に追加する。これにより、図５（Ｄ）の３行目のようになる。また、領域断片ＣＬ（４）は方向が異なるので新たな分割領域の境界線の一部として登録する。領域種別は図３からＡｃ∩Ｂが付加される。ここまでで登録された分割領域境界線情報の一例を図５（Ｄ）に示している。
【００４２】
次に交点ａ（５）を基点とする。そして、次の交点ａ（６）を第１の交点とし、この交点ａ（６）から閉領域Ｂを時計回り方向にたどって交点ａ（５）に至る領域断片ＣＲ（５）と、交点ａ（６）から閉領域Ｂを反時計回り方向にたどって交点ａ（１）に至る領域断片ＣＬ（５）を得る。図５（Ｄ）の２行目に示すように、基点である交点ａ（５）を終点とする分割領域境界線情報が記憶部１１に記憶されており、この方向は反時計回り方向である。従って、領域断片ＣＬ（５）を図５（Ｄ）の２行目の分割領域境界線情報に追加する。これにより、図６（Ａ）の２行目のようになる。また、領域断片ＣＲ（５）は方向が異なるので新たな分割領域の境界線の一部として登録する。領域種別は図３からＡｃ∩Ｂｃが付加される。ここまでで登録された分割領域境界線情報の一例を図６（Ａ）に示している。
【００４３】
次に交点ａ（６）を基点とする。そして、次の交点ａ（１）を第１の交点とし、この交点ａ（１）から閉領域Ｂを時計回り方向にたどって交点ａ（６）に至る領域断片ＣＲ（６）と、交点ａ（１）から閉領域Ｂを反時計回り方向にたどって交点ａ（４）に至る領域断片ＣＬ（６）を得る。図６（Ａ）の６行目に示すように、基点である交点ａ（６）を終点とする分割領域境界線情報が記憶部１１に記憶されており、この方向は反時計回り方向である。従って、領域断片ＣＬ（６）を図６（Ａ）の６行目の分割領域境界線情報に追加する。これにより、図６（Ｂ）の６行目のようになる。また、領域断片ＣＲ（６）は方向が異なるので新たな分割領域の境界線の一部として登録する。領域種別は図３からＡ∩Ｂが付加される。ここまでで登録された分割領域境界線情報の一例を図６（Ｂ）に示している。
【００４４】
次の交点は交点ａ（１）である。閉領域Ａを周回したので処理を終える。ここまでの処理で記憶部１１に記憶されている分割領域境界線情報は図６（Ｂ）に示されており、それぞれが分割領域である。また、各分割領域には閉領域Ａと閉領域Ｂとの集合演算により定められる領域を示す領域種別が付加されている。
【００４５】
図７は、本発明の第２の実施の形態を示すブロック図である。図中、２１は交点検出部、２２は交点判定部、２３は包含処理部、２４は回転方向判定部、２５は領域分割部、２６は接触点分割部である。この第２の実施の形態では、上述の第１の実施の形態で示した構成により領域分割の処理を実行するための前処理と、一方の閉領域が他方の閉領域の内部に含まれている場合の処理を追加したものである。
【００４６】
交点検出部２１は、閉領域Ａの境界線と閉領域Ｂの境界線の交点を検出して、その交点の情報を閉領域Ａ境界線情報及び閉領域Ｂ境界線情報として追加して記憶部１１に記憶させる。上述の第１の実施の形態における動作の一例の説明では、交点が閉領域Ａ境界線情報及び閉領域Ｂ境界線情報に含まれているものとして説明しているが、交点検出部２１はこの交点に関する情報を閉領域Ａ境界線情報及び閉領域Ｂ境界線情報に追加するものである。
【００４７】
交点判定部２２は、閉領域Ａと閉領域Ｂが交点を有するか否かを判定する。与えられた閉領域Ａと閉領域Ｂとは、例えば重なる部分がない場合あるいは一方が他方の内部に存在する場合には交点を有しない。交点判定部２２は、このような場合については後述する包含処理部２３により分割の処理を行わせるためのものである。この交点判定部２２が交点を有すると判定した場合に、領域分割部２５による上述の第１の実施の形態で説明した領域分割の処理を行う。
【００４８】
包含処理部２３は、交点判定部２２で閉領域Ａと閉領域Ｂが交点を有しないと判定した場合に、包含処理を行う。閉領域Ａと閉領域Ｂが交点を有しない場合としては、閉領域Ａと閉領域Ｂに重なりがない場合と、いずれか一方の閉領域が内部に他方の閉領域を包含する場合である。閉領域Ａと閉領域Ｂに重なりがない場合には、領域を分割する必要がないので、閉領域Ａおよび閉領域Ｂのデータをそのまま処理結果とすればよい。一方の閉領域が内部に他方の閉領域を包含する場合には、一方の閉領域の他方の閉領域を除く領域を分割して、分割した各領域と他方の閉領域を処理結果とする。なお、包含処理部２３で処理する場合には領域分割部２５による分割処理は行わず、処理を効率化する。
【００４９】
回転方向判定部２４は、閉領域Ａおよび閉領域Ｂの境界線を示す点列が時計回り方向に並べられているのか、あるいは反時計回り方向に並べられているのかを判定する。第１の実施の形態における動作の一例でも説明したように、いずれの方向に境界線をたどるかによって、新たに部分領域を登録する際に付加する領域種別が異なってくる。そのため、この回転方向判定部２４において閉領域Ａおよび閉領域Ｂの回転方向を判定しておく。あるいはさらに、所定の方向、例えば時計回り方向となるように点列を並べ直しておけばよい。
【００５０】
領域分割部２５は、上述の第１の実施の形態で示した読出部１２、領域断片取得部１３、判定部１４、登録部１５を有し、領域分割処理を行う。
【００５１】
接触点分割部２６は、領域分割部２５で領域分割処理を行ったことにより得られた記憶部１１に分割領域境界線情報として記憶されている各分割領域について、境界線が接触点または接触線を含む場合に、接触する点で分割領域をさらに分割する。あるいは、接触点または接触線を微少な距離だけ離した点または線を設定し、分割領域が接触点または接触線を含まないように変更してもよい。
【００５２】
本発明の第２の実施の形態における動作の一例について説明してゆく。閉領域Ａおよび閉領域Ｂの境界線を示す点列のデータが与えられると、このデータを閉領域Ａ境界線情報および閉領域Ｂ境界線情報として記憶部１１に記憶する。ここでは閉領域Ａ境界線情報の一例として、例えば境界線上のｎ番目の点について、その点の参照用座標ＰＸＡ０（ｎ）、ＰＹＡ０（ｎ）、その点が交点かそれ以外の点かを示すフラグＶＴＡ（ｎ）、交点の場合には閉領域Ｂの点と対応づける情報ＶＮＡ（ｎ）などを含んでいるものとする。閉領域Ｂ境界線情報についても、例えば境界線上のｎ番目の点について、その点の参照用座標ＰＸＢ０（ｎ）、ＰＹＢ０（ｎ）、その点が交点かそれ以外の点かを示す情報ＶＴＢ（ｎ）、交点の場合には閉領域Ａの点と対応づける情報ＶＮＢ（ｎ）などを含んでいるものとする。
【００５３】
図８は、交点検出部による交点検出処理の一例を示す流れ図である。ここでは、閉領域Ａの境界線上の点列としてｎＡ個の点が与えられ、また閉領域Ｂの境界線上の点列としてｎＢ個の点が与えられているものとする。つまり、ＰＸＡ０（ｎ）、ＰＹＡ０（ｎ）（ｎ＝０，…，ｎＡ−１）及び、ＰＸＢ０（ｎ）、ＰＹＢ０（ｎ）（ｎ＝０，…，ｎＢ−１）が与えられているとする。これらの与えられた参照用座標をもとに、交点を加えてゆくための更新用座標ＰＸＡ（ｎ）、ＰＹＡ（ｎ）及び更新用座標ＰＸＢ（ｎ）、ＰＹＢ（ｎ）を用いる。なお、処理前はＶＴＡ（ｎ）、ＶＴＢ（ｎ）は交点以外を示す情報が設定され、ＶＮＡ（ｎ）、ＶＮＢ（ｎ）には情報が設定されていない状態になっているものとし、交点の追加などにより更新用座標ＰＸＡ（ｎ）、ＰＹＡ（ｎ）及び更新用座標ＰＸＢ（ｎ）、ＰＹＢ（ｎ）を更新するのに合わせて、ＶＴＡ（ｎ）、ＶＮＡ（ｎ）、ＶＴＢ（ｎ），ＶＮＢ（ｎ）も更新してゆくものとする。
【００５４】
Ｓ４１において、閉領域Ａの点列を選択するための変数ｎを初期値０に設定する。また、ｎＡ０＝ｎＡ、ｎＢ０＝ｎＢとしてｎＡとｎＢの値をｎＡ０，ｎＢ０に退避しておく。さらに、
ＰＸＡ（ｉ）＝ＰＸＡ０（ｉ） （ｉ＝０，…，ｎＡ−１）
ＰＹＡ（ｉ）＝ＰＹＡ０（ｉ） （ｉ＝０，…，ｎＡ−１）
ＰＸＢ（ｉ）＝ＰＸＢ０（ｉ） （ｉ＝０，…，ｎＢ−１）
ＰＹＢ（ｉ）＝ＰＹＢ０（ｉ） （ｉ＝０，…，ｎＢ−１）
で更新用座標を初期化する。更にまた、閉領域Ａ上の点列更新用のカウンタｃＡを０で初期化し、閉領域Ｂ上の点列更新用のカウンタｃＢ（ｉ）をｃＢ（ｉ）＝１（ｉ＝０，…，ｎＢ−１）で初期化する。
【００５５】
Ｓ４２において、閉領域Ａの境界線上で変数ｎで示されるｎ番目の点（ＰＸＡ０（ｎ），ＰＹＡ０（ｎ））とｎ＋１番目の点（ＰＸＡ０（ｎ＋１），ＰＹＡ０（ｎ＋１））とをつなぐ線分Ｃと、閉領域Ｂの境界線を示す各線分、すなわちｍ＝０，…，ｎＢ０−１についてｍ番目の点（ＰＸＢ０（ｍ），ＰＹＢ０（ｍ））とｍ＋１番目の点（ＰＸＢ０（ｍ＋１），ＰＹＢ０（ｍ＋１））とをつなぐ線分Ｄｍとの交点を全て計算し、線分Ｃ上でｎ番目の点（ＰＸＡ０（ｎ），ＰＹＡ０（ｎ））に近い方から順に並べ替える。交点の数をｋ個とし、ｊ番目（ｊ＝１，…，ｋ）の交点の座標をＣＸ（ｊ）、ＣＹ（ｊ）とし、閉領域Ｂにおいて交点が得られた線分Ｄｍを特定するための情報をＣＮ（ｊ）＝ｍとする。
【００５６】
Ｓ４３において、Ｓ４２で交点が見つかったか否かを判定し、交点がない場合にはＳ５０に進み、交点がｋ個（ｋ≧１）ある場合にはＳ４４〜Ｓ４９の処理を行う。
【００５７】
Ｓ４４において、交点を特定する変数ｊを１に初期化した後、ｊ番目の交点についての境界線情報を追加すべく、Ｓ４５において閉領域Ａ境界線情報を更新し、Ｓ４６において閉領域Ｂ境界線情報を更新する。これらの閉領域Ａ境界線情報及び閉領域Ｂ境界線情報の更新のため、まず、線分Ｃ上でＰＸＡ０（ｎ）、ＰＹＡ０（ｎ）に近い側からｊ番目の交点が、それぞれ閉領域Ａ、Ｂの境界線上において現状で何番目の点であるかを示す変数ａと変数ｂを定める。具体的には、変数ａにはｃＡ＋ｊを、また変数ｂにはΣi=1CN(j)+1ｃＢ（ｉ）を設定する。なお、ａは閉領域Ａの境界線上で順に更新されていった番号でよいが、ｂは閉領域Ａの境界線との交わりが発見されるごとに追加されるため、上記のような和の形で定義される。ここで求める変数ｂの値は、閉領域Ｂにおいて１番目からＣＮ（ｊ）＋１番目までの、もともとの閉領域Ｂの点列の数と、既に得られている交点の数の合計値となる。これにより、当該交点が閉領域Ｂ上で他の交点を含めて何番目であるかがわかる。
【００５８】
更に、ｃＢ（ＣＮ（ｊ））＞１の場合、つまり、閉領域Ｂの境界線上で（ＰＸＢ０（ＣＮ（ｊ）），ＰＹＢ０（ＣＮ（ｊ）））と（ＰＸＢ０（ＣＮ（ｊ）＋１），ＰＹＢ０（ＣＮ（ｊ）＋１））との間の交点が既に登録されている場合には、ｊ番目の交点と既に登録されている交点が閉領域Ｂの境界線上でどの順番で現れるかによってｂの値を変動させる。具体的には、ｌ＝ｂとして、（ＰＸＢ０（ＣＮ（ｊ）），ＰＹＢ０（ＣＮ（ｊ）））と（ＰＸＢ（ｌ），ＰＹＢ（ｌ））との閉領域Ｂの境界線上での長さと、（ＰＸＢ０（ＣＮ（ｊ）），ＰＹＢ０（ＣＮ（ｊ）））と（ＣＸ（ｊ），ＣＹ（ｊ））との閉領域Ｂの境界線上での長さとを比較し、前者の長さが後者の長さより小さくなるまでｌから１を引いて再び比較を繰り返す。このようにして閉領域Ｂの境界線上でｂ番目の交点から交点を１つずつ戻りながら、閉領域Ｂの境界線上での交点が存在する位置（どの点の間にあるか）を特定する。その後に、ｂにｌ＋１を代入しなおす。
【００５９】
そしてＳ４５における閉領域Ａ境界線情報の更新においては、ａ番目以降の境界線の点列の情報を１つ分シフトするため、
ＰＸＡ（ｉ）＝ＰＸＡ（ｉ−１） （ｉ＝ａ＋１，…，ｎＡ＋ｊ）
ＰＹＡ（ｉ）＝ＰＹＡ（ｉ−１） （ｉ＝ａ＋１，…，ｎＡ＋ｊ）
ＶＴＡ（ｉ）＝ＶＴＡ（ｉ−１） （ｉ＝ａ＋１，…，ｎＡ＋ｊ）
ＶＮＡ（ｉ）＝ＶＮＡ（ｉ−１）＋ｐ （ｉ＝ａ＋１，…，ｎＡ＋ｊ）
を行う。ここでｐは、ＶＮＡ（ｉ−１）＜ｂならば０とし、ＶＮＡ（ｉ−１）≧ｂならば１とする。なお、後者は閉領域Ａの境界線上においてａ番目に新しい交点を加える際に、閉領域Ｂの境界線上でより後段側にある点の参照番号が１つ後ろにずれることを意味している。
【００６０】
そして、ａ番目に交点の情報を追加挿入する。すなわち、
ＰＸＡ（ａ）＝ＣＸ（ｊ）
ＰＹＡ（ａ）＝ＣＹ（ｊ）
ＶＴＡ（ａ）＝１（交点を示す）
ＶＮＡ（ａ）＝ｂ（閉領域Ｂのｂ番目の交点と対応することを示す）
を行う。更に、ｃＢ（ＣＮ（ｊ））に１を加える。
【００６１】
また、Ｓ４６における閉領域Ｂ境界線情報の更新においては、ｂ番目以降の境界線の点列の情報を１つ分シフトするため、
ＰＸＢ（ｉ）＝ＰＸＢ（ｉ−１） （ｉ＝ｂ＋１，…，ｎＢ＋ｊ）
ＰＹＢ（ｉ）＝ＰＹＢ（ｉ−１） （ｉ＝ｂ＋１，…，ｎＢ＋ｊ）
ＶＴＢ（ｉ）＝ＶＴＢ（ｉ−１） （ｉ＝ｂ＋１，…，ｎＢ＋ｊ）
ＶＮＢ（ｉ）＝ＶＮＢ（ｉ−１）＋ｐ （ｉ＝ｂ＋１，…，ｎＢ＋ｊ）
を行う。ここでｐは、ＶＮＢ（ｉ−１）＜ａならば０とし、ＶＮＢ（ｉ−１）≧ａならば１とする。なお、後者は閉領域Ｂの境界線上においてｂ番目に新しい交点を加える際に、閉領域Ａの境界線上でより後段側にある点の参照番号が１つ後ろにずれることを意味している。
【００６２】
そして、ｂ番目に交点の情報を追加挿入する。すなわち、
ＰＸＢ（ｂ）＝ＣＸ（ｊ）
ＰＹＢ（ｂ）＝ＣＹ（ｊ）
ＶＴＢ（ｂ）＝１（交点を示す）
ＶＮＢ（ｂ）＝ａ（閉領域Ａのａ番目の交点と対応することを示す）
を行う。これにより、１つの交点の情報が各境界線情報に追加される。
【００６３】
Ｓ４７において、変数ｊに１を加え、Ｓ４８において、ｊがｋを超えたか否かを判定する。変数ｊの値がｋを超えていなければ、未処理の交点が残っているのでＳ４５へ戻って次の交点を追加する処理を行う。変数ｊの値がｋを超えたら、交点の追加が終了しているのでＳ４９に進む。
【００６４】
Ｓ４９において、交点を加えたことによる点列の数の更新を行う。すなわち、ｎＡ及びｎＢにｋを加えるとともに、点列更新用のカウンタｃＡにｋ＋１を加える。
【００６５】
Ｓ５０において、変数ｎに１を加え、Ｓ５１において、閉領域Ａを周回したか否かを判定する。Ｓ５１の判定は、変数ｎの値がｎＡ０に達したか否かを判定すればよい。変数ｎの値がｎＡ０に達していなければ、Ｓ４２へ戻って閉領域Ａの境界線を構成する次の線分と閉領域Ｂとの交点を見つける処理を行う。変数ｎがｎＡ０に達していれば、閉領域Ａを周回したので、処理を終了する。この処理によって、閉領域Ａ境界線情報及び閉領域Ｂ境界線情報として、両者の交点を含めた点列の情報が記憶されることになる。
【００６６】
なお、閉領域Ａ及び閉領域Ｂの境界線は直線による折れ線で構成されていなくてもよく、例えばベジエ曲線などの曲線で構成されていてもよい。境界線が曲線で構成されている場合には、曲線間の近似交点を求めてもよいし、あるいは、曲線を直線による折れ線で近似して交点を求め、近似してもよい。
【００６７】
交点判定部２２では、上述の交点検出部２１による処理の際に、交点を検出したか否かを示す情報を受け取って、閉領域Ａと閉領域Ｂとが交点を有するか否かを判定すればよい。あるいは、記憶部１１に記憶されている閉領域Ａ境界線情報あるいは閉領域Ｂ境界線情報を順に読み出して交点として登録されている点があるか否かを判定してもよい。
【００６８】
交点判定部２２で交点がないと判定された場合には、領域分割部２５が分割処理を行わずに、処理が簡単な包含処理部２３による包含処理を行う。図９は、包含処理部における包含処理の一例を示す流れ図、図１０は、包含処理部における包含処理の具体例の説明図である。まずＳ６１において、閉領域Ａと閉領域Ｂとの包含関係を判定するため、ある特定の点を閉領域Ａ及び閉領域Ｂから求める。特定の点としては、例えば最小の点や最大の点などを求めるとよい。ここでは一例としてｘ座標が最小の点をそれぞれ求めることとし、閉領域Ａのｘ座標が最小の点をａ、閉領域Ｂのｘ座標が最小の点をｂとする。
【００６９】
Ｓ６２において、直線ｘ＝ａと閉領域Ｂとの交点が、直線ｘ＝ａにおいて点ａを挟んで両側に存在するか否かを判定する。両側に存在する場合には、閉領域Ｂが閉領域Ａを内部に含むことを示している。この場合には、Ｓ６３において、閉領域Ｂのうち閉領域Ａに含まれない部分を分割し、分割した複数の領域と閉領域Ａを処理結果とする。分割する位置は閉領域Ａの境界線を含むように分割するとよい。例えば直線ｘ＝ａあるいは直線ｘ＝ａ＋αで分割すると簡単である。
【００７０】
Ｓ６２で直線ｘ＝ａと閉領域Ｂの交点がない場合や、交点があっても点ａを挟むように存在しない場合には、さらにＳ６４において、直線ｘ＝ｂと閉領域Ａとの交点が、直線ｘ＝ｂにおいて点ｂを挟んで両側に存在するか否かを判定する。両側に存在する場合には、閉領域Ａが閉領域Ｂを内部に含むことを示している。この場合には、Ｓ６５において、閉領域Ａのうち閉領域Ｂに含まれない部分を分割し、分割した複数の領域と閉領域Ｂを処理結果とする。分割する位置は閉領域Ｂの境界線を含むように分割するとよい。例えば直線ｘ＝ｂあるいは直線ｘ＝ｂ＋αで分割すると簡単である。
【００７１】
Ｓ６４でも直線ｘ＝ｂと閉領域Ａの交点がない場合や、交点があっても点ｂを挟むように存在しない場合には、いずれか一方が他方を含む関係にはないものと判断できる。この場合には、閉領域Ａと閉領域Ｂをそのまま処理結果とすればよい。
【００７２】
例えば図１０（Ａ）に示した例では、直線ｘ＝ａは交点を持たないためＳ６２からＳ６４へ移り、直線ｘ＝ｂと閉領域Ａとの交点を求めると、点ｂを挟んで両側に交点を有している。従って、閉領域Ａが閉領域Ｂを内部に含むと判断し、Ｓ６５において、閉領域Ａの閉領域Ｂ以外の部分を分割する。この例では、直線ｘ＝ｂ＋αで分割した例を図１０（Ｂ）に示している。このように分割しておけば、分割領域はそれぞれ数学的に同位相の閉領域となるため、さらに他の閉領域との重なりに応じた分割処理を行う場合でも支障はない。
【００７３】
交点判定部２２で交点がないと判定された場合には、領域分割部２５が分割処理を行うが、上述のように新たに部分領域を登録する際に付加する領域種別を決定する際に、各閉領域の境界線を示す点列の回転方向を求めておくとよい。その判定を回転方向判定部２４で行っておく。なお、領域種別を付加せずに領域分割を行う場合には、回転方向判定部２４は不要である。
【００７４】
図１１は、回転方向判定部における回転方向の判定処理の一例を示す流れ図、図１２は、同じく具体例の説明図である。Ｓ７１において、閉領域の境界線上の特定の点を選択する。特定の点としては、ここではｘ座標の値が最も小さい点のうち、ｙ座標の値が最も小さい点ａを選択する。Ｓ７２において、閉領域の境界線を構成する点列から点ａの一つ後の点ｂを取得する。またＳ７３において、閉領域の境界線を構成する点列から点ａの一つ前の点ｃを取得する。
【００７５】
Ｓ７４において、点ａと点ｂを通る直線上で点ａから点ｂに向かう方向から見て右側に点ｃが存在するのか、左側に点ｃが存在するのかを判定する。点ａから点ｂへ向かう方向から見て右側に点ｃが存在する場合には、Ｓ７５において、当該閉領域は時計回り方向と判定する。また、点ａから点ｂへ向かう方向から見て左側に点ｃが存在する場合には、Ｓ７６において、当該閉領域は反時計回り方向と判定する。
【００７６】
図１２（Ａ）に示す例では、点ａから点ｂへ向かう方向から見て左側に点ｃが存在するので、反時計回り方向と判定される。図１２（Ｂ）に示す場合にも、点ａから点ｂへ向かう方向から見て左側に点ｃが存在するが、実際には時計回り方向である。この場合、Ｓ７１において点ａを選択する際のｘ座標値が最小であるという条件を満たしていないので、図１２（Ｂ）に示すような不都合は生じない。
【００７７】
このようにして回転方向判定部２４によって各閉領域の境界線を示す点列の回転方向がわかる。この回転方向に従って領域分割部２５による分割処理により各分割領域に付加する領域種別を変更したり、あるいは、回転方向を統一して点列を並べ替えてから領域分割部２５による分割処理を行えばよい。領域分割部２５による分割処理は第１の実施の形態において説明した通りである。
【００７８】
領域分割部２５による分割処理では、接触点や接触線は交点ではないため境界線上の１点として扱われる。そのため、領域分割部２５で分割された分割領域では、接触点や接触線がそのまま残った状態となっている。もちろんこのまま処理結果としてもよいが、例えば領域分割後に半透明処理を行う場合などでは、接触点あるいは接触線では塗りつぶしを行う面積がないため、不具合を生じかねない。そのため、ここでは接触点分割部２６によって接触点または接触線で分割領域をさらに分割する。
【００７９】
図１３は、接触点分割部２６による分割処理の一例を示す流れ図である。この処理は、処理結果として得られている各領域について、それぞれを処理対象として行う。Ｓ８１において、処理対象の領域は接触点あるいは接触線を含むか否かを判定し、含まなければその処理対象の領域に対する接触点分割部２６の処理は終了する。
【００８０】
接触点あるいは接触線を含んでいる場合には、Ｓ８２において、処理対象の領域の境界線上の点ｐを特定する。この点ｐは任意に特定すればよいが、ここではｘ座標の値が最小となる点を点ｐとする。
【００８１】
Ｓ８３において、処理対象の領域の境界線上にある接触点のうち、点ｐを挟む接触点を点ａ（１）、点ａ（２）とし、この点ａ（１）から点ａ（２）の方向に処理対象の領域の境界線をたどって接触点に番号を付与し、番号ｉにより特定される接触点を点ａ（ｉ）とする。接触点では、境界線をたどると行きと帰りで２回の番号付けがなされることになる。なお、接触線では、その始点と終点を接触点とする。
【００８２】
Ｓ８４において、変数ｉを１に初期化し、Ｓ８５において、点ａ（ｉ）と次の点ａ（ｉ＋１）とが１つの接触点に番号付けしたものであるか否かを判定する。１つの接触点に番号付けした点である場合には、Ｓ８６において、点ａ（ｉ）から点ａ（ｉ＋１）までにより境界線が構成される領域を１つの分割領域とする。
【００８３】
また、点ａ（ｉ）と点ａ（ｉ＋１）が異なる接触点のものである場合には、Ｓ８７において、点ａ（ｉ）から点ａ（ｉ＋１）までと、１つの接触点に点ａ（ｉ＋１）とともに付与されている番号を有する点ａ（ｔ）から次の点ａ（ｔ＋１）までにより境界線が構成される領域を１つの分割領域とする。なお、接触線の部分については分割領域とはしない。
【００８４】
Ｓ８６あるいはＳ８７の処理の後、Ｓ８８において、点ａ（ｉ）と次の点ａ（ｉ＋１）とが１つの接触点に番号付けしたものとの判定が２回行われたか否かを判定し、２回行われた場合には処理を終了する。０回または１回であればＳ８９において、変数ｉに１を加えてＳ８５へ戻り、次の点についての処理を行う。
【００８５】
図１４は、接触点における分割処理の具体例の説明図である。例えば図１４（Ａ）に示すような閉領域Ａ及び閉領域Ｂが与えられた場合には、領域分割部２５によって図１４（Ｂ）に示すような分割領域ａ，ｂ，ｃ，ｄが得られる。このうち分割領域ａは接触点を有している。そのため、接触点分割部２６によって図１４（Ｃ）に示すように分割領域ａを分割領域ｅ，ｆに分割する。
【００８６】
図１５は、接触点における分割処理の別の具体例の説明図である。図１４では接触点を有する簡単な例を示したが、図１３に示す処理では、より複雑な例に対応している。図１５（Ａ）に示した分割領域の例では、接触点が２つと接触線が１つ含まれている。このような場合に、図１３の処理に従いＳ８２で点ｐを特定し、Ｓ８３で各接触点に番号を付与してゆく。これによって図１５（Ｂ）に示すように点ｐ及び各点ａ（ｉ）（ｉ＝１，…，８）が得られる。
【００８７】
まずｉ＝１とし、点ａ（１）と点ａ（２）は１つの接触点に対して番号が付与された点であるから、Ｓ８６において、点ａ（１）から点ａ（２）へ至る境界線で構成される領域を１つの分割領域とする。これを図１５（Ｃ）に示している。
【００８８】
次にｉ＝２とし、点ａ（２）と点ａ（３）を参照すると、異なる接触点であるので、Ｓ８７において、点（２）から点ａ（３）までと、１つの接触点に点ａ（３）とともに付与されている番号を有する点ａ（８）から次の点ａ（１）までにより境界線が構成される領域を１つの分割領域とする。これを図１５（Ｄ）に示している。
【００８９】
さらにｉ＝３とし、点ａ（３）と点ａ（４）を参照すると、異なる接触点であるので、Ｓ８７における処理を行うが、この部分は接触線の部分であるので分割領域とはせずに次に進む。
【００９０】
ｉ＝４とし、点ａ（４）と点ａ（５）を参照すると、異なる接触点であるので、Ｓ８７において、点（４）から点ａ（５）までと、１つの接触点に点ａ（５）とともに付与されている番号を有する点ａ（６）から次の点ａ（７）までにより境界線が構成される領域を１つの分割領域とする。これを図１５（Ｅ）に示している。
【００９１】
ｉ＝５として点ａ（５）と点ａ（６）を参照すると、点ａ（５）と点ａ（６）は１つの接触点に対して番号が付与された点であるから、Ｓ８６において、点ａ（５）から点ａ（６）へ至る境界線で構成される領域を１つの分割領域とする。これを図１５（Ｆ）に示している。
【００９２】
このｉ＝５において、点ａ（ｉ）と次の点ａ（ｉ＋１）とが１つの接触点に番号付けしたものとの判定が２回（ｉ＝１とｉ＝５の場合）行われたので、これで接触点に関する分割処理を終える。この処理によって、図１５（Ａ）に示した接触点及び接触線を含む分割領域は、図１５（Ｃ）、（Ｄ）、（Ｅ）、（Ｆ）に示した４つの領域に分割される。
【００９３】
上述のように、この接触点及び接触線における分割処理は行わなくてもよい。あるいは、分割する代わりに接触点及び接触線で接触しないように境界線を構成することも可能である。すなわち、接触点を微少な距離だけ離した複数の点で近似したり、接触線を微少な間隔を有する複数の線で近似すればよい。
【００９４】
あるいは、交点検出部２１で交点を検出する際に、１つの接触点を微少な間隔を有する２つの交点として登録し、また接触線については両端を交点として登録すれば、領域分割部２５において接触点の部分で分割された分割領域が得られる。なお、この場合には接触点を２つ交点としたことにより微少な分割領域が生成されるが、この微少な分割領域は後で削除すればよい。
【００９５】
図１６は、本発明の各実施の形態の機能をコンピュータプログラムで実現した場合におけるコンピュータプログラム及びそのコンピュータプログラムを格納した記憶媒体とコンピュータの一例の説明図である。図中、１０１はプログラム、１０２はコンピュータ、１１１は光磁気ディスク、１１２は光ディスク、１１３は磁気ディスク、１１４はメモリ、１２１はＣＰＵ、１２２は内部メモリ、１２３は読取部、１２４はハードディスク、１２５はインタフェース、１２６は通信部である。
【００９６】
上述の本発明の各実施の形態で説明した各部の機能の一部または全部を、コンピュータにより実行可能なプログラム１０１によって実現してもよい。その場合、そのプログラム１０１およびそのプログラムが用いるデータなどは、コンピュータが読み取り可能な記憶媒体に記憶させておいてもよい。記憶媒体とは、コンピュータのハードウェア資源に備えられている読取部１２３に対して、プログラムの記述内容に応じて、磁気、光、電気等のエネルギーの変化状態を引き起こして、それに対応する信号の形式で、読取部１２３にプログラムの記述内容を伝達できるものである。例えば、光磁気ディスク１１１，光ディスク１１２（ＣＤやＤＶＤなどを含む）、磁気ディスク１１３，メモリ１１４（ＩＣカード、メモリカードなどを含む）等である。もちろんこれらの記憶媒体は、可搬型に限られるものではない。
【００９７】
これらの記憶媒体にプログラム１０１を格納しておき、例えばコンピュータ１０２の読取部１２３あるいはインタフェース１２５にこれらの記憶媒体を装着することによって、コンピュータからプログラム１０１を読み出し、内部メモリ１２２またはハードディスク１２４に記憶し、ＣＰＵ１２１によってプログラム１０１を実行することによって、各実施の形態で説明した機能が実現される。あるいは、ネットワークなどを介してプログラム１０１をコンピュータ１０２に転送し、コンピュータ１０２では通信部１２６でプログラム１０１を受信して内部メモリ１２２またはハードディスク１２４に記憶し、ＣＰＵ１２１によってプログラム１０１を実行することによって、各実施の形態で説明した機能を実現してもよい。なお、コンピュータ１０２には、このほかインタフェース１２５を介して様々な装置と接続してもよい。また、例えば記憶部１１はハードディスク１２４や内部メモリ１２２により構成すればよい。
【００９８】
もちろん、一部の機能についてハードウェアによって構成してもよいし、すべてをハードウェアで構成してもよい。あるいは、他の構成とともに本発明も含めたプログラムとして構成してもよい。例えば描画処理を行うプログラムとともに構成し、画像形成装置や表示装置に対して描画した画像を出力するように構成してもよい。もちろん、他の用途に適用する場合には、その用途におけるプログラムと一体化してもよい。
【図面の簡単な説明】
【００９９】
【図１】本発明の第１の実施の形態を示すブロック図である。
【図２】本発明の第１の実施の形態における動作の一例を示す流れ図である。
【図３】領域種別の一例の説明図である。
【図４】本発明の第１の実施の形態における動作の具体例の説明図である。
【図５】分割領域境界線情報の変化の一例の説明図である。
【図６】分割領域境界線情報の変化の一例の説明図（続き）である。
【図７】本発明の第２の実施の形態を示すブロック図である。
【図８】交点検出部による交点検出処理の一例を示す流れ図である。
【図９】包含処理部における包含処理の一例を示す流れ図である。
【図１０】包含処理部における包含処理の具体例の説明図である。
【図１１】回転方向判定部における回転方向の判定処理の一例を示す流れ図である。
【図１２】回転方向判定部における回転方向の判定処理の具体例の説明図である。
【図１３】回転方向判定部における回転方向の判定処理の具体例の説明図である。
【図１４】接触点における分割処理の具体例の説明図である。
【図１５】接触点における分割処理の別の具体例の説明図である。
【図１６】本発明の各実施の形態の機能をコンピュータプログラムで実現した場合におけるコンピュータプログラム及びそのコンピュータプログラムを格納した記憶媒体とコンピュータの一例の説明図である。
【図１７】領域分割の一例の説明図である。
【符号の説明】
【０１００】
１１…記憶部、１２…読出部、１３…領域断片取得部、１４…判定部、１５…登録部、２１…交点検出部、２２…交点判定部、２３…包含処理部、２４…回転方向判定部、２５…領域分割部、２６…接触点分割部、１０１…プログラム、１０２…コンピュータ、１１１…光磁気ディスク、１１２…光ディスク、１１３…磁気ディスク、１１４…メモリ、１２１…ＣＰＵ、１２２…内部メモリ、１２３…読取部、１２４…ハードディスク、１２５…インタフェース、１２６…通信部。
【特許請求の範囲】
【請求項１】
第１の閉領域の境界線の情報を記憶する第１の記憶手段と、前記第１の閉領域と境界線が交差する第２の閉領域の境界線の情報を記憶する第２の記憶手段と、分割領域の境界線の情報を記憶する第３の記憶手段と、前記第１の記憶手段から前記第２の閉領域との交点を所定の方向に前記第１の閉領域を周回するまで順に基点として読み出す読出手段と、前記読出手段で読み出した基点から前記第１の閉領域の境界線を所定の方向にたどって次の第２の閉領域の境界線との交点である第１の交点から第２の閉領域の境界線を時計方向と反時計方向にたどってそれぞれ基点から第１の交点を通り第２の交点を終点とする領域断片と基点から第１の交点を通り第３の交点を終点とする領域断片をそれぞれ求める領域断片取得手段と、前記領域断片取得手段で求めた２つの領域断片について前記領域断片の始点が前記第３の記憶手段に記憶されている分割領域の境界線のその時点での終点として登録されているか否か及び登録されている場合に該登録されている分割領域の境界線をたどった方向と前記領域断片が前記第２の閉領域をたどった方向が同じか否かを判定する判定手段と、前記判定手段によって基点が既に登録されていると判定され領域断片がたどった方向が分割領域の境界線がたどった方向であると判定された場合には該登録されている分割領域の境界線として前記領域断片を追加しそのほかの場合には前記領域断片を新たな分割領域の境界線として前記第３の記憶手段に登録する登録手段を有することを特徴とする領域分割装置。
【請求項２】
前記登録手段は、前記領域断片を新たな分割領域の境界線として前記第３の記憶手段に登録する際に、前記領域断片の基点から第１の交点までの前記第１の閉領域の境界線が前記第２の閉領域の内部か否か及び第１の交点から前記第２の閉領域の境界線をたどった方向により、当該分割領域が前記第１の閉領域と前記第２の閉領域との集合演算により定められる領域のいずれに属するかを示す領域種別を決定し、該領域種別を前記新たな分割領域に付加して登録することを特徴とする請求項１に記載の領域分割装置。
【請求項３】
さらに、前記第１の閉領域と前記第２の閉領域の交点を検出して前記第１の記憶手段及び第２の記憶手段に境界線の情報として記憶させる交点検出手段を有することを特徴とする請求項１または請求項２に記載の領域分割装置。
【請求項４】
さらに、前記第１の閉領域と前記第２の閉領域が交点を有するか否かを判定する交点判定手段と、前記交点判定手段が交点を有しないと判定した場合に包含処理を行う包含処理手段を有し、前記判定手段が交点を有すると判定した場合に前記読出手段、領域断片取得手段、判定手段、登録手段による処理を行い、前記包含処理手段は、前記第１の閉領域と前記第２の閉領域に重なりがない場合には前記第１の閉領域及び前記第２の閉領域を処理結果とし、一方の閉領域が内部に他方の閉領域を包含する場合には、前記一方の閉領域の前記他方の閉領域を除く領域を分割して、分割した各領域と前記他方の閉領域を処理結果とすることを特徴とする請求項１ないし請求項３のいずれか１項に記載の領域分割装置。
【請求項５】
さらに、前記第３の記憶手段に登録された分割領域が接触点または接触線を含む場合に接触する点で分割領域を分割する接触点分割手段をさらに有することを特徴とする請求項１ないし請求項４のいずれか１項に記載の領域分割装置。
【請求項６】
さらに、前記第１の閉領域と前記第２の閉領域が接触点を有する場合に２つの交点となるように前記第１の記憶手段に記憶されている前記第１の閉領域の境界線の情報または前記第２の記憶手段に記憶されている前記第２の閉領域の境界線の情報を変更する変更手段を有することを特徴とする請求項１ないし請求項４のいずれか１項に記載の領域分割装置。
【請求項７】
コンピュータに、請求項１ないし請求項６のいずれか１項に記載の領域分割装置の機能を実行させることを特徴とする領域分割プログラム。
【請求項１】
第１の閉領域の境界線の情報を記憶する第１の記憶手段と、前記第１の閉領域と境界線が交差する第２の閉領域の境界線の情報を記憶する第２の記憶手段と、分割領域の境界線の情報を記憶する第３の記憶手段と、前記第１の記憶手段から前記第２の閉領域との交点を所定の方向に前記第１の閉領域を周回するまで順に基点として読み出す読出手段と、前記読出手段で読み出した基点から前記第１の閉領域の境界線を所定の方向にたどって次の第２の閉領域の境界線との交点である第１の交点から第２の閉領域の境界線を時計方向と反時計方向にたどってそれぞれ基点から第１の交点を通り第２の交点を終点とする領域断片と基点から第１の交点を通り第３の交点を終点とする領域断片をそれぞれ求める領域断片取得手段と、前記領域断片取得手段で求めた２つの領域断片について前記領域断片の始点が前記第３の記憶手段に記憶されている分割領域の境界線のその時点での終点として登録されているか否か及び登録されている場合に該登録されている分割領域の境界線をたどった方向と前記領域断片が前記第２の閉領域をたどった方向が同じか否かを判定する判定手段と、前記判定手段によって基点が既に登録されていると判定され領域断片がたどった方向が分割領域の境界線がたどった方向であると判定された場合には該登録されている分割領域の境界線として前記領域断片を追加しそのほかの場合には前記領域断片を新たな分割領域の境界線として前記第３の記憶手段に登録する登録手段を有することを特徴とする領域分割装置。
【請求項２】
前記登録手段は、前記領域断片を新たな分割領域の境界線として前記第３の記憶手段に登録する際に、前記領域断片の基点から第１の交点までの前記第１の閉領域の境界線が前記第２の閉領域の内部か否か及び第１の交点から前記第２の閉領域の境界線をたどった方向により、当該分割領域が前記第１の閉領域と前記第２の閉領域との集合演算により定められる領域のいずれに属するかを示す領域種別を決定し、該領域種別を前記新たな分割領域に付加して登録することを特徴とする請求項１に記載の領域分割装置。
【請求項３】
さらに、前記第１の閉領域と前記第２の閉領域の交点を検出して前記第１の記憶手段及び第２の記憶手段に境界線の情報として記憶させる交点検出手段を有することを特徴とする請求項１または請求項２に記載の領域分割装置。
【請求項４】
さらに、前記第１の閉領域と前記第２の閉領域が交点を有するか否かを判定する交点判定手段と、前記交点判定手段が交点を有しないと判定した場合に包含処理を行う包含処理手段を有し、前記判定手段が交点を有すると判定した場合に前記読出手段、領域断片取得手段、判定手段、登録手段による処理を行い、前記包含処理手段は、前記第１の閉領域と前記第２の閉領域に重なりがない場合には前記第１の閉領域及び前記第２の閉領域を処理結果とし、一方の閉領域が内部に他方の閉領域を包含する場合には、前記一方の閉領域の前記他方の閉領域を除く領域を分割して、分割した各領域と前記他方の閉領域を処理結果とすることを特徴とする請求項１ないし請求項３のいずれか１項に記載の領域分割装置。
【請求項５】
さらに、前記第３の記憶手段に登録された分割領域が接触点または接触線を含む場合に接触する点で分割領域を分割する接触点分割手段をさらに有することを特徴とする請求項１ないし請求項４のいずれか１項に記載の領域分割装置。
【請求項６】
さらに、前記第１の閉領域と前記第２の閉領域が接触点を有する場合に２つの交点となるように前記第１の記憶手段に記憶されている前記第１の閉領域の境界線の情報または前記第２の記憶手段に記憶されている前記第２の閉領域の境界線の情報を変更する変更手段を有することを特徴とする請求項１ないし請求項４のいずれか１項に記載の領域分割装置。
【請求項７】
コンピュータに、請求項１ないし請求項６のいずれか１項に記載の領域分割装置の機能を実行させることを特徴とする領域分割プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２００９−８０７２５（Ｐ２００９−８０７２５Ａ）
【公開日】平成２１年４月１６日（２００９．４．１６）
【国際特許分類】
【出願番号】特願２００７−２５０６５５（Ｐ２００７−２５０６５５）
【出願日】平成１９年９月２７日（２００７．９．２７）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
【公開日】平成２１年４月１６日（２００９．４．１６）
【国際特許分類】
【出願日】平成１９年９月２７日（２００７．９．２７）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
[ Back to top ]