2D衝突編
その10 線分と線分の衝突
2Dの線分と線分の交点を求める問題は色々な局面で出てきます。直線同士と違い、線分は端が切れていますのでその分の処理が必要になりますが、最終的なアルゴリズムは極めてすっきりです。
① 線分同士の衝突判定
線分の表現は2つの端点、もしくは始点とベクトルで表すのが普通です。より具体的な情報を持っているのは始点とベクトルの表現なので、ここでもそれを使います。
始点をS、終点に向けたベクトルをvとします。この時2つの線分を引き伸ばした直線は交差するか並行かのどちらかです。平行の判定は簡単で、2つの線分の方向ベクトルv1とv2の外積を取って0になったら平行です。平行でない場合は交点が1つ定まります。2直線の交点は次のように考えます：
S1から交点へ伸ばしたベクトル（v1'）はベクトルvとt2・v2の合成ベクトルです。つまりV1' = v + t2 * v2。この合成ベクトルはベクトルv1と平行です。つまり外積が0。ここから、
となります。外積は2行目のように分解できるので便利です。また外積の掛ける順序を反対にすると符号も反対になるため最後の2行が導けます。このt2から交点の座標は、
と直ちに求まります。
これと全く同様の考えでt1も求まります。t1の場合（S1-S2)=-vとt1v1の合成ベクトルとv2が平行になる（外積が0）性質を利用して、
となります。外積するベクトルのうち一方を反対方向にすると符号が反対になる性質を利用すると最後の2行が導けます。
以上から、t1及びt2を求めるにはベクトルv（=S2-S1）、Cross(v1,v2)、Cross(v,v1)そしてCross(v,v2)があれば良いだけだとわかります。
t1、t2がわかると、線分の交差も直ちにわかります。すなわち、0≦t1≦1かつ0≦t2≦1ならば、2つの線分は交差しています。
② 線分衝突判定関数
線分同士の衝突を判定する関数を公開します。使い方は至って簡単なのでご自由にお使い下さい：
線分衝突判定関数 // 線分構造体
struct Segment {
D3DXVECTOR2 s; // 始点
D3DXVECTOR2 v; // 方向ベクトル（線分の長さも担うので正規化しないように！）
};
// 2Dベクトルの外積
float D3DXVec2Cross( D3DXVECTOR2* v1, D3DXVECTOR2* v2 ) {
return v1->x * v2->y - v1->y * v2->x;
}
// 線分の衝突
bool ColSegments(
Segment &seg1, // 線分1
Segment &seg2, // 線分2
float* outT1 = 0, // 線分1の内分比（出力）
float* outT2 = 0, // 線分2の内分比（出力
D3DXVECTOR2* outPos = 0 // 交点（出力）
) {
D3DXVECTOR2 v = seg2.s - seg1.s;
float Crs_v1_v2 = D3DXVec2Cross( &seg1.v, &seg2.v );
if ( Crs_v1_v2 == 0.0f ) {
// 平行状態
return false;
}
float Crs_v_v1 = D3DXVec2Cross( &v, &seg1.v );
float Crs_v_v2 = D3DXVec2Cross( &v, &seg2.v );
float t1 = Crs_v_v2 / Crs_v1_v2;
float t2 = Crs_v_v1 / Crs_v1_v2;
if ( outT1 )
*outT1 = Crs_v_v2 / Crs_v1_v2;
if ( outT2 )
*outT2 = Crs_v_v1 / Crs_v1_v2;
const float eps = 0.00001f;
if ( t1 + eps < 0 || t1 - eps > 1 || t2 + eps < 0 || t2 - eps > 1 ) {
// 交差していない
return false;
}
if( outPos )
*outPos = seg1.s + seg1.v * t1;
return true;
}
D3DXVECTOR2の外積関数はDirect3Dに用意されていないため、上で独自に設けています。出力は3つありますが、NULLを渡せば無視されますので、交差判定だけ知りたい場合は第2引数まで渡せば十分です。交差比較の部分に誤差許容値（0.00001f）を持たせているため、交差判定は少しだけゆるくなっています。
