☰

2つの長方形が重なり合っているかどうかを確認します。質問する

tag-icon • tag-icon c++ algorithm geometry overlap rectangles
2つの長方形が重なり合っているかどうかを確認します。質問する

私は、ユーザーから次の入力を受け取り、長方形 (2 から 5 の間) を作成する C++ プログラムを作成しようとしています: 高さ、幅、x 位置、y 位置。これらの長方形はすべて 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) リンクしたアルゴリズムを正しく実装したかどうか、またはこれをどのように解釈すればよいか正確にはわかりません。

助言がありますか？

ベストアンサー1

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)

Rect A と Rect B があるとします。証明は背理法です。4 つの条件のいずれかが重なりが存在しないことが保証されます。

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

重複しない条件は

重複なし => 条件 1 または条件 2 または条件 3 または条件 4

したがって、Overlap の十分な条件はその逆になります。

重複 => NOT (条件 1 または条件 2 または条件 3 または条件 4)

ド・モルガンの法則は、
Not (A or B or C or D)と同じであると言うのでNot A And Not B And Not C And Not D
、ド・モルガンの法則を用いると、

条件1 ではない、条件2 ではない、条件3 ではない、条件4 ではない

これは次と同等です:

  • Aの左端がBの右端の左側にある、[ RectA.Left < RectB.Right]、そして
  • Aの右端からBの左端の右側、[ RectA.Right > RectB.Left]、そして
  • Aの上部がBの下部より上、[ RectA.Top > RectB.Bottom]、そして
  • Aの下部がBの上部より下[ RectA.Bottom < RectB.Top]

注 1 : この同じ原理を任意の数の次元に拡張できることは明らかです。
注 2 : 1 ピクセルだけの重なりを数えることも明らかです。その境界上の<および/または をまたはに変更します。注 3 : この回答は、直交座標 (X, Y) を使用する場合、標準的な代数直交座標 (x は左から右に増加し、Y は下から上に増加) に基づいています。 当然のことながら、コンピュータ システムが画面座標を異なる方法で機械化する場合 (たとえば、Y が上から下に増加したり、X が右から左に増加したりする場合)、構文をそれに応じて調整する必要があります。><=>=

おすすめ記事