(57)【要約】【課題】  厚みの薄い形状など、複雑な形状を境界とする場合にも容易に境界形状データの生成を可能にする為の技術を提供すること。【解決手段】  複数の領域が設定された２次元仮想平面を分割した矩形領域のうち、設定された領域同士の境界部分を含む境界矩形領域を所定数の領域に分割し（Ｓ５０８）、分割領域を構成する各頂点について分割領域内の境界部分との位置関係を求め、分割領域を構成する頂点若しくは稜線と、分割領域内の境界部分との交点位置を求め、上記位置関係、及び上記交点位置を用いて、分割領域内で設定された領域に属している部分、属していない部分を特定することで、分割領域が、予め作成された複数種のパターンのうち何れのパターンに相当するのかを決定する（Ｓ５０５）。【選択図】  図５
2006323780.tif 000002
【特許請求の範囲】
【請求項１】
２次元仮想平面中に複数の領域を設定する設定手段と、
前記２次元仮想平面を複数の矩形領域に分割する分割手段と、
前記分割手段によって得られた矩形領域群のうち、前記設定手段によって設定された領域同士の境界部分を含む境界矩形領域を選択する選択手段と、
前記選択手段が選択した境界矩形領域を構成する各頂点について、当該境界矩形領域内の前記境界部分との位置関係を求める第１の計算手段と、
前記境界矩形領域を構成する頂点若しくは稜線と、前記境界矩形領域内の前記境界部分との交点位置を求める第２の計算手段と、
前記境界矩形領域を構成する各頂点と前記境界矩形領域内の前記境界部分との位置関係、及び前記境界矩形領域を構成する頂点若しくは稜線と前記境界矩形領域内の前記境界部分との交点位置を用いて、前記境界矩形領域内で前記設定手段によって設定された領域に属している部分、属していない部分を特定することで、前記境界矩形領域のパターンが、予め作成された複数種のパターンのうち何れのパターンに相当するのかを決定する決定手段と
を備えることを特徴とする画像処理装置。
【請求項２】
前記決定手段が決定したパターンの矩形領域を構成する頂点若しくは稜線と、当該矩形領域内で前記境界部分に相当する部分との交点を求めた後に、交点同士を結ぶ線分を求めることを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記第１の計算手段は、前記選択手段が選択した矩形領域を構成する各頂点について、当該矩形領域内の前記境界部分上に位置するのか、若しくは前記設定手段が設定した領域の内外の何れに位置するのかに応じた値を求めることを特徴とする請求項１又は２に記載の画像処理装置。
【請求項４】
前記決定手段は、前記選択手段が選択した矩形領域を構成する各頂点について前記第１の計算手段が求めた値の配置、及び当該矩形領域を構成する頂点若しくは稜線と当該矩形領域内の前記境界部分との交点位置を用いて、当該矩形領域内で、前記設定手段によって設定された領域に属している部分、属していない部分を特定することで、当該矩形領域のパターンが、予め作成された複数種のパターンのうち何れのパターンに相当するのかを決定することを特徴とする請求項３に記載の画像処理装置。
【請求項５】
２次元仮想平面中に複数の領域を設定する設定工程と、
前記２次元仮想平面を複数の矩形領域に分割する分割工程と、
前記分割工程で得られた矩形領域群のうち、前記設定工程で設定された領域同士の境界部分を含む境界矩形領域を選択する選択工程と、
前記選択工程で選択した境界矩形領域を構成する各頂点について、当該境界矩形領域内の前記境界部分との位置関係を求める第１の計算工程と、
前記境界矩形領域を構成する頂点若しくは稜線と、前記境界矩形領域内の前記境界部分との交点位置を求める第２の計算工程と、
前記境界矩形領域を構成する各頂点と前記境界矩形領域内の前記境界部分との位置関係、及び前記境界矩形領域を構成する頂点若しくは稜線と前記境界矩形領域内の前記境界部分との交点位置を用いて、前記境界矩形領域内で前記設定工程で設定された領域に属している部分、属していない部分を特定することで、前記境界矩形領域のパターンが、予め作成された複数種のパターンのうち何れのパターンに相当するのかを決定する決定工程と
を備えることを特徴とする画像処理方法。
【請求項６】
コンピュータに請求項５に記載の画像処理方法を実行させることを特徴とするプログラム。
【請求項７】
請求項６に記載のプログラムを格納したことを特徴とする、コンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、界面などの境界形状データの生成技術に関するものである。
【背景技術】
【０００２】
近年、流体解析等、境界を扱う数値解析手法では、計算機の急速な進歩に伴い、古くから知られていた直交格子法が大規模計算に適した手法として再注目されており、直交格子上での境界形状データを生成する有力な方法の１つにカットセル法が知られている。特に２次元空間上の境界形状を扱うカットセル法は非特許文献１に開示されている。
【０００３】
非特許文献１に開示されているカットセル法は、まず一様な間隔を持つ直交格子によって生成されるセル（格子で仕切られた矩形からなる領域）の集合の中から、境界セル（境界が通過するセル。境界がセルを通過する状態とは、セルの輪郭を成す稜線または頂点と境界が交わっている状態を指す）を検出する。この検出により、セルの集合内の、境界セル、非境界セル（境界が通過しないセル）が明らかになる。次に上記検出により検出された境界セルを予め用意した基本パターンと照合する。図２は、基本パターンの例を示す図である。
【０００４】
基本パターンとは、ある仮定に基づいて予め数え上げた境界セルのパターンであり、従来では、適切な大きさのセルで切り取られた境界が一本の線分で表現されると暗黙に仮定し、その仮定の元で考えられる全ての境界セルのパターンを数え上げることで基本パターンを作成する。この基本パターンは、境界セル内部に存在する複数の交点の接続に関する情報と、境界によって分断されたセルの断片が境界の内側外側のどちらに属するかという情報（以下、上記二つの情報をまとめて境界セル情報と呼ぶ）を有している。
【０００５】
照合の結果、境界セルと基本パターンが一致を見る場合には、基本パターンにより境界セルに関する境界セル情報が明らかになる。照合の結果、境界セルと基本パターンとの一致が見られない場合は、境界セルを分割し再照合する。上記分割は、予め定められた分割回数の上限までの範囲内で、一致を見るまで繰り返し行う。
【０００６】
上記カットセル法を使用し、境界セル毎に、境界セルの稜線と境界との交点を求め、境界セル情報を使用すれば、交点を構成要素とする向き付けられた線分を用いて境界を近似表現できる。
【０００７】
入力された境界形状データが図３（ａ）、（ｂ）に示す３０１，３０２のような形状の場合、１セル内に境界が複数存在しているため上記の方法では処理できない。しかしながら非特許文献２で開示されているbluntingと呼ばれる処理（先端部を切り落とす）を行うことで、それぞれ３１１，３１２で示すように近似表現を得られる事が知られている。
【０００８】
図３から明らかなように同図（ａ）の場合は、注目しているセルのみで上記処理が行われ、同図（ｂ）の場合は、周辺セルの情報を用いてbluntingを実行する。
【非特許文献１】J.J. Quirk、”An alternative to unstructured grids for computing gas dynamic flows around arbitrarily complex two-dimensional bodies”、Computers Fluids、Vo. ２３, No. １, pp. １２５-１４２, １９９４。
【非特許文献２】J.J. Quirk、”A CARTESIAN GRID APPROACH WITH HIERARCHICAL REFINEMENT FOR COMPRESSIBLE FLOWS”、NASA CR-１９４９３８ ICASE Report、No.９４-５１、pp. ２３、June １９９４.
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、従来の２次元のカットセル法には、以下に述べる３つの問題がある。
【００１０】
１．  境界の形状が複雑である場合には、境界セルの分割を多数回実行し、その結果生成される膨大な数のセルを使用するため、数値解析での計算負荷が増大する。
【００１１】
２．  予め定められた分割回数の上限に達した場合に、図２のような基本パターンと一致を見ない境界セル（厚みの薄い形状や、尖鋭の形状など）が存在する場合には、入力形状、もしくは格子を生成するパラメータ（分割回数の上限等）を修正しなければならない。
【００１２】
３．  予め定められた分割回数の上限に達した場合に、尖鋭な部分を有する形状があれば、複雑なblunting処理を行わなければならない。
【００１３】
本発明は以上の問題に鑑みてなされたものであり、上記問題点１，２，３を改善するための技術、特に、従来では困難であった尖鋭な部分を有する形状や、厚みの薄い形状など、複雑な形状を境界とする場合にも容易に境界形状データの生成を可能にする為の技術を提供することを目的とする。
【課題を解決するための手段】
【００１４】
本発明の目的を達成するために、例えば本発明の画像処理装置は以下の構成を備える。
【００１５】
即ち、２次元仮想平面中に複数の領域を設定する設定手段と、
前記２次元仮想平面を複数の矩形領域に分割する分割手段と、
前記分割手段によって得られた矩形領域群のうち、前記設定手段によって設定された領域同士の境界部分を含む境界矩形領域を選択する選択手段と、
前記選択手段が選択した境界矩形領域を構成する各頂点について、当該境界矩形領域内の前記境界部分との位置関係を求める第１の計算手段と、
前記境界矩形領域を構成する頂点若しくは稜線と、前記境界矩形領域内の前記境界部分との交点位置を求める第２の計算手段と、
前記境界矩形領域を構成する各頂点と前記境界矩形領域内の前記境界部分との位置関係、及び前記境界矩形領域を構成する頂点若しくは稜線と前記境界矩形領域内の前記境界部分との交点位置を用いて、前記境界矩形領域内で前記設定手段によって設定された領域に属している部分、属していない部分を特定することで、前記境界矩形領域のパターンが、予め作成された複数種のパターンのうち何れのパターンに相当するのかを決定する決定手段と
を備えることを特徴とする。
【００１６】
本発明の目的を達成するために、例えば本発明の画像処理方法は以下の構成を備える。
【００１７】
即ち、２次元仮想平面中に複数の領域を設定する設定工程と、
前記２次元仮想平面を複数の矩形領域に分割する分割工程と、
前記分割工程で得られた矩形領域群のうち、前記設定工程で設定された領域同士の境界部分を含む境界矩形領域を選択する選択工程と、
前記選択工程で選択した境界矩形領域を構成する各頂点について、当該境界矩形領域内の前記境界部分との位置関係を求める第１の計算工程と、
前記境界矩形領域を構成する頂点若しくは稜線と、前記境界矩形領域内の前記境界部分との交点位置を求める第２の計算工程と、
前記境界矩形領域を構成する各頂点と前記境界矩形領域内の前記境界部分との位置関係、及び前記境界矩形領域を構成する頂点若しくは稜線と前記境界矩形領域内の前記境界部分との交点位置を用いて、前記境界矩形領域内で前記設定工程で設定された領域に属している部分、属していない部分を特定することで、前記境界矩形領域のパターンが、予め作成された複数種のパターンのうち何れのパターンに相当するのかを決定する決定工程と
を備えることを特徴とする。
【発明の効果】
【００１８】
本発明の構成により、上記問題点１，２，３を改善することができる。特に、従来では困難であった尖鋭な部分を有する形状や、厚みの薄い形状など、複雑な形状を境界とする場合にも容易に境界形状データの生成を可能にすることができる。
【発明を実施するための最良の形態】
【００１９】
以下添付図面を参照して、本発明を好適な実施形態に従って詳細に説明する。
【００２０】
図４は、以下説明する各処理を実行する画像処理装置として機能するコンピュータのハードウェア構成を示すブロック図である。
【００２１】
４０１はＣＰＵで、ＲＡＭ４０４にロードされたプログラムやデータを用いて本コンピュータ全体の制御を行うと共に、コンピュータが行う後述の各処理を実行する。
【００２２】
４０２は表示装置で、ＣＲＴや液晶画面などにより構成されており、ＣＰＵ４０１による処理結果を画像や文字などでもって表示する。
【００２３】
４０３は入力装置で、キーボードやマウスなどにより構成されており、本コンピュータの操作者が操作することで、各種の指示をＣＰＵ４０１に対して入力することができる。
【００２４】
４０４はＲＡＭで、外部記憶装置４０５からロードされたプログラムやデータを一時的に記憶するためのエリア、通信装置４０６が外部から受信したプログラムやデータを一時的に記憶するためのエリア、そして、ＣＰＵ４０１が各種の処理を実行する際に用いるワークエリア等、各種のエリアを適宜提供することができる。
【００２５】
４０５は外部記憶装置で、ハードディスクドライブ装置に代表される大容量情報記憶装置であって、ここにＯＳ（オペレーティングシステム）や、コンピュータが行う後述の各処理をＣＰＵ４０１に実行させるためのプログラムやデータが保存されており、これらはＣＰＵ４０１による制御に従ってＲＡＭ４０４にロードされ、ＣＰＵ４０１による処理対象となる。
【００２６】
４０６は通信装置であって、ＬＡＮやインターネットなどのネットワークを介して外部装置とのデータ通信を行うものであり、外部記憶装置４０５に保存されているとするプログラムやデータの一部若しくは全部は、通信装置４０６により適宜外部装置から受信してＲＡＭ４０４に転送するようにしても良い。
【００２７】
４０７は上述の各部を繋ぐバスである。
【００２８】
次に、仮想の２次元平面上で流体力学計算などの計算処理を行う場合について説明する。上述の通り、仮想の２次元平面上でこのような計算処理を行う場合には、先ず、この２次元仮想平面上に例えば流体の内部領域、外部領域等のように、複数の領域を設定する必要がある。このように複数の領域を設定するということは同時に、領域同士の境界（界面）を設定することに等価である。
【００２９】
次に、複数の領域を設定した２次元仮想平面を複数の矩形領域に分割する。その場合、矩形領域によっては、境界を含むものもある。以下の説明では、このように、分割された複数の矩形領域のうち、境界部分を含むものがある場合には、矩形内の境界部分を線形に近似するための処理を行う。
【００３０】
図５は、このような処理のフローチャートである。なお、同図のフローチャートに従った処理をＣＰＵ４０１に実行させるためのプログラムやデータは外部記憶装置４０５に保存されており、これをＣＰＵ４０１による制御に従って適宜ＲＡＭ４０４にロードし、ＣＰＵ４０１がこれを用いて処理を実行することで、本コンピュータは以下説明する各処理を実行する。
【００３１】
先ず、２次元仮想平面上に設定する各領域を定義するデータ（境界形状データ）を外部記憶装置４０５からＲＡＭ４０４にロードする（ステップＳ５００）。例えば２次元仮想平面上で固体と流体との界面を扱う流体解析計算処理を行う場合には、境界の内側が固体、外側が流体等、境界の内側外側の情報が必要となる。よって境界形状データは、境界の形状を示すと共に、この境界を境にどの側が内側でどの側が外側なのかを示すものである。本実施形態では境界形状データは、陰関数の組み合わせにより定義される。
【００３２】
例えば図６に示す円形において円形領域の内部ＤinはＤin＝｛（ｘ、ｙ）｜ｘ２＋ｙ２−１＜０｝と定義されるし、円形領域の外部ＤoutはＤout＝｛（ｘ、ｙ）｜ｘ２＋ｙ２−１＞０｝と定義される。
【００３３】
また、図７に示す三角形の領域において、領域内部ＤinはＣ言語等のプログラミング言語を意識した不等式の論理演算式
（ｙ−２ｘ−１＜０）∩（ｙ＋２ｘ−１＜０）∩（ｙ＞０）
でもって定義される。
【００３４】
このように、領域内部Ｄinは３つの集合Ａin＝｛（ｘ、ｙ）｜ｙ−２ｘ−１＜０｝、Ｂin＝｛（ｘ、ｙ）｜ｙ＋２ｘ−１＜０｝、Ｃin＝｛（ｘ、ｙ）｜ｙ＞０｝の論理積Ａi∩Ｂin∩Ｃinでもって定義される。
【００３５】
一方、図７に示す三角形の領域の外部Ｄoutは、Ａout＝｛（ｘ、ｙ）｜ｙ−２ｘ−１＞０｝、Ｂout＝｛（ｘ、ｙ）｜ｙ＋２ｘ−１＞０｝、Ｃout＝｛（ｘ、ｙ）｜ｙ＜０｝の論理和Ａout∪Ｂout∪Ｃoutでもって定義される。
【００３６】
また、図７に示す三角形の領域上Ｄは、ｃ（Ｄin∪Ｄout）でもって定義される。ここでｃ（Ａ）は、集合Ａの補集合を表す。
【００３７】
このような不等式の論理演算による境界形状の表現は、Ｃ言語等のプログラミング言語で用意されている条件式と真偽値を使用することで、容易に実現できる。
【００３８】
このように、２次元仮想平面上に設定されたそれぞれの領域の境界の形状、及び、２次元仮想平面上の各位置がその領域の内部／外部に位置するのかを示す境界形状データをＲＡＭ４０４にロードする。
【００３９】
次に、２次元仮想平面を複数の矩形領域に分割する（ステップＳ５０１）。即ち、２次元仮想平面上に格子点を格子状に配置することで、格子点で囲まれた領域（矩形領域）毎に２次元仮想平面を分割する。なお、矩形領域の縦横のサイズについては特に限定するものではない。
【００４０】
図８は、複数の矩形領域に分割された２次元仮想平面の一部の例を示す図である。同図において８００は２次元仮想平面の一部を示すものであり、同図に示す如く、２次元仮想平面は複数の矩形領域に分割されている。また、同図において８０３は境界を示すものであり、上記境界形状データでもって定義されるものである。
【００４１】
また同図において８０２は、境界８０３が通過している矩形領域（境界部分８０３を含む矩形領域）であり、８０１は、境界８０３が通過していない矩形領域（境界部分８０３を含まない矩形領域）である。ここで、境界部分を含む矩形領域とは、矩形領域の輪郭を成す稜線や頂点と境界部分との交点が存在するような矩形領域である。以下では、境界部分を含む矩形領域を境界矩形領域と呼称する。
【００４２】
図５に戻って、次に、それぞれの矩形領域を順次参照し（ステップＳ５０２）、参照した矩形領域が境界矩形領域であるのか否かを判断する（ステップＳ５０３）。ここで、矩形領域が境界矩形領域であるのか否かを判断するための処理について説明する。
【００４３】
例えば、境界矩形領域を構成する全ての稜線と境界との交点の個数を用いる方法がある。境界が境界矩形領域の頂点上を通る場合や、境界の先端部が境界矩形領域の外側から境界矩形領域の稜線に接している場合などは、最小の交点の個数をもつ場合であり、その個数は１である。もちろん、非境界矩形領域の交点の個数は０である。
【００４４】
一方、矩形領域における交点の個数の最大値は、境界形状の複雑さと矩形領域の大きさに依存するため無限である。
【００４５】
従って、注目する矩形領域の稜線と境界との交点の個数をＮとした場合に、Ｎ＞０であればこの注目する矩形領域は境界矩形領域、それ以外であれば非境界矩形領域であると判別する。なお、矩形領域が境界矩形領域であるのか否かを判別するための処理についてはこれに限定するものではない。
【００４６】
従って、ステップＳ５０２で参照した矩形領域がステップＳ５０３で非境界矩形領域であると判別された場合には、処理をステップＳ５０７に進め、未だ参照していない矩形領域がある場合には処理をステップＳ５０２に戻し、次の矩形領域について以降の処理を行う。一方、ステップＳ５０２で参照した矩形領域がステップＳ５０３で境界矩形領域であると判別された場合には、処理をステップＳ５０４に進め、以降ではステップＳ５０２で参照した矩形領域を分割するのであるが、ステップＳ５０４では、この分割する回数が予め定められた回数に達したのか否かを判断する。
【００４７】
ここで、境界矩形領域の分割とは、図１８に示す如く、１つの境界矩形領域を再帰的に分割することである。同図では４分木分割ステップで分割が行われている。よって、ステップＳ５０４では、図１８の場合、現在の分割が４分木における階層の深さに達したのか否かを判断することになる。
【００４８】
ステップＳ５０４で、境界矩形領域の分割回数が予め定められた回数に達していない場合には処理をステップＳ５０８に進め、境界矩形領域を分割し、それぞれの分割境界矩形領域についてステップＳ５０２以降の処理を行う。
【００４９】
一方、ステップＳ５０４で、境界矩形領域を予め定められた回数だけ分割していた場合には処理をステップＳ５０５に進め、外部記憶装置４０５に保存されている複数の基本パターンのうち、分割境界矩形領域が何れの基本パターンに相当するのか（最も近いのか）を判断する。なお、ここではステップＳ５０８により必要な回数だけ分割後に、ステップＳ５０５の判断を行なうようにしたが、分割前や分割する毎にステップＳ５０５の判断を行なうようにしてもよい。
【００５０】
ここで、本実施形態では、境界矩形領域（分割境界矩形領域）内に含まれている境界部分の形状は２本以下の線分でもって表現されるものであるとする。従って、基本パターンはこのような仮定を満たす様々な形状の境界部分を含む境界矩形領域を示すものである。このような基本パターンは予め作成され、データとして外部記憶装置４０５に保存されているものである。
【００５１】
図９は、このような基本パターンを作成する為の処理のフローチャートである。なお、同図のフローチャートに従った処理は、上述の通り、図５に示したフローチャートに従った処理の実行前に事前に行われているものである。
【００５２】
ステップ１：矩形領域内に１つの線分が存在する全ての場合を数え上げる。この中には、右回りに０°、９０°、１８０°、２７０°回転させると一致するパターンが含まれている。
【００５３】
ステップ２：ステップ１で数え上げられたパターン群に対し、右回りに０°、９０°、１８０°、２７０°回転させると一致するパターンを１つのパターンとしてまとめる。
【００５４】
ステップ３：ステップ１とステップ２で得られた２種類のパターン群からそれぞれ１つずつ選ぶ全ての組み合わせから、２本の線分が通るパターンを作成する。
【００５５】
ステップ４：ステップ３で作成されるパターン群の内、線分が交差する可能性のあるパターンについて、図１０に示すように、更に、
（状況１）  ２本の線分が交差する場合
（状況２）  ２本の線分が交差しない場合
（状況３）  ２本の線分が稜線上で交差する場合
に分ける。
【００５６】
ステップ５：境界が不等式の論理演算式の領域で与えられることを考慮し、（状況１）について、図１１に示す例のように、４つのパターンに分ける。
【００５７】
以上の順序で数え上げた境界矩形領域のパターン群をまとめることによって、図１２に示すような基本パターン群を得る。図１２は、本実施形態で用いる基本パターン群の例を示す図である。同図に示す例では、それぞれの基本パターンでの回転対象性をまとめている。
【００５８】
次に、分割境界矩形領域が何れの基本パターンに一致するのかを決定する処理について詳細に説明する。
【００５９】
先ず、分割境界矩形領域内で、境界形状データが示す領域の内側に属している部分、外側に属している部分を特定する処理を行う。
【００６０】
そのためには先ず、分割境界矩形領域を構成する４つの頂点のそれぞれが、境界形状データが定義する領域の内側、外側、境界上の何れに属しているのかをチェックする。
【００６１】
例えば図１３Ａの左側に示すように、分割境界矩形領域１３０１と領域１３０２との位置関係が同図に示すような状態である場合、同図右側に示すように分割境界矩形領域を構成する４つの頂点のうち左上隅の頂点（黒丸で示した頂点）以外の３頂点（白丸で示した頂点）が領域１３０２の内側に含まれており、左上隅の頂点のみが境界１３０２の外側に位置する。
【００６２】
なお、それぞれの頂点が、境界形状データが定義する領域の内側、外側、境界上の何れに属しているのかをチェックする方法については様々なものが考えられるが、本実施形態では境界形状データは、領域を定義するための不等式の論理演算式を用いたものであるので、任意の座標位置をこの不等式の左辺に代入し、その結果が正負、または０であるかどうかによって、この任意の座標位置が、境界形状データが定義する領域の内側、外側、境界上の何れに属しているのかをチェックすることができる。そして、頂点が境界形状データが定義する領域の内側、外側、境界上の何れに属しているのかを示す値を、この頂点に対して設定する。
【００６３】
本実施形態では、境界形状データが定義する領域の内側に頂点が位置する場合にはこの頂点に対して「０」を設定し、外側に頂点が位置する場合にはこの頂点に対して「１」を設定し、境界上に位置する場合にはこの頂点に対して「２」を設定する。これにより、１つの分割境界矩形領域を構成するそれぞれの頂点には値（以下、内外判定値と呼称する）が設定されることになる。
【００６４】
以上の処理により、分割境界矩形領域を構成するそれぞれの頂点が、境界形状データが定義する領域の内側、外側、境界上の何れに属しているのかをチェックすることができる。
【００６５】
また、図１４Ａの左側に示すように、分割境界矩形領域１３０１と領域１３０２との位置関係が同図に示すような状態である場合（即ち図１３Ａの左側に示すような状態）、分割境界矩形領域を構成する稜線（頂点を含む）と領域１３０２の境界との交点は同図右側に示す如く、２点求まる。
【００６６】
よって、分割境界矩形領域１３０１と領域１３０２の内側との位置関係が図１３Ａの左側に示すような状態である場合、分割境界矩形領域内において、この交点間を結ぶ線分を境界として一方側が領域１３０２の内側、他方側が領域１３０２の外側と定義することができるが、この線分を境界として一方側に位置する１つの頂点は内外判定値が「１」、他方側に位置する３つの頂点は内外判定値が「０」であることから、この線分を境界として左上側が領域１３０２の外側、その残りが内側であるとすることができる。
【００６７】
また、分割境界矩形領域１３０１と領域１３０２との位置関係は図１３Ｂの左側に示すようなものも考えられ、このような状態である場合、同図右側に示すように分割境界矩形領域１３０１を構成する４つの頂点のうち左上隅の頂点以外の３頂点が領域１３０２の内側に含まれており、左上隅の頂点のみが領域１３０２の境界上に位置する。
【００６８】
また、分割境界矩形領域１３０１と領域１３０２の内側との位置関係が図１４Ｂの左側に示すようなものも考えられ、このような状態である場合、分割境界矩形領域１３０１を構成する稜線（頂点を含む）と領域１３０２との交点は同図右側に示す如く、３点求まる。
【００６９】
このようにして、分割境界矩形領域内で、境界形状データが示す領域の内側に属している部分、外側に属している部分を特定することができる。
【００７０】
なお、図１５の１５０１に示すように、境界形状データが示す領域１５０８と分割境界矩形領域１５０７との位置関係では、１５３０に示す如く、分割境界矩形領域１５０７を構成する４つの頂点１５２１〜１５２４のうち、頂点１５２１、１５２４が領域１５０８の外側、頂点１５２２、１５２３が領域１５０８の内側に位置すると共に、領域１５０８と分割境界矩形領域１５０７との交点は１５４１〜１５４４となる。
【００７１】
一方、１５０２に示すように、境界形状データが示す領域１５１０、１５１１と分割境界矩形領域１５０７との位置関係では、１５３０に示す如く、分割境界矩形領域１５０７を構成する４つの頂点１５２１〜１５２４のうち、頂点１５２１、１５２４が領域１５１０、１５１１の外側、頂点１５２２、１５２３がそれぞれ領域１５１１、１５１０の内側に位置すると共に、領域１５１０と分割境界矩形領域１５０７との交点は１５４２、１５４３となり、領域１５１１と分割境界矩形領域１５０７との交点は１５４１、１５４４となる。
【００７２】
即ち、境界形状データが示す領域と分割境界矩形領域との位置関係が１５０１，１５０２に示すようにそれぞれ異なる位置関係であったとしても、各頂点に設定した内外判定値の配置関係は同じであるし、交点位置も同じである。これでは、分割境界矩形領域内で、境界形状データが示す領域の内側に属している部分、外側に属している部分を一意に特定することはできない。
【００７３】
そこで、１５４０に示す如く、分割境界矩形領域の略中心部に新たに追加点１５６０を設け、この追加点１５６０について、各頂点に対して行った内外判定処理を行う。その結果、１５０１で示す状態であれば、この追加点１５６０は「領域１５０８の内部である」と判定される。一方、１５０２で示す状態であれば、１５５０で示す如く、この追加点１５６０は「領域１５１０、１５１１の外側である」と判定される。これにより、１５０１、１５０２といったそれぞれ異なった状態においても、分割境界矩形領域内で、境界形状データが示す領域の内側に属している部分、外側に属している部分を一意に特定することができる。
【００７４】
図１６は、以上説明した、分割境界矩形領域内で、境界形状データが示す領域の内側に属している部分、外側に属している部分を一意に特定する為の処理を示す図である。
【００７５】
図１６（ａ）において１６０１は分割境界矩形領域で、１６０２は境界形状データが示す領域を示す。先ず、分割境界矩形領域１６０１を構成するそれぞれの頂点が領域１６０２の内部に位置するのか、外部に位置するのかそれとも領域１６０２の境界上に位置するのかを判定する。その結果、左上隅の頂点のみが領域１６０２の外部に位置し、残りの３つの頂点が領域１６０２の内部に位置するので、左上隅の頂点に対しては内外判定値「２」を設定し、残りの３つの頂点のそれぞれに対しては内外判定値「１」を設定する。
【００７６】
次に、分割境界矩形領域１６０１の稜線（頂点を含む）と領域１６０２との交点を求める。その結果２つの交点が求まる。よって、内外判定値の配置関係、及び交点位置により、分割境界矩形領域１６０１内で領域１６０２の内部に属する部分と属していない部分とを示すパターンは１６１０で示すパターン、即ち、図１２に示した基本パターンのうち（ｋ）のパターンに一致する。これにより、分割境界矩形領域１６０１がどの基本パターンに一致するのかを決定することができる。
【００７７】
一方、図１６（ｂ）において１６０１は分割境界矩形領域で、１６０３は境界形状データが示す領域を示す。先ず、分割境界矩形領域１６０１を構成するそれぞれの頂点が領域１６０３の内部に位置するのか、外部に位置するのかそれとも領域１６０３の境界上に位置するのかを判定する。その結果、左上隅、右下隅の頂点のみが領域１６０３の外部に位置し、残りの２つの頂点が領域１６０３の内部に位置するので、左上隅、右下隅の頂点に対しては内外判定値「２」を設定し、残りの２つの頂点のそれぞれに対しては内外判定値「１」を設定する。次に、分割境界矩形領域１６０１の稜線（頂点を含む）と領域１６０３との交点を求める。その結果４つの交点が求まる。
【００７８】
しかし、このような場合、内外判定値の配置関係、及び交点位置だけでは、分割境界矩形領域１６０１内で領域１６０３の内部に属する部分と属していない部分とを一意に特定することはできない。そこでこのような場合には追加点を分割境界矩形領域１６０１の略中心部に設け、この追加点について内外判定処理を行う。その結果、この追加点は領域１６０３の内部に位置していると判断することができるので、この追加点に対して内外判定値「１」を設定する。これにより分割境界矩形領域１６０１内で領域１６０３の内部に属する部分と属していない部分とを示すパターンは１６２０で示すパターン、即ち、図１２に示した基本パターンのうち（ｏ）のパターンに一致する。これにより、分割境界矩形領域１６０１がどの基本パターンに一致するのかを決定することができる。
【００７９】
なお、分割境界矩形領域が何れの基本パターンとも一致しない場合には、予め指定された分割回数により生成される分割境界矩形領域の大きさが、境界形状に対して適切ではないと判断し、その旨を伝える警告文を表示し終了する。
【００８０】
図５に戻って、ステップＳ５０５で分割境界矩形領域に一致する基本パターンを決定すると、処理をステップＳ５０６に進め、分割境界矩形領域はこれに一致する基本パターンでもって、交点の接続と境界の内側外側が明確になっているため、後述する向き付けられた線分データを作成する（ステップＳ５０６）。
【００８１】
即ち、交点間を結ぶ線分のデータを作成する。なお、この線分は向き付けられているとする。即ち、二次元空間に存在する点ｖ１と点ｖ２によって構成されている線分は、［ｖ１ｖ２］と記述することを前提とする。従って、２次元空間に存在する点ｖ１と点ｖ２によって構成される線分は、［ｖ１ｖ２］と記述することによって、点ｖ１から点ｖ２へ向かうとき、右を外側、左を内側と定義する。
【００８２】
図１７において１７００を点ｖ１、１７０１を点ｖ２とすると、上側が内側で下側が外側ということになる。こうして生成された線分を定義するデータ（例えばｖ１ｖ２のように、順序付の線分の構成要素からなる）を以下、線分データと呼ぶ。
【００８３】
そして処理をステップＳ５０７に進め、未だ参照していない矩形領域（もしくは分割境界矩形領域）がある場合には処理をステップＳ５０２に戻し、次の矩形領域（もしくは分割境界矩形領域）について以降の処理を行うのであるが、全ての矩形領域（もしくは分割境界矩形領域）を参照した場合には本処理を終了する。
【００８４】
以上説明した処理により、１つの分割境界矩形領域内における境界部分を線分でもって表すことができるので、１つの分割境界矩形領域について１つの線分データを作成することができる。
【００８５】
次に、境界形状データが示す領域が以下の式が示す領域である場合に、以上説明した処理によって得られる領域の形状について説明する。
【００８６】
（ｙ−１．２ｘ＋０．１＞０）∩（ｙ−０．８ｘ−０．１＜０）∩
（ｙ−０．８ｘ＋０．１＞０）∩（ｙ−１．２ｘ−０．１＜０）∩
（ｙ＋１．２ｘ＋０．１＞０）∩（ｙ＋０．８ｘ−０．１＜０）∩
（ｙ＋０．８ｘ＋０．１＞０）∩（ｙ＋１．２ｘ−０．１＜０）
図２０は、このような式で表される領域を示す図である。同図において点線部分が各不等式を等式とした場合の直線で、実線部分で囲まれた領域が上記式が示す領域である。このような領域を２次元仮想平面上に設定し、その後この２次元仮想平面を矩形領域に分割した後に、境界矩形領域について対応する基本パターンを決定すると、境界矩形領域については基本パターンでもって表現することができ、その結果、図１に示した形状の領域が得られる。
【００８７】
即ち、このような尖鋭を有する多角形で表現される形状等、複雑な形状に対して、従来の方法では境界形状データの生成が困難であったが、本実施形態によると、容易に実現される。
【００８８】
また、以上の処理により得られた線分データに対し、図１９に示す処理を行う事により、従来法と同じく矩形領域内に１つの直線が通る場合に制限した線分データを作成することができる。図中のステップＳ１９００では、基本パターンとして図２に示す線分が１つ通るパターンを使用する。
【００８９】
また、本発明の目的は、前述した実施形態の機能を実現するソフトウェアのプログラムコードを記録した記録媒体（または記憶媒体）を、システムあるいは装置に供給し、そのシステムあるいは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記録媒体に格納されたプログラムコードを読み出し実行することによっても、達成されることは言うまでもない。この場合、記録媒体から読み出されたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコードを記録した記録媒体は本発明を構成することになる。
【００９０】
また、コンピュータが読み出したプログラムコードを実行することにより、前述した実施形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているオペレーティングシステム（ＯＳ）などが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【００９１】
さらに、記録媒体から読み出されたプログラムコードが、コンピュータに挿入された機能拡張カードやコンピュータに接続された機能拡張ユニットに備わるメモリに書込まれた後、そのプログラムコードの指示に基づき、その機能拡張カードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【００９２】
本発明を上記記録媒体に適用する場合、その記録媒体には、先に説明したフローチャートに対応するプログラムコードが格納されることになる。
【図面の簡単な説明】
【００９３】
【図１】図２０に示した領域を２次元仮想平面上に設定し、その後この２次元仮想平面を矩形領域に分割した後に、境界矩形領域について対応する基本パターンでもって表現した場合の形状の領域を示す図である。
【図２】基本パターンの例を示す図である。
【図３】境界形状データが示す形状の例を示す図である。
【図４】画像処理装置として機能するコンピュータのハードウェア構成を示すブロック図である。
【図５】分割された複数の矩形領域のうち、境界部分を含むものがある場合には、矩形内の境界部分を線形に近似するための処理のフローチャートである。
【図６】境界形状データが示す形状、及びその内外の例を示す図である。
【図７】境界形状データが示す形状、及びその内外の例を示す図である。
【図８】複数の矩形領域に分割された２次元仮想平面の一部の例を示す図である。
【図９】基本パターンを作成する為の処理のフローチャートである。
【図１０】線分が交差する可能性のあるパターンの例を示す図である。
【図１１】ステップ５で分けられる４つのパターンを示す図である。
【図１２】本発明の実施形態で用いる基本パターン群の例を示す図である。
【図１３Ａ】分割境界矩形領域１３０１の各頂点と領域１３０２との位置関係を説明する図である。
【図１３Ｂ】分割境界矩形領域１３０１の各頂点と領域１３０２との位置関係を説明する図である。
【図１４Ａ】分割境界矩形領域１３０１の稜線と領域１３０２との交点を示す図である。
【図１４Ｂ】分割境界矩形領域１３０１の稜線と領域１３０２との交点を示す図である。
【図１５】境界形状データが示す領域と分割境界矩形領域との位置関係がそれぞれ異なる位置関係である場合の、各頂点に設定した内外判定値の配置関係、交点位置を示す図である。
【図１６】分割境界矩形領域内で、境界形状データが示す領域の内側に属している部分、外側に属している部分を一意に特定する為の処理を示す図である。
【図１７】線分データを説明する図である。
【図１８】境界矩形領域の分割を説明する図である。
【図１９】矩形領域内に１つの直線が通る場合に制限した線分データを作成する為の処理のフローチャートである。
【図２０】領域の形状の例を示す図である。
【図１】
2006323780.tif 000003
【図２】
2006323780.tif 000004
【図３】
2006323780.tif 000005
【図４】
2006323780.tif 000006
【図５】
2006323780.tif 000007
【図６】
2006323780.tif 000008
【図７】
2006323780.tif 000009
【図８】
2006323780.tif 000010
【図９】
2006323780.tif 000011
【図１０】
2006323780.tif 000012
【図１１】
2006323780.tif 000013
【図１２】
2006323780.tif 000014
【図１３Ａ】
2006323780.tif 000015
【図１３Ｂ】
2006323780.tif 000016
【図１４Ａ】
2006323780.tif 000017
【図１４Ｂ】
2006323780.tif 000018
【図１５】
2006323780.tif 000019
【図１６】
2006323780.tif 000020
【図１７】
2006323780.tif 000021
【図１８】
2006323780.tif 000022
【図１９】
2006323780.tif 000023
【図２０】
2006323780.tif 000024