« オブリビオン実績1000ポイント達成! | トップページ | 2つの直線が交差している場合の交点を求める »

2つの直線が交差しているかのチェック(C言語)

ブロック崩しの壁判定や、レーザーなどの当たり判定に必要で

尚且つ2Dゲームでは最強とも言える「線分交差判定」を作る事にした

まず、ゲームではそれぞれ座標で管理しているので、
 ・線分は(x1, y1) → (x2, y2)
と考える事とする


まずは、

2つの直線(接線)
 ①(a1x, a1y) → (a2x, a2y)
 ②(b1x, b1y) → (b2x, b2y)
が交差するかの確認を行う


①をAベクトル、②をBベクトルとしておき

・Aベクトルから見てb1とb2が左右に存在している
 ・Bベクトルから見てa1とa2が左右に存在している

の2つの条件を満たした時は線分が交差している事になる


では、どうやって左側か右側に存在するかの確認を行うのかというと

「2つのベクトルの外積を求めて判断する」という方法でできるのだ


ある点がベクトルの右にあるか左にあるかは、
 ・点がベクトルの左側なら外積は正
 ・点がベクトルの右側なら外積は負
で判別していく

この際、正負のどっちを向いているかは関係なくて
「両方が、正負に分かれていること」が重要になる


具体的に、
Aベクトルから見て、Bベクトルの両端の点が左右にあるかをチェックするには

 ①線分(a1x, a1y) → (a2x, a2y)と線分(a1x, a1y) → (b1x, b1y)の外積の値
 ②線分(a1x, a1y) → (a2x, a2y)と線分(a1x, a1y) → (b2x, b2y)の外積の値

の2つの結果が+値同士、-値同士になっていなければ
線分に対して左右に存在する事が言える


実際は、
Bベクトルから見て、Aベクトルの両端の点が左右にあるかも必要なので

 ①線分(b1x, b1y) → (b2x, b2y)と線分(b1x, b1y) → (a1x, a1y)の外積の値
 ②線分(b1x, b1y) → (b2x, b2y)と線分(b1x, b1y) → (a2x, a2y)の外積の値

の2つの結果でも+-判定を行う必要がある


ちなみに、外積の計算は
 「Aベクトル×Bベクトル」と表し、(Xはクロスという)
 外積:a×b = ax*by - ay*bx
で求める事ができる

実際の処理はこんな感じ・・

bool CrossHitCheck(XY a1, XY a2, XY b1, XY b2)
{
  // 外積:axb = ax*by - ay*bx
  // 外積と使用して交差判定を行なう
  double v1 = (a2.x - a1.x) * (b1.y - a1.y) - (a2.y - a1.y) * (b1.x - a1.x);
  double v2 = (a2.x - a1.x) * (b2.y - a1.y) - (a2.y - a1.y) * (b2.x - a1.x);

  double m1 = (b2.x - b1.x) * (a1.y - b1.y) - (b2.y - b1.y) * (a1.x - b1.x);
  double m2 = (b2.x - b1.x) * (a2.y - b1.y) - (b2.y - b1.y) * (a2.x - b1.x);

  // +-,-+だったら-値になるのでそれぞれを掛けて確認する
  if((v1*v2 <= 0) && (m1*m2 <= 0)){
    return true; // 2つとも左右にあった
  }else{
    return false;
  }
}


CrossHitCheck関数に、チェックしたい2直線の
両端の座標を渡すと、交差したかの判定が帰ってくるのだ・・

例えば、
 ①p1(x,y) → p2(x,y)
 ②p3(x,y) → p4(x,y)
の2つの接線が交差しているかの判断をするには、

if(CrossHitCheck(p1, p2, p3, p4) == true){
// 交差している
}else{
// 交差していない
}

という感じの処理となる

一応360度どんな向き同士でも判定ができるので
汎用性の高い判定処理だと言えます


でも、実際は交点の座標などが分からないと
使い物にならないので、次回は交点座標のチェックにチャレンジします

Cross1


|

« オブリビオン実績1000ポイント達成! | トップページ | 2つの直線が交差している場合の交点を求める »

ゲーム」カテゴリの記事

パソコン・インターネット」カテゴリの記事

日記・コラム・つぶやき」カテゴリの記事

趣味」カテゴリの記事

コメント

この記事へのコメントは終了しました。

トラックバック


この記事へのトラックバック一覧です: 2つの直線が交差しているかのチェック(C言語):

« オブリビオン実績1000ポイント達成! | トップページ | 2つの直線が交差している場合の交点を求める »