微小移動後の多角形の内外の判断

質問

多角形が点列｛Pi} により与えられている場合、任意の点Ｑが多角形の内部にあるかどうかを判断する関数の高速化を考えています。
今考えているアルゴリズムは以下のとおりです。

はじめの１回は、点Ｑから任意の方向に向けた半直線と多角形の交差回数が奇数なら内部と判断できます。
はじめの点Ｑの近傍の点Ｑ’が与えられたとき、ＱＱ’と多角形の交差回数でも判断できることは判ります。
しかし、結局、線分ＱＱ’と多角形の全ての辺との交差を判断するので、あまり高速化になりません。
チェックする辺の数を絞り込むうまいアルゴリズムなどありますでしょうか？
願わくば、そのようなプログラム例が載っているサイトがあれば、御紹介ください。
よろしくお願いいたします。

回答No.10

stomachman · ベストアンサー

ANo.5へのコメントについてです。

　ご質問の背景にある様子がだいぶ分かってきました。

　多角形から(mapのような)データ構造を生成するための前処理にある程度の手間を掛けても良いようです。ならば（mapよりも気合いを入れて）、2次元平面を台形の領域に予め分割しておく方法が便利だろうと思います。

　すなわち、x軸に平行な直線L(y)について、L(y)と交差する多角形の辺を、交点のx座標が小さい順に並べたリストE(y)[k] (n=1,2,…）を考えます。（すると、L(y)上の全ての点Qについて、Qが丁度多角形の頂点である場合を除いて、内点か外点かの判断が予め終わっているわけです。）
　さて、y=-∞から∞まで走らせたとき、E(y)はほとんど一定であるけれども、yが多角形のどれかの頂点のy座標と一致する前後でだけ離散的に変化します。つまり、多角形の頂点のy座標を小さい順にsortしたリストをY[j](j=1,2,…,N)とし、またY[0]=-∞, Y[N+1]=+∞として、辺のリストをたとえば
　　D[j] = E((Y[j-1]+Y[j])/2) (j=1,2,…,N)
とすると、（Q=(x,y)が丁度頂点である場合を除けば、）
　　Y[j-1]≦y≦Y[j] ⇒ E(y)=D[j] (j=1,2,…,N)
が成立つ。
　なので、Dは2次元平面を台形の領域に分割する情報を保持するデータ構造、ということになります。
　Dへのアクセスには、Qのy座標をリストYからlook upしてjを決め、さらにx座標をリストD(j)からlook upして（この時に、D(j)が示す辺にy座標を代入してx座標を計算します）nを決めることになりますから、二分探索の手間（log N程度）が掛かります。しかし、Qの近くの点Q'に対応するj', n'を調べる場合には、jおよびjの前後を探せば良いから、もっと速くなるでしょう。

　なお、Qが多角形の頂点である場合と、y座標が同一の複数の頂点が存在する場合の扱いには、ちょっと工夫が必要ですね。

お礼

すばらしい回答、感謝です。
かなりの高速化ができそうな手法ですね。

マップを作る方法ですと多角形の面積により必要なメモリが決まり、マップの最適な細かさを決めるのが問題でしたが、提案いただいた方法ですと、台形の数は、面積ではなく、多角形の角の数によって上限が決まるのがうれしいです。

また探索に、直前の位置Ｑを有効に活用できる点も、希望通りのアルゴリズムです！

回答No.1

noname#221368

お考えのアルゴリズムより高速かは、わかりませんが、自分は以下の方法を採用しています。

　多角形が点列｛Pi} で与えられるのですから、｛Pi} は多角形頂点を、左回りか右回りに並べたものと思います。ここでは、左回りを仮定します。さらに、Ｐ[１]を始まり、Ｐ[ｎ]を終わりとして、Ｐ[ｎ＋1]＝Ｐ[１]になるようにデータを追加して、点列｛Ｒi}を作っておきます。

　図を書くとすぐわかりますが、 任意点Ｑから見たＰ[ｉ]からＰ[ｉ＋1]への角度増分⊿θ[ｉ]を、積算すると（Σは、ｉ＝1～ｎに関するもの）、

　　1)Ｔ＝Σ⊿θ[ｉ]＝2πなら内部．

　　2)Ｔ＝Σ⊿θ[ｉ]＝πなら境界．

　　3)Ｔ＝Σ⊿θ[ｉ]＝0なら外部．

となります。2)のケースは、ＱがＰ[ｉ]のどれかに一致した場合、ＴがＰ[ｉ]における内角になったり、角度が計算できなくなったりしてちょっと厄介ですが、具体的に点列｛Ｒi}（｛Pi} ）があるので、座標値で境界点かどうか、あらかじめ判定しておきます。そうすると、

　　1')座標値で境界点か判定．境界点なら2)はスルー．

　　2')Ｔ＞0なら内部，Ｔ＝0なら外部．

というアルゴリズムなり、常に最大2ｎ回のループで、｛Ｒi}（｛Pi} ）を最大2周すれば、判定できる事になります。もちろん1')にも2')にも、0判定の類が含まれるので、桁落ち誤差等のEps限界は考慮しておきます。

　アルゴリズムが単純なのと、ループ回数がほぼ常に一定なので実行速度を予想しやすく、自分は気に入っています。

　交差辺の絞り込みについてですが、Ｑが多角形の内部か外部かは、けっきょく多角形の大域的性質（全体の形）で決定されるものです。どのような方法を取ろうと、どこかで｛Ｒi}（｛Pi} ）の情報を全部使わざる得ないと思われます。例えば絞り込みアルゴリズムにおいて。

　そう考えると、あまりクヨクヨせずに、明解な方法を採用した方が良い気がするのですが、どうでしょうか？。

お礼

回答ありがとうございます。
角度増分⊿θ[ｉ]の計算方法が結構重そうなのであきらめましたが、参考にします。

＞　交差辺の絞り込みについてですが、Ｑが多角形の内部か外部かは、けっきょく多角形の大域的性質（全体の形）で決定されるものです。どのような方法を取ろうと、どこかで｛Ｒi}（｛Pi} ）の情報を全部使わざる得ないと思われます。例えば絞り込みアルゴリズムにおいて。

想定している多角形は人のシルエットの感じで、大体５０角形程度です。

たとえば右手部分に点Ｑがあった場合、直後のＱ’の判断には、遠く離れた左手部分や両足部分の辺は関与しないと思います。「点Ｑが内点である」という情報をうまく使うアルゴリズムがきっとあると思い質問してみました。