DirectX「線分と線分の交差判定」で外積を応用する

「DirectXで内積と外積を探る」の稿で、外積を用いるとベクトル間の左右判定が可能であることを説明しました。この外積の機能を活用すると、線分と線分の交差判定を行うことができます。では、「線分と線分の交差判定」を行ってみましょう。

線分と線分の交差判定

はじめに、２Dの外積の計算式を示します。

外積の計算

C++のプログラムで記述すると次のようになります。

// Vector2の外積(v1 × v2)
static float Cross(const Vector2& v1, const Vector2& v2)
{
    return v1.x * v2.y - v1.y * v2.x;
}

外積を使い2つのベクトルが平行であるかどうかを検証する

線分と線分の交差判定をおこなうには、予め２つの線分が平行かどうかを検証します。線分同士が平行な場合、外積の計算結果は0となり、２つのベクトルの交差結果は偽であることを示します。

DirectX::SimpleMath::Vector2 fromV1ToV2 = v2 - v1;
DirectX::SimpleMath::Vector2 fromV3ToV4 = v4 - v3;

// 外積の結果が0の場合2つの線分は平行になる
if (Cross2D(fromV1ToV2, fromV3ToV4) == 0.0f)
	return false;

V1からV2へのベクトルがもう１つのベクトルの左右にあるかどうかを調べる

V1からV2へのベクトルがもう１つのベクトルの左右にあるかどうかを調べるためベクトルの外積を計算します。v1からv3へのベクトルがv1からv2へのベクトルの左側にあれば外積は０よりも大きい値になり、v1からv4へのベクトルがv1からv2へのベクトルの右側にあれば外積かは０よりも小さい値になります。つまり、２つの外積の積を計算し、計算結果が０より小さくなると２つのベクトルが交差していると考えます。

Cross2D(v2-v1, v3-v1) × Cross2D(v2-v1, v4-v1) < 0 

ベクトルがもう１つのベクトルの左右にあるかどうかを調べるためのプログラムを次に示します。

DirectX::SimpleMath::Vector2 fromV1ToV2 = v2 - v1;
DirectX::SimpleMath::Vector2 fromV1ToV3 = v3 - v1;
DirectX::SimpleMath::Vector2 fromV1ToV4 = v4 - v1;
DirectX::SimpleMath::Vector2 fromV3ToV1 = v1 - v3;
bool result = Cross2D(fromV1ToV2, fromV1ToV3) * Cross2D(fromV1ToV2, fromV1ToV4) < 0.0f;

V3からV4へのベクトルがもう１つのベクトルの左右にあるかどうかを調べる

V3からV4へのベクトルがもう１つのベクトルの左右にあるかどうかを調べるためベクトルの外積を計算します。v3からv1へのベクトルがv3からv4へのベクトルの左側にあれば外積は０よりも大きい値になり、v3からv2へのベクトルがv3からv4へのベクトルの右側にあれば外積かは０よりも小さい値になります。つまり、２つの外積の積を計算し、計算結果が０より小さくなると２つのベクトルが交差していると考えます。

Cross2D(v1-v3, v4-v3) × Cross2D(v4-v3, v2-v3) < 0 

DirectX::SimpleMath::Vector2 fromV3ToV1 = v1 - v3;
DirectX::SimpleMath::Vector2 fromV3ToV2 = v2 - v3;
DirectX::SimpleMath::Vector2 fromV3ToV4 = v4 - v3;
bool result1 = Cross2D(fromV3ToV4, fromV3ToV1) * Cross2D(fromV3ToV4, fromV3ToV2) < 0.0f;

これまでの説明をIntersectLines2Dのプログラムにまとめると次のようになります。プログラムの最適化のため、プログラムな冗長な部分は修正しています。

// 線分と線分が交差しているかどうかを調べる
inline bool IntersectLines2D
(
	const DirectX::SimpleMath::Vector2& v1,
	const DirectX::SimpleMath::Vector2& v2,
	const DirectX::SimpleMath::Vector2& v3,
	const DirectX::SimpleMath::Vector2& v4
)
{
	DirectX::SimpleMath::Vector2 fromV1ToV2 = v2 - v1;
	DirectX::SimpleMath::Vector2 fromV1ToV3 = v3 - v1;
	DirectX::SimpleMath::Vector2 fromV1ToV4 = v4 - v1;
	DirectX::SimpleMath::Vector2 fromV3ToV1 = v1 - v3;
	DirectX::SimpleMath::Vector2 fromV3ToV2 = v2 - v3;
	DirectX::SimpleMath::Vector2 fromV3ToV4 = v4 - v3;

	// 外積が0の場合2つの線分は平行になる
	if (Cross2D(fromV1ToV2, fromV3ToV4) == 0.0f)
		return false;

	return (Cross2D(fromV1ToV2, fromV1ToV3) * Cross2D(fromV1ToV2, fromV1ToV4) < 0.0f) &&
		(Cross2D(fromV3ToV4, fromV3ToV1) * Cross2D(fromV3ToV4, fromV3ToV2) < 0.0f);
}

「IntersectLines」プロジェクトは下記のGithubサイトからダウンロードすることができます。

線分と線分の交差判定

プログラムを実行することができたら、「Ctrl」+マウスの右ボタンのドラッグで画面を回転させることができます。左右キーで線分を回転させることができます。上下キーで線分のサイズを拡大縮小することができます。線分同士の交差を判定できると線分が赤色に変化します。Githubのサイトへのリンクは次のとおりです。