当たり判定の数学(1)～動く矩形～

プログラミングをしているとこの手の当たり判定はよく出会います。
これは単純な矩形どうしの当たり判定でしてもいいのですが、
速度によっては、単純な矩形の当たり判定ではすり抜けるという現象が発生します。それを防ごうという試み。

そこであたっている、あたっていないを数学的に定義します。
まず、図形を数学的に表現することを考えます。
これははある条件を満たす点の集合として捉えられそうです。
たとえば矩形だと
$A=\{(x,y)| a< x< b, c< y< d\}$
みたいな感じです。
ここで図形AとBがあたっている(何次元でもいい)とは
AとBの共通部分がないといえるので、数式で表せば
$A\cap B \neq \emptyset$
となります。
このままではいまいち使い勝手が悪いです。
しかし、以下の便利な定理を用いると非常に扱いが簡単になります。
集合A,Bが2つの条件に分解できたとき
つまり
$A = A_x \times A_y$
$B = B_x \times B_y$
となるとき
$A \cap B=$
$(A_x \times A_y) \cap (B_x \times B_y)=(A_x \cap B_x) \times (A_y \cap B_y)$
となる。
この定理は簡単にn個の条件に分解できたとき
$A \cap B=\sqcap_i^{n} ( A_i \cap B_i)$
となることを示せます。
証明は大体同じになるためn=2の時だけ示します。
証明)
$A_x \times A_y=$
$\{(x,y)| (x \in A_x) \wedge (y \in A_y)\}$
$B_x \times B_y=$
$\{(x,y)| (x \in B_x) \wedge (y \in B_y)\}$
なので
$A \cap B=$
$(A_x \times A_y) \cap (B_x \times B_y)=$
$\{(x,y)| ( (x \in A_x) \wedge (y \in A_y) ) \wedge ( (x \in B_x) \wedge (y \in B_y) )\}$
ここで論理積が可換であるということより、
$\{(x,y)| ( (x \in A_x) \wedge (x \in B_x) ) \wedge ( (y \in A_y) \wedge (y \in B_y) )\}$
よって
$=(A_x \cap B_x) \times (A_y \cap B_y)$
ゆえに
$A \cap B=(A_x \cap B_x) \times (A_y \cap B_y)$
となる。

さて、この定理(以下定理1)を使うと何がうれしいかというとn次元の
当たり判定が1次元の当たり判定に分解できるのです。
つまり、当たり判定の定義を
$A \cap B \neq \emptyset$
としているので定理1を用いてこれを変形してあげれば
$\sqcap_i^{n} ( A_i \cap B_i)\neq \emptyset$
ここで空集合との直積は常に空集合であることを考えると
$A_i \cap B_i\neq \emptyset$
という条件となります。

さて、以上が準備(長い...)です。本題に入りましょう。
問題を簡略化するため一方が静止していて、もう片方が動いている(等速直線運動している)という状況を考えます。
これは等速直線運動なら平行移動して線形変換(座標変換)してうまい座標系に持っていってあげる(あるいはガリレイ変換)ことが
可能なので一般性は失われません。また、短い時間では(1ループ)などでは等速直線運動
というコードを書くことが多いと思うのでこれも問題ないと思います。
ここで一番のポイントは二次元の移動を考えるときはさらにtを座標軸として付け加えて
3次元空間とみなしてあげるということです。こうすると3次元の物体の当たり判定ということになり、
定理1より「基本的に」1次元の当たり判定にばらして考えることができます。
基本的にと書いたのは座標が時間に依存しているためそこが若干の変更の必要があるということです。

でははじめましょう。面倒なのでx成分のみについてしますが、y成分についても同様にできます。
静止しているx軸に平行な線分Aと速度vで動いているx軸に線分Bを考え、tが(0,1)の範囲*1で衝突するかどうかを考えます。
このとき
$A=\{(x,t)| 0< t< 1 ,a_{1}< x< a_{2} \}$
$B=\{(x,t)| 0< t< 1 , (b_{1}+vt) < x<(b_{2}+vt) \}$
と表すことができます。t成分についての積集合は明らかに空集合ではないので
x成分について考えます。図示すると以下の2パターンです。(最初から衝突しているものは図示していませんが、この2つに~~自然に含まれます~~どうやら含まれていないっぽいです...)
f:id:ikaro1192:20120812165902p:plain
f:id:ikaro1192:20120812165918p:plain
紫色になっている範囲にtが1のまでの時に入っていればいいわけですね。
まずは上のパターンから考えてみます。
つまり
(i) $a_1> b_2$ の時
$a_1$ の直線と $b_2$ の直線が
衝突する点が存在すれば当たっているといえます。
これはどの点で衝突するかは言わなくていいので中間値の定理を用いて
$(b_2-a_1)\{b_2+v-a_1\}<0}$
ここで直線なので最初と最後の点のみを考慮すればよいということを使いました。
さて、最初の部分は条件より負なので後ろの部分が正であればこの式が成り立ちます。
$b_2+v-a_1>0}$
これが満たすべき条件です。
(ii) $a_2< b_1$ の時
同様に
$(b_1-a_2)\{b_1+v-a_2\}<0}$
で前の部分が正なので、後ろの部分が負になる必要があり
$b_1+v-a_2<0$
が条件となります。
yについてもまったく同様な手順で(文字を置き換えるだけで)行うことができます。