ある点が凹凸多角形の内部にあるか？外部にあるか？

いつもお世話になっております．
タイトルに書きましたとおり，
「ある点が凹凸多角形の内部にあるか？外部にあるか？」を判断するためのアルゴリズムを探しております．

ネットを散策して，
「ある点から伸ばしたRayと多角形との交差回数」というアルゴリズムを見つけたのですが，計算とプログラムでの実装が大変そうなので

http://www.330k.info/essay/takakugatanonaigaihan …参考サイト1)のサイトや
http://soudan1.biglobe.ne.jp/qa3990775.html(参考サイト2)の４番目の回答で紹介されている
「偏角の和」といった条件を使った判定方法を利用したいと考えております．

しかしながら，私の知識では，こちらに書かれているアルゴリズムを理解することができません．

（参考サイト1）を読んでいると，
多角形の角頂点Pnを (Xn, Yn) (n=0,1,・・・・)，ある点をR (Xr，Yr)とした時に
∠Pn R Pn+1の和が
0，±4π，±8π，…のとき，点Rは多角形の外
±2π，±6π，±10π…のとき，点Rは多角形の中
と判断できるそうなのですが，上手くいきません．

∠Pn R Pn+1の和を求めてはみたのですが，上記の条件に当てはまりません．

どなたか「偏角の和」使った「ある点が凹凸多角形の内部にあるか？外部にあるか？」の判断方法を解説していただけないでしょうか？

また，計算コストが軽ければ上記の方法でなくても問題ありませんので，別の方法を教えていただけても助かります．

よろしくお願いします．

No.1 回答者： skydaddy 回答日時： 2010/11/19 18:42

多角形を三角形の集合ととらえ、ある点が各三角形の中にあるかどうか調べるのはどうでしょうか？

すべての三角形の中に無ければ外にあることが判ります。

この回答へのお礼

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

この方法だと多角形を自動的に三角形に分けるのが難しくないでしょうか？

お礼日時：2010/11/19 22:43

No.2 回答者： nattocurry 回答日時： 2010/11/19 19:20

∠Pn R Pn+1 の和ですが、

m角形の場合は、

∠P1 R P2
∠P2 R P3
：
：
∠Pm-2 R Pm-1
∠Pm-1 R Pm

これらの和だけではダメだと思います。

更に
∠Pm R P1 (∠P1 R Pm では符号が逆になってしまう)
の角度も足す必要があると思います。

それも解った上で、「上記の条件に当てはまりません」なのでしょうか？

この回答へのお礼

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

＞∠Pm R P1 (∠P1 R Pm では符号が逆になってしまう)の角度も足す必要があると思います。
はい，多角形は閉じた図形を想定しており，∠Pm R P1も足していますが
合計値は，中途半端な値になってしまい
0，±4π，±8πや±2π，±6π，±10πといった値にはなりません．

考え方としては，∠Pn R Pn+1 の和が
4πで割った時の余りが0なら外，
4πで割った時の余りが2なら内
であっているのでしょうか？

お礼日時：2010/11/19 22:52

No.3 回答者： nag0720 回答日時： 2010/11/19 21:10

＞「ある点から伸ばしたRayと多角形との交差回数」というアルゴリズムを見つけたのですが，計算とプログラムでの実装が大変そうなので

４点P1(X1,Y1)、P2(X2,Y2)、R(Rx,Ry)、Q(Qx,Qy)があるとき、
線分P1P2とRQが交差しているかどうかの判定は、
{(Qx-Rx)(Y1-Ry)-(X1-Rx)(Qy-Ry)}{(Qx-Rx)(Y2-Ry)-(X2-Rx)(Qy-Ry)}<0　かつ
{(X2-X1)(Y1-Ry)-(X1-Rx)(Y2-Y1)}{(X2-X1)(Y1-Qy)-(X1-Qx)(Y2-Y1)}<0
でできます。

点Qのx座標が点Rのx座標と同じでy座標が遥か上にある場合、つまりQ(Rx,∞)の場合、上記の判定式は、
(X1-Rx)(X2-Rx)<0　かつ　{(X2-X1)(Y1-Ry)-(X1-Rx)(Y2-Y1)}(X2-X1)>0
となります。

P1(X1,Y1)、P2(X2,Y2)を変えていけば、多角形との交差回数を求めることができます。


これは、arcsinやarctanなどで角度を求めるよりはかなり計算量が少なくなると思いますが。

No.4 回答者： 178-tall 回答日時： 2010/11/19 22:32

　

http://www.330k.info/essay/takakugatanonaigaihan …
の後に余計な文字列があるので、チャンと飛びませんヨ。

それはさておき、
* ある点から多角形の各頂点を順番に見ていったときに何回転するか
の方法が推奨されてますね。

初めに「ある点」を原点にシフトすれば、考えやすそうです。
その際、気をつけねばならないのは、「ある点」が多角形の辺上にある場合。
最初に、それをチェックしてしまうほうがわかり易そうです。

「ある点」が多角形の辺上になければ、各頂点が辺を順繰りにたどるよう整列されている場合、全頂点を一巡したときに原点のまわりを 360 度めぐったか否か、判定すれば良いのでは？
　　　

この回答へのお礼

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

リンクミスしてしまったみたいです．申し訳ないです．

＞初めに「ある点」を原点にシフトすれば、考えやすそうです。
「ある点を原点に移動させる場合の移動量」多角形の各頂点を移動させればいいでしょうか？

＞「ある点」が多角形の辺上になければ、各頂点が辺を順繰りにたどるよう整列されている場合、
各頂点は左回りでリストに格納しています．

＞全頂点を一巡したときに原点のまわりを 360 度めぐったか否か、判定すれば良いのでは？
この方法は，
「∠Pn R Pn+1の和」でいいのでしょうか？

お礼日時：2010/11/19 22:58

No.5 回答者： 178-tall 回答日時： 2010/11/20 08:44

大したハナシではないので、かなり端折ってました。

>多角形の各頂点を移動させればいいでしょうか？

もちろん。Pn，R すべて単純に平行移動、がわかり易いでしょうね。


>各頂点は左回りでリストに格納しています．
>　…
>「∠Pn R Pn+1の和」でいいのでしょうか？

向きを示す符号 (+, -) も勘定に入れれば、P0 からスタートして P0 へ戻ったとき、
　「∠Pn R Pn+1の和」= 0 度ならば、R は多角形外部
　「∠Pn R Pn+1の和」= 360 度ならば、R は多角形内部
になるのでは？
　　　

No.6 回答者： nattocurry 回答日時： 2010/11/20 10:43

> 考え方としては，∠Pn R Pn+1 の和が

> 4πで割った時の余りが0なら外，
> 4πで割った時の余りが2なら内
> であっているのでしょうか？

それで合ってると思います。

実際にどのような状況でどのような計算をして、条件に当てはまらなかったのか、具体例を挙げてみませんか？
もしかしたら、意外なところで考え違いや計算違いをしているかもしれませんよ。

ちなみに、和が奇数πのときは、多角形の線上にあることになりますね。

No.7 回答者： 178-tall 回答日時： 2010/11/21 20:47

点 R を原点にした場合、P を複素平面上の点 (X + i*Y) とみなして偏角を求めるのがいちばん簡単みたい。

スプレッドシート上にて、シート関数で組むには、細かな配慮が要るようで…。

・スプレッドシートが返してくる主値 ASIN(X/SQRT(X^2+Y^2)) から点 P (X + i*Y) の偏角φ (≧0) を得るには、
　　ASIN(X/SQRT(X^2+Y^2)) を A (セルアドレス) として、
　　　=IF(X<0,PI()-A,IF(Y<0,2*PI()+A,A))
などの後処理を要する。

・点 P の偏角φの増分を累計し終えたとき、その結果がスタート点 P0 の偏角φ0 を超える場合と、超える場合とがありえる。
φ0 を超えたら、φ0 →φ0+2*PI() の修正が必要。
超えなければ、そのまま。
このあたりを熟慮すれば、もっとスマートなアルゴリズムが得られるのかも…。
　　　

No.8 回答者： nattocurry 回答日時： 2010/11/24 12:34

たとえば、

A(10,10) B(-10,10) C(-10,-10) D(10,-10) という四角形があって、O(0,0)が内部にあるかどうかを判定するときに、
∠AOB＝∠BOC＝∠COD＝∠DOA＝90°になりますよね。

次に、BとDの座標を入れ替えて、
A(10,10) B(10,-10) C(-10,-10) D(-10,10) という四角形があって、O(0,0)が内部にあるかどうかを判定するときは、
∠AOB＝∠BOC＝∠COD＝∠DOA＝－90°になりますよね。

あなたの計算式では、そのような計算結果になっていますか？



＞ちなみに、和が奇数πのときは、多角形の線上にあることになりますね。

これは私の勘違いでした。すみません。