多角形の内部かどうか判定する方法

質問

2次元座標系にあるn個の点を順に接続して多角形を作ります。
n個の点は(x1,y1)-(x2,y2)-…-(xn,yn)とします。
(xn,yn)と(x1,y1)を最後につないで閉じた多角形とします。

このとき点(a,b)が多角形の内部にあるかどうかを判定するにはどのようにしたら良いでしょうか？

辺同士が交わるような点の配置は無いとします。

よろしくお願いします。

回答No.10

BlurFiltan

＃７ です。
遅くなりましたが補足します。

> 判定関数が内部でどのように判定しているのか、
> を知りたいと思っています。

Adobe（Macromedia）の社員でもプログラマでもないので，
そのアルゴリズムはわかりませんが，
当たり判定をするときのアルゴリズムは，おそらく，見たそのままのアルゴリズムだと思いますよ。
つまり，
内積とか外積とか角度とかそういう計算は内部でしていないと思います。
「オブジェクトに面を持たせて，
その面が点と接触しているかしていないかを判定している。」
つまり，見たそのまんまです。

オブジェクトに面を持たせるときには複雑な計算もさせている部分もあると思います（例：面を閉じるとかいうアルゴリズム）。
しかしいったん面を作成してしまったあとは，その面と接触しているかしていないかです。
たとえば背景と面との色を比べても良いと思います。
つまり点がある場所の背景色を get して，
FFFFFF だったらハズレ，00FFFF だったらアタリ。
色がダメでしたら，色とは別の１ビットのプロパティを与えても良いと思います。
そのような演算をしていると思います。

なぜそう思うかと言うと，
＃７ ではプログラムによって面を作図しましたが，実際そんなことはまずしません。
適当に描いた絵やラフな手描きの絵（と言ってもベクトルデータ（ミサイルとかゴジラとか））で当たり判定をとるのが普通です。

その図形を一々方程式に変換して，その方程式で当たり判定をとるなどということはナンセンスです。
してできなくはないと思いますが，おそらくその演算でアニメーションが止まります。

ActinScript は直接関係ないとはわかっていましたが，
そう言った意味を含めて ＃７ を書かせていただきました次第です。

回答No.9

POTATO_XP

あ！下のやつは星型で手詰まりますね。もう一工夫いります。それと、もっといい方法がありました。完全に閉じている訳ですからx=aの直線で貫いた場合、[ P_i+1 - P_i ]区間内に交点が存在する線分が偶数個あるはずです。それをy軸の値が大きい順にソートすれば、[y0-y1][y2-y3]・・・[y_2m-1,y_2m]が区間内を表します。この区間内にbが入っていれば、(a,b)は領域内になります。ただ、y軸と平行な線分にぶつかった場合の特殊処理を忘れずに。この方法なら多面体の内点判定も楽勝ですな。恐らくコレが最強かと・・・。

以前、この方法でレイトレーシングの交差判定やったのスッカリ忘れてました・・・。発想次第でこれだけスピードが変わるというのを試してみると面白いですよ。自分の時は３角形の内点判定が複数個って感じで大きな速度差が出てました・・・。お試しあれ。

お礼

ありがとうございます。
他の方からも同様のご回答をいただきました。
参考になりました。

回答No.8

POTATO_XP

＞第一段階の、凸な多面体になるまで分割、とあるので、このアルゴリ
＞ズムを考えないといけませんが、すぐに思いつきませんでした。

ではでは、補足です。真の第一段階は、

＞n個の点は(x1,y1)-(x2,y2)-…-(xn,yn)とします。
＞(xn,yn)と(x1,y1)を最後につないで閉じた多角形とします。

この順序を自動的に確定する所なんですが、それは定まっているものとして話を進めます。次は以下のベクトルの外積を使い、トレースしつつ
凸な多角形(こう言うんだ・・・)を切り出していきます。(x1,y1)-(x2,y2)-…-(xn,yn)は循環リスト構造にしとくとよいよ。

まず、
vf_n=(x_n+1-x_n,y_n+1-y_n,0)
vb_n=(x_n-x_n-1,y_n-y_n-1,0)
を定義します。(_以降は表記の都合上、添え字を表す事にします。f,bはフォワードとバック)

これも同様にvfnとvbnの外積のz成分の符号で内角が180度超えの分割すべき点かどうかを順々に判断していきます。一つも無ければハッピーで次の内点判定に進んで下さい。手順は以下の通りです。

i=1～nまで繰り返す(ここでnは元の循環参照リストの要素数を表す事に注意。循環参照リストの要素数は除外されていくので可変の値である)

mfg=false、i=1、k=0を初期状態として始める。

1).vf_iとvb_iの外積計算を行う。
2).内角180以下であればiをインクリメントし1).へ
内角180より大きければであれば3).へ
3).マークポイント保持フラグmfgがfalseであれば4).へ
マークポイント保持フラグmfgがtrueであれば5).へ
4).マークポイント保持フラグmfgをtrueに設定し、マークポイント指数kにiの値を設定し1).へ
5).vfmpとvb_iの外積を計算する。ここで、
　　　　vfmp=(x_k-x_i,y_k-y_i,0)
とする。
6).この結果が内角180より大きければkをインクリメントし5).へ
内角180以下なら7).へ進みます。
7).P_kからP_iまでを凸多角形領域として新たに循環参照リストを生成します。これはもういじらない。
8).P_k+1からP_i-1を元の循環参照リストから除外します。
9).mfgをfalse、iを1、kを0と初期化し1).へ

i>nの時点で処理が終了。

ここで終了時に状態が二つある事に注意。mfg=falseで終了する場合と、mfg=trueで終了する場合である。前者は内角180を越える点が存在しなかった場合である。それ以外は後者となり、更に一回分割の必要を残したまま終了する。

その分割は、新たにベクトル
vlf=(x_k+1-x_k,y_k+1-y_k)
vbf=(x_k-1-x_k,y_k-1-y_k)
を定義し、vlf+vbfで生成されるベクトルで点P_kを通る直線に最も近い循環参照リスト上の点をP_sとする。s>k、s<kを気にしつつ領域を除外。P_kが内角１８０以下であれば終了。１８０よりで大きければもう一回で終了です。

多分これで全ての場合で凸領域に分割できるはず。思いつきだからあまり巧くないですが・・・。外積は安易な方法なので、パフォーマンスに関して更に上があるかもしれません。考えてみて下さい。

例えば、浮動少数値でなくていいなら、Zバッファの様な方式の方がレスポンスは良い。ただ、パフォーマンスと使用メモリがトレードオフになってしまいます。とかみたいに。

文章に起こすの超大変でした。
以上、参考にして下さいね。

お礼

詳細に書いていただきありがとうございました。
とても参考になりました。

回答No.7

BlurFiltan

他の方も書かれていらっしゃいますが，
まずご質問の言語がわかりません。

ご質問の言語が もし，
「２次元平面を持つオブジェクト（インスタンス）が作成できるような言語」
でしたら，
多角形の線で区切られた平面 を持つ オブジェクト を作成して，
そのオブジェクトと点との座標接触判定をすれば簡単ではないかと思います。
最初から考えることに比べると反則的なことかもしれませんが...。

多角形の辺で囲まれた中にあるとかないというような座標で全てを考えるのではなくて，
オブジェクト（インスタンス）というものを利用するということです。

＃３ の方の書かれていらっしゃいますが，
Flash(ActionScript) には当たり判定メソッド（MovieClip.hitTest メソッド）があります。
※ActionScript は
　 Adobe Flash というソフトでなくても使用できます。

ご質問の言語は ActionScript ではないとは思いますが，
この ActionScript を用いた例を書くと以下のようになります。

多角形の作図から判定まで，
すべてを ActionScript でしてしまうコードです（本当に動作する例）。

----------------------------------------------
// 座標データ格納配列の作成
crdArr = new Array();

// 各 xy座標をハッシュで代入(データは適当)
crdArr.push({x:40, y:30});
crdArr.push({x:100, y:40});
crdArr.push({x:130, y:90});
crdArr.push({x:90, y:110});
crdArr.push({x:90, y:150});
crdArr.push({x:30, y:120});
crdArr.push({x:30, y:90});
crdArr.push({x:70, y:110});
crdArr.push({x:90, y:80});

// 多角形描画用ムービークリップを深度 0 に作成
this.createEmptyMovieClip("polygon", 0);

// ムービークリップの中に多角形の塗りを描画
polygon.beginFill(0x00FFFF, 100);
polygon.moveTo(crdArr[0].x, crdArr[0].y);
for (i=1; i<crdArr.length; i++) {
polygon.lineTo(crdArr[i].x, crdArr[i].y);
}
polygon.endFill();

// 判定結果表示用テキストフィールドを作成
this.createTextField("judge_txt", 1, 150, 30, 0, 0);
judge_txt.autoSize = true;

// 任意の場所でマウスダウンしたときの動作
this.onMouseDown = function() {
judge_txt.text = "座標 ("+_xmouse+", "+_ymouse+") は";
if (polygon.hitTest(_xmouse, _ymouse, true)) {
judge_txt.text += "\n多角形内にあります。 ○";
} else {
judge_txt.text += "\n多角形内にありません。 ×";
}
};
----------------------------------------------

動作検証を簡単にするため，
Flash上をクリックしたときのマウスの座標が多角形と当たっているかどうかを調べていますが，
特にマウスの座標でなくてもかまいません。

　オブジェクト.hitTest(任意x座標, 任意y座標, true)

これで true か false の戻り値を得ることができるので，
多角形オブジェクトが任意の x座標 y座標 と当たっているかどうかが調べられます。
（シューティングゲームにはこの hitTestメソッド を使ったものが多いです。）

上記スクリプトコードを書いて作成できるのは Flash です。
しかし簡単な ActionScript だけですから，
上にも書きました通り少しだけ高度な ActionScript が使えるソフトであれば，
Adobe Flash を使う必要は全くありません。

例えば フリー の Flash作成ソフト ParaFla! や Suzuka でも，
十分作成できます。

・ParaFla!
http://www.geocities.jp/coa9999/

・Suzuka
http://www.cty-net.ne.jp/~uzgensho/

・ParaFla! であれば
ParaFla! をインストール(DL＆解凍)して ParaFla! を起動。
フレーム1 となっている部分を右クリック→「アクションを挿入」。
出てくる イベントのプロパティ パネル でアクションの設定を ＜スクリプト＞ にする。
「スクリプトを編集」ボタンをクリックしてスクリプトエディタを出し，
そこに上記スクリプトをコピペ。
「適用」ボタンを押してスクリプトエディタを閉じ，
[プレビュー]→[プレビューウィンドウ] で動作確認できます。

・Suzuka であれば
Suzuka をインストール(DL＆解凍)して Suzuka を起動。
上部左にある □背景 となっているレイヤーを選択して，
右クリック→アクションレイヤーの挿入 で「フレームアクション」のレイヤーを挿入。
その右の タイムライン の フレーム1 を選択し，
画面右下の「スクリプトを編集」ボタンをクリックしてスクリプトエディタを出して，
そこに上記スクリプトをコピペ。
[ウィンドウ]→[プレビュー] で動作確認できます。

座標は適当だと言っても，一応辺どうしの交差はないようにはしてあります。
上スクリプトの座標の場合だと，
だいたい次のような形の多角形が自動描画されますが，

　□□□□□□□□□□□□
　□□■■■□□□□□□□
　□□□■■■■■■□□□
　□□□□□■■■■■□□
　□□□□□□□■■■■□
　□■□□□□■■■■□□
　□■■■□■■■■□□□
　□□■■■■■■□□□□
　□□□□□■■■□□□□
　□□□□□□□■□□□□
　□□□□□□□□□□□□

■の(実際は 水色00FFFF に塗られる)部分でマウスダウンすると，
その座標と　多角形内にあります。 ○　が表示されます。
□の(実際は何もない部分)部分でマウスダウンすると，
その座標と　多角形内にありません。 ×　が表示されます。

Flashは使い方によって，
このように図形演算ソフト（道具）としても使えることもあります。
Flash は元が図形と図形のアニメーションソフトですから，
このようなものの場合（場合によります），
例えば Excel (VBA や ワークシート関数)などでプログラミングするよりはるかに簡単かもしれません。

以上，
ご質問の言語は ActionScript ではないことは推測できますが，
「２次元平面を持つオブジェクト（インスタンス）が作成できるような言語」であると，
場合によっては非常に簡単にできることもあるという参考例です。

お礼

別の回答にも書きましたが、あえて言語を書くならばC言語です。
ActionScriptは使用したことがありませんが、記述していただいたプログラムの内容は理解できます。しかし、判定関数が内部でどのように判定しているのか、を知りたいと思っています。もしご存知でしたらよろしくお願いいたします。

ありがとうございました。

回答No.6

POTATO_XP

もし内角が180度を超える点がある場合は、それが発生しない多角形
となるまで分割します。この処理を一段かませます。これがミソ。

その後の多角形の各座標が(x1,y1)-(x2,y2)-…-(xn,yn)、任意の点が
(a,b)であるとして、以下ベクトルを定義します。都合上３次元ベクト
ルとします。

v1=(x2-x1,y2-y1,0),vp1=(a-x1,b-y1,0)
v2=(x3-x2,y3-y2,0),vp2=(a-x2,b-y2,0)
v3=(x4-x3,y4-y3,0),vp3=(a-x3,b-y3,0)
・・・
vn=(x1-xn,y1-yn,0),vpn=(a-xn,b-yn,0)

このviとvpiの外積をそれぞれ求め,その結果のzベクトル成分が全て同
一符号であった場合のみ、内点です。言い換えるなら、

k1=(x2-x1)*(b-y1)-(y2-y1)*(a-x1)
k2=(x3-x2)*(b-y2)-(y3-y2)*(a-x2)
k3=(x4-x3)*(b-y3)-(y4-y3)*(a-x3)
・・・
kn=(x1-xn)*(b-yn)-(y1-yn)*(a-xn)

の全てのｋが同一符号であれば良いということになります。注意すべき
点としてP1、P2、・・・とたどっていく順序が右回り・左回りの夫々で
正負が逆転します。必ずどちらかとなる様に定義しプログラミングして
下さい。また、線上に(a,b)がある場合、ki＝０となる状況が１つだけ
存在します。線上は内点とした方が良い(上の分割境界上の時)為、０以
上、０以下と判定してください。

コレを分割領域全てにおいて計算し、内点との判定が出た時点でbreak
します。どういうプログラムを書くべきか見えてきましたね？

余裕があったら、応用として多面体の内点を判定する方法を考えてみて
ください。かなり頭の体操になりますよ。

お礼

数学的にエレガントな回答だと思います。
第一段階の、凸な多面体になるまで分割、とあるので、このアルゴリズムを考えないといけませんが、すぐに思いつきませんでした。

多面体への応用としては、面の法線ベクトルと、判定すべき点と面の頂点を結ぶベクトルとのなす角度を調べれば‥‥などと考えましたが、ひょっとして外積を4次元に拡張するとか。。。

ありがとうございました。

回答No.5

ncc-1701_a

解法の考え方の一つとしてですが。

必ず多角形の外側になる点 （a',b'） を設定します。
具体的には、次の４つの内いずれかの条件を満たす点です。
a'>Xmax
a'<Xmin
b'>Ymax
b'<Ymin

この (a',b') と (a，b) を結ぶ直線を引きます。
線 (a，b)-(a'，b') と多角形の辺との交点の数が奇数なら内側、偶数 (当然、０も含みます。) なら外側となります。

お礼

確かに判定できそうです。

(a',b') と (a，b) は、a'=a または b'=b となるように取ると計算がより楽になりそうな気がします。

ありがとうございました。

回答No.4

ultraCS

考え方です

まず、角(xi,yi)(a,b)(xi+1、yi+1)の角度を-πからπの範囲(-180度から+180度でもいいです)で求めます。大切なのは、(xi,yi)(a,b)(xi+1、yi+1)の方向を常に決めておくことで、前の点iに対して左回りになっていればプラス、右回りであればマイナスとします。
これをi=1～nまで繰り返し(i=nでは、nをi+1とします)、その総和を求めて2πになれば内側、0になれば外側です。計算誤差が出てぴったりにはならないのでその辺は判定してください。

同様に角度の代わりとして三角形(xi,yi)(a,b)(xi+1、yi+1)の面積をヘロンの公式で求め、方向に応じて加減していけば一周すると内側なら面積、外側なら0になります。こちらの方が使い勝手がよいかも(これはちょっと記憶が怪しい)

点が辺上に来た場合や頂点上の場合の別判定はしてください。

お礼

S=(1/2)ab sin(C)、S:面積、a b:辺の長さ、C:角Cの大きさ
の公式で角度または方向を求めることになると思いますので、前者と後者はほぼ同じだと思います。

理論上、外部にあれば0になりますが、丸め誤差で0にならなかった場合に辺上にあるかどうかを毎回別判定しなければならなくなるのではないかという懸念が若干あります。

ありがとうございました。

回答No.3

noname#58606

お使いの言語は何なのでしょうか？
使ったことはないので、知識だけなのですが、Delphiには多角形の交差判定の関数があったと思います。（Flashでもあったかな？うろ覚え。

Win32APIでも、あったような。
とりあえず、CombineRgnは見つかりましたが。
http://www.geocities.jp/asumaroyuumaro/program/winapi/region.html
これって、うまく使えないんですかね？
ゲームは、いつか作っては見たくて、それらしいものをスクラップはしているのですが。

お礼

言語はC言語を想定しています。
アルゴリズムについての質問ですので、
判定関数を用いることは想定していません。

もしくは、判定関数があるとしたら、その中では
どのようなアルゴリズムになっているのかを知りたいと思っています。

ありがとうございました。

回答No.2

denbee

このページの下の方に原理が記載されていました。
（凹凸両方の場合）
http://kite.meikai.ac.jp/csaito/HTML/ARCAD11/ARCAD11.HTM

お礼

辺の方程式と定義域のリストを作成して、
ターゲットの点との上下関係から求めるという方法ですね。
直感的で分かりやすいです。
直線の式を求めるところで計算量が増えそうな点が若干心配ですね。
ありがとうございました。

回答No.1

denbee

単なる思い付きですが・・・
　１）点(a,b)と多角形の1点Ｘを結ぶ線分を考える
　２）上記線分が多角形のすべての辺と交わらないかチェック。
　　　交わる辺が存在するなら、点(a,b)は多角形の外部にある
　　　（三角形で考えてみてください）
　３）多角形のすべての点について、２）のチェックを繰り返す
　４）３）のチェックで交わる辺が存在しないならば、点（a,b)は
　　　多角形の内部に存在する

２つの線分が交わるかどうかのチェック方法はこちら。
http://www.deqnotes.net/acmicpc/2d_geometry/lines

・・・と、ここまで考えて、上記の方法は多角形の内閣が180度を超えるものが存在する場合は
使えないことに気がつきました。
（星形みたいなギザギザの奴）
うーん。もうちょっと検討が必要ですね。

お礼

確かに多角形が非凸型の場合には、うまくいかない気がします。
ありがとうございました。