解説

重なっていない場合

もし $A, B$ が初期状態で衝突しておらず、後で衝突するときを考えます。

$A$ のある辺について、始点の位置ベクトルを $\boldsymbol{a}$ 、そこから終点までのベクトルを $\boldsymbol{u}$ とします。 $B$ のある頂点の位置ベクトルを $\boldsymbol{b}$ 、 $B$ が移動する速度のベクトルを $\boldsymbol{v}$ とします。

$A$ の辺と $B$ の頂点が衝突すると考えたとき、衝突する点は変数 $t, s$ を用いて $\boldsymbol{a} + s \boldsymbol{u} = \boldsymbol{b} + t \boldsymbol{v}$ と表せます。 この式は二元一次連立方程式であるため、行列計算によって $s, t$ を求めることが可能です。

このとき、 $0 \le s \le 1$ かつ $t \ge 0$ なら実際に時間 $t$ で衝突していると考えられます。

これを $A$ のすべての辺と $B$ のすべての頂点について行います。

次に、同じことを、 $A$ が速度 $-\boldsymbol{v}$ で $B$ に向かっていると考えて、 $A, B$ を逆にして行います。

これによって衝突する最短の時間がわかります。

重なっている場合

上で述べた方法は、 $A, B$ が初期状態で重なっている場合はうまくいきません。

例えば次のような場合を考えてみましょう。

この例では頂点と辺がくっついているわけではないため、上で述べた解き方では正しい衝突までの時間が出ません。 そこで、三角形が重なっているか判定し、重なっていれば 0 を出力します。

2 つの三角形が重なっているとき、片方の辺ともう片方の辺が重なっています。 互いの辺について重なっていないか $3^2$ 通り試すことで判定することができます。