TOP > 国内特許検索 > 図形データ処理方法、図形データ処理プログラム及びそのプログラムを記録した記録媒体 > 明細書

明細書 :図形データ処理方法、図形データ処理プログラム及びそのプログラムを記録した記録媒体

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第3988945号 (P3988945)
公開番号 特開2005-122302 (P2005-122302A)
登録日 平成19年7月27日(2007.7.27)
発行日 平成19年10月10日(2007.10.10)
公開日 平成17年5月12日(2005.5.12)
発明の名称または考案の名称 図形データ処理方法、図形データ処理プログラム及びそのプログラムを記録した記録媒体
国際特許分類 G06T  11/60        (2006.01)
G06T  11/80        (2006.01)
G09B  29/00        (2006.01)
FI G06T 11/60 300
G06T 11/80 B
G09B 29/00 Z
請求項の数または発明の数 17
全頁数 27
出願番号 特願2003-354037 (P2003-354037)
出願日 平成15年10月14日(2003.10.14)
審査請求日 平成15年10月14日(2003.10.14)
特許権者または実用新案権者 【識別番号】501203344
【氏名又は名称】独立行政法人農業・食品産業技術総合研究機構
発明者または考案者 【氏名】飯嶋 孝史
【氏名】石田 憲冶
【氏名】松森 堅治
【氏名】嶺田 拓也
個別代理人の代理人 【識別番号】100091096、【弁理士】、【氏名又は名称】平木 祐輔
【識別番号】100105463、【弁理士】、【氏名又は名称】関谷 三男
【識別番号】100102576、【弁理士】、【氏名又は名称】渡辺 敏章
審査官 【審査官】橋爪 正樹
参考文献・文献 特開平10-021415(JP,A)
特開平11-258984(JP,A)
特開平01-273175(JP,A)
特開平07-200664(JP,A)
特開2000-148907(JP,A)
特開2003-288606(JP,A)
調査した分野 G06T11/00-11/80
G06T 7/00- 7/60
G06F17/50
特許請求の範囲 【請求項1】
図形データとプログラムを格納する記憶装置と、上記図形データを一時的に格納するRAMと、上記図形データを用いて上記プログラムを実行するCPUと、を有するコンピュータを用いて、平面領域を複数の多角形によって表す図形データを処理する図形データ処理方法において、
上記記憶装置から多角形の図形データを読出し、上記RAMに格納する図形データ読出ステップと、
自己交差する多角形を自己交点又は自己接点で分割して自己交差のない複数の多角形に変換する自己交差多角形分割ステップと、
互いに交差する複数の多角形を交差しない複数の多角形に変換する複数多角形の重複解消ステップと、
入れ子状の多角形のうち、内包関係にあり且つ面積の大きさの順番が隣接する2つの多角形の頂点列の方向が互いに逆向きになるように、頂点列を調整する入れ子状多角形頂点列方向調整ステップと、
を上記CPUによって実行し、
上記自己交差多角形分割ステップは、
自己交差する多角形の頂点列に自己交点又は自己接点に等しい頂点を挿入する頂点挿入ステップと、
上記自己交差する多角形の頂点列より座標値が等しい2個の頂点の組み合わせを探索する組み合わせ探索ステップと、
座標値が等しい2個の頂点が見出された場合に当該頂点で上記多角形を2分割する多角形分割ステップと、
上記2分割後の多角形の各々について自己交差がなくなるまで上記組み合わせ探索ステップ及び上記多角形分割ステップを繰り返すことと、
を含むことを特徴とする図形データ処理方法。
【請求項2】
請求項1記載の図形データ処理方法において、上記複数多角形の重複解消ステップは、上記自己交差多角形分割ステップによって得られた自己交差のない多角形の全てについて、多角形の頂点列の方向を判定する頂点列方向判定処理ステップと、
多角形の頂点列の方向を時計回り又は反時計回りに統一化する頂点列方向統一化処理ステップと、
一方の多角形の辺が他方の多角形の辺と交差する2個の多角形の組み合わせ、又は、一方の多角形の頂点が他方の多角形の辺に接する2個の多角形の組み合わせ、を探索する交点探索処理ステップと、
該交点探索処理ステップにて検出された2個の多角形の頂点列に交点又は接点の座標値に等しい頂点を挿入する頂点挿入処理ステップと、
互いに交差する2個の多角形を探索する多角形重畳検索処理ステップと、
交差する2個の多角形を頂点追跡法の原理により結合領域を囲む多角形と穴領域を囲む多角形に変換する多角形変換ステップと、
上記交差する2個の多角形の組み合わせがなくなるまで上記多角形重畳検索処理ステップと上記多角形変換ステップを繰り返すことを特徴とする図形データ処理方法。
【請求項3】
請求項記載の図形データ処理方法において、上記頂点列方向判定処理ステップは、
多角形の頂点列のうち、x座標値が最小の頂点p2と、当該頂点列におけるその直前の頂点p1及び直後の頂点p3を選び、ベクトルp2p1とベクトルp2p3の外積Gを計算することと、
上記外積Gが非ゼロの場合には、その正負により当該頂点列の回転方向を判定することと、
上記外積Gがゼロの場合には頂点p2と頂点p3、又は頂点p2と頂点p1のy座標値の大小関係により当該頂点列の回転方向を判定することと、
を含むことを特徴とする図形データ処理方法。
【請求項4】
請求項記載の図形データ処理方法において、上記多角形重畳検索処理ステップは、
上記頂点挿入処理ステップによって得られた座標値が等しい頂点が挿入された2個の多角形の頂点列において、一方の多角形の頂点列における当該頂点と、その直前及び直後の頂点を結ぶ線分上に任意の2個の点を選ぶ2点選択ステップと、
上記2点選択ステップにて選んだ2個の点の一方が他方の多角形の内部にあり、かつ、2個の点の他方が他方の多角形の外部にある場合に、当該頂点は交点であると判定する交点判定ステップと、
該交点判定ステップにて当該頂点は交点であると判定されないとき当該頂点は接点であると判定する接点判定ステップと、を含むことを特徴とする図形データ処理方法。
【請求項5】
請求項記載の図形データ処理方法において、上記交点判定ステップにおいて、2個の点の一方が他方の多角形の内部にあり、かつ、2個の点の他方が他方の多角形の外部にあると判定する工程は、
判定対象点を端とする半直線を引く半直線ステップと、
隣接する任意の2つの頂点を始点候補及び終点候補として選択し、該始点候補及び終点候補が上記半直線を含む直線上にあるか否かを判定し、上記始点候補及び上記終点候補が上記半直線を含む直線上にない場合には、上記始点候補及び上記終点候補を始点及び終点に選定する始点終点選定ステップと、
上記始点終点選定ステップにて、上記始点候補が上記半直線を含む直線上にあると判定された場合には、上記始点候補から頂点を1つずつ順次後退させ、上記半直線を含む直線上にない最初の頂点が見つかったらそれを始点とする始点選定ステップと、
上記始点終点選定ステップにて、上記終点候補が上記半直線を含む直線上にあると判定された場合には、上記終点候補から頂点を1つずつ順次前進させ、上記半直線を含む直線上にない最初の頂点が見つかったらそれを終点とする終点選定ステップと、
上記始点終点選定ステップ、又は、上記始点選定ステップ及び終点選定ステップにて選定された始点と終点の間を「判定対象の辺の範囲」に選定する判定対象の辺の範囲選定ステップと、
上記判定対象の辺の範囲にて、上記半直線が多角形と交差するか否かを判定する交差判定ステップと、
該交差判定ステップにて、上記半直線が多角形と交差すると判定された場合には交差回数を1増加し、交差しないと判定された場合には交差回数をそのままにする交差計数ステップと、
上記始点終点選定ステップ、上記始点選定ステップ、上記終点選定ステップ、上記判定対象の辺の範囲選定ステップ、上記交差判定ステップ及び上記交差計数ステップを、多角形の全周に渡って、順次繰り返す繰返しステップと、
上記交差計数ステップにて計数した交差回数が偶数である場合には、判定対象点は多角形の外部にあると判定し、交差回数が奇数である場合には、判定対象点は多角形の内部にあると判定する判定対象点判定ステップと、
を含むことを特徴とする図形データ処理方法。
【請求項6】
請求項1記載の図形データ処理方法において、上記入れ子状多角形頂点列方向調整ステップは、
上記複数の多角形がn個の多角形であるとし、該n個の多角形のうち面積最大の多角形を選択し、該面積最大の多角形とそれより面積が小さい全ての多角形との間の内包関係を調べる第1の内包関係検索ステップと、
上記面積最大の多角形を表す頂点列を時計回り又は反時計回りにし、上記面積最大の多角形に内包される全ての多角形の頂点列を上記面積最大の多角形を表す頂点列の方向とは逆の方向にし、上記面積最大の多角形に内包されない全ての多角形の頂点列を上記面積最大の多角形を表す頂点列の方向と同一の方向にする第1ステップと、
上記n個の多角形のうちk(k=2~n-1)番目に面積が大きい多角形を選択し、該k番目に面積が大きい多角形とそれより面積が小さい全ての多角形との間の内包関係を調べる第2の内包関係検索ステップと、
上記k番目に面積が大きい多角形の頂点列はそのままにし、上記k番目に面積が大きい多角形に内包される全ての多角形の頂点列の方向を反転し、上記k番目に面積が大きい多角形に内包されない且つ上記k番目に面積が大きい多角形より面積が小さい多角形の頂点列はそのままにする第2のステップと、
を含み、上記第2の内包関係検索ステップ及び第2のステップをインデックスkを2から1ずつ増やしながらn-1まで処理を繰り返すことを特徴とする図形データ処理方法。
【請求項7】
請求項記載の図形データ処理方法において、上記入れ子状多角形検索ステップの第1及び第2の内包関係検索ステップは、
内包関係を調べる対象として互いに交わらない2個の多角形を設定することと、
該2個の多角形のうち面積が小さい方の多角形と面積が大きい方の多角形を判定することと、
面積が小さい方の多角形の少なくとも1個の頂点が面積が大きい方の多角形の外部にある場合には面積が小さい方の多角形は面積が大きい方の多角形に内包されないと判定することと、
面積が小さい方の多角形の全ての頂点が面積が大きい方の多角形の内部にある場合には面積が小さい方の多角形は面積が大きい方の多角形に内包されると判定することと、
を含むことを特徴とする図形データ処理方法。
【請求項8】
請求項1~のいずれか1項記載の図形データ処理方法をコンピュータに実行させるためのコンピュータにより読み取り可能なプログラム。
【請求項9】
請求項記載のプログラムを格納したコンピュータにより読み取り可能な媒体。
【請求項10】
図形データとプログラムを格納する記憶装置と、上記図形データを一時的に格納するRAMと、上記図形データを用いて上記プログラムを実行するCPUと、を有するコンピュータを用いて、自己交差する多角形を分割するための図形データ処理方法において、
上記記憶装置から多角形の図形データを読出し、上記RAMに格納する図形データ読出ステップと、
多角形を表す頂点列より座標値が等しい連続する複数の頂点があったとき、該連続する複数の頂点より1個の頂点を残し他の頂点を削除する重複頂点削除ステップと、
多角形を表す頂点列より多角形の辺と辺が交差する自己交点及び頂点が辺と接する自己接点の座標値を求める交点等座標値検出ステップと、
多角形の頂点列に上記自己交点及び自己接点の座標値に等しい頂点を挿入する頂点挿入ステップと、
上記頂点列より座標値が等しい2個の頂点の組み合わせを探索する組み合わせ探索ステップと、
座標値が等しい2個の頂点が見出された場合に当該頂点で上記多角形を2分割する2分割ステップと、
上記2分割後の多角形の各々について自己交差がなくなるまで上記組み合わせ探索ステップ及び上記2分割ステップを繰り返すことと、
を上記CPUによって実行することを特徴とする図形データ処理方法
【請求項11】
請求項10に記載の図形データ処理方法をコンピュータに実行させるためのコンピュータにより読み取り可能なプログラム。
【請求項12】
請求項11に記載のプログラムを格納したコンピュータにより読み取り可能な媒体。
【請求項13】
図形データとプログラムを格納する記憶装置と、上記図形データを一時的に格納するRAMと、上記図形データを用いて上記プログラムを実行するCPUと、を有するコンピュータを用いて、頂点列によって表される多角形と判定対象点が与えられたとき該判定対象点が上記多角形の内部にあるか又は外部にあるかを判定する図形データ処理方法において、
上記記憶装置から多角形の図形データを読出し、上記RAMに格納する図形データ読出ステップと、
判定対象点を端とする半直線を引く半直線ステップと、
隣接する任意の2つの頂点を始点候補及び終点候補として選択し、該始点候補及び終点候補が上記半直線を含む直線上にあるか否かを判定し、上記始点候補及び上記終点候補が上記半直線を含む直線上にない場合には、上記始点候補及び上記終点候補を始点及び終点に選定する始点終点選定ステップと、
上記始点終点選定ステップにて、上記始点候補が上記半直線を含む直線上にあると判定された場合には、上記始点候補から頂点を1つずつ順次後退させ、上記半直線を含む直線上にない最初の頂点が見つかったらそれを始点とする始点選定ステップと、
上記始点終点選定ステップにて、上記終点候補が上記半直線を含む直線上にあると判定された場合には、上記終点候補から頂点を1つずつ順次前進させ、上記半直線を含む直線上にない最初の頂点が見つかったらそれを終点とする終点選定ステップと、
上記始点終点選定ステップ、又は、上記始点選定ステップ及び終点選定ステップにて選定された始点と終点の間を「判定対象の辺の範囲」に選定する判定対象の辺の範囲選定ステップと、
上記判定対象の辺の範囲にて、上記半直線が多角形と交差するか否かを判定する交差判定ステップと、
該交差判定ステップにて、上記半直線が多角形と交差すると判定された場合には交差回数を1増加し、交差しないと判定された場合には交差回数をそのままにする交差計数ステップと、
上記始点終点選定ステップ、上記始点選定ステップ、上記終点選定ステップ、上記判定対象の辺の範囲選定ステップ、上記交差判定ステップ及び上記交差計数ステップを、多角形の全周に渡って、順次繰り返す繰返しステップと、
上記交差計数ステップにて計数した交差回数が偶数である場合には、判定対象点は多角形の外部にあると判定し、交差回数が奇数である場合には、判定対象点は多角形の内部にあると判定する判定対象点判定ステップと、
を上記CPUによって実行することを特徴とする図形データ処理方法
【請求項14】
請求項13記載の図形データ処理方法において、上記交差判定ステップは、
上記半直線の方向をy軸の正の方向に設定するとき、判定対象点のx座標値が上記始点のx座標値と上記終点のx座標値の間にあるか否かを判定するx座標値判定ステップと、
上記x座標値判定ステップにて、判定対象点のx座標値が上記始点のx座標値と上記終点のx座標値の間にないと判定された場合には、上記交差判定ステップを終了する終了ステップと、
上記x座標値判定ステップにて、判定対象点のx座標値が上記始点のx座標値と上記終点のx座標値の間にあると判定された場合で、上記始点と上記終点が多角形の連続する2頂点である場合には、上記始点と上記終点を結ぶ直線と上記半直線を含む直線の交点のy座標値と判定対象点のy座標値とを比較し、上記始点又は上記終点が上記始点選定ステップ又は終点選定ステップにて選定された頂点である場合には、上記始点と上記終点の間にある頂点のy座標値と判定対象点のy座標値とを比較するy座標値比較ステップと、
上記y座標値比較ステップにおける比較結果から、上記判定対象の辺の範囲にて上記半直線が多角形と交差するか否かを判定する比較結果交差判定ステップと、
を有することを特徴とする図形データ処理方法
【請求項15】
請求項13記載の図形データ処理方法において、上記始点終点選定ステップは、2回目以降のループでは、前回のループにおける終点を始点として選択し、該始点から頂点を1つ前進させた頂点を終点候補として選択し、該終点候補が上記半直線を含む直線上にあるか否かを判定し、上記終点候補が上記半直線を含む直線上にない場合には、上記終点候補を終点とし、上記終点候補が上記半直線を含む直線上にある場合には、上記終点候補から頂点を1つずつ順次前進させ、上記半直線を含む直線上にない最初の頂点が見つかったらそれを終点とすることを特徴とする図形データ処理方法
【請求項16】
請求項1315のいずれか1項記載の図形データ処理方法をコンピュータに実行させるためのコンピュータにより読み取り可能なプログラム。
【請求項17】
請求項16記載のプログラムを格納したコンピュータにより読み取り可能な媒体。
発明の詳細な説明 【技術分野】
【0001】
本発明は、平面領域を多角形として表示する図形データの処理方法に関し、特に、地理情報システムで使用する図形データを修正するための図形データ処理方法に関する。
【背景技術】
【0002】
地理情報システムで使用するデータ形式として広く採用されているシェープファイル形式では、例えば市町村の区域のような飛び地や穴のある平面領域を次の規則に従って複数の多角形で表すこととしている。
(1) 多角形が自己交差しないこと。
(2) 多角形同士が交差しないこと。なお、頂点で接しても良いが、辺を共有してはならない。
(3) 多角形の頂点列の方向に対して右側を当該多角形が表そうとする平面領域の内部としていること。
(4) 多角形が閉じていること。つまり、多角形の頂点列の始点と終点が同じ座標値であること。
【0003】
しかし、地理情報システムで使われるデータはデジタイザ等を用いて手動操作により地図から読み込んで作成することも多く、細部にわたって完璧に上記規則に従ったものとするのは困難であり、部分的に規則に従わないデータが混在する場合がある。そして、たとえごく一部であっても規則に従わないデータが混在している場合には、地理情報システムはそれを正常に処理できないことがあり、また、多量のデータの中から規則に従わない部分を検出して修正するのには多大な労力を要するという問題がある。

【特許文献1】特開昭61-180378号公報
【特許文献2】特開平10-154237号公報
【特許文献3】特開平10-21367号公報
【発明の開示】
【発明が解決しようとする課題】
【0004】
本発明は、地理情報システムによって表示、加工等の処理を行うことを目的として作成された平面領域を表すデータについて、上記規則に従わない部分があった場合に自動的に修正する図形データ処理方法を提供することを目的とするものである。
【課題を解決するための手段】
【0005】
本発明は、多角形をx座標値とy座標値からなる頂点データの配列(以下「頂点列」という)で表し、複数の多角形によってひとつの平面領域を構成するような形式のデータが与えられたとき、1個の平面領域のデータに対して次の処理を行う。
(1) 自己交差多角形分割処理
当該平面領域を構成する多角形のうち、自己交点又は自己接点(以下「カット点」という)を有する多角形について当該カット点で複数の多角形に分割する。図18(a)は自己交差多角形分割処理を行う前を示し、図18(b)は自己交差多角形分割処理を行った後を示す。
(2) 複数多角形の重複解消処理
当該平面領域を構成する多角形のうち、複数の多角形が交差して領域の一部で重なり合う場合(辺の一部を共有する場合を含む。以下同じ)に、当該複数の多角形を重なり合いのない複数の多角形に変換する。詳細には、次の3つの処理を含む。(a)全ての頂点列の方向を統一する。(b)2個の多角形の間の交点又は接点(以下「交点等」という)を検索する。(c)重複した2個の多角形を複数の多角形に変換する。こうして得られた複数の多角形より必要なものを選択する。図19(a)は複数多角形の重複解消処理を行う前を示し、図19(b)は複数多角形の重複解消処理を行った後を示す。
(3) 入れ子状多角形頂点列方向調整処理
当該平面領域を構成する多角形のうち、複数の多角形が入れ子状になっている場合に、最も外側の多角形の頂点列の方向を時計回りとして、内側の多角形の頂点列の方向をそのすぐ外側の多角形の頂点列の方向の逆方向にする。図20(a)は頂点列方向調整処理を行う前を示し、図20(b)は頂点列方向調整処理を行った後を示す。
(4) 後処理
当該平面領域を構成する全ての多角形の頂点列の終点に、当該頂点列の始点と同じ座標値の頂点を追加する。
【0006】
上述の一連の処理を、全ての平面領域のデータに対して施し、処理後のデータを外部記憶媒体に保存する。
【発明の効果】
【0007】
本発明によると、平面領域を表すデータに含まれる不規則な部分を自動的に且つ簡単に修正するから、地理情報システムによって表示、加工等の処理を正常に行うことができる。
本発明によると、デジタイザ等を用いたデータ作成時に、規則をあまり気にせずに作成することができ、また、確認作業も省けることによって効率化できる。
【発明を実施するための最良の形態】
【0008】
図1は、本発明における図形データ処理方法を実行するための回路のブロック図である。本例の装置は、CPU11、ROM12、RAM13、及び入出力I/F回路14を有し、これらは、内部バス15を介して互いに接続されており、互いにデータの通信が可能である。CPU11は装置全体の制御を司り、ROM12には本発明を構成する各処理方法がプログラムの形態で格納され、RAM13には各処理方法が使用するデータが格納される。入出力I/F回路14は外部記憶装置16と接続されている。本例の装置は、外部記憶装置16を介して外部記憶媒体からデータを受け取るとともに、本例の装置による処理後のデータを外部記憶媒体に対して出力する。
【0009】
図2は、本装置による図形データ処理の全体の手順を示したものである。まず、ステップS10にて、外部記憶媒体からデータを読み込み、それをRAM13に格納する。ステップS11にて、全ての平面領域のデータについて処理が終了したかを判定し、終了していない場合には、ステップS20にて、RAM13に格納されたデータより、平面領域を単位としてデータを取り出す。ステップS21にて、自己交差多角形分割処理を行い、ステップS22にて、複数多角形の重複解消処理を行い、ステップS23にて、入れ子状多角形頂点列方向調整処理を行い、ステップS24にて、後処理を施す。ステップS11にて、全ての平面領域のデータについてこれらの処理が終了したと判定したら、ステップS30にて、処理後のデータを外部記憶媒体に保存する。
【0010】
以下、本発明における図形データ処理方法について詳述する。
(1) 自己交差多角形分割処理
特開平10-154237号公報には、y軸方向に対して凸な多角形を対象として自己交差する多角形を自己交点で分割する方法が提案されている。しかし、本発明が対象とする多角形は、地理情報システムによる処理の対象であり、形状に制約条件のない一般の多角形であるから、特開平10-154237号公報の方法は適用できない。
【0011】
図3を参照して、本発明による自己交差多角形分割処理の概要を説明する。図3(a)の多角形は、頂点p1が辺p3p4と接しており、辺p3p4と辺p5p0が交差している。図3(b)には、自己接点をc1、自己交点をc2としてそれらの位置を示した。まず、接点c1の座標値(この場合は頂点p1の座標値に等しい)と交点c2の座標値を求める。接点c1及び交点c2が存在する辺にそれぞれ、それらと座標値が等しい頂点を挿入する。すなわち、辺p3p4には接点c1の座標値に等しい頂点と交点c2の座標値に等しい頂点を挿入し、辺p5p0には、交点c2の座標値に等しい頂点を挿入する。尚、以下に、接点及び交点をカット点と称する。
【0012】
図3(c)は、このようにして元の多角形に頂点を挿入し、番号をふり直したものである。このような処理を施した後の多角形の頂点列には、1個のカット点につき、その座標値に等しい頂点が2個以上存在することになる。
【0013】
次に、この多角形について2個の頂点の組み合わせを番号の若い方から順番に調べていくと、頂点p1とp4の座標値が等しいこと、すなわちそれらがカット点に等しいことが見出される。そこで多角形をカット点p1とp4にて2分割すれば図3(d)と図3(e)の2個の多角形が得られる。さらに、図3(d)の頂点の番号をふり直して図3(f)となる。図3(f)において、同様に2個の頂点の組み合わせを調べると、頂点p2とp5がカット点に等しいことが見出されるので、そこで多角形を2分割すれば図3(g)と図3(h)の2個の多角形が得られる。
【0014】
本発明が提案する分割方法は、上記のように、対象とする多角形にカット点に等しい頂点を挿入した上で、頂点列における座標値が等しい2個の頂点の探索と当該頂点における頂点列の2分割を再帰処理によって繰り返すことにより、カット点が複数ある場合でも分割することを可能とするものである。
【0015】
以下、この方法を実現するための具体的な処理手順について述べる。
(1-1)頂点列において連続する複数の頂点が等しい場合には、それらのうち1個のみを残して他は削除する。
上記説明から分かるように、本発明における分割方法では、2個の頂点の座標値が等しい場合にカット点であると判定するため、処理前の多角形の頂点列のうち連続する2個の頂点(当該頂点列の終点と始点の組み合わせを含む。以下同じ)の座標値が等しい場合には正しく判定できない。
【0016】
そのため、前処理として、頂点列において連続する複数の頂点が等しい場合には、あらかじめ、それらのうち1個のみを残して他は削除することにより、連続する2頂点が重複しない頂点列に変換する。
【0017】
(1-2)カット点を探索し、探索したカット点の座標値に等しい頂点を頂点列の該当箇所に挿入する。
多角形の2辺の全ての組み合わせについて、2辺が交差するかどうか、又は一方の辺の端点が他方の辺上にあるかどうかを調べることによりカット点を探索する。カット点があった場合には、そのカット点の座標値に等しい頂点を頂点列の該当箇所に挿入する。
【0018】
図4及び図5を参照して、カット点の探索と頂点列にカット点に等しい頂点を挿入する処理の手順を説明する。ステップS400にて、多角形の頂点列{p0, p1, ..., pn-1}を選ぶ。ステップS401にて、頂点列に挿入すべき頂点の挿入位置の情報とその座標値を一時的に格納しておくための連想コンテナMを用意する。
【0019】
連想コンテナMのキーは、頂点の挿入位置の情報として、頂点を挿入する位置の直前の頂点の番号とする。連想コンテナMに格納するデータは、当該位置に挿入すべき頂点の集合とする。M[ i ]は点piとpi+1の間に挿入すべき頂点の集合を表し、M[ j ]は点pjとpj+1の間に挿入すべき頂点の集合を表す。
【0020】
ステップS401~S412、及び、ステップS420~S426はカット点の探索処理である。ステップS402~S406は、n個の頂点を1つずつ処理し、全ての頂点に対して処理が完了したかを判定する。全ての頂点に対して処理が完了していない場合には、ステップS407に進む。
【0021】
ステップS407にて、eiとejの傾きが等しいか否かを判定する。eiは頂点piとpi+1を端点とする辺、ejは、頂点pjとpj+1(j=n-1のときはp0)を端点とする辺である。
辺eiと辺ejの傾きが等しい場合には、ステップS408~S412に進み、辺eiと辺ejの傾きが等しくない場合には、ステップS420~S426に進む。
【0022】
ステップS408~S412では、辺eiと辺ejが同一線状にあり、且つ、頂点pjが辺ei上にある場合には、M[ i ]に頂点pjと等しい頂点を追加し、頂点piが辺ej上にある場合には、M[ j ]に頂点piと等しい頂点を追加する。ステップS420~S423では、辺eiと辺ejの傾きが同一でなく、且つ、頂点pjが辺ei上にある場合には、M[ i ]に頂点pjと等しい頂点を追加し、頂点piが辺ej上にある場合には、M[ j ]に頂点piと等しい頂点を追加する。ステップS424、S425では、辺eiと辺ejが交差する場合、M[ i ]及びM[ j ]に辺eiと辺ejの交点と等しい頂点を追加する。
【0023】
図5を参照する。ステップS4300~S4304は頂点列にカット点に等しい頂点を挿入する処理である。ステップS4301は、連想コンテナMに格納された全てのデータに対して処理を完了したか否かを判定する。全てのデータに対して処理が完了していない場合には、ステップS4302に進み、M[ i ]に頂点のデータが格納されているかどうかを判定する。M[ i ]に頂点のデータが格納されている場合(空でない)には、ステップS4304に進み、頂点piとpi+1の間にM[ i ]に格納されている頂点のデータを頂点piからの距離の昇順で挿入する。
【0024】
(1-3)多角形をカット点で分割する。
以上の処理を施した後の多角形よりカット点を検索し、カット点が存在する場合には、そこで多角形を分割する。カット点の検索は、その頂点列中に同じ座標値の頂点が2個以上あるかどうかを調べることによってなされる。このことを利用した多角形の分割の手順について図6のフローチャートを参照して説明する。
【0025】
図6を参照して、多角形よりカット点を検索し、多角形を分割する手順を説明する。ステップS500にて、多角形の頂点列V0{p0, p1, ..., pn-1}を選ぶ。ステップS501~S508は、座標値が等しい2個の頂点があるかどうかを調べる処理を、n個の頂点に対して順に行い、全ての頂点に対して処理が完了したかを判定する。ステップS507にて、座標値が等しい2個の頂点pi、pjが見つかった場合には、それらがカット点に等しい頂点であると判断できるので、ステップS510に進む。座標値が等しい2個の頂点が見つからなかった場合には、ステップS509に進み、当該多角形にはカット点がないと判断し、頂点列V0を更新後データに追加して終了する。ここで、更新後データとは、平面領域を表す全ての頂点列に対して分割処理が終了するまでの間、処理後の頂点列データを格納して保持しておくものである。
【0026】
ステップS510にて、頂点列V0の始点p0からpiの直前の頂点pi-1までの部分頂点列{p0, ..., pi-1}と、pjを始点として頂点列V0の終点pn-1までの部分頂点列{pj, ..., pn-1}を連結することにより頂点列{p0, ..., pi-1, pj, ..., pn-1}を作成してV1とし、頂点piを始点としてpjの直前の頂点pj-1までの部分頂点列{pi, ..., pj-1}をV2とする。これらが、頂点列V0をカット点pi、pjで2分割した多角形の頂点列である。
【0027】
ステップS511及びS512にて、このようにして作成された頂点列V1、V2をそれぞれ頂点列V0に読み替える。次に、図6の処理を再帰することにより、カット点がなくなるまで2分割が繰り返され、再帰処理が終了した時点で、全てのカット点で分割された複数の多角形の頂点列が更新後データに格納される。
【0028】
ステップS501の処理について説明する。処理前の多角形において連続する2辺が同じ直線上で重なっている場合、上記処理の過程において重なっている部分が分離され、その両端の2頂点だけからなる頂点列が生成される。これは、面積のない線分であり、平面領域を表すデータとしては不要なものなので、ステップS501にて、分割後の頂点列の頂点数が3個未満の場合は格納しないことにより排除する。
【0029】
(1-4)元の平面領域データにおける全ての頂点列に対して上記(1-1)~(1-3)の処理を施すことにより、自己交差しない複数の多角形の頂点列データに変換され、更新後データとして保持されているので、最後に、元の平面領域データを更新後データに置き換える。
【0030】
(2) 複数多角形の重複解消処理
2個の多角形の重なり合いを解消するには、それを複数の多角形に変換すればよい。このような多角形の変換方法として、従来、頂点追跡による方法が知られている。図7を参照して、頂点追跡による方法を説明する。例えば、図7(a)の2個の多角形A、Bが図7(b)のように重なり合うときに、それらの頂点列を再編して図7(c)~図7(e)に示すような複数の多角形に変換し、そのうち目的に応じて必要なものを利用すれば良い。
【0031】
先ず、図7(b)に示すように、多角形AとBの頂点列の向きを時計回りに統一し、多角形AとBの交点p1、p2、p3、p4を求める。次に、交点p1を出発点として多角形Aの頂点列をその方向に従って辿り、別の交点p4に達したところで多角形Bの頂点列に乗り換えて同様に辿り、出発点p1まで戻ると、図7(c)に示すように、多角形AとBの領域を結合した領域(以下、「結合領域」という)を囲む多角形が得られる。
【0032】
このように、ある交点を出発点として多角形Aの頂点列を辿り、別の交点に達したら多角形Bの頂点列に乗り換え、更に、次の交点に達したときに、そこが出発点でなければ再び多角形Aの頂点列に乗り換えて頂点列を辿る。このように、多角形AとBの頂点列を交点で交互に乗り換えて出発点に戻るまで辿ることによって多角形を作成する手順を、多角形A、Bの全ての辺を一回ずつ辿り終わるまで行うことにより、複数個の多角形に変換できる。それらの多角形は、図7(c)に示す時計回りのもので最大のものが多角形AとBの結合領域を囲む多角形、図7(d)に示すその他の時計回りものが多角形AとBが重なり合う領域(以下「重複領域」という)を囲む多角形、及び図7(e)に示す反時計回りのものが多角形AとBを結合してできた穴の領域(以下「穴領域」という)を囲む多角形に分類できる。もちろん、多角形AとBの位置関係によっては、穴領域は発生しないこともある。こうして得られた複数の多角形より必要に応じて1又は複数の多角形を選択する。
【0033】
なお、多角形A、Bの頂点列の方向がいずれも反時計回りである場合には、前記手順と同様の手順で生成される多角形について、その分類における頂点列の向きをそれぞれ逆方向に読み替えれば同じ結果となる。
【0034】
本発明における複数多角形の重複解消処理では、この頂点列追跡の方法によって、ひとつの平面領域を表す複数の多角形のうち、重なり合うものを結合領域を囲む多角形と穴領域を囲む多角形に変換する処理を行う。以下、具体的な処理手順について述べる。
【0035】
(2-1) 頂点列方向判定処理及び頂点列方向統一化処理
以上の説明から明らかなように、頂点追跡の方法で期待する結果を得るには、対象とする多角形の頂点列の方向が時計回り又は反時計回りのどちらかで統一されている必要がある。そこで、まず、前処理として、平面領域を構成する全ての頂点列についてその方向を判定し、反時計回りであると判定された頂点列について頂点列の順番を逆転させることにより、全ての頂点列の方向を時計回りに統一する。
【0036】
従来、多角形の頂点列の方向を判定する方法としては、ベクトルの外積を計算し、外積の正負によって方向を判定する方法が知られている。この方法では、先ず、x座標値が最小の頂点、x座標値が最大の頂点、y座標値が最小の頂点、y座標値が最大の頂点のうちいずれか1個(p2とする)を選び、当該頂点列における頂点p2の直前の頂点(p1とする)と直後の頂点(p3とする)を選ぶ。次に、ベクトルp2p1とp2p3の外積Gを計算し、外積Gの正負を判定する。
【0037】
具体的には、x軸の正の方向が右向き、y軸の正の方向が上向きの座標系における多角形について、前述のように選んだ頂点p1、 p2、 p3の座標値をそれぞれ(x1, y1)、(x2, y2)、(x3, y3)とすると、外積Gは式1によって求められ、外積Gが正の場合は当該多角形の頂点列の方向は時計回り、負の場合は反時計回りであると判定できる。
【0038】
G = p2p1 × p2p3 = (x1 - x2) × (y3 - y2) - (y1 - y2) × (x3 - x2) ・・・ (式1)
【0039】
しかし、この方法には外積Gが0になった場合には判定できないという問題がある。一般論として、ベクトルp2p1とp2p3の外積が0となるのは、点p1、点p2、点p3が全て同一直線上にある場合(いずれかの2点あるいは3点とも等しい場合を含む)である。ここで、点p1、p2、p3が前述の自己交差多角形分割処理を施した後の多角形の頂点であることを前提とすれば、3点p1、p2、p3はいずれも等しくないこと、及び辺p1p2と辺p2p3は重ならないことが保証されている。また、頂点列の方向を判定するうえで、x座標値が最小の頂点をp2とし、その直前の頂点をp1、直後の頂点をp3とすれば、点p2のx座標値は点p1及びp3のx座標値より大きくなることはない。したがって、ここでは、外積の計算結果が0の場合として、y軸に平行な直線上に3点p1、p2及びp3が{p1, p2, p3}又は{p3, p2, p1}の順番で並ぶ場合だけを考えればよい。以上の考察から、この問題は初等幾何学的な方法により解決できることが見出される。
【0040】
図8を参照して、多角形の頂点列の方向を判定し、反時計回りの場合に時計回りに変更する手順を説明する。ステップS700にて、多角形の頂点列V0を用意する。ステップS701にて、多角形の頂点列からx座標値が最小の頂点p2を選び、ステップS702にて、当該頂点列におけるその直前の頂点p1及び直後の頂点p3を選ぶ。ステップS703にて、ベクトルp2p1とp2p3の外積Gを計算する。ステップS704~S707にて、外積Gが非0であれば従来の方法によって判定を行う。即ち、外積Gが正なら、時計回りであると判定し、外積Gが負なら、反時計回りであると判定する。外積Gが0の場合は、上記考察よりy軸に平行な同一の直線上に頂点列{p1, p2, p3}又は{p3, p2, p1}の順番で並んでいると判断できる。従って、ステップS706にて、頂点p3のy座標値と頂点p2のy座標値を比較する。頂点p3のy座標値が頂点p2のy座標値よりも大きければ当該多角形の頂点列の方向は時計回り、小さければ反時計回りであると判定できる。頂点p2と頂点p1のy座標値を比較することによっても同様の判定ができることは言うまでもない。反時計回りである場合には、ステップS707にて、多角形の頂点列の順を逆転する。
【0041】
(2-2) 2個の多角形間の交点等の探索と頂点の挿入を行う。
次に、平面領域データから2個の多角形A、Bの頂点列Va、Vbを取り出し、2つの多角形AとBの間の交点又は接点(以下「交点等」という)を探索する。2個の多角形A、Bの辺の全ての組み合わせについて交差するかどうか、又は一方の辺の端点が他方の辺上にあるかどうかを調べる。交点等があった場合、その交点等に等しい頂点を頂点列VaとVbの該当箇所に挿入する。
【0042】
図9及び図10を参照して、2個の多角形の間の交点等の探索と頂点挿入の手順を説明する。ステップS800にて、2個の多角形の頂点列Va{pa0, pa1, ..., pana-1}、Vb{pb0, pb1, ..., pbnb-1}を選ぶ。頂点列Va、Vbは、それぞれna個、nb個の頂点を持つ多角形A、Bを表す。ステップS801にて、頂点列Va、Vbに挿入すべき頂点の挿入位置の情報とその座標値を一時的に格納しておくための連想コンテナMa、Mbを用意する。
【0043】
連想コンテナMa、Mbのキーは、頂点の挿入位置の情報として、頂点を挿入する位置の直前の頂点の番号とする。連想コンテナMa、Mbに格納するデータは、当該位置に挿入すべき頂点の集合とする。
Ma[ i ]は点paiとpai+1の間に挿入すべき頂点の集合を表し、Mb[ j ]は点pbjとpbj+1の間に挿入すべき頂点の集合を表す。
【0044】
ステップS802~S812、及び、ステップS820~S826は交点等の探索処理である。これらの処理は、図4のステップS402~S412及びS420~S426と同様であるが、図4の例では、同一の多角形におけるカット点を探索したが、図9の例では、異なる2個の多角形の間の交点等を探索する点が異なる。従って、本例では、eiは点paiとpai+1(i=na-1のときはpa0)を端点とする多角形Aの辺、ejは、点pbjとpbj+1(j=nb-1のときはpb0)を端点とする多角形Bの辺である。
【0045】
図10を参照する。ステップS8300~S8304及びステップS8400~S8404は頂点列に交点等に等しい頂点を挿入する処理である。ステップS8304では、頂点列Vaの頂点paiとpai+1の間にMa[ i ]に格納されている頂点のデータを頂点paiからの距離の昇順で挿入する。ステップS8404では、頂点列Vbの頂点pbjとpbj+1の間にMb[ j ]に格納されている頂点のデータを頂点pbjからの距離の昇順で挿入する。
【0046】
この処理を平面領域を構成する頂点列の全ての組み合わせについて行うことにより、任意の2個の多角形の間に交点等がある場合、当該2個の多角形の両方が必ず当該交点等に等しい頂点を有することとなる。
【0047】
(2-3) 以上の処理を施した後、平面領域データから重なり合う2個の多角形を表す頂点列を取り出し、前述の頂点追跡の方法によってそれらを結合領域を囲む多角形と穴領域を囲む多角形に変換して平面領域データを更新する処理を、更新後の平面領域データに属する頂点列の全ての組み合わせにおいて重なり合いがなくなるまで繰り返すことにより、当該平面領域データにおける複数の多角形の重なり合いを解消する。
【0048】
図11を参照して複数の多角形の重なり合いを解消する手順を説明する。ステップS900にて、平面領域データとして、n個の頂点列の集合{V0, V1, ..., Vn-1}を用意する。ステップS901~S907は、2個の頂点列が表す2個の多角形が重なり合うかどうかを調べる処理を、n個の頂点列に対して順に行い、全ての頂点列に対して処理が完了したかを判定する。ステップS905にて、2個の頂点列Vi、Vjが表す2個の多角形が重なり合う場合には、ステップS908に進む。
【0049】
ステップS908にて、頂点列ViのコピーVa、頂点列VjのコピーVbを作成し、平面領域データから、頂点列Vi、Vjを削除する。ステップS909にて、頂点列Va、Vbを頂点追跡法により、結合領域を囲む多角形と穴領域を囲む多角形に変換する。ステップS910にて、変換後の多角形の頂点列を平面領域データに追加する。ステップS911にて、更新後の平面領域データについて、再帰処理を行う。
【0050】
(2-4) 図11のステップS905における、2個の多角形が重なり合うかどうかを判定する処理を説明する。ここでは、2個の多角形の間に交点があるかどうかを調べ、交点がある場合には重なり合うと判定し、交点がない場合には重なり合わないと判定する。処理(2-2)を施した後の平面領域データでは、2個の多角形の間に交点又は接点がある場合、それらの多角形を表す2個の頂点列に、必ず同一の座標値を有する頂点が存在することが保証されている。従って、2個の頂点列についてそれぞれの頂点の座標値を調べ、同じ座標値の頂点が見出された場合に、それは交点又は接点であると判定できる。
【0051】
図12を参照して、その頂点が交点又は接点であると判定されたとき、その頂点が交点と接点のどちらであるかを判定する方法を説明する。まず、2個の多角形をA、Bとし、それらの頂点の座標値を調べ、点pに等しい頂点が多角形AとBの両方に存在する、すなわち、点pが多角形AとBの間の交点又は接点であると分かったとする。多角形Aにおける点pに等しい頂点とその直前の頂点を結ぶ辺上の任意の点m1と、点pに等しい頂点とその直後の頂点を結ぶ辺上の任意の点m2を選ぶ。
【0052】
そして、点m1とm2のいずれか一方が多角形Bの内部、他方が多角形Bの外部にある場合は点pは交点であり、点m1とm2の両方が多角形Bの外部又は内部にある場合は点pは接点であると判定する。例えば、図12(a)の場合は、点m1が多角形Bの内部、点m2が外部にあるからpは交点であり、図12(b)の場合は、点m1、m2が両方とも多角形Bの外部にあるから点pは接点であると判定できる。
【0053】
また、本発明の目的から、2個の多角形の辺が重なる場合も重複解消処理の対象としなくてはならないので、例えば、図12(c)のように多角形AとBの辺が重なっている場合の点pも交点として取り扱う必要がある。図12(c)の場合について前述のように選んだ点m1、m2と多角形Bとの位置関係を見ると、点m1は多角形Bの外部、点m2は多角形Bの辺上にある。ここで、多角形の辺上の点は当該多角形の内部であると定義すれば、図12(c)の場合の点m2は多角形Bの内部にあると言えるので、図12(a)の場合と同様に、図12(c)の場合における点pも交点であると判定できるようになる。
【0054】
このことから、本発明における図形データ処理方法においては、多角形の辺上の点は当該多角形の内部にあると定義し、また、それとの整合性から、多角形の頂点と等しい点も当該多角形の内部にあると定義する。なお、上記説明中の点m1、m2の選び方としては、処理の簡便さを考慮して、点pとその直前又は直後の頂点を結ぶ辺の中点を選ぶ方法などが考えられる。
【0055】
上記の方法で交点かどうかを判定するには、任意の点が多角形の内部にあるかどうかを判定しなければならない。従来、任意の点が多角形の内部にあるかどうかを判定する方法としては、鉛直線算法による内点判定法が知られている。
【0056】
鉛直線算法による内点判定法とは、判定の対象とする点(以下、判定対象点という)から任意の方向に半直線を引き、その半直線が対象とする多角形と交差する回数を数え、それが偶数(0を含む)ならば当該判定対象点は当該多角形の外部にあり、奇数ならば内部にあると判定するものである。
【0057】
図13を参照して、鉛直線算法による内点判定法の具体的な手順について説明する。まず、判定対象点p1、点p2、点p3から半直線L1、L2、L3を引く。次に、多角形と半直線L1、L2、L3の交差回数を計算する。多角形と半直線L1の交差回数を計算する場合には、先ず、交差回数の初期値を0とし、6個の辺を順番に、辺と半直線L1との交差の有無について調べ、交差する場合には交差回数を1増加させる。例えば、辺abは半直線L1と交差するので交差回数を1増加させ、辺bc、cd、de、efは、半直線L1と交差しないので交差回数を変更せず、辺faは再び半直線L1と交差するので交差回数を1増加させる。結局、交差回数2(偶数)が得られ、判定対象点p1は多角形の外部にあると判定できる。同様の手順により、半直線L2については交差回数1(奇数)が得られ、判定対象点p2は多角形の内部にあると判定できる。
【0058】
半直線L3は頂点bと頂点fを通る。このような場合に、その半直線が多角形と交差しているのか接しているのかを判別するために、特別な判定手順が必要となる。
具体的には、辺abについて調べたときには、半直線L3が辺abの終点bを通っていることと、辺abの始点aが半直線L3の方向に向かって左側にあることを記憶する。次に辺bcについて調べたときに、半直線L3が辺bcの始点bを通っていることと、辺bcの終点cが半直線L3の方向に向かって右側にあることを記憶する。それによって、半直線L3が通る頂点bの前後の頂点a及び頂点cが半直線L3の方向に向かって左側と右側に分かれていることが判明する。従って、半直線L3は頂点bでこの多角形と交差していると判定して交差回数を1増加させる。
【0059】
同様に、辺efについて調べたときには、半直線L3が辺fの終点fを通っていることと、辺efの始点eが半直線L3の方向に向かって左側にあることを記憶する。次に辺faについて調べたときに、半直線L3が辺faの始点fを通っていることと、辺faの終点aが半直線L3の方向に向かって左側にあることを記憶する。それによって、半直線L3が通る頂点fの前後の頂点e及び頂点aが半直線L3の方向に向かって同じ側にあることが判明する。従って、半直線L3は頂点fでこの多角形と接していると判定して交差回数は変更しない。
【0060】
このような特別な判定手順を回避するために、例えば、特開昭61-180378号公報では、判定に用いる半直線が頂点を通る場合には、その半直線から平行にわずかに離れた位置、又は、判定対象点を中心としてわずかな角度回転させた位置に、多角形のどの頂点も通らない第2の半直線を設けて、第2の半直線と多角形の辺の交差回数を数える方法が提案されている。
【0061】
前述のように、本発明における図形データ処理方法においては、多角形の辺上の点及び頂点と等しい点は当該多角形の内部にあると定義した。ここでは、従来の鉛直線算法による内点判定法によって、これを検証する。
【0062】
図14を参照して説明する。判定対象点p4、p5はいずれも多角形の辺上にあり、それらから半直線L4、L5を引く。半直線L4と多角形の辺との交差回数は、判定対象点p4における交差を含めて2回、半直線L5と多角形の辺との交差回数は、判定対象点p5における交差だけであり1回である。従って、判定対象点p4は多角形の外部、判定対象点p5は多角形の内部と判定される。また、判定対象点は半直線に含まないと定義すると、半直線L4と多角形の辺との交差回数は1回、半直線L5と多角形の辺との交差回数は0回となり、判定結果は逆になる。
さらに、半直線を引く方向をさまざまに変えた場合を考えると、判定対象点p4とp5についての判定結果は不定であることは明らかである。
【0063】
以上の検討から、従来の方法では、判定対象点を半直線に含むかどうかについてどのように定義しても、又は、半直線を引く方向をどのようにしても、辺上にある点について多角形の内部にあると判定することはできないことが分かる。特開昭61-180378号公報で提案されている方法も、この問題を解決するものではないことは明らかである。
【0064】
(2-5) そこで、本発明では、鉛直線算法による内点判定法の原理を基本としつつ、次に述べるように、多角形の辺上の点及び頂点と等しい点を当該多角形の内部であると判定する手順を備えた内点判定法を提供する。
まず、鉛直線算法による内点判定法の原理に基づき、判定対象点から引いた半直線と多角形との周との交差回数を計数する手順について説明する。
【0065】
判定対象点をpt(xt, yt)、多角形の頂点数をn、頂点列を{p0, p1, ... pi, ... pn-1}とし、鉛直線算法による内点判定に用いる半直線Ltを判定対象点ptからy軸と平行に且つy軸に正の方向に引く。
【0066】
交差回数の初期値を0としたうえで、頂点pn-1を開始点とし、多角形の全周について、原則として辺を単位として調べていき、以下に説明する交差判定方法によって、半直線Ltと多角形の周が交差すると判定されたときに交差回数を1ずつ増加させることによって、交差回数を計数する。
【0067】
上記半直線Ltと多角形の周の交差判定は、当該多角形のある辺についてみたとき、当該辺の両端の頂点が、いずれも判定対象点ptを通るy軸に平行な直線 x = xt 上にない場合(以下「ケースA」という)には、半直線Ltと当該辺が交差するか否かを判定することによって行い、当該辺の両端の頂点のいずれかが直線 x = xt 上にある場合(以下「ケースB」という)には、当該直線 x = xt 上にある頂点を間に挟み、かつ、直線 x = xt 上にない頂点を始点及び終点とする連続した複数の辺の範囲を選定し、当該辺の範囲において半直線Ltと多角形の周が交差するか否かを判定することによって行うことを基本とする。
ただし、判定対象点ptは多角形のどの頂点とも等しくなく、かつ、多角形のy軸に平行な辺上にはないものとする。
【0068】
判定対象点ptが多角形の頂点のいずれかと等しい場合、あるいは、多角形のy軸に平行な辺上にある場合は、上記基本方針による交差判定手順は適用できないからであり、そのような場合の処理については、ケースCとして後述する。
【0069】
ケースA
多角形のある辺pipi+1を見たとき、その両端の頂点が、いずれも直線 x = xt 上にない場合をケースAとする。
この場合は、半直線Ltと辺pipi+1が交差するか否かによって、頂点piとpi+1の間で半直線Ltが多角形の周と交差するか否かを判定する。
【0070】
その方法を、図15(a)、図15(b)を参照して説明する。まず、判定対象点ptのx座標値xtが、辺の始点piのx座標値xiと、辺の終点pi+1のx座標値xi+1の範囲内にあるか否かを調べる。
【0071】
判定対象点ptのx座標値xtが辺の始点piのx座標値xiと終点pi+1のx座標値xi+1の範囲外にある場合は、半直線Ltと辺pipi+1が交差することはないと判定できるで、交差回数を変更せずに、次の辺pi+1pi+2についての交差判定に移る。
判定対象点ptのx座標値xtが辺の始点piのx座標値xiと終点pi+1のx座標値xi+1の範囲内にあれば、半直線Ltと辺pipi+1が交差する可能性があると判定できる。
【0072】
図15(a)、図15(b)は、いずれも判定対象点ptのx座標値xt が辺の始点piのx座標値xiと終点pi+1のx座標値xi+1の範囲内にあるので、半直線Ltと辺pipi+1が交差する可能性があると判定できる場合の例である。
【0073】
このように、半直線Ltと辺pipi+1が交差する可能性があると判定された場合には、次に、判定対象点ptを通るy軸に平行な直線 x = xt と辺pipi+1の交点pcのy座標値ycを求め、それと判定対象点のy座標値ytとの大小関係を調べる。
【0074】
図15(a)のように、交点pcのy座標値ycが判定対象点のy座標値ytより大きい、即ち、yc>ytならば、半直線Ltは辺pipi+1と交差すると判定し、交差回数を1増加させ、次の辺pi+1pi+2についての交差判定に移る。
【0075】
図15(b)のように、交点pcのy座標値ycが判定対象点のy座標値ytより小さい、即ち、yc<ytならば、半直線Ltは辺pipi+1と交差しないと判定し、交差回数を変更せずに、次の辺pi+1pi+2についての交差判定に移る。交点pcのy座標値ycが判定対象点のy座標値ytに等しい、即ち、yc=yt のときは、判定対象点ptは辺pipi+1上にあるので、ptは多角形の辺上にあると判定する。
【0077】
ここで、本発明においては、前述のように多角形の辺上の点は、多角形の内部にあると定義したので、判定対象点ptが多角形の辺上にあると判定された場合には、判定対象点ptは多角形の内部にあると判定して、内点判定処理を終了する。
【0078】
ケースB
多角形のある辺pipi+1を見たとき、その両端のうち、いずれか一方の頂点が、直線 x = xt上にある場合をケースBとする。
まず、辺pipi+1の終点pi+1が、直線 x = xt上にある場合、すなわち、判定対象点ptのx座標値xtと終点pi+1のx座標値xi+1が等しい場合について考える。
【0079】
この場合は、頂点pi+1において半直線Ltが多角形の周と交差する可能性があるが、半直線Ltと辺pipi+1の相対的な位置関係を調べるだけでは、交差するのか接するだけなのかを判別することはできない。
【0080】
そこで判定対象点ptのx座標値xtと終点pi+1のx座標値xi+1が等しい場合、即ち、xt = xi+1の場合には、頂点piを始点とし、頂点pi+1から出発して1個ずつ頂点を前進させていき、最初に直線 x = xt上からはずれた頂点を終点とする、連続した複数の辺を選定し、当該連続する複数の辺の範囲において、半直線Ltが多角形の周と交差するか否かを判定することとする。
【0081】
ここで、ケースAの場合の単一の辺も、上記のように選定した連続した複数の辺も、半直線Ltと交差するか否かの判定対象とする多角形の周の一部であるという意味においては同じものであるので、以下の説明において、両者を総称して「判定対象の辺の範囲」と言うこととする。
【0082】
図15(c)、図15(d)、図15(e)、図15(f)を参照して、ケースBの場合の「判定対象の辺の範囲」の終点の選定手順と、当該「判定対象の辺の範囲」において半直線Ltが多角形の周と交差するか否かの判定手順について説明する。
【0083】
図15(c)、図15(d)、図15(e)、図15(f)の辺pipi+1についてみたとき、xt = xi+1なので、頂点pi+1から出発して1個ずつ頂点を前進させていき、最初に直線 x = xt上からはずれた頂点を「判定対象の辺の範囲」の終点として選ぶ。
【0084】
以下、このように選んだ「判定対象の辺の範囲」の終点をpeで表すこととする。例えば、図15(c)、図15(d)では頂点pi+2を、図15(e)、図15(f)では頂点pi+3を、終点peに選ぶことになる。
【0085】
次に、判定対象点ptのx座標値xtが、「判定対象の辺の範囲」の始点piのx座標値xiと終点peのx座標値xeの範囲内にあるか否かを調べる。
図15(f)のように、判定対象点ptのx座標値xtが始点piのx座標値xiと終点peのx座標値xeの範囲内になければ、半直線Ltが始点piと終点peの間で多角形の周と交差する可能性がないと判定できるので、交差回数を変更せずに、このときの終点peを始点とする次の「判定対象の辺の範囲」についての交差判定に移る。
【0086】
図15(c)、図15(d)、図15(e)のように、判定対象点ptのx座標値xtが始点piのx座標値xiと終点peのx座標値xeの範囲内にあれば、半直線Ltが「判定対象の辺の範囲」pipeの間で多角形の周と交差する可能性があると判定できる。
【0087】
図15(c)、図15(d)、図15(e)のように、半直線Ltが「判定対象の辺の範囲」pipeにおいて多角形の周と交差する可能性があると判定された場合には、始点piと終点peの間の頂点(直線 x = xt上にある)のy座標値と、判定対象点ptのy座標値ytとの大小関係を調べる。
【0088】
図15(c)、図15(d)の例では、始点piと終点pe(=pi+2)の間の頂点はpi+1の1個だけなので、頂点pi+1のy座標値yi+1と判定対象点ptのy座標値ytとの大小関係を調べればよい。
図15(e)の例では、始点piと終点pe(=pi+3)の間の頂点は、pi+1, pi+2の2個であるが、それらのy座標値と判定対象点ptのy座標値ytとの大小関係は一様である。
【0089】
さらに、始点piと終点peの間の頂点が3個以上あることも想定できるが、その場合でも、頂点pi+1は必ずそれらの頂点の内の1個であり、かつ、それらの頂点のy座標値と判定対象点ptのy座標値ytとの大小関係は一様である。
【0090】
したがって、始点piと終点peの間の頂点が複数ある場合でも、頂点pi+1でそれらを代表させ、頂点pi+1のy座標値yi+1と判定対象点ptのy座標値ytとの大小関係を調べることとする。
【0091】
頂点pi+1のy座標値yi+1と判定対象点ptのy座標値ytの大小関係を調べた結果、図15(c)、図15(e)のように、yi+1>ytならば、半直線Ltは、「判定対象の辺の範囲」pipeにおいて多角形の周と交差すると判定できるので、交差回数を1増加させ、このときの終点peを始点とする次の「判定対象の辺の範囲」についての交差判定に移る。
【0092】
図15(d)の例のように、yi+1<ytならば、半直線Ltは、「判定対象の辺の範囲」pipeにおいて多角形の周と交差しないと判定できるので、交差回数を変更せずに、このときの終点peを始点とする次の「判定対象の辺の範囲」についての交差判定に移る。【0093】
また、「判定対象の辺の範囲」の始点は、直前の処理における「判定対象の辺の範囲」の終点である。したがって、原則として、「判定対象の辺の範囲」の始点が直線 x = xt上にあることはないことが分かる。
【0094】
ただし、計数処理を始めるときの開始点pn-1だけは、直線 x = xt上にある可能性がある。そこで、pn-1が直線 x = xt上にある場合をケースBの特殊ケースとして扱うこととし、その場合の「判定対象の辺の範囲」の設定手順と、当該「判定対象の辺の範囲」において半直線Ltと多角形の周と交差するか否かの判定手順について説明する。
【0095】
まず、開始点pn-1から出発して頂点を1個ずつ遡り、最初に直線 x = xt上からはずれた頂点を選ぶ。例えば、頂点pn-2が直線 x = xt上になければ、頂点pn-2を選び、頂点pn-2もまた直線 x = xt上にあれば、さらに頂点を1個遡る、という処理を繰り返せばよい。
このように選んだ頂点が、開始点pn-1が直線 x = xt上にあった場合の「判定対象の辺の範囲」の始点であり、以下、psで表すこととする。
この場合、多角形の周と半直線Ltの交差回数の計数処理の開始点もpsに変更されたことになる。
【0096】
頂点pn-1が直線 x = xt上にあった場合の最初の「判定対象の辺の範囲」の終点について説明する。上記のように最初の「判定対象の辺の範囲」の始点psが選ばれた時点で、その終点は頂点p0に仮定されている。ここで、頂点p0が直線 x = xt上になければ、頂点p0を最初の「判定対象の辺の範囲」の終点peとして決定する。
【0097】
しかし、頂点p0もまた直線 x = xt上にあった場合には、前述の「判定対象の辺の範囲」の終点を選ぶ手順によって、頂点p0から出発して頂点を1個ずつ前進させ、最初に直線 x = xt上からはずれた頂点を、最初の「判定対象の辺の範囲」の終点peとして選ばよい。
【0098】
次に、以上のように設定された最初の「判定対象の辺の範囲」pspeにおいて、半直線Ltと多角形の周が交差するか否かを判定する手順について説明する。
【0099】
まず、判定対象点ptのx座標値xtが、始点psのx座標値xsと、終点peのx座標値xeの範囲内にあるか否かを調べる。
【0100】
判定対象点ptのx座標値xtが始点psのx座標値xsと終点peのx座標値xeの範囲内になければ、半直線Ltが始点psと終点peの間で多角形の周と交差する可能性がないと判定できるので、交差回数を変更せずに、このときの終点peを始点とする次の「判定対象の辺の範囲」についての交差判定に移る。
【0101】
判定対象点ptのx座標値xtが始点psのx座標値xsと終点peのx座標値xeの範囲内にあれば、半直線Ltが「判定対象の辺の範囲」pspeの間で多角形の周と交差する可能性があると判定できる。
【0102】
このように、半直線Ltが「判定対象の辺の範囲」pspeにおいて多角形の周と交差する可能性があると判定された場合には、始点psと終点peの間にある頂点(直線 x = xt 上にある)と、判定対象点ptのy座標値ytとの大小関係を調べる。
【0103】
ここで、上記の始点psの選定手順から分かるように、頂点pn-1は「判定対象の辺の範囲」pspeの間の頂点の内の1個であるから、頂点pn-1で「判定対象の辺の範囲」pspeの間の頂点を代表させ、頂点pn-1のy座標値yn-1と判定対象点ptのy座標値ytとの大小関係を調べることとする。
【0104】
頂点pn-1のy座標値yn-1と判定対象点ptのy座標値ytの大小関係を調べた結果、yn-1>ytならば、半直線Ltは、最初の「判定対象の辺の範囲」pspeにおいて多角形の周と交差すると判定できるので、交差回数を1増加させ、このときの終点peを始点とする次の「判定対象の辺の範囲」についての交差判定に移る。
【0105】
yn-1<ytならば、半直線Ltは、最初の「判定対象の辺の範囲」pspeにおいて多角形の周と交差しないと判定できるので、交差回数を変更せずに、このときの終点peを始点とする次の「判定対象の辺の範囲」についての交差判定に移る。以上のように、計数処理を開始するときの最初の辺の始点pn-1が直線 x = xt上にあった場合でも、開始点を遡って最初の「判定対象の辺の範囲」を設定することによって、半直線Ltとの交差判定が可能となった。
【0107】
ここまでのケースAとケースBについての検討により、判定対象点ptが多角形のどの頂点とも等しくなく、かつ、多角形のy軸に平行な辺上にはない場合においては、鉛直線算法の原理を応用して、判定対象点ptからy軸と平行に且つy軸に正の方向に引いた半直線Ltと多角形の周との交差回数の計数処理が可能になり、かつ、それと一体的な手順の中で、判定対象点が辺上にある場合についても判定することが可能となった。
【0108】
ケースC
判定対象点ptが多角形の頂点のいずれかと等しい場合、及び、判定対象点ptが多角形のy軸に平行な辺上にある場合をケースCとする。
前述のように、本発明においては、多角形の頂点上の点、辺上の点は当該多角形の内部であると定義したので、ケースCの場合には、判定対象点ptは多角形の内部にあると判定しなくてはならない。
【0109】
ケースCの場合には、これまでに説明した鉛直線算法の原理の応用による内点判定処理では正しく判定ができないため、鉛直線算法の原理の応用による内点判定処理を行う前に、多角形の全ての辺を順番に辿りつつ、各辺について以下の判定処理を行うことにより、ケースCに該当するか否かを判定するものとする。
【0110】
まず、判定対象点ptが辺の始点と等しいか否かを判定する。ここで、判定対象点ptが辺の始点と等しいと判定された場合には、判定対象点ptは多角形の内部にあると判定して、内点判定処理を終了する。
判定対象点ptが辺の始点と等しくない場合には、当該辺がy軸に平行であり、かつ、判定対象点ptが当該辺上にあるか否かを判定する。
【0111】
ここで、当該辺がy軸に平行であり、かつ、判定対象点ptが当該辺上にあると判定された場合には、判定対象点ptは多角形の内部にあると判定して、内点判定処理を終了する。
当該辺がy軸に平行でないか、または、y軸に平行であっても、判定対象点ptが当該辺上にないと判定された場合には、次の辺についての上記処理を繰り返す。
【0112】
多角形の全ての辺について上記処理を行っても、判定対象点ptが多角形の内部にあると判定されなかったならば、ケースCには該当しないので、前述の鉛直線算法の原理を応用した内点判定処理に移れば良い。
【0113】
(2-6) 図11のステップS909における、重なり合う2個の多角形の頂点列Va、Vbを変換する処理の手順を、図16の例を参照しながら説明する。AとBはそれぞれ11個の頂点を持つ多角形で、それらの頂点列Va、Vbをそれぞれ{a0, a1, a2, .... a10}、{b0, b1, b2, ..., b10}とし、図のように重なり合っているものとする。また、これらの多角形は、(2-1)、(2-2)の処理を終了したものであり、頂点列の方向はどちらも時計回りで統一されており、両方の頂点列には交点に等しい頂点がすでに挿入されていることを前提とする。図の記号で言えば、頂点a3とb7、a5とb5、a7とb3、a9とb1の組がそれぞれ等しく、かつ、交点と等しい頂点である。
【0114】
まず、頂点列Va、Vbから、交点に等しい頂点を始終点とした次のような頂点列の集合を作成する。
Sa = { Va0{a3, a4, a5}, Va1{a5, a6, a7}, Va2{a7, a8, a9}, Va3{a9, a10, a0, a1, a2, a3} }
Sb = { Vb0{b1, b2, b3}, Vb1{b3, b4, b5}, Vb2{b5, b6, b7}, Vb3{b7, b8, b9, b10, b0, b1} }
【0115】
次に、集合Saの中から1個の頂点列、例えばVa0を選び、続いて、その終点a5と等しい始点を持つ集合Sbの要素を選ぶ。ここでは、頂点a5とb5が等しいから、頂点b5を始点とする頂点列Vb2が選ばれる。このとき、頂点列Vb2の終点b7は、頂点列Va0の始点a3と等しい。
【0116】
このように選んだ頂点列Va0とVb2を、それぞれ終点を削除した上で連結し、頂点列V0{a3, a4, b5, b6 }を得る。以後、頂点列Va1、Va2、Va3を順次選んで同様の処理をすることによって、頂点列V1{a5, a6, b3, b4}、V2{a7, a8, b1, b2}、V3{a9, a10, a0, a1, a2, b7, b8, b9, b10, b0}が得られる。
【0117】
このようにして得られた頂点列について前述の頂点列の方向判定法を用いて、頂点列V0、V2、V3を時計回り、頂点列V1を反時計回りに分類する。
時計回りの頂点列のうち、それらが囲む領域の面積が最大のもの、この場合は頂点列V3が結合領域を囲む多角形のデータ、反時計回りの頂点列V1が穴領域を囲む多角形のデータであるので、これらを頂点列VaとVbの変換後の多角形とする。
【0118】
なお、変換前の2個の多角形の辺が重なっている場合にこのような手順で頂点列を生成すると、当該辺の両端の2頂点だけからなる頂点列が生成される。これは、面積のない線分であり、平面領域を表すデータに含む必要はないので、変換後の頂点列の頂点数が3個未満のものは、更新後の平面領域データには追加しないことにより排除すれば良い。
【0119】
(3) 入れ子状多角形頂点列方向調整
平面領域を構成する多角形に入れ子状になっている多角形が存在する場合には、次のような処理によって、頂点列方向を調整する。
まず、平面領域に存在するn個の多角形を表す頂点列の格納順を、多角形の面積の降順に並び替える。並び替えられたn個の多角形P0, P1, ..., Pn-1の面積A0, A1, ..., An-1は、A0≧A1≧... ≧An-1の関係となる。先ず、面積最大の多角形P0を選択し、多角形P0とそれより面積が小さい多角形との間の内包関係を調べる。多角形P0の頂点列を時計回りにし、多角形P0に内包される全ての多角形の頂点列を反時計回りにし、多角形P0に内包されない全ての多角形の頂点列を時計回りにする。
【0120】
次に、2番目に面積が大きい多角形P1を選択し、多角形P1とそれより面積が小さい多角形との間の内包関係を調べる。多角形P1の頂点列はそのままにし、多角形P1に内包される全ての多角形の頂点列の方向を反転させ、多角形P1に内包されない且つ多角形P1より面積が小さい多角形の頂点列はそのままにする。
【0121】
以下、添字番号を1ずつ増やしながらn-2まで、処理を繰り返す。面積が2番目に小さい多角形Pn-2について処理が終了すると、全ての多角形の頂点列の方向が確定する。処理が終了すると、内包関係、即ち、入れ子状態にある多角形について、内側の多角形の頂点列の方向は、そのすぐ外側の多角形の頂点列の方向と反対になる。従って、全ての多角形において、頂点列の方向に向かって右側が内部領域となる。
【0122】
図17を参照して具体例について説明する。図17(a)に示すように、6個の多角形P0, P1, P2, P3, P4, P5の面積A0, A1, A2, A3, A4, A5の大小関係を、A0≧ A1≧ A2≧ A3≧ A4≧ A5とする。図17(b)に示すように、先ず、面積最大の多角形P0を選択し、その頂点列を時計回りにする。次に、図17(c)に示すように、多角形P0とそれより面積が小さい多角形との間の内包関係を調べる。多角形P0の頂点列はそのままにし、多角形P0に内包される多角形P1, P3, P5の頂点列を反時計回りにし、多角形P0に内包されない且つ多角形P0より面積が小さい多角形P2, P4の頂点列を時計回りにする。図17(d)に示すように、多角形P0の次に面積が大きい多角形P1を選択し、多角形P1とそれより面積が小さい多角形との間の内包関係を調べる。多角形P1の頂点列はそのままにし、多角形P1に内包される多角形の頂点列の方向を反転させ、多角形P1に内包されない且つ多角形P1より面積が小さい多角形P2, P3, P4, P5の頂点列はそのままにする。図17(d)の例では、多角形P1に内包される多角形は存在しない。
【0123】
図17(e)に示すように、多角形P1の次に面積が大きい多角形P2を選択し、多角形P2とそれより面積が小さい多角形との間の内包関係を調べる。多角形P2の頂点列はそのままにし、多角形P2に内包される多角形P4の頂点列の方向を反転させ、多角形P2に内包されない且つ多角形P2より面積が小さい多角形P3, P5の頂点列はそのままにする。図17(f)に示すように、多角形P2の次に面積が大きい多角形P3を選択し、多角形P3とそれより面積が小さい多角形との間の内包関係を調べる。多角形P3の頂点列はそのままにし、多角形P3に内包される多角形P5の頂点列の方向を反転させ、多角形P3に内包されない且つ多角形P3より面積が小さい多角形P4の頂点列はそのままにする。
【0124】
図17(g)に示すように、多角形P3の次に面積が大きい多角形P4を選択し、多角形P4とそれより面積が小さい多角形との間の内包関係を調べる。多角形P4の頂点列はそのままにし、多角形P4に内包される多角形の頂点列の方向を反転させ、多角形P4に内包されない且つ多角形P4より面積が小さい多角形P5の頂点列はそのままにする。図17(g)の例では、多角形P4に内包される多角形は存在しない。多角形P4は、面積が2番目に小さい。従って、ここまでの処理によって、全ての多角形の頂点列の方向が確定する。図17(h)の斜線にて示すように、頂点列の方向に向かって右側が内部領域となる。
【0125】
上述の処理において、2個の多角形の内包関係を判定する処理が含まれる。その方法は、次のとおりである。ここで対象とする多角形は、前述の複数多角形の重複解消処理を施したものであり、重なり合うことがないことが保証されている。したがって、例えば、2個の多角形のうち面積が大きい方をA、小さい方をBとすれば、Bのうち1個の頂点がAの外部にあることが分かれば、BはAが表す多角形には内包されないと言える。
【0126】
したがって、Bの頂点を順番に調べていき、Aの外部にある頂点が見つかった時点で内包されていないと判定し、全ての頂点を調べ終わった段階で外部にある頂点が見つからなければ、Aに内容されていると判定する。この手順中、Bの頂点がAの内部であるか外部であるかの判定は、前述の内点判定法を用いる。
(4) 後処理
以上の処理手順から明らかなように、ここまでの処理を施した平面領域データにおける頂点列は閉じていない。このため、後処理として全ての頂点列に対して、始点と同じ座標値の頂点データを終点に追加する処理を施す。
【図面の簡単な説明】
【0127】
【図1】本発明による図形データ処理方法を実行する装置の構成を示す図である。
【図2】本発明による図形データ処理方法の全体の手順を示す図である。
【図3】本発明による自己交差多角形分割処理の概要を説明するための説明図である。
【図4】本発明による自己交差多角形分割処理のうち、多角形よりカット点を探索し、頂点列にカット点に等しい頂点を挿入する手順を説明するための説明図である。
【図5】図4の手順の次の手順を説明するための説明図である。
【図6】本発明による自己交差多角形分割処理のうち、多角形よりカット点を検索し、多角形を分割する手順を説明するための説明図である。
【図7】複数多角形の重複解消処理のうち、従来の頂点追跡法を説明するための説明図である。
【図8】本発明による複数多角形の重複解消処理のうち、多角形の頂点列の方向を判定し、反時計回りの場合に時計回りに変更する手順を説明するための説明図である。
【図9】本発明による複数多角形の重複解消処理のうち、2個の多角形の間の交点等の探索と頂点挿入の手順を説明するための説明図である。
【図10】図9の手順の次の手順を説明するための説明図である。
【図11】本発明による複数多角形の重複解消処理のうち、複数の多角形の重なり合いを解消する手順を説明するための説明図である。
【図12】図11の処理にて、2個の多角形の間に交点又は接点が見つかった場合、それが交点と接点のどちらであるかを判定する方法を説明するための説明図である。
【図13】従来の鉛直線算法による内点判定法を説明するための説明図である。
【図14】鉛直線算法による内点判定法において、判定対象点が多角形の辺上にある場合の問題を説明するための説明図である。
【図15】本発明による内点判定法を説明するための説明図である。
【図16】図11のステップS909における、重なり合う2個の多角形の頂点列を変換する処理の手順を説明するための説明図である。
【図17】本発明による入れ子状多角形頂点列方向調整処理を説明するための図である。
【図18】本発明による自己交差多角形分割処理の具体例を示す図である。
【図19】本発明による複数多角形の重複解消処理の具体例を示す図である。
【図20】本発明による入れ子状多角形頂点列方向調整処理の具体例を示す図である。
【符号の説明】
【0128】
11…CPU、12…ROM、13…RAM、14…入出力I/F回路、15…内部バス、16…外部記憶装置
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12
【図14】
13
【図15】
14
【図16】
15
【図17】
16
【図18】
17
【図19】
18
【図20】
19