1. ホーム
  2. c++

[解決済み】2つの長方形が重なり合っているかどうかを判定する?

2022-04-18 14:23:21

質問

高さ、幅、x-pos、y-posを入力して矩形(2以上5以下)を作るC++プログラムを作ろうとしているのですが、この矩形はどのように作られるのですか?これらの矩形はすべて x 軸と y 軸に平行に存在し、すべての辺の傾きは 0 または無限大となります。

に書かれていることを実装してみました。 これ の質問ですが、あまりうまくいきません。

私の現在の実装では、以下のようにしています。

// Gets all the vertices for Rectangle 1 and stores them in an array -> arrRect1
// point 1 x: arrRect1[0], point 1 y: arrRect1[1] and so on...
// Gets all the vertices for Rectangle 2 and stores them in an array -> arrRect2

// rotated edge of point a, rect 1
int rot_x, rot_y;
rot_x = -arrRect1[3];
rot_y = arrRect1[2];
// point on rotated edge
int pnt_x, pnt_y;
pnt_x = arrRect1[2]; 
pnt_y = arrRect1[3];
// test point, a from rect 2
int tst_x, tst_y;
tst_x = arrRect2[0];
tst_y = arrRect2[1];

int value;
value = (rot_x * (tst_x - pnt_x)) + (rot_y * (tst_y - pnt_y));
cout << "Value: " << value;  

しかし、私は(a)私がリンクしたアルゴリズムを正しく実装したのか、またはこれを解釈する方法を正確に行ったのか、よく分からないのです。

何かご指摘はありますか?

解決方法は?

if (RectA.Left < RectB.Right && RectA.Right > RectB.Left &&
     RectA.Top > RectB.Bottom && RectA.Bottom < RectB.Top ) 

または、直交座標を使用する場合

(X1が左座標、X2が右座標とします。 左から右へ増加 で、Y1が上部の座標、Y2が下部の座標です。 下から上に向かって増加 -- もしあなたの座標系がこうでないなら(例えば、ほとんどのコンピュータはY方向が逆になっている)。 以下の比較を入れ替える ) ...

if (RectA.X1 < RectB.X2 && RectA.X2 > RectB.X1 &&
    RectA.Y1 > RectB.Y2 && RectA.Y2 < RectB.Y1) 

レクトA、レクトBがあるとする。 証明は矛盾によって行われる。4つの条件のうち、どれかが保証されている。 重なりが存在しないこと :

  • 条件1. Aの左辺がBの右辺の右側にある場合。 - AはBの右側にある
  • 条件2. Aの右辺がBの左辺より左側にある場合。 - AはBの左側にある
  • 条件3. Aの上辺がBの下辺より下にある場合。 - AはBより完全に下である
  • 条件4. Aの下辺がBの上辺より上にある場合。 - AはBの上にある

つまり、重ならないための条件は

NON-Overlap => Cond1 Or Cond2 Or Cond3 Or Cond4

したがって、オーバーラップの十分条件は、その逆である。

オーバーラップ => NOT (条件1または条件2または条件3または条件4)

ド・モルガンの法則では

Not (A or B or C or D) と同じです。 Not A And Not B And Not C And Not D

ということで、De Morgan を使って、次のようになります。

条件1ではなく、条件2でもなく、条件3でもなく、条件4でもなく

と同等である。

  • Aの左エッジがBの右エッジの左側にある、[ ]。 RectA.Left < RectB.Right ]であり、かつ
  • Aの右端からBの左端の右側、[... RectA.Right > RectB.Left ]であり、かつ
  • AのトップがBのボトムより上、[ RectA.Top > RectB.Bottom ]であり、かつ
  • BのTopの下にあるAのBottom [ ]。 RectA.Bottom < RectB.Top ]

注1 : この同じ原理を任意の数の次元に拡張できることは、かなり明白です。

注2 : また、1ピクセルの重なりをカウントするのは簡単なことです。 < とか > をその境界線上に <= または >= .

注3 : この答えは、デカルト座標(X、Y)を利用する場合、標準的な代数的デカルト座標(xは左から右に増加し、Yは下から上に増加する)に基づいています。明らかに、コンピュータシステムが画面座標を異なる方法で機械化する場合(例えば、Yを上から下へ、またはXを右から左へ増加)、構文はそれに合わせて調整する必要があります。