直線と短形の当たり判定について

[at]

C++にて直線（2点間の線）と短形（四角形）の当たり判定を実装したいと考えております。
プログラムを書いてみたのですが、判定がとれたり取れなかったりとバグがあるようで原因がわかりません。

どちらも回転する可能性があるので、線分交差を使い実装しております。
バグがありそうな箇所お分かりになる方おりませんでしょうか。

HitCheckLine・・・線分同士の当たり反転 (a1 a2)、(b1 b2)それぞれを結ぶ線があたっているか。
HitCheckLineBox・・・直線の座標と四角形の４点の位置座標を引数に設定。一箇所でも当たっていればtrue
HitCheckLineBox・・・HitCheckLineBoxを使いやすくした関数

コード:

class POS{
public:
    float x,y;
    void Init(){ this->x = 0.0f; this->y = 0.0f; }
    void Init( float pram ){ this->x = pram; this->y = pram; }
    void Init( float x, float y ){ this->x = x; this->y = y; }
};
	
// 線分交差
bool GAME::HitCheckLine( POS a1, POS a2, POS b1, POS b2 ){

    float tc=(a1.x-a2.x)*(b1.y-a1.y)+(a1.y-a2.y)*(a1.x-b1.x);
    float td=(a1.x-a2.x)*(b2.y-a1.y)+(a1.y-a2.y)*(a1.x-b2.x);
    
    // tcとtdの符号が違ったら
    if( tc*td<0 ) return true;
    
    return false;
}

// 線と短形の当たり判定
bool GAME::HitCheckLineBox( POS l1, POS l2, POS bLeftUp, POS bRightUp, POS bLeftDown, POS bRightDown ){
    
    // 各辺ごとの線分交差
    if( this->HitCheckLine( l1, l2, bLeftUp, bRightUp ) ) return true;
    if( this->HitCheckLine( l1, l2, bRightUp, bRightDown ) ) return true;
    if( this->HitCheckLine( l1, l2, bLeftDown, bRightDown ) ) return true;
    if( this->HitCheckLine( l1, l2, bLeftUp, bLeftDown ) ) return true;
    
    return false;
}

// 線と短形の当たり判定
bool GAME::HitCheckLineBox( POS l1, POS l2, POS bCenter, int width, int height ){
    
    // 各辺ごとの線分交差
    POS bLeftUp, bRightUp, bLeftDown, bRightDown;
    
    bLeftUp.x = bCenter.x - width/2;
    bLeftUp.y = bCenter.y - height/2;
    bRightUp.x = bCenter.x + width/2;
    bRightUp.y = bCenter.y - height/2;
    bLeftDown.x = bCenter.x - width/2;
    bLeftDown.y = bCenter.y + height/2;
    bRightDown.x = bCenter.x + width/2;
    bRightDown.y = bCenter.y + height/2;
    
    if( this->HitCheckLineBox( l1, l2, bLeftUp, bRightUp, bLeftDown, bRightDown ) ) return true;
    
    return false;
}

[usao]

>直線（2点間の線）と短形（四角形）の当たり判定

本当にやりたいのは
「線分」と矩形　だとかいう話ではありませんか？

オフトピック

HitCheckLine()は，　直線と線分　の判定？
→　やりたいのは　線分と線分　なのかな？

[at]

usao様

確認ありがとうございます！
お恥ずかしい話なのですが、線分と直線の違いを理解しておりません。

やりたいこととしましては、
２点間を結んだ線と四角形があたっているかということになります。

直線A(100,0)(200,0)があるとして、
この直線に四角形があたっているか？という判定をしたいです。

実装方法がわからなく、線と四角形のどこかの辺が交差していたら、
当たりだと考えていたのですが違うのでしょうか。

線分交差についてもネット上で見つけた計算式を
それっぽくC++で書きなおしただけですので、
もしかしたら線分交差自体の認識を間違えているのかもしれません。

[at]

連レスすみません。

HitCheckLineは、少しでもわかりやすくするために用意している関数になります。
その２点間同士の直線があたっているか？を判定しております。

説明がわかりにくくて申し訳ないのですが、

A(100,100)(200,100) ←長さ100
B(150,100)(150,200)　←長さ100

↑だと100の範囲内にもう一つの100があるか？をチェックしたいです。

[みけCAT]

お恥ずかしい話なのですが、線分と直線の違いを理解しておりません。

線分 : 両端が閉じている(端がある)まっすぐな線。長さは有限。
(半直線 : 端が1個あり、ある向きに向かってまっすぐに伸びる線。長さは無限。)
直線 : 端は存在せず、まっすぐに伸びる線。長さは無限。

やりたいこととしましては、
２点間を結んだ線と四角形があたっているかということになります。

直線A(100,0)(200,0)があるとして、
この直線に四角形があたっているか？という判定をしたいです。

確認したいのですが、「四角形」に四角形の内部は含まれますか？
また、「四角形」は任意の四角形に対応させますか？それとも長方形(矩形(短形ではない))のみでいいですか？

実装方法がわからなく、線と四角形のどこかの辺が交差していたら、
当たりだと考えていたのですが違うのでしょうか。

線分ではなく直線との当たり判定なら、四角形の内部が含まれるかに関わらず正しいと思います。
線分との当たり判定であり、かつ四角形の内部が含まれる場合、例えば下図のケースで誤判定するので違うと思います。

撃墜例

gekitui20150914.png (829 バイト) 閲覧数: 6340 回

[usao]

"直線"は長さが無限，"線分"は有限，です．
（もっとまともな説明は，いろいろ調べたりして得て下さい）


>線分交差についてもネット上で見つけた計算式を
>それっぽくC++で書きなおしただけですので、

そういう場合は，例えば参考にしたところをリンクで示すとかしないと
コードだけ見ても謎の計算式なので答え難いとは思いませんか……？
で，

>HitCheckLine()

で行っている計算が何をしているのかはさっぱりわからないわけですが，Web検索してみたところ
http://www5d.biglobe.ne.jp/~tomoya03/sh ... ection.htm
に書かれているものに式の形が近いように見えました．
仮にここと同じことをしているのだとして……
ここの話はどうやら
直線vs線分　の判定を２回行うことで，　線分vs線分　の判定を実現する流れのようです．
それに対して，
HitCheckLine()ではそのうちの一方の判定しかしていない形になっているように見えます．

[at]

みけCAT様

回答が遅くなってしまい申し訳御座いません。
線分と直線のご説明ありがとうございます。

非常にわかりやすくて助かりました。
今回は有限の線分と長方形（正方形の可能性もあり）をしたいです。

線分のは２点間で様々な角度がありますが、長方形は回転などはしません。
しかし、回転する可能性も考え、各辺ごとに判定をしたいと考えております。

図までありがとうございます。
なるほど・・・。今、考えていた方法ですと、その場合が漏れてしまいそうです。

かなり難しいですね・・・。

[at]

usao様

ご回答が遅くなってしまい申し訳ございません。
仰るとおりでして、配慮が欠けておりました。

こちら申し訳ございません。
参考にしたサイトはいくつかあるのですが、
添付して頂きましたURLをメインで関数を記載しております。
こちらお探し頂きましてありがとうございました。

HitCheckLine()に関しましては、上記のサイトの式をプログラムに書きなおしたものになります。
かなり読み込んでみたのですが、２回判定する部分が理解できませんでした。

こちら可能でしたらで構いませんので、アドバイスを頂くことは難しいでしょうか。
何から何まで聞いてしまい申し訳ございません・・・。

[usao]

>かなり読み込んでみたのですが、２回判定する部分が理解できませんでした。

ページの真ん中らへんに

>そして、線分ABと直線CDについても同様の計算を用いて、
>...(数式)
>上記のものとあわせて、２つの条件判定すれば、2つの線分の交差判定を行うことができます。

と書いてありますよ．

[みけCAT]

テストはしていませんが、
「線分と四角形の各辺のいずれかが当たっている(今目指しているもの)、または線分の端点のいずれかが四角形の周または内部にある」とき、かつそのときに限り線分と四角形が当たっているという判定にすることで、
No: 5で提示したケースも含めていい感じの判定になりそうだと思います。