複数の回転する長方形の衝突判定

プログラミング初心者です。
言語は「processing」ですが、他の言語での解説でもＯＫです！

二次元内で画面内の複数の正方形がランダムに回転しながら移動するときの衝突判定ができずに悩んでいます。
回転がない場合はできるのですが・・。

色々調べてみて、各頂点と辺の最短距離を全ての場合に調べたり、分離線というものを使ったりと、考え方としては納得できるのですが、具体的にどのように書けばいいかが分かりません。

私のベクトルの理解が不十分なのかもしれないのですが、具体的な例があれば嬉しいです。

よろしくお願いします。

No.1 回答者： DIooggooID 回答日時： 2009/06/26 15:27

もし、正方形の重心を中心にして回転させるのでしたら、・・・

最初から全ての場合で条件判定をするのではなく、・・・

まずは、正方形の外接円を考え、その外接円同士が衝突する状況を
判断し、外接円どおしが衝突したら、その時点で、二つの回転している正方形としての衝突判定を行ってみてはいかがでしょうか。

この回答への補足

質問のミスなのですが正方形ではなく細長い長方形でした。申し訳ありません・・。

回答ありがとうございます！
円を使う発想は無かったです。長方形でも応用できますね。参考にさせていただきます。

補足日時：2009/06/26 15:51

No.2 回答者： fujillin 回答日時： 2009/06/26 16:34

ご質問なさっているのは、プログラムと言うよりは、その前の数学の問題ではないでしょうか？

はるか昔の学校の知識を思い出しながらの回答なので、もっとエレガントな回答がありだろうと思いますが、それは他の方に譲るとして…
（実際には、そちらの方法の方が計算負荷が少ないと思いますが）

1）2つの正方形（A,Bとする）の中心間距離Dを求める。
2）Dが、A、Bの対角の和の1/2より大きければ、重ならない。
3）Dが、A、Bの一辺の和の1/2より小さければ、重なる。

4）上記2）、3）以外の場合
　Aの頂点4点のうちBに近い2点を選択して、その辺にBの各辺（実際
　は近い2辺をチェックすれば足りると思う）が交わっていれば、重なっ
　ていると判定。
　（Aの2点は、2番目、3番目が同じ距離の場合があるがどちらでもOK）
4-2）Aの1辺が座標軸（仮にX軸とする）となるようにBの頂点を座標変換
4-3）Bの各辺について、端点の新座標のｙ座標の正負が逆で、かつ新
　　X軸に交わる時のX座標がAの一辺の長さ以下であれば交わっている。
　　（＝重なっている）

…ってな感じではどうでしょうか？
実際の計算では、並行な場合とか角度0などで0割り算が出ないようにしなければならない分注意が必要でしょうけど。
また、4）の座標変換は、事前に一般式で机上で解いておけば計算がもっと簡単にできそうな気がします。（判定したい内容は決まっているので）

もしかすると、曲座標系で解いた方が簡単かも…（忘れてしまったけど）

この回答へのお礼

ご回答ありがとうございます！
数学の問題・・・。確かにそうかもしれないですね。
参考にさせていただきます！

お礼日時：2009/06/29 03:04

No.3 ベストアンサー 回答者： zwi 回答日時： 2009/06/26 17:35

素直に当たり判定するなら、線分と線分が交わるかだけで判定できます。

四角形と四角形同士の全部の線分の交わりチェックをしてみてください。
http://www5d.biglobe.ne.jp/~tomoya03/shtml/algor …
ただこれは問題が合って、動くもの同士だとすり抜ける可能性があります。例えば四角の角の先だけが近い状態でお互いに逆方向に回転しているとしたらどうですか？いとも簡単にすり抜けると思いませんか？理由はフレームという切り取られた時間で処理するから位置がジャンプするために起こる問題です。なので実際には連続した時間での動きを擬似的に処理しないといけません。良いサイトがないか探して見ますがとりあえずここまで書き込んでおきます。

No.4 回答者： zwi 回答日時： 2009/06/26 18:16

＃３の回答は少しウソがありまいた。

完全に内包していると判定できません(^^ゞ
で、回転する長方形の当たり判定を書いたサイトを見つけたので参考にしてください。
http://www.c3.club.kyutech.ac.jp/gamewiki/index. …
これでも動きのある物体の当たり判定には問題が残ります。

この回答へのお礼

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

一応外積を使った方法でやってみましたが、一見上手くいったと思いきや、やはりおっしゃるとおり回転する矩形ではすり抜けが頻繁に起こってしまいました。

軌跡を出してその交差から判定するのも考えましたが、複雑な形になりすぎてどうした物か・・・。

もうちょっと考えてみます。

お礼日時：2009/06/29 03:08

No.5 回答者： zwi 回答日時： 2009/06/29 10:12

すいません。

丁度よいサイトが見つけられませんでした。
提案ですが３Ｄ格闘ゲーム系では当たり判定で動く直方体の当たり判定をしてますから参考になると思います。
関連する本を上げておきますので本屋で参考になるかチェックしてみてください。
http://www.amazon.co.jp/dp/4797341807
http://www.amazon.co.jp/dp/4798021180
http://www.amazon.co.jp/dp/4873113776

この回答へのお礼

ありがとうございます。チェックしてみます！

お礼日時：2009/07/04 21:56