矩形と線分の当たり判定

キャラクターとレーザーの当たり判定をやろうと思ってぶち当たりました。キャラクターが矩形なのに対してレーザーは線分。直線なら話はかなり簡単だったんだけど残念ながら線分です。線分と直線の違いは説明するまでもないと思いますがこの程度ぐーぐる様の手を煩わせることもないと思うので説明すると直線が無限に続くのに対して線分は両端が存在します。ので、線分を表すには両端の座標を利用するのが普通です。んで矩形はおなじみのleft top right bottomの４パラメータ。合計８パラメータですね。
さてどうやればいいのか？ちょい考えてみたのですが、矩形は４つの線分から出来ていると考えて、1つの辺でも線分と交差していれば当たっていることになるということに気がつきます。ということは線分同士の当たり判定を考えればいいわけです。パラメータは線分Ａの片方の端の座標をA1(A1x,A1y)もう片方をA2(A2x,A2y)、同様にして線分ＢをB1(B1x,B1y),B2(B2x,B2y)とします。
線分同士をいきなり考えるのは難しいので、まずは片方が直線だと仮定しましょう。この直線Ｂと線分Ａの交差する条件は、線分Ａの両端がそれぞれ直線Ｂの反対側にいるとよいことがわかると思います。それを式で表します。線分Ｂを直線Ｂとした場合、その接線ベクトルは、B1B2( Bx2 - Bx1, By2 - By1 )になります。点A1がこの接線ベクトルの右にいるか左にいるかは外積をとればわかります。B1B2×B1A1　これが正なら右側、負なら左側になります。同様にしてA2に関してもB1B2×B1A2で表せます。これら２つの符号が違えば逆側になるので、掛け算して負になっていればOKです。
ここまでは直線と線分でしたが、今度はＡとＢを逆にして、つまりＡを直線、Ｂを線分として同様の当たり判定を計算します。直感的ではあるけどこの両方が成り立っていれば線分Ａと線分Ｂが交わっていることがわかると思います。
というわけで条件は
B1B2×B1A1・B1B2×B1A2 <= 0 ∪ A1A2×A1B1・A1A2×A1B2 <= 0
になります。
これをC++で書くと・・

bool LineAndLine( float A1x, float A1y, float A2x, float A2y, float B1x, float B1y, float B2x, float B2y ){
	{
		const float baseX = B2x - B1x;
		const float baseY = B2y - B1y;
		const float sub1X = A1x - B1x;
		const float sub1Y = A1y - B1y;
		const float sub2X = A2x - B1x;
		const float sub2Y = A2y - B1y;

		const float bs1 = baseX * sub1Y - baseY * sub1X;
		const float bs2 = baseX * sub2Y - baseY * sub2X;
		const float re = bs1 * bs2;
		if( re > 0 ){
			return false;
		}
	}
	{
		const float baseX = A2x - A1x;
		const float baseY = A2y - A1y;
		const float sub1X = B1x - A1x;
		const float sub1Y = B1y - A1y;
		const float sub2X = B2x - A1x;
		const float sub2Y = B2y - A1y;

		const float bs1 = baseX * sub1Y - baseY * sub1X;
		const float bs2 = baseX * sub2Y - baseY * sub2X;
		const float re = bs1 * bs2;
		if( re > 0 ){
			return false;
		}
	}
	return true;
}

前半と後半で同じことをやっているのでインライン関数とか使えばもっとスッキリすると思います(^^;
さてこれで線分同士の当たり判定がわかったので、あとは矩形に直すだけ。

bool RectAndLine( float left, float top, float right, float bottom, float x1, float y1, float x2, float y2 ){
	if( LineAndLine( left, top, right, top, x1, y1, x2, y2 ) ){ return true; 	}
	if( LineAndLine( right, top, right, bottom, x1, y1, x2, y2 ) ){ return true; }
	if( LineAndLine( right, bottom, left, bottom, x1, y1, x2, y2 ) ){ return true; }
	if( LineAndLine( left, bottom, left, top, x1, y1, x2, y2 ) ){ return true; }

	return false;
}

なんだかあんまりキレイじゃないけど、御愛嬌ということで（謎

ちなみにこの方法なんですが、矩形である必要はないんですね。それどころか四角形である必要すらない。あらゆる多角形と線分との当たり判定が行えます。

bool AnyAndLine( float* ax, float* ay, int size, float x1, float y1, float x2, float y2 ){
	for( int n1 = 0; n1 < size; ++n1 ){
		const int n2 = ( ( n1 == 0 ) ? ( size - 1 ) : ( n1 - 1 ) );
		if( LineAndLine( ax[n1], ay[n1], ax[n2], ay[n2], x1, y1, x2, y2 ) ){
			return true;
		}
	}
	return false;
}

さらに言うと、多角形同士も可能です。

bool AnyAndAny( float* ax1, float* ay1, int size1, float* ax2, float* ay2, int size2 ){
	for( int n11 = 0; n11 < size1; ++n11 ){
		const int n12 = ( ( n11 == 0 ) ? ( size1 - 1 ) : ( n11 - 1 ) );
		for( int n21 = 0; n21 < size2; ++n21 ){
			const int n22 = ( ( n21 == 0 ) ? ( size2 - 1 ) : ( n21 - 1 ) );
			if( LineAndLine( ax1[n11], ay1[n11], ax1[n12], ay1[n12], ax2[n21], ay2[n21], ax2[n22], ay2[n22] ) ){
				return true;
			}
		}
	}
	return false;
}

まあ、需要があるかはわかりませんけど(^^;