2Dの線分と線分の当たり判定

概要

最終更新日:2020/03/16

2Dの線分と線分の当たり判定について書いた記事です。
主に以下の内容を知りたい方に向けて書いています。
  • 2Dの線分と線分の当たり判定の方法を知りたい
  • 外積を使ってみたい
  • 実装方法が知りたい

注意点

この記事内の座標軸はX軸「右が正、左が負」Y軸「下が正、上が負」で書いています。

サンプル

サンプルはここからダウンロードでき、環境については以下の内容となっています。

開発環境
VSのバージョン VisualStudio 2019
DirectXのバージョン DirectX9


判定方法

線分と線分の当たり判定は線分が交差していたら当たっていると判定します。
これは2Dでも3Dでも同じです。
では、交差判定はどうすればいいかというと、方法は複数あるのですが、
今回の記事では外積を使用した方法で交差判定を行いたいと思います。

2Dの外積の特性

2Dのベクトルの外積計算では計算結果の正負の符号で片方のベクトルが、
もう一つのベクトルの左右(上下)のどちらにあるかを判断することが出来ますcollision_0070
計算結果 方向
負の値 上(左)
正の値 下(右)
上の表とは違い左が正の値とされていることもありますが、 これは座標軸の問題です。 Windowsの座標軸はY軸が下なので右が正の値になっていますが、 Y軸が上の座標軸では左が正の値になっています。

外積を使った判定方法

外積を使った判定の説明をします。
まず結論である交差していると判定する条件は以下の通りです。
  • 片方の線分の始点と終点がもう片方の線分をまたいだ位置にある
  • 二つの線分の両方が上の条件を満たしている
collision_0067

上の図なら線分ABの始点Aと終点Bが線分CDの線をまたいだ位置にあり、
線分CDの始点Cと終点Dが線分ABの線をまたいだ位置にあれば交差していると判定します。
線分ABと線分CDは交差していますが、次の図は線分が交差していない例です。

collision_0071

線分EFの始点Eと終点Fが線分GHの線をまたいでいないため、
条件を満たせず、交差していないと判定します。
この始点と終点が線分をまたいでいるかを判定する方法として外積を使用します。

判定の流れ

判定の流れは以下の通りです。
  1. 線分をベクトルにしてグループを作る
  2. グループのベクトルで外積計算する
  3. 計算結果が条件を満たしているかを確認する
  4. ②に戻りもう一つのグループでやり直す

線分をベクトルにしてグループを作る

まずはこの二つ線分から二つのグループを作り、
一つのグループで三つのベクトルを用意します。
線分ABをメインで使うグループ
  • AB:線分ABのベクトル
  • AC:線分ABの始点と線分CDの始点(C)とのベクトル
  • AD:線分ABの始点と線分CDの終点(D)とのベクトル
collision_0068
線分CDをメインで使うグループ
  • CD:線分CDのベクトル
  • CA:線分CDの始点と線分ABの始点(A)とのベクトル
  • CB:線分CDの始点と線分ABの終点(B)とのベクトル
collision_0069

グループのベクトルで外積計算する

グループのベクトルを使って外積計算を行います。
線分ABをメインで使うグループを例に説明しますが
どのグループでも方法は変わりません。

「ベクトル① × ベクトル②」のベクトル①の項に
グループのメインとして扱っているベクトルを指定します。
今回はベクトルABがメインなので「AB × ベクトル②」になります。

ベクトル②の項には線分CDから作ったAC、またはADを設定します。
これで「AB × AC or AD」となり、外積計算をするための情報が
集まったので計算を行います。

collision_0072

上の式が外積の定義です。
今回はなす角を求めていないのでベクトルの成分のみの式を使って計算します。
計算を行ったら、もう一つのベクトルで再度計算を行います。
ACで計算をしていたら次はADで計算をするということです。

計算結果が条件を満たしているかを確認する

これで外積の結果がそろったので判定します。
判定条件は「片方の線分の始点と終点がもう片方の線分をまたいだ位置にある」です。

if ( (AB × AC) * (AB × AD) < 0)
{
	条件を満たしている
}
else
{
	条件を満たしていない
}

上の条件式のように、ベクトルを乗算した結果が負の値になっているなら、
ベクトルACとADはベクトルABをまたいだ位置にあるとします。
なぜ計算結果を乗算しているかというと下の表から分かるように
乗算して負の値になるということは計算を行った値の符号が異なることを示しています。

符号① 符号② 乗算結果
同じベクトルを対象として複数のベクトルで外積計算を行って 結果で符号が異なるということは各ベクトルが対象とする ベクトルを挟んだ位置にあるということを示しています。 今回なら、同じベクトルというのはベクトルABで複数のベクトルがACとADです。

②に戻りもう一つのグループでやり直す

ABをメインとしたグループの判定結果が条件を満たしていたら
もう一つのCDをメインとしたグループでも外積計算と条件チェックを行い、
そちらも条件を満たすことが出来たら二つの線分は交際していると判定します。

実装方法

実装は「判定の流れ」の順番で行っていきます。
まずは線分からベクトルの作成します。

// グループ①
Vec2 a_to_b = Vec2(line_ab.End.X - line_ab.Start.X, line_ab.End.Y - line_ab.Start.Y);
Vec2 a_to_c = Vec2(line_cd.Start.X - line_ab.Start.X, line_cd.Start.Y - line_ab.Start.Y);
Vec2 a_to_d = Vec2(line_cd.End.X - line_ab.Start.X, line_cd.End.Y - line_ab.Start.Y);

// グループ②
Vec2 c_to_d = Vec2(line_cd.End.X - line_cd.Start.X, line_cd.End.Y - line_cd.Start.Y);
Vec2 c_to_a = Vec2(line_ab.Start.X - line_cd.Start.X, line_ab.Start.Y - line_cd.Start.Y);
Vec2 c_to_b = Vec2(line_ab.End.X - line_cd.Start.X, line_ab.End.Y - line_cd.Start.Y);

ベクトルが完成したら外積計算をします。

// グループ①の外積
float d_01 = (a_to_b.X * a_to_c.Y) - (a_to_c.X * a_to_b.Y);
float d_02 = (a_to_b.X * a_to_d.Y) - (a_to_d.X * a_to_b.Y);

計算結果が出たら判定します。

// 乗算結果が正なので始点と終点がまたがっていない
if (d_01 * d_02 >= 0.0f)
{
	return false;
}

判定の条件は成功ではなく、失敗の条件に変えているので注意して下さい。
これで、グループ①の判定が完了したのでグループ②も同じように計算と判定をします。

// グループ②の外積
d_01 = (c_to_d.X * c_to_a.Y) - (c_to_a.X * c_to_d.Y);
d_02 = (c_to_d.X * c_to_b.Y) - (c_to_b.X * c_to_d.Y);

// 乗算結果が正なので始点と終点がまたがっていない
if (d_01 * d_02 > 0.0f)
{
	return false;
}

最終的に関数の最後まで来たら当たりとします。

// 当たり
return true;

これで、2Dの線分同士の当たり判定の実装は終了です。