多角形が点列{Pi} により与えられている場合、任意の点Qが多角形の内部にあるかどうかを判断する関数の高速化を考えています。
今考えているアルゴリズムは以下のとおりです。
はじめの1回は、点Qから任意の方向に向けた半直線と多角形の交差回数が奇数なら内部と判断できます。
はじめの点Qの近傍の点Q’が与えられたとき、QQ’と多角形の交差回数でも判断できることは判ります。
しかし、結局、線分QQ’と多角形の全ての辺との交差を判断するので、あまり高速化になりません。
チェックする辺の数を絞り込むうまいアルゴリズムなどありますでしょうか?
願わくば、そのようなプログラム例が載っているサイトがあれば、御紹介ください。
よろしくお願いいたします。
No.10ベストアンサー
- 回答日時:
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座標が同一の複数の頂点が存在する場合の扱いには、ちょっと工夫が必要ですね。
すばらしい回答、感謝です。
かなりの高速化ができそうな手法ですね。
マップを作る方法ですと多角形の面積により必要なメモリが決まり、マップの最適な細かさを決めるのが問題でしたが、提案いただいた方法ですと、台形の数は、面積ではなく、多角形の角の数によって上限が決まるのがうれしいです。
また探索に、直前の位置Qを有効に活用できる点も、希望通りのアルゴリズムです!
No.12
- 回答日時:
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.9
- 回答日時:
No6です。
もう少し考えてみました違うと思ったのは、経路を交差する直線群の数を全て補正してしまっては
恐らく全部同じ側に判定されてしまうという点です
このやり方の肝は境界を突っ切るか突っ切らないかを不等式の符号に読み取らせる点で
R→R'経路上で頂点を通るとき、これまで辿ってきた辺を交差したかどうかを判定して
その頂点を交差点であるかどうかの判定をすることになりますが
これをすべての辺でやってしまうと符号をすべて補正してしまい判定に差異がでません
たとえば最後のR'がR'→Q'の経路に移るときにR'が乗っている辺が突っ切られたか突っ切られないかの
判定は行わないように(R'は交差点でないと)すれば
結果どちら側にいるかが、不等式の符号に現れると思います
それでいいんだと思いますが、何か自信がないので、ご検証いただけたらと思います
回答ありがとうございます。
すいません。
私の質問は「チェックする辺の数を絞り込むうまいアルゴリズムなどありますでしょうか?」です。
回答を読ませていただきましたが私の理解力不足で、「検索すべき直線群が絞られ、高速化される」ことが読み取れません。
よろしくお願いいたします。
No.8
- 回答日時:
#1です。
読んでいて、皆さんの仰る探索ローカライズの方法を、動的にうまく更新できれば、なんとかなりそうだなぁ~、などと勝手な印象を持ちました。実は、最近接点探索で自分も、mapのような機構を使っています。
・多角形を運転するのはあなたですから、更新領域を予想する事もできる気がします。
動かしてみないと大概はわからないですけど、高速化コードを加えれば加えるほど、それにCPUパワーが食われて、本来の計算量の減少とのトレードオフが生じてしまうのが、難しいところだと思います。どこかで妥協も必要な気はします。
ところで、内部的には秒当たり100回の更新があったとしても、出力の更新は秒当たり25回くらいで良い気もします。人間の目なんてそんなものです。もう考慮されたかも知れませんが・・・。
実際に動いているキャリヤー系のゲームは沢山ある訳で、きっと適切な仕様は作れると思います(無責任ですが)。
回答ありがとうございます。
>・多角形を運転するのはあなたですから、更新領域を予想する事もできる気がします。
ちょっと意味不明ですが、動点Qを制御する(多角形を運転する?)のは環境であって、環境の変化にすばやく応答するのが私(プログラム)です。
>ところで、内部的には秒当たり100回の更新があったとしても、出力の更新は秒当たり25回くらいで良い気もします。人間の目なんてそんなものです。もう考慮されたかも知れませんが・・・。
おっしゃるとおりですが、ゲームのようなものですが、ゲームではありませんので、出力の更新は秒当たり25回も必要ありません。変化自体は10分に1回あるか無いかなので、最大でも1秒1回対応できれば十分です。
しかし、変化があってからの応答時間が問題なので秒100回程度のサンプリングしています。
当然ほとんどは「変化なし」の判断となります。
また、変化した直後に変化することは無いし、あったとしても無視してかまわないので、
変化検出後に、高速検出のネタをじっくり仕込んで、次回の検出に備える
といったアルゴリズムも大歓迎です。
No.6
- 回答日時:
こんなのはどうでしょうか?
辺を延長して得られる直線l_nからできる直線群Lの不等式の符号の積を
QからQ'へ向かう経路が直線群をまたぐ回数で補正して(内/外の)同じ側か違う側かを判定します
といっても結局直線だけでなく辺をまたぐ回数でも
符号の積と同じ側であるか違う側であるかの判定は影響を受けるため
境界をまたぐのは1回だけになるように経路を
多角形の境界上へ他の境界をまたがずにアクセスする経路(Q→R/Q'→R')と
境界上を周回する経路(R→R')という経路の合成経路S:Q→R→R'→Q'上を考え
経路S上で何回直線群Lを横切ったかによって補正します
横切る直線群の数が偶数なら(符号の積)>0で同じ側、(符号の積)<0で違う側
横切る直線群の数が奇数なら(符号の積)<0で同じ側、(符号の積)>0で違う側
とします
不幸にして直線l_n上にQ、Q'がなってしまい、符号の正負が判定できないときには、
内外の判定には無関係な範囲にQ、Q'をほんの少しだけ移動させたらよいかと思います
Q→Rを横切る直線l_nの数や、周回経路R→R'上で横切る直線の数は
たとえば多角形の辺毎に予め横切る直線の数を算出するなどしておけば、
新しいQ'毎に毎回計算しなくてもよいので
アプリケーションにもよるのでしょうが高速化に繋がるのではないでしょうか?
No.5
- 回答日時:
ANo.3へのコメントについてです。
> 想定している多角形は人のシルエットを折れ線近時した凹凸のある多角形の感じで、大体50角形程度です。
用途はゲームみたいなものでしょうかね。50角形程度なら、内か外かを毎回判定しても、フツーのプロセッサで数μ秒もあれば足りる。ということは、低速の組込用マイコンなどを使う話でしょうか。
50角形でシルエットを近似できるのであれば、空間分解能はたいしたことないでしょう。さらにその多角形が変化しないのであれば、一度mapを作っておけば、以後は速くできます。mapは、輪郭線のごく近くでは「境界線付近だからきっちり調べなさい」、それ以外では「内側」か「外側」を意味する3値を取る画素(pixel) p(x,y)を適当な間隔で敷き詰めたもの。Qを与えたとき、Qに最寄りのpixelを参照すれば、ほとんどの場合にはそれで判定完了です。
なお、多角形が変化する場合には、正直にmapを作る代わりに、x軸に平行な直線y=cと多角形との交点を調べてrun length codeを作るほうがずっと速く作れます。mapへのアクセスにちょっとだけ時間が掛かるのが欠点ですが。
再度、回答ありがとうございます。
> 用途はゲームみたいなものでしょうかね。50角形程度なら、内か外かを毎回判定しても、フツーのプロセッサで数μ秒もあれば足りる。ということは、低速の組込用マイコンなどを使う話でしょうか。
そんな感じです。判定だけなら問題になりませんが、他の仕事の足を引っ張らないように軽いアルゴリズムを探索中です。
荒いマップをつかう方法ですね。
「境界線付近だからきっちり調べなさい」でなく、「境界線xx番付近だから線分XXとの交差をきっちり調べなさい」に出来れば、探索時間が大幅に低減できそうですね。問題はマップの最適な細かさを決めるところでしょうか。
ありがとうございます。検討したいと思います。
No.3
- 回答日時:
問題の多角形が凸だ、というような条件があれば速くできそうですが、どんな形でもありうるのだとすると、たとえばQが交差した辺とは全く無縁の辺がQとQ'を切り分けている可能性がありますから、基本的には全部の辺を調べざるを得ないと思います。
多角形の辺(頂点も含む)上の点のうち、Qに最も近い点Rを調べておけば(これはご質問のアルゴリズムで各辺を調べるツイデに行えるので、手間はさほど大きくならないでしょう)、QからRまでの距離をrとするとき、Qを中心とする半径rの円内の点はすべてQと同じ側にあるから、もしQとQ'の距離がr未満ならそれだけで判定は完了します。だから、Qとごく近いQ'をいくつも調べたいという時には有効でしょう。
回答ありがとうございます。
>問題の多角形が凸だ、というような条件があれば
すいません。
想定している多角形は人のシルエットを折れ線近時した凹凸のある多角形の感じで、大体50角形程度です。
点Qの座標は秒100回程度更新され、そのつど、内点か外点かを判断していのです。
点Qが境界線から十分離れた位置を移動している場合には、半径rが大きく取れるので、十分実用的なアイデアと思います。早速、使わせていただきます。
ありがとうございます。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 『弧は弦より長し』 8 2022/04/18 10:23
- 数学 複素数平面についての問題です。 2点α、βが定められており、それらともう1点γと結ぶ三角形が直角二等 6 2023/06/30 09:47
- 高校 数学Aの問題で、円に内接するN角形(N>4)の対角線の総数は ア 本である。また、Fの頂点三つからで 1 2023/04/13 17:47
- 数学 数学の質問です。 abcはそれぞれ三角形の一辺である。 a²+b²+c²−ab-bc−ca=0が成り 4 2022/10/29 12:57
- 数学 場合の数、確率 30 円周上の鋭角三角形(偶数等分) 2 2023/07/07 04:56
- 数学 数学 三角形の3つの頂点から出る3本の直線が1点で交わる この場合3本の線は「角の二等分線」以外あり 2 2023/02/21 21:01
- 数学 問題文 正n角形がある(nは3以上の整数)。この正n角形のn個の頂点のうちの3個を頂点とする三角形に 4 2023/03/22 14:57
- 数学 AB=2,BC=3,∠ABC=60°の三角形がある。 点Aから辺BCに垂線を下ろし辺BCとの交点をD 4 2023/02/02 15:55
- 数学 数学得意な方教えてください 平面上の任意の点から同一平面上にある多角形の各頂点までの距離の平均は、多 1 2023/08/28 16:36
- 数学 三角比の相互関係「sinA^2+cosA^2=1」が直角でなくても成り立つ理由について。 これは、三 8 2022/03/31 09:22
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
メール文章で直線の描き方について
-
偏微分の「偏導関数の応用」の問...
-
PowerPoint 罫線で直線を引く...
-
電気ハンドホールの設置間隔の...
-
不等号をはじめて習うのは?
-
3次元の近似直線
-
曲面(楕円)と直線との点の最...
-
軌跡と領域 円に接するときに...
-
general formとstandard formの...
-
実数x,yはx^2+y^2=4を満たすと...
-
線形代数の線形変換などに関す...
-
自己インダクタンスの計算
-
点(1,2,-1))を通り、2平面 x+y+...
-
円x²+y²=1と直線y=x+mが接する...
-
wordの図形の描き方について
-
三次元空間での直線の式
-
恒等式の質問
-
直線を含む平面
-
合同変換 3つの鏡映の合成で...
-
直線の傾き「m」の語源
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
メール文章で直線の描き方について
-
PowerPoint 罫線で直線を引く...
-
三角形の面積を問う。正方形の...
-
エクセル・パワーポイントなど...
-
電気ハンドホールの設置間隔の...
-
グランドにきれいな長方形を描...
-
円を直線で分割すると・・・?
-
数学 整数 数的推理
-
ユークリッド幾何学とは?
-
円x²+y²=1と直線y=x+mが接する...
-
直線を含む平面
-
三角形の辺の和が最小になるよ...
-
実数x,yはx^2+y^2=4を満たすと...
-
不等号をはじめて習うのは?
-
3点が「同一直線上」と「一直...
-
なまし鉄線(番線)をまっすぐ...
-
excelで、曲線の長さを計測する...
-
平面と面の違い
-
作図の問題です
-
指数近似曲線の計算方法について
おすすめ情報