2007/02/23 (Fri) 多角形の内外判定

さて、これでパズルを作り始めれる...と思ったら、まだ問題があることに気がつきました。

空白のピースから隣のピースにマウスが移った時に、始めてその（逆の）方向にピースを動かす...といった動作をさせるためには、現在のマウスがどのピースの上に存在するかということを判定しなければなりません。

今までは、長方形や円に近似させれば良かったのですが、今回は斜め向きの台形などもあるため、もう少し真面目に内外判定をしなければユーザーの思ったとおりの動きにはならないことに気がつきました。

う～ん、これは数学に頼るしかない...。


ということで、「内外判定」「座標」あたりで検索をかけると、
「偏角の原理」というものを見つけました。

あなたがビルのてっぺんにいるとします。
４つの地点を結んでできる四角形の左回り（または右回り）の順番で
それぞれの地点を見ていく時、元の頂点に戻るまでに一周したら
あなたは４つの地点の内部にいます。
一周せずに体をねじるだけに終わったら外部にいることになります。

...なるほど、体感しました。


で、これを式に表すと

すべての辺に対し対象点との外積が全て同一符号なら内部

（Ｐ－Ａ）×（Ｂ－Ａ）
（Ｐ－Ｂ）×（Ｃ－Ｂ）
（Ｐ－Ｃ）×（Ｄ－Ｃ）
（Ｐ－Ｄ）×（Ａ－Ｄ）

となるそうです。

ちなみに外積は

Ｑ×Ｒ ＝ Ｑx × Ｒy - Ｒx × Ｑy
　　　 ＝ |Ｑ||Ｒ|ｓｉｎ（θ）

なので、２つをあわせると

（Ｐx - Ａx）×（Ｂy - Ａy）－（Ｂx - Ａx）×（Ｐy - Ａy）
（Ｐx - Ｂx）×（Ｃy - Ｂy）－（Ｃx - Ｂx）×（Ｐy - Ｂy）
（Ｐx - Ｃx）×（Ｄy - Ｃy）－（Ｄx - Ｃx）×（Ｐy - Ｃy）
（Ｐx - Ｄx）×（Ａy - Ｄy）－（Ａx - Ｄx）×（Ｐy - Ｄy）

となるのではないかと。

やっとプログラムにできるところまできましたね。

で、すっ飛ばしたにしても、ここまでたどりついたあなたのために、サンプルを作ってみました。 (^^)v

こちら です。

カーソルを動かすと、４つの黄色の点の内部にある時は青色、外部にある時は赤色にかわります。

単にそれだけのサンプルですが、ぐりぐり動かしていると、何かゲームができそうな気が...。

そう、昔はサンプルを作りながらゲームの発想が生まれたものでした。
しばらく忘れていたなぁ...この感覚。