トップ :: G 物理学 :: G06 計算;計数




【発明の名称】 内外点判定アルゴリズム
【発明者】 【氏名】新庄 克彦
【住所又は居所】東京都大田区下丸子３丁目３０番２号キヤノン株式会社内
【要約】 【課題】

【解決手段】
【特許請求の範囲】
【請求項１】 多角形Ａの頂点の座標列と或る点Ｐの座標が与えられたとき、第１に多角形Ａの頂点のうちに点Ｐと一致するものが存在する場合は、該点Ｐは多角形の頂点上にあるとし、第２に点Ｐが多角形の頂点上にない場合で、該多角形の何れかの辺上に点Ｐを含む場合は、該点Ｐは多角形の辺上にあるとし、第３に点Ｐが多角形の頂点上にも辺上にも存在しない場合、点Ｐから或る方向に半直線ＰＸを引き、初期値０の内外判定数Ｎを考え、多角形Ａの全ての辺に対して辺と半直線ＰＸが共有点を持たない場合はＮの増減は０とし、半直線ＰＸと交差するとＮに１を加え、多角形Ａの或る辺の始点及び終点の両方が半直線ＰＸ上にある場合は、Ｎの増減は０、多角形Ａの或る辺の始点或は終点の何れか一方が半直線ＰＸ上にある場合は、始点或は終点が半直線ＰＸ上にある辺を、該始点或は終点方向に延長した線分が一方向きに半直線ＰＸと交差するとＮに０．５を加え、他方向きに半直線ＰＸと交差するとＮに０．５を減じる演算を行い、最終的にＮが偶数ならば、点Ｐは多角形Ａの外点であり、Ｎが奇数ならば、点Ｐは多角形Ａの内点であるとすることを特徴とする内外点判定アルゴリズム。
【発明の詳細な説明】【０００１】
【発明の属する技術分野】本発明は、計算機を利用した様々な応用分野、例えば数値シミュレーションの分野やグラフィックの基本ツール群としてグラフィック描画装置に応用することができる内外点判定アルゴリズムに関する。
【０００２】
【従来の技術】平面上に与えられた点が同一平面上の閉曲線の内に存在するか否かという問題は、数学的興味から古くから研究されてきた。現在では基本群と呼ばれるトポロジーの言葉で最も厳密且つ抽象的に表現することが可能であるが、留数の定理に関連する解析的な問題でもある。
【０００３】与えられた平面に自然な複素座標を導入することによって平面を複素平面と見なし、与えられた閉曲線をΓとし、与えられた点をｚ0 とすると、関数ｆ（ｚ）＝１／（ｚ−ｚ0 ）として次の一周積分：
を計算することによって、与えられた点が平曲線の内点か否かを判定することができる。つまり、留数の定理によると、この積分の値が零であれば、ｚ0 は曲線の外に存在し、零でなければ、即ち±２πｉであれば、点は閉曲線内の点であることが判明する。
【０００４】デュドネ編「数学史1700-1900 Ｉ」（波書店1985年発行）によると、留数の定理を発見したのはコーシーのようである。1826年のSur un nouveau genre de calcul infinitesmal という題の論文（Exercices de mathematiques）において、特異点の周りの無限小解析を行うことにより留数の定理を発見したとある。コーシーは、その後、長方形の周りでの複素函数の積分がその内部の留数の総和であることを計算し、その後２０年に亘ってこの問題に深く関わったとある。この留数の計算をもって幾何学と函数論とが結び付いたと言っても過言ではない。つまり、解析的な関数の値の和（積分）によって純粋に幾何学的な事実が判明するのである。
【０００５】実際の計算においては、閉曲線は任意のものではなく、区分的に直線で表されたものがより実用的に重要である。つまり、多角形と点Ｐが与えられた際に点Ｐが多角形の内部にあるか否かの判定をする場合が多い。
【０００６】このような与えられた点が図形の内点か否かを判定する必要性は計算機の性能の発達と共に、近年、非常に増加していると考えられる。近年のグラフィック描画装置或はそれに関する基本的な問題においては、マウス等で指示した点が与えられた図形の内点か否かという判定を必要とする。又、モンテカルロ法等の数値計算においては、多数の点が１つの多角形の内点か否かを判断することが求められる。
【０００７】上述の留数の定理に従った内外判定アルゴリズムは、多角形の各辺の終端の点Ｐから臨む角度を計算し、その角度の総和が±２πであるか否かを調べる必要がある。
【０００８】しかしながら、角度の計算は超越関数である逆３角関数を使うため、計算時間を多く必要とするものである。
【０００９】特許第２５９５３６１号に記載の「折線から成る図形の内外判定方法」においては、上述の留数の定理に沿った内外判定を多くの場合使わないで内外判定を行う方法が提案されている。この発明は、上述の留数の定理を利用したものとｘ−ｙ座標の特徴を利用した外接する長方形での内外判定を組み合わせたものである。計算時間を多く必要な留数の定理を利用した内外判定の問題点を避けるために図１１に示すようなフローチャートに従ったアルゴリズムが特許第２５９５３６１号に記載の「折線から成る図形の内外判定方法」では提供されている。
【００１０】図９に示すように、多角形Ａと点Ｐが与えられたとき、多角形Ａを内包する長方形Ｄを多角形Ａの座標のｘ軸、ｙ軸の最大値と最小値を利用して形成する。図１１に示すフローチャートにおいては、先ず始めに図形の埋め込まれたｘｙ座標のｘ、ｙ軸のそれぞれの最大値と最小値によって形成される長方形に関して、予め大小判定による内外判定を行い、その後、長方形の内であるとした場合は、長方形内の点に対する多角形の内外判定を行うこととなっている。
【００１１】又、Postscriptリフアレンスマニュアル 第２版Adobe Systems 著：アドビシステムズジャパン監訳、アスキー出版： 1991 には、ワインディング規則及び奇偶規則による内点判定法が記載されている。ワインディング規則は、判定しようとする点から或る方向に伸びる半直線を引く。０から数え始めて、１つの方向に多角形の辺がこの半直線と交差する毎に１を加える。そして、逆方向に多角形の辺が半直線と交差する毎に１を引く。全ての交差をカウントした後、結果が０の場合には、その点は多角形の外側である。結果が０以外の場合には、その点は多角形の内側である。
【００１２】図１２に示すように、奇偶規則では、単に半直線と交差する多角形の辺の数をカウントすることによりその点が内部か否か判断する。この数が奇数である場合には、点は内側にある。この数が偶数である場合には、点は外側にあるとする。
【００１３】
【発明が解決使用とする課題】従来の技術である特許第２５９５３６１号に記載された発明においては、一般の多角形に対する内点判定は計算時間を非常に必要とするため、多角形を埋め込んだ長方形に対する予備的内点判定を行っていた後に、もしも目的とする点が長方形外に存在した場合は、該点が多角形の外部に存在していると判定し、又、逆に長方形の内部に存在した場合は、計算時間の掛かる多角形と点に対する内外判定を行っていた。
【００１４】しかしながら、図１０に示したような多角形Ａがｘｙ軸に対して斜めの方向に延びている場合、対応するｘ軸とｙ軸の最大値と最小値から形成される長方形は広い面積を持つ。そのため、図１１のフローチャートに沿った予備的な内点判定を行う長方形の面積が本来求めたい多角形の面積に比較して非常に大きくなり、ランダムな点分布を考えた場合、予備的内点判定が十分機能していないこととなる。つまり、予備的な内点判定を行っても、次の詳細な内点判定の計算を非常に多くの場合、行う必要が生じて高速化を図ることができない。
【００１５】又、ワインディング規則や奇偶規則においては、多角形の辺が半直線と一致する場合やその半直線に接する場合にどうすべきかを指定しない。任意の半直線を使用できることから、単にそのような問題のある交差に出会わない別の直線を選ぶことにしているのみである。従って、或る多角形に対して、多数の判定すべき点を有する問題に関しては、判定点によっては何度も半直線を取り直す必要が生じる可能性が高い。
【００１６】本発明は上記問題に鑑みてなされたもので、その目的とする処は、折線閉多角形と或る点が与えられたとき、判定点と閉多角形の位置関係に拘らず、判定点が閉多角形内にあるか否かを判定することができる内外点判定アルゴリズムを提供することにある。
【００１７】
【課題を解決するための手段】上記目的を達成するため、本発明は、多角形Ａの頂点の座標列と或る点Ｐの座標が与えられたとき、第１に多角形Ａの頂点のうちに点Ｐと一致するものが存在する場合は、該点Ｐは多角形の頂点上にあるとし、第２に点Ｐが多角形の頂点上にない場合で、該多角形の何れかの辺上に点Ｐを含む場合は、該点Ｐは多角形の辺上にあるとし、第３に点Ｐが多角形の頂点上にも辺上にも存在しない場合、点Ｐから或る方向に半直線ＰＸを引き、初期値０の内外判定数Ｎを考え、多角形Ａの全ての辺に対して辺と半直線ＰＸが共有点を持たない場合はＮの増減は０とし、半直線ＰＸと交差するとＮに１を加え、多角形Ａの或る辺の始点及び終点の両方が半直線ＰＸ上にある場合は、Ｎの増減は０、多角形Ａの或る辺の始点或は終点の何れか一方が半直線ＰＸ上にある場合は、始点或は終点が半直線ＰＸ上にある辺を、該始点或は終点方向に延長した線分が一方向きに半直線ＰＸと交差するとＮに０．５を加え、他方向きに半直線ＰＸと交差するとＮに０．５を減じる演算を行い、最終的にＮが偶数ならば、点Ｐは多角形Ａの外点であり、Ｎが奇数ならば、点Ｐは多角形Ａの内点であるとすることを特徴とする。
【００１８】
【発明の実施の形態】以下に本発明の実施の形態を添付図面に基づいて説明する。
【００１９】図１に本発明の内外点判定アルゴリズムの概要を示す。
【００２０】多角形Ａと判定点Ｐを考え、Ａi Ａi+1 を多角形Ａの辺の１つとする。図１（ａ）に示すように、Ａi 或はＡi+1 が点Ｐと一致する場合は、該点Ｐは多角形Ａの頂点上にある。
【００２１】次に、図１（ｂ）に示すように、Ａi 或はＡi+1 は点Ｐと一致しないが、線分Ａi Ａi+1 上に点Ｐがある場合は、該点Ｐは多角形Ａの辺上にある。更に、点Ｐが多角形Ａの頂点上にも辺上にも存在しない場合、内外判定数Ｎを考える。多角形Ａの全ての辺に対して、その辺の始点及び終点を考慮し、或る辺の終点が次に続く辺の始点となると考える。即ち、各辺を向きを持った線分と考える。
【００２２】更に、点Ｐからある半直線ＰＸを引き、多角形の全ての辺に対応する向きを持った線分と半直線ＰＸとの位置関係によって、内外判定数Ｎを初期値０から増減させ、最終的にＮが０ならば、点Ｐは外点、Ｎが０でなければ内点とする。
【００２３】Ｎの増減の仕方を図１（ｃ）に示す。即ち、図中、Ａ1 Ａ2 、Ａ3 Ａ4 、Ａ5Ａ6 のように辺が半直線ＰＸと共有点を持たない場合は、Ｎの増減は０、Ａ7 Ａ8 、Ａ9 Ａ10のように線分と半直線が交差するときはＮに１を加える。Ａ11Ａ12のように向き付き線分の始点及び終点の両方が半直線ＰＸ上にある場合は、Ｎの増減は０、更に線分の始点或は終点の一方のみが半直線上にある場合、半直線ＰＸを下から上に横切る場合を正の方向と仮定した場合、Ａ13Ａ14、Ａ15Ａ16のように向き付き線分の始点或は終点の一方が半直線ＰＸ上にあり、該向き付き線分と半直線ＰＸの交差方向が正の向きである場合はＮに０．５を加え、逆にＡ17Ａ18、Ａ19Ａ20のように向き付き線分の始点或は終点の一方が半直線ＰＸ上にあり、該向き付き線分と半直線ＰＸの交差方向が負の向きである場合はＮから０．５を減ずる。
【００２４】以上の操作を多角形Ａの全ての辺に対応する向き付けされた線分に対して行えば良い。尚、ここでは、辺が半直線ＰＸを下から上に横切る場合に正の方向としたが、逆にこの交差方向を負の方向としても、内外判定に影響しないことは明らかである。図２に上述のアルゴリズムをフローチャートにて示す。
【００２５】以上説明した方法によって、或る多角形Ａに対してどのような判定点Ｐ、半直線ＰＸを考えても、半直線ＰＸを選び直すことなく必ずＰの内外判定を行うことができる。
【００２６】［実施例１］図３に実施例１を示す。三角形ＡＢＣの各頂点の座標がＡ（１，３）、Ｂ（２，１）、Ｃ（３，２）であるとき、点Ｐ（１，１）) が三角形の内点であるか否かを判定する。
【００２７】点Ｐを原点とする座標系では三角形ＡＢＣの各頂点の座標はＡ（０，２）、Ｂ（１，０）、Ｃ（２，１）となる。点Ｐを原点とする座標系のｘ軸の正の部分を判定に用いる半直線と考え、三角形ＡＢＣの各辺が交差するか否かを調べる。尚、始点或は終点の一方のみが半直線上にある場合のＮの増減の符号を決定するための方向付けは、上向きの交差をプラス、下向きの交差をマイナスとした。
【００２８】先ず、内外半定数Ｎを０とする。辺ＡＢについて、頂点Ａのｙ座標は正であり、頂点Ｂのｘ座標は正、ｙ座標は０、従って、辺ＡＢのｘ軸の正の部分との交差は−０．５であるため、Ｎの値を０．５減ずる。辺ＢＣについて、頂点Ｃのｙ座標は正であり、頂点Ｂはｘ軸上の正の領域にあるため、辺ＢＣのｘ軸の正の部分との交差は＋０．５であり、Ｎの値に０．５を加える。
【００２９】辺ＣＡについて、頂点Ｃと頂点Ａのｙ座標は共に正であるため、辺ＣＡのｘ軸の正の部分との交差は０であり、Ｎの増減はない。最終的にＮの値は０で偶数となる。従って、点Ｐは三角形ＡＢＣの外側にあると判定される。
【００３０】［実施例２］図４は実施例２を示す。三角形ＡＢＣの各頂点の座標がＡ（１，３）、Ｂ（２，１）、Ｃ（２，２）であるとき、点Ｐ（２，３）が三角形の内点であるか否かを判定する。
【００３１】点Ｐを原点とする座標系では三角形ＡＢＣの各頂点の座標はＡ（−１，０）、Ｂ（０，−２）、Ｃ（０，−１）となる。点Ｐを原点とする座標系のｙ軸の負の部分を判定に用いる半直線とし、三角形ＡＢＣの各辺が交差するか否かを調べる。尚、始点或は終点の一方のみが半直線上にある場合のＮの増減の符号を決定するための方向付けは、右向きの交差をプラス、左向きの交差をマイナスとした。
【００３２】先ず、内外判定数Ｎの初期値を０とする。ＡＢについて、頂点Ａのｘ座標は負であり、頂点Ｂのｘ座標は０、ｙ座標は負、即ち、頂点Ｂはｙ軸上の負の領域にある。従って、辺ＢＣとｙ軸の負の部分との交差は正方向であり、Ｎの値に０．５を加える。辺ＢＣについて、頂点Ｃのｘ座標は０、ｙ座標は負、即ち、頂点Ｂと頂点Ｃは共にｙ軸上の負の領域にある。従って、辺ＢＣとｙ軸の負の部分との交差はなく、Ｎの増減はない。辺ＣＡについて、頂点Ｃはｙ軸上の負の領域にあり、頂点Ａのｘ座標は負であるため、辺ＣＡとｙ軸の負の部分との交差は負方向であり、Ｎの値を０．５減ずる。
【００３３】以上の結果から最終的にＮの値は０、つまり偶数であるため、点Ｐは三角形ＡＢＣの外側にあると判定される。
【００３４】［実施例３］図５は実施例３を示す。本実施例では、２２角形を考える。
【００３５】今、判定点Ｐを原点、及び判定に用いる半直線をｘ軸正の方向とする座標系で考える。図５中、２２角形の２２本の辺上には点Ｐは存在しないため、半直線ＰＸと各辺との位置関係から内外半定数Ｎを計算することになる。具体的には、各頂点Ａi ｘ、ｙ座標値、及び各線分と半直線ＰＸとの交点が存在する場合はそのｘ座標値を求めることによりＮの増減を決定するが、ここでは、その計算の過程は説明しない。今、半直線ＰＸを下から交差する場合を正の向きとすると、各辺に対応するＮの増減は次の通りとなる。
【００３６】即ち、Ａ1 Ａ2 、Ａ2 Ａ3 、Ａ3 Ａ4 、Ａ4 Ａ5 、Ａ5 Ａ6 、Ａ8 Ａ9 、Ａ10Ａ11、Ａ13Ａ14、Ａ15Ａ16、Ａ17Ａ18、Ａ19Ａ20、Ａ22Ａ1 ではＮの増減は０、Ａ6 Ａ7 、Ａ11Ａ12、ＡＡ16Ａ17、Ａ21Ａ22ではＮの値は１増加し、Ａ14Ａ15、Ａ18Ａ19ではＮの値は０．５増加し、Ａ7 Ａ8 、Ａ9 Ａ10、Ａ12Ａ13、Ａ20Ａ21ではＮの値は０．５減少する。全体では、Ｎ＝１×４＋０．５×２−０．５×４＝３で奇数であるため、点Ｐは２２角形の内点である。
【００３７】［実施例４］本実施例は、２次元平面を図８に示すように有限の要素に分割し、その分割された要素中を運動する粒子の軌道を計算するシミュレーション装置に関するものである。
【００３８】本実施例の実現は図６に示したような計算機内で行われる。図６において、６１は計算機本体であり、ＣＰＵ、メモリ、記憶媒体であるフロッピー（登録商標）を読み込む装置６５、ＣＤ−ＲＯＭを読み込む装置６６、ハードディスク６７等を含んでいる。又、モニター６２やキーボード６３やマウス６４とケーブルを通じて電気的に連結され、様々な制御を行ったり、又は行われたりしている。
【００３９】本発明の内外点判定方法は、実施例１〜３で示したものであり、粒子の運動を計算する方法と共にプログラムとして媒体６８に書かれている。媒体６８のデータを計算機６１内部のメモリに展開し、実際の内外点判定を計算機６１内で行っている。
【００４０】本実施例は、図８に示したような粒子の運動についてのものである。図８において矢印が粒子の軌跡を示している。要素を指定すると粒子に加わる力が一意的に決まるとし、粒子は加わった力から或る運動方程式を解いて次のステップの軌道を描いて運動するとしている。従って、本実施例の問題は、粒子の位置を決定した際に、その粒子がどの要素に属しているかを決定することが重要なステップである。
【００４１】図７に本実施例の荷電粒子の運動を本実施例の荷電粒子の運動を計算するアルゴリズムを示す。
【００４２】先ず、各要素は閉多角形で構成されていることとする。ステップ２１で開始したシミュレーションはステップ２２の前処理計算で、全ての要素に対して粒子の力を予め計算することとする。ステップ２３において粒子の軌道計算が所望の結果を得て終了するか否かの判断をする。計算を終えない場合はステップ２４に進み、どの要素に属するかの内外点判定を行う。或る要素を指定すると仮定より粒子に加わる力が計算されるため、対応する力で軌道計算（ステップ２５）を行い、点の移動をステップ２６で行い、ステップ２３に進む。このようにして、所望の結果を得るまで粒子の軌道を追ってゆけば良い。
【００４３】尚、本実施例では、粒子の軌道シミュレーションを行う装置及びそのシミュレーションを行うプログラムを記録した記録媒体について述べたが、本発明の内外点判定アルゴリズムは、粒子の軌道シミュレーションに限って応用されるものではない。より汎用のグラフィック処理装置においても使用可能である。
【００４４】
【発明の効果】以上の説明で明らかなように、本発明によれば、多角形Ａの頂点の座標列と或る点Ｐの座標が与えられたとき、第１に多角形Ａの頂点のうちに点Ｐと一致するものが存在する場合は、該点Ｐは多角形の頂点上にあるとし、第２に点Ｐが多角形の頂点上にない場合で、該多角形の何れかの辺上に点Ｐを含む場合は、該点Ｐは多角形の辺上にあるとし、第３に点Ｐが多角形の頂点上にも辺上にも存在しない場合、点Ｐから或る方向に半直線ＰＸを引き、初期値０の内外判定数Ｎを考え、多角形Ａの全ての辺に対して辺と半直線ＰＸが共有点を持たない場合はＮの増減は０とし、半直線ＰＸと交差するとＮに１を加え、多角形Ａの或る辺の始点及び終点の両方が半直線ＰＸ上にある場合は、Ｎの増減は０、多角形Ａの或る辺の始点或は終点の何れか一方が半直線ＰＸ上にある場合は、始点或は終点が半直線ＰＸ上にある辺を、該始点或は終点方向に延長した線分が一方向きに半直線ＰＸと交差するとＮに０．５を加え、他方向きに半直線ＰＸと交差するとＮに０．５を減じる演算を行い、最終的にＮが偶数ならば、点Ｐは多角形Ａの外点であり、Ｎが奇数ならば、点Ｐは多角形Ａの内点であるとしたため、折線閉多角形と或る点が与えられたとき、判定点と閉多角形の位置関係に拘らず、判定点が閉多角形内にあるか否かを判定することができるという効果が得られる。
【出願人】 【識別番号】０００００１００７
【氏名又は名称】キヤノン株式会社
【住所又は居所】東京都大田区下丸子３丁目３０番２号
【出願日】 平成１３年９月１４日（２００１．９．１４）
【代理人】 【識別番号】１０００９２８５３
【弁理士】
【氏名又は名称】山下 亮一
【公開番号】 特開２００３−８５５６９（Ｐ２００３−８５５６９Ａ）
【公開日】 平成１５年３月２０日（２００３．３．２０）
【出願番号】 特願２００１−２８０１８０（Ｐ２００１−２８０１８０）