多角形の当たり判定

[戻る]
you 2010/11/05(金) 17:14:45
多角形と点の当たり判定を行う方法を教えてください。
ベクトルの内積を使うそうなのですが具体的なコードを掲載しているサイトが見つかりま
せんでした。お願いします。

you 2010/11/05(金) 17:45:19
環境はVC++2008 OSはWin2008です

you 2010/11/05(金) 17:45:44
Win32APIを使用します.

Alq3 2010/11/05(金) 20:57:12
数学的には多角形を三角形に分割して、各三角形の内部にあるかどうか判定すればいい
です。
実装に依存する部分が大きいので、具体的なコードはまず見つからないでしょう。
自分で書くしかありません。

いずれにせよ
1.ベクトルの内積の使い方は分かっているが実装の仕方が分からないor面倒くさい
のか
2.ベクトルの使い方がそもそも分からない
のかハッキリさせるべきだと思いますよ。

you 2010/11/05(金) 22:34:36
Alq3さん
2の方です。
実装するときに
HitCheck(POINT* side,int sidenum,POINT pt)
のような引数にしたいです。

Alq3 2010/11/06(土) 03:22:20
>実装するときに
>HitCheck(POINT* side,int sidenum,POINT pt)
>のような引数にしたいです。
あなたがそのように実装すればできるでしょう。

…
多角形が凸であるかないかによって難しさが格段に変わります。
(1)多角形が凸なら上で述べたように三角形に分割し、どれかの三角形の内部に含まれる
か否かで判定をするのが、良いと思います。
この場合は内積を考える必要もありません。連立方程式で解けます。

(2)多角形が凸でないなら
http://soudan1.biglobe.ne.jp/qa3990775.html
のNo.5がわかりやすいと思います。こちらも内積は必要ありません。
またNo.8の回答者が示されている、凸図形に分割したあと(1)を適用する方法も非常に良
いですね。かなりややこしいですが

なおWin32APIを使うのであれば
Polygon関数で多角形を塗りつぶし描画
⇒該当点が塗りつぶしの色に一致するかどうかGetPixelで判定
という力技もあります。

you 2010/11/06(土) 09:49:36
alq3さん
丁寧なご回答ありがとうございます。
参考URLの(5)ですが、引いた線分が頂点を通る場合どうすればいいのでしょうか?

Alq3 2010/11/06(土) 12:32:42
頂点に近い所を通ってしまう場合は、外側の点を適当に変更して
もう一度判定するということが考えられます。

なおPOINT型のx,y座標が整数である場合なら
外側の点のx,y座標のどちらか片方のみを無理数とすることで
そもそも頂点を通ると言う状況を回避できます。


どちらのばあいにしても外部に取る点は多角形の近くにしておくのが
計算精度上非常によろしいと思われます。

you 2010/11/06(土) 18:02:40
[[解決]]
Alq3さん
何度もありがとうございました。

古いスレッドには追加発言できません。