四角形と点の当たり判定

[チルチル]

ＤＸライブラリでゲームを製作中なのですが
四角形と点との当たり判定を求める処理が思い付きません

何か良い式や処理は無いでしょうか？

四角形は斜めもある長方形とします

龍神録プログラミングの館の「レーザーを作ってみよう」の２番目の処理が使えそうなのですが
ＡベクトルとＢベクトルが何を指すのもわかりません・・

[non]

>龍神録プログラミングの館の「レーザーを作ってみよう」の２番目の処理が使えそうなのですが

使えそうですね。

Aベクトルは 「レーザーを作ってみよう」の２番目の図では、
ｂ点からa点へ向かうベクトルで、Bベクトルはｂ点からｒ点へ向かうベクトルです。

チルチルさんの学年等がわからないと、どこまで説明して良いかわかりません。

なお、外積の式
AXB＝Ax*By+Ay*Bx と書いてありますが、
AXB＝Ax*By-Ay*Bx　の間違いだと思います。
（プログラムではそうなっているので）

[GPGA]

以下のページの一番下にアルゴリズムがあります。
http://marupeke296.com/COL_2D_No4_SquareToSquare.html

プログラムにすると以下のようになります。

struct Point {
	int x, y;
};


/*!
 * @brief 変形矩形と点の辺り判定
 */
bool Hit(Point rect[4], Point point) {
	int cnt = 0;
	for (int i = 0; i < 4; ++i) {
		const int x1 = rect[(i + 1) % 4].x - rect.x;
		const int y1 = rect[(i + 1) % 4].y - rect.y;
		const int x2 = point.x - rect.x;
		const int y2 = point.y - rect.y;
		if (x1 * y2 - x2 * y1 < 0) {
			++cnt;
		} else {
			--cnt;
		}
	}
	return cnt == 4 || cnt == -4;
}

　

[チルチル]

え～と高校２年生でベクトルは合成ぐらいしかできません・・

文字式とかで説明してくれるとありがたいです

[ねこ]

GPGAさんのレスをスルーしてるのは何故ですか？外積で計算するので問題無いと思うのですが・・・

数学的な意味で分からないのなら星の数ほどある数学系サイト見た方が図と詳しい説明もあって理解しやすいと思うよ。
sin,cosなら分かると思うけど、知らない人に図もなく文字だけで説明しろって言われたら厳しいでしょ？

答えだけ欲しいのならGPGAさんの関数を拝借するのが一番早いけどね。

[チルチル]

あ～別にスルーしてるわけではないです・・

やはり理解しないで実装すると問題が出そうなので・・

文字だけと言うか・・変数名を文字に置き換えてくれると意味が分かりやすいかも・・

数学的もそうなんですけど・・プログラムで再現する方も知りたいので・・

[non]

GPGAさんの紹介されている方法の方が簡単なようです。
簡単なプログラムもGPGAさんから載せてあるし、外積は高校で習わないからわからないと
思いますが、このプログラムだけ使わせてもらったらどうでしょうか。
どうしても、龍神録の方法を理解したいなら説明しますが、どっちにしても
内積と外積の式は公式だと思ってもらうよりないとは思います。

[ねこ]

＞チルチルさん
数学とプログラムをくっつけるのが難しいのは分かるんだけど、それならもうちょっと具体的に言って欲しいな。
「この変数」「この１行」「この計算」、問題点のフォーカスを絞らないから問題解決に遠回りしてるんですよ。

数学的に分からなくてもプログラムとアルゴリズムの説明ページは出てるんだから、そこから自分で解析するのも大事です。
そうしないともっと高度な演算や物理計算が必要になった時手が付けられなくなっちゃいますよ。
複雑な内容は解説ページのURL張るしかなくなりますからね(レスじゃ説明しきれない)

[チルチル]

ええ、仰る通りなんですが
やはり当たり判定の処理は自分で作らないと後々まずい事になりそうなので
GPGAさんのリンクを元に処理を考えてみます

まず(vx2-vx1)*(yp-vy1) - (xp-vx1)*(vy2-vy1)が１つでもプラスなら当たっていないと言う事ですよね・・
つまりこの処理を４回行ってプラスになったらやめる、最後まで行われたら当たっていると・・

そして(vx2-vx1)*(yp-vy1) - (xp-vx1)*(vy2-vy1)の意味は

(辺の終点のＸ座標-辺の始点のＸ座標)*(点のＹ座標-辺の始点のＹ座標) - (辺の終点のY座標-辺の始点のY座標)*(点のX座標-辺の始点のX座標)

と言う解釈で合っているでしょうか？
辺が時計回りに伸びている場合ですよね・・
何か個人的にしっくり来なかったので後半を逆にしました

[ねこ]

「全部右」か「全部左」か、の二択です。点の配列が時計回りと半時計周りで方向が逆転するからです。

　→
↑・↓
　←

　←
↓・↑
　→

各矢印の方を「目線」として、点がどっちにあるかを考えてるのです。

＜そして(vx2-vx1)*(yp-vy1) - (xp-vx1)*(vy2-vy1)の意味は
＜(辺の終点のＸ座標-辺の始点のＸ座標)*(点のＹ座標-辺の始点のＹ座標) - (辺の終点のY座標-辺の始点のY座標)*(点のX座標-辺の始点のX座標)

外積の公式の話ですよね。これはもう「そうですよ」としか答えられないです。
参考ページにも「v1の始点を(vx1, vy1)、終点(vx2, vy2)をとし、調べたい点（正方形Bの頂点）をP(xp, yp)」って説明されてますよね。

＜やはり当たり判定の処理は自分で作らないと後々まずい事になりそうなので
多分自分で作った方がまずい事になりますよ・・・先人の知識は様々な方の検証の後に定義されてるものなのですから。完全に扱えるようになるまでは無駄にバグで時間に振り回されるより知恵に頼った方が成長も効率も良いと思います、まぁそれでもやりたいなら止めはしませんが。

[チルチル]

え～とこの場合は全部右ですね・・

できれば先人の知恵に頼りたいんですが
私の場合は、組み込む時に間違える可能性が高いのと
コードの構造が個性的で他の人の処理と合わないと言う問題があるので
自分で組むしかないです・・

あと自分で作った処理の方が応用も利くし愛着が湧くので・・

とりあえずコードを組んでみるので少々お待ちください・・

[チルチル]

ん？そういえばリンクに「正方形」って描いてありますけど長方形でも大丈夫なんでしょうか？
まあ最後に「時計回りのベクトルで構成されたすべての平面について成り立ちます」と書いてあるから
大丈夫だとは思いますが、と言う事は台形とか三角形でも使えるんでしょうか？
使えるなら後々応用できそうなのですが・・
とりあえず時計回りだから凸レンズとか凹レンズはダメそうですね・・

[Libra]

ゲームの処理ということで、自分であれば、

・正方形(or長方形)の中心座標
・正方形(or長方形)の表示角度
・縦の長さ、横の長さ

を使って、当たり判定を行う関数内で4つの頂点位置を出してから、計算しますね。
こうすれば、頂点座標4つの右回り、左回りを考えなくて済みます。


> 私の場合は、組み込む時に間違える可能性が高いのと
> コードの構造が個性的で他の人の処理と合わないと言う問題があるので
> 自分で組むしかないです・・
> あと自分で作った処理の方が応用も利くし愛着が湧くので・・
> とりあえずコードを組んでみるので少々お待ちください・・

他の人がソースを見るということを意識してプログラムを書いてはどうでしょうか？

[チルチル]

＞を使って、当たり判定を行う関数内で4つの頂点位置を出してから、計算しますね。
あ～確かに私のコードで判定を行う場合も
与えられている情報は
・正方形(or長方形)の中心座標
・正方形(or長方形)の表示角度
・縦の長さ、横の長さ
だけだと思うので、それで行けると思います

＞こうすれば、頂点座標4つの右回り、左回りを考えなくて済みます。
ん～これはよくわからないですね・・
頂点座標を時計回りの順番で計算して行くと言う事でしょうか？

＞他の人がソースを見るということを意識してプログラムを書いてはどうでしょうか？
できればそうしたいんですが、私の実力では後で自分が見てギリギリ理解できるコードが精一杯です・・
あと私は神経質なので変数名,関数名もスペルを略さないので全体的に式が長くなっています・・
略した場合は後で自分が見て理解できないと言う問題も出てきますが・・

[ねこ]

＜矩形計算
龍神録の例やベクトルの例は応用出来るからよく使われているだけで単純な矩形の内部判定ならいくらでもありますよ。
例えば調べたい座標と矩形の中心を結ぶ線が矩形の四辺のどれかと交差しているか、とかね。

＜凹凸
ベクトルの例なら応用すりゃ出来るよ。テンキーの１７５９３を結ぶような形なら１７９３の矩形を判定して、矩形内部にあったら７５９の三角形で判定して、三角形内部だったら範囲外とかね。

＜あと私は神経質なので変数名,関数名もスペルを略さないので全体的に式が長くなっています・・
これは全然構わないと思うよ、ていうか僕も長い方だし。
略語は例えばExtraをEx、PointをPntとか後から見ようがいつでも分かるものをするのが理想だと考えてます。
主処理(MainScript)をms、WindowWidthをwwとか略されてるとナニコレ？って思う派です。

[チルチル]

スペルが長いのもアリなんでしょうかね～
長いと言えば一般的には関数の引数は少ない方が良いらしいですが
私は分けると書き忘れる可能性があるので
１つの関数にできるだけ詰め込む努力を延々としています
これは他の人が見て見やすいコードは難しいかもしれませんね・・
自分にとって見やすいコードと一般的に見やすいコードが違うようです・・

[lbfuvab]

長方形が細長ければ、
直線と点の距離と長方形の中心からの距離でも良い近似になりそうですね。

[チルチル]

あ～それも良いかもしれませんね
でも今回は近似だとまずいんですよね・・
想定している処理だと辺の長さが１ピクセル以下になる場合もあるんですが大丈夫かな・・

[チルチル]

コードを作ってみました
マウスポインタが四角形の中に入ると「当たっています」と表示されます
左クリックで頂点を動かせます
使う状況は未定だから効率化は今は良いかな・・
ちなみに「時計回りのベクトルで構成された平面」と言うのはこの場合「頂点で辺が全部右に曲がっている」って事ですよね・・

#include "DxLib.h"

typedef struct{
    int x;
    int y;          //座標
    int WheelRotVol;//ホイールの回転量
    unsigned int Button[8];  //ボタンの押した状態
}Mouse_t;

Mouse_t Mouse;
 
int GetHitMouseStateAll_2(Mouse_t *Nezumi){
    if(GetMousePoint( &Nezumi->x, &Nezumi->y ) == -1){ //マウスの位置取得
        return -1;
    }
    int MouseInput=GetMouseInput();    //マウスの押した状態取得
    for(int i=0; i<8; i++){            //マウスのキーは最大8個まで確認出来る
        if( (MouseInput & 1<<i ) != 0 ) Nezumi->Button++;   //押されていたらカウントアップ
        else                            Nezumi->Button = 0; //押されてなかったら0
    }
    Nezumi->WheelRotVol = GetMouseWheelRotVol() ;    //ホイール回転量取得
    return 0;
}

int Key[256];

int GetHitKeyStateAll_2(int GetHitKeyStateAll_InputKey[/url]){
    char GetHitKeyStateAll_Key[256];
    GetHitKeyStateAll( GetHitKeyStateAll_Key );
    for(int i=0;i<256;i++){
        if(GetHitKeyStateAll_Key==1) GetHitKeyStateAll_InputKey++;
        else                            GetHitKeyStateAll_InputKey=0;
    }
    return 0;
}

int count=0;
    
void wait_fanc(){
    int term;
    static int t=0;
    term = GetNowCount()-t;
    if(16-term>0)
            Sleep(16-term);
    t=GetNowCount();
    return;
}

void fps(){
    int i;
    static int t=0,ave=0,f[60];

    f[count%60]=GetNowCount()-t;
    t=GetNowCount();
    if(count%60==59){
        ave=0;
        for(i=0;i<60;i++)
            ave+=f;
        ave/=60;
    }
    if(ave!=0){
        DrawFormatString(0, 0,GetColor(255,255,255),"%.1fFPS",1000.0/(double)ave);
        DrawFormatString(0,20,GetColor(255,255,255),"%dms"  ,ave);
    }
    return;
}

float X[4]={100,300,300,100},Y[4]={100,100,300,300};

char H,V;

int WINAPI WinMain( HINSTANCE hInstance, HINSTANCE hPrevInstance,LPSTR lpCmdLine, int nCmdShow ){
ChangeWindowMode(TRUE);SetOutApplicationLogValidFlag( FALSE );
if(DxLib_Init() == -1 || SetDrawScreen( DX_SCREEN_BACK )!=0) return -1;//初期化と裏画面化

while(ProcessMessage()==0 && ClearDrawScreen()==0 && GetHitKeyStateAll_2(Key)==0 && Key[KEY_INPUT_ESCAPE]==0){
          //↑メッセージ処理       　  ↑画面をクリア    　　　    ↑入力状態を保存　　　　　　　↑ESCが押されていない

GetHitMouseStateAll_2(&Mouse);  //マウスの入力状態取得

if( Mouse.Button[0]==1 )X[V]=Mouse.x,Y[V]=Mouse.y,++V,V-=4*(V==4);

for(int i=0;i<4;i++)DrawLine( X , Y , X[(i+1)%4] , Y[(i+1)%4] , GetColor( 255 , 255 , 255 ) );

for(int i=0;i<4;i++){

	if( (X[(i+1)%4]-X)*(Mouse.y-Y)-(Y[(i+1)%4]-Y[i])*(Mouse.x-X[i])>0 )H=1;

	else{H=0;break;}

}

if( H )DrawString( 100 , 0 , "当たっています" , GetColor( 255 , 255 , 255 ) );

fps();
count++;
ScreenFlip();
wait_fanc();

}

DxLib_End();
return 0;

}