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

内積と外積を使用し、「円と線分の交差判定」について考察してみましょう。

線分と円の中心へのベクトルの外積を計算する

線分と円の交差判定を行うには、はじめに線分v1と円の中心までのベクトルv2の「外積」を計算します。外積の結果は、「線分v1に円の中心までのベクトルv2を射影した正射影ベクトルと円の中心までの高さ」となります。従って、外積の結果が円の半径より小さいか等しい場合は円と線分は接するか交差している可能性があります。
前稿の「DirectXで内積と外積を探る」では、外積は２つのベクトルが存在する稿き、一つのベクトルの右か左にもう一つのベクトルが存在するかどうかを調べることができましたが、本稿の外積の使い方は、２つのベクトル間で一方のベクトルの正射影後のベクトル間の高さを計算するために使用しています。重要なポイントはベクトルの正射影を計算することなく、外積の計算だけで、円の中心点への垂線の高さを計算することができることです。外積の計算をするときに忘れてはいけないことは、線分を正規化しておく必要があることです。

// 線分の開始位置から終了位置へのベクトル
DirectX::SimpleMath::Vector2 vectorV1 = end - start;
// 線分の開始地点から円の中心へのベクトル
DirectX::SimpleMath::Vector2 vectorV2 = center - start;
// 線分の開始位置から終了位置へのベクトルを正規化する
DirectX::SimpleMath::Vector2 normalVectorV1 = Normalize(vectorV1);
// 円の中心から線分までの距離を計算する
float length = Cross2D(vectorV2, normalVectorV1);

正規化とは、ベクトルの向きを保持しつつ、ベクトルの大きさを１にすることです。プログラムは次のようになります。

// ベクトルを正規化する
inline DirectX::SimpleMath::Vector2 Normalize(const DirectX::SimpleMath::Vector2& v1)
{
	// ベクトルを正規化する
	return v1 * (1.0f / v1.Length());
}

線分(始点)-円の中心の内積と線分(終点)-円の中心の内積を計算する

線分の始点と円の中心点までの内積と線分の終点と円の中心点までの内積を計算します。線分の始点と円の中心点と線分のなす角度θ1が「鋭角」、線分と線分の終点と円の中心点のなす角度が「鋭角」の場合、つまり、２つの角度が「鋭角」同士の場合は線分と円は接しているか、交わっていることが判定されます。

if (Dot2D(vectorV2, vectorV1) * Dot2D(vectorV3, vectorV1) <= 0)
			return true;

ベクトルv1とベクトルv2の角度θ1が「鋭角」, ベクトルv1とベクトルv3の角度θ2が「鋭角」の場合
交差している

線分の始点と円の中心点と線分のなす角度θ1が「鋭角」、線分と線分の終点と円の中心点のなす角度θ2が「鈍角」の場合は、つまり、「鋭角」と「鈍角」の場合は線分と円は交わっていません。

if (Dot2D(vectorV2, vectorV1) * Dot2D(vectorV3, vectorV1) > 0)
			return false;

ベクトルv1とベクトルv2の角度θ1が「鋭角」, ベクトルv1とベクトルv3の角度θ2が「鈍角」の場合
交差していない

これまでの条件で円と線分の交点が判定されない場合でも、円の半径が線分の始点から円の中心点までのサイズより大きい場合、または円の半径が線分の終点から円の中心的のサイズより大きい場合は、円と線分は接するか交差していることが判定されます。

IntersectCircleLine関数を実装する

これまでの説明内容をIntersectCircleLine関数にすると次のようになります。

// 円と線分の交差判定を行う
inline bool IntersectCircleLine(
	const DirectX::SimpleMath::Vector2& center,		// 中心点
	const float& radius,					// 半径
	const DirectX::SimpleMath::Vector2& start,		// 線分の始点
	const DirectX::SimpleMath::Vector2& end			// 線分の終点
)
{
	// 線分の開始位置から終了位置へのベクトル
	DirectX::SimpleMath::Vector2 vectorV1 = end - start;
	// 線分の開始地点から円の中心へのベクトル
	DirectX::SimpleMath::Vector2 vectorV2 = center - start;
	// 線分の終了地点から円の中心へのベクトル
	DirectX::SimpleMath::Vector2 vectorV3 = center - end;
	// 線分の開始位置から終了位置へのベクトルを正規化する
	DirectX::SimpleMath::Vector2 normalVector1 = Normalize(vectorV1);
	// 円の中心から線分までの距離を計算する
	float length = Cross2D(vectorV2, normalVector1);
	// 円の中心から線分までの距離が半径より小さい場合
	if (abs(length) <= radius)
	{
		if (Dot2D(vectorV2, vectorV1) * Dot2D(vectorV3, vectorV1) <= 0)
			return true;
		else if (radius > vectorV2.Length() || radius > vectorV3.Length())
			return true;
	}
	return false;
}

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

円と線分の交差判定

プログラムを実行することができらら、「Ctrl」+マウスの右ボタンのドラッグで画面を回転させることができます。左右キーで線分を回転させることができます。上下キーで線分のサイズを拡大縮小することができます。
画面の左上部には線分の位置、円の中心から線分への垂線の長さを表示します。Githubのサイトへのリンクは次のとおりです。

GitHub - ShozoTanaka/IntersectCircleLine: 円と線分の交差判定