2D衝突編
その２ 点と線
点と線が衝突しているか？ここからベクトルが登場します。また、双方ともボリューム（体積）の存在しないオブジェクトですから、特有の難しさがあります。
① 線の上に点があるか？
まず座標上の線とは「点が隙間無く無限にまっすぐ並んだ集合」です。よって、特定の点を結んで「線です」というのは厳密には間違いで、それは「線分」と言います。となると、線はどのように表すのか？ちょっと難しいですが、一般には始点とベクトルで表すのが妥当と思われます。
線：「点(x0, y0) を通り向きv=(vx, vy)」
点：P(x2, y2)
この線と点の衝突は、実はえらく簡単なのです。基礎の基礎編で外積をやりました。外積の計算結果にはsin(θ)が出てきます。これを利用するのです。
まず、線上の点(x0, y0)を始点として、P(x2, y2)を終点とするベクトルv1を作ります。これは終点の座標から始点の座標を引けば求められます。
v1 = (x1, y1) = (x2-x0, y2-y0)
このベクトルが線の方向を表すvと並行であれば、点は線の上にあることになります。2つのベクトルが平行な時、外積の結果は|v||v1|sin(0) = 0となります。
まとめると、
(x2-x0)*vy - vx*(y2-y0)が 0 ならば点と線は衝突している
となります。
② 浮動小数点の場合はやっぱり誤差判定を
「その１」の点と点でも議論したのですが、浮動小数点を扱う場合にはぴったり0になる保障はありません。よって、わずかな誤差は許容する工夫が必要になります。上の結論において、例えば外積の絶対値が0.0001以下であれば衝突しているとするわけです。
通り抜けの問題もやはりあります。線が動く場合、そこには「領域」が生じます。点も動くなら「線分」が生じるわけで、面倒な衝突判定が必要になってきます。
③ 点と線分の衝突
線が有限の長さを持っているとき、それは「線分」と言います。線分を表現するときには、2点を示せばよいだけです。
線分： 始点P0(x0, y0)、終点P1(x1, y1)
点 ：P(x2, y2)
線分上の点。ちょっと難しそうに思えますが、これも実に簡単なんです。先ほどは外積を用いましたが、今度は内積を用います。
線分の始点P0から終点までの軌跡をv1、点Pまでの軌跡をベクトルv2とします。
v1 = (x1 - x0, y1 - y1)
v2 = (x2 - x0, y2 - y0)
このベクトルが平行ならばv1・v2=|v1||v2|cos(θ)=±|v1||v2|となります。プラスマイナスがあるのは、平行だけれども向きが逆という場合があるからです。少なくとも、cos(θ)がマイナスのときは、始点を中心として真逆を向いているのですから、点は線分上にはありません。よって、
v1・v2=|v1||v2|cos(θ)=|v1||v2|
の時に線分上に点がある候補になります。あとは、線分の長さ|v1|よりも点までの距離|v2|が短ければ、点は線分の上にあることになります。
点と線分の衝突は次のようになります。
線分の長さ L1 = sqrt( (x1-x0)^2 + (y1-y0)^2 )
線分の始点から点までの長さ L2 = sqrt( (x2-x0)^2 + (y2-y0)^2 )
(x1-x0)*(x2-x0) + (y1-y0)*(y2-y0) が L1*L2 に等しく、かつL1≧L2の時衝突している
多少面倒ですが、作ってしまえば簡単です。