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

質問

多角形が点列｛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.12

stomachman

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

　もし、Q点がリアルタイムの測定で得られるのだとするならば、一番のお薦めはやっぱりmapであって、しかも、境界付近でも内か外かの2値しか取らない最も単純なbinary mapです。Q点の測定精度から、mapの適切なpixelサイズが決定できるでしょう。
　たとえば「写真を被験者に見せてアイカメラで注視点の位置Qを追い、どこをどれだけの時間見ていたかを計測する」というような応用を想定すると、Q点の測定値が持つ不確かさは写真の被写体の実スケール換算で1cmのオーダであろうと思われ、また、視野のサイズは(写真の被写体の実スケール換算で）1m四方程度と考えられ、なのでpixel数は数百×数百もあれば足りるだろう、と分かるわけです。もちろんこの話は、多角形で近似した輪郭と実際のシルエットの輪郭とのずれの程度が、Q点の不確かさと整合している、というのが前提です。（で、50角形程度というかなり荒っぽい図形で人体や頭部のシルエットを表現することと、Q点の不確かさが1cm程度という推定とは良く整合すると思います。）
　なお、ここで勝手に想定した応用では、多角形はカメラなどで得られたシルエットのpixel map画像をトレースして作られることになりますが、mapを使うのならそのトレース作業すら不要です。

お礼

更なる回答、ありがとうございます。
おっしゃるとおり、最速はバイナリマップ方と思っています。
想定された応用では、最適解とも思います。
しかしNo10のお礼にも書いたように、mapですと多角形の大きさに依存するメモリが必要な点が、アルゴリズムとしてはエレガントでない気がしています。

貴重なご意見、参考にさせていただきます。

回答No.11

hrsmmhr

申し訳ありません。
お礼で書かれた「チェックする辺の数を絞り込むうまいアルゴリズム」については書いておりません。
No.1さんが書かれているような、別の方法を提案しただけです
ご質問の意図を汲み取れずに申し訳ありませんでした

お礼

回答ありがとうございます。
了解しました。私の理解不足でないことがわかり、一安心です。
「別の方法の提案」という位置づけで読ませていただきます。

これに懲りず、活発な回答、これからもよろしくお願いいたします。

回答No.9

hrsmmhr

No6です。もう少し考えてみました

違うと思ったのは、経路を交差する直線群の数を全て補正してしまっては
恐らく全部同じ側に判定されてしまうという点です
このやり方の肝は境界を突っ切るか突っ切らないかを不等式の符号に読み取らせる点で
R→R'経路上で頂点を通るとき、これまで辿ってきた辺を交差したかどうかを判定して
その頂点を交差点であるかどうかの判定をすることになりますが
これをすべての辺でやってしまうと符号をすべて補正してしまい判定に差異がでません
たとえば最後のR'がR'→Q'の経路に移るときにR'が乗っている辺が突っ切られたか突っ切られないかの
判定は行わないように（R'は交差点でないと）すれば
結果どちら側にいるかが、不等式の符号に現れると思います

それでいいんだと思いますが、何か自信がないので、ご検証いただけたらと思います

お礼

回答ありがとうございます。
すいません。
私の質問は「チェックする辺の数を絞り込むうまいアルゴリズムなどありますでしょうか？」です。
回答を読ませていただきましたが私の理解力不足で、「検索すべき直線群が絞られ、高速化される」ことが読み取れません。
よろしくお願いいたします。

回答No.8

noname#221368

#1です。

　読んでいて、皆さんの仰る探索ローカライズの方法を、動的にうまく更新できれば、なんとかなりそうだなぁ～、などと勝手な印象を持ちました。実は、最近接点探索で自分も、mapのような機構を使っています。

　　・多角形を運転するのはあなたですから、更新領域を予想する事もできる気がします。

　動かしてみないと大概はわからないですけど、高速化コードを加えれば加えるほど、それにCPUパワーが食われて、本来の計算量の減少とのトレードオフが生じてしまうのが、難しいところだと思います。どこかで妥協も必要な気はします。

　ところで、内部的には秒当たり100回の更新があったとしても、出力の更新は秒当たり25回くらいで良い気もします。人間の目なんてそんなものです。もう考慮されたかも知れませんが・・・。

　実際に動いているキャリヤー系のゲームは沢山ある訳で、きっと適切な仕様は作れると思います（無責任ですが）。

お礼

回答ありがとうございます。

＞・多角形を運転するのはあなたですから、更新領域を予想する事もできる気がします。
ちょっと意味不明ですが、動点Qを制御する（多角形を運転する？）のは環境であって、環境の変化にすばやく応答するのが私（プログラム）です。

＞ところで、内部的には秒当たり100回の更新があったとしても、出力の更新は秒当たり25回くらいで良い気もします。人間の目なんてそんなものです。もう考慮されたかも知れませんが・・・。

おっしゃるとおりですが、ゲームのようなものですが、ゲームではありませんので、出力の更新は秒当たり25回も必要ありません。変化自体は１０分に１回あるか無いかなので、最大でも１秒１回対応できれば十分です。
しかし、変化があってからの応答時間が問題なので秒１００回程度のサンプリングしています。
当然ほとんどは「変化なし」の判断となります。

また、変化した直後に変化することは無いし、あったとしても無視してかまわないので、
　変化検出後に、高速検出のネタをじっくり仕込んで、次回の検出に備える
といったアルゴリズムも大歓迎です。

回答No.7

hrsmmhr

スミマセン。ちょっと違うみたいです。
もう少し考えます。

回答No.6

hrsmmhr

こんなのはどうでしょうか？

辺を延長して得られる直線l_nからできる直線群Lの不等式の符号の積を
QからQ'へ向かう経路が直線群をまたぐ回数で補正して（内／外の）同じ側か違う側かを判定します
といっても結局直線だけでなく辺をまたぐ回数でも
符号の積と同じ側であるか違う側であるかの判定は影響を受けるため
境界をまたぐのは１回だけになるように経路を
多角形の境界上へ他の境界をまたがずにアクセスする経路（Q→R／Q'→R'）と
境界上を周回する経路（R→R')という経路の合成経路S:Q→R→R'→Q'上を考え
経路S上で何回直線群Lを横切ったかによって補正します

横切る直線群の数が偶数なら（符号の積）＞０で同じ側、（符号の積）＜０で違う側
横切る直線群の数が奇数なら（符号の積）＜０で同じ側、（符号の積）＞０で違う側

とします

不幸にして直線l_n上にQ、Q'がなってしまい、符号の正負が判定できないときには、
内外の判定には無関係な範囲にQ、Q'をほんの少しだけ移動させたらよいかと思います

Q→Rを横切る直線l_nの数や、周回経路R→R'上で横切る直線の数は
たとえば多角形の辺毎に予め横切る直線の数を算出するなどしておけば、
新しいQ'毎に毎回計算しなくてもよいので
アプリケーションにもよるのでしょうが高速化に繋がるのではないでしょうか？

回答No.5

stomachman

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

> 想定している多角形は人のシルエットを折れ線近時した凹凸のある多角形の感じで、大体５０角形程度です。

　用途はゲームみたいなものでしょうかね。50角形程度なら、内か外かを毎回判定しても、フツーのプロセッサで数μ秒もあれば足りる。ということは、低速の組込用マイコンなどを使う話でしょうか。

　50角形でシルエットを近似できるのであれば、空間分解能はたいしたことないでしょう。さらにその多角形が変化しないのであれば、一度mapを作っておけば、以後は速くできます。mapは、輪郭線のごく近くでは「境界線付近だからきっちり調べなさい」、それ以外では「内側」か「外側」を意味する3値を取る画素(pixel) p(x,y)を適当な間隔で敷き詰めたもの。Qを与えたとき、Qに最寄りのpixelを参照すれば、ほとんどの場合にはそれで判定完了です。
　なお、多角形が変化する場合には、正直にmapを作る代わりに、x軸に平行な直線y=cと多角形との交点を調べてrun length codeを作るほうがずっと速く作れます。mapへのアクセスにちょっとだけ時間が掛かるのが欠点ですが。

お礼

再度、回答ありがとうございます。
＞　用途はゲームみたいなものでしょうかね。50角形程度なら、内か外かを毎回判定しても、フツーのプロセッサで数μ秒もあれば足りる。ということは、低速の組込用マイコンなどを使う話でしょうか。
そんな感じです。判定だけなら問題になりませんが、他の仕事の足を引っ張らないように軽いアルゴリズムを探索中です。

荒いマップをつかう方法ですね。
「境界線付近だからきっちり調べなさい」でなく、「境界線ｘｘ番付近だから線分ＸＸとの交差をきっちり調べなさい」に出来れば、探索時間が大幅に低減できそうですね。問題はマップの最適な細かさを決めるところでしょうか。
ありがとうございます。検討したいと思います。

回答No.4

Tacosan

多角形が固定されてるならアレンジメントかなんかでできる... かなぁ?

お礼

回答ありがとうございます。
すいません、私の理解不足のためでしょうが、せっかく回答いただきましたが、おっしゃっている内容、理解できません。
素人にもわかる言葉でのわかりやすい回答、よろしくお願いいたします。

回答No.3

stomachman

問題の多角形が凸だ、というような条件があれば速くできそうですが、どんな形でもありうるのだとすると、たとえばQが交差した辺とは全く無縁の辺がQとQ'を切り分けている可能性がありますから、基本的には全部の辺を調べざるを得ないと思います。
　多角形の辺（頂点も含む）上の点のうち、Qに最も近い点Rを調べておけば（これはご質問のアルゴリズムで各辺を調べるツイデに行えるので、手間はさほど大きくならないでしょう）、QからRまでの距離をrとするとき、Qを中心とする半径rの円内の点はすべてQと同じ側にあるから、もしQとQ'の距離がr未満ならそれだけで判定は完了します。だから、Qとごく近いQ'をいくつも調べたいという時には有効でしょう。

お礼

回答ありがとうございます。
＞問題の多角形が凸だ、というような条件があれば
すいません。
想定している多角形は人のシルエットを折れ線近時した凹凸のある多角形の感じで、大体５０角形程度です。
点Ｑの座標は秒１００回程度更新され、そのつど、内点か外点かを判断していのです。

点Ｑが境界線から十分離れた位置を移動している場合には、半径ｒが大きく取れるので、十分実用的なアイデアと思います。早速、使わせていただきます。
ありがとうございます。

回答No.2

chie65536（@chie65535）

＞しかし、結局、線分ＱＱ’と多角形の全ての辺との交差を判断するので、あまり高速化になりません。

まず「多角形に外接する矩形」を作ります。

これは（多角形の点列のX座標の最小値，多角形の点列のY座標の最小値）－（多角形の点列のX座標の最大値，多角形の点列のY座標の最大値）の矩形になります。

点Qがこの矩形の外にあれば「外」です。

矩形の中にある場合、判定用の線分を「Qを通り、X軸またはY軸と並行」とします。

判定用の線分は４種類（点Qから上下左右の４方向）あります。

４つから選ぶ場合は「外接する矩形に、一番近い方向」を選びます。

例えば「Qを通り、X軸と並行で、点Qより右に伸びる線分」を判定用の線分にしたとします。

この時、多角形のある辺の始点と終点のY座標が、共に点QのY座標から見て同じ方向にある（始点と終点のY座標が、どちらも点Qより上にある、どちらも点Qより下にある）と言う場合、その始点と終点は無視して構いません。

判定が必要になるのは「始点が上、終点が下」か「始点が下、終点が上」の場合だけです。

これは「Y座標の大小比較」だけで済みます。

そうやって絞り込むと「判定すべき多角形の辺」はかなり減ります。

しかも、判定する線分は「軸に並行」なのですから、多角形の辺の方程式に、点QのX座標かY座標のどちらかを代入するだけで、交差するかどうか判ります。

お礼

回答ありがとうございます。
外接矩形を求め、それを活用するアイデア、ありがとうございます。

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

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