algorithm - 2つの長方形の交差点

Question

それぞれ4つの値で特徴付けられる2つの長方形があります：

左の位置X、上の位置Y、幅Wと高さH：

X1, Y1, H1, W1
X2, Y2, H2, W2

次のように、長方形は回転しません。

+--------------------> X axis
|
|    (X,Y)      (X+W, Y)
|    +--------------+
|    |              |
|    |              |
|    |              |
|    +--------------+
v    (X, Y+H)     (X+W,Y+H)

Y axis

2つの長方形の交点が空であるかどうかを判断するための最良の解決策は何ですか？

score 94 · Accepted Answer

if (X1+W1<X2 or X2+W2<X1 or Y1+H1<Y2 or Y2+H2<Y1):
    Intersection = Empty
else:
    Intersection = Not Empty

2つのプラスの幅と高さではなく、4つの座標（((X,Y),(A,B))および）がある場合、次のようになります。((X1,Y1),(A1,B1))

if (A<X1 or A1<X or B<Y1 or B1<Y):
    Intersection = Empty
else:
    Intersection = Not Empty

score 5 · Accepted Answer

最良の例..

/**
 * Check if two rectangles collide
 * x_1, y_1, width_1, and height_1 define the boundaries of the first rectangle
 * x_2, y_2, width_2, and height_2 define the boundaries of the second rectangle
 */
boolean rectangle_collision(float x_1, float y_1, float width_1, float height_1, float x_2, float y_2, float width_2, float height_2)
{
  return !(x_1 > x_2+width_2 || x_1+width_1 < x_2 || y_1 > y_2+height_2 || y_1+height_1 < y_2);
}

また、もう1つの方法は、このリンクを参照してください...そしてそれを自分でコーディングしてください。

score 3 · Accepted Answer

2つの長方形の寸法が同じである場合は、次のことができます。

if (abs (x1 - x2) < w && abs (y1 - y2) < h) {
    // overlaps
}

score 0 · Accepted Answer

私はちょうどacプログラムで試し、以下に書きました。

#include<stdio.h>

int check(int i,int j,int i1,int j1, int a, int b,int a1,int b1){
    return (\
    (((i>a) && (i<a1)) && ((j>b)&&(j<b1))) ||\ 
    (((a>i) && (a<i1)) && ((b>j)&&(b<j1))) ||\ 
    (((i1>a) && (i1<a1)) && ((j1>b)&&(j1<b1))) ||\ 
    (((a1>i) && (a1<i1)) && ((b1>j)&&(b1<j1)))\
    );  
}
int main(){
    printf("intersection test:(0,0,100,100),(10,0,1000,1000) :is %s\n",check(0,0,100,100,10,0,1000,1000)?"intersecting":"Not intersecting");
    printf("intersection test:(0,0,100,100),(101,101,1000,1000) :is %s\n",check(0,0,100,100,101,101,1000,1000)?"intersecting":"Not intersecting");
    return 0;
}

score 0 · Accepted Answer

（0、0）が左上隅である座標系を使用します。

私はそれを垂直と水平のスライディングウィンドウの観点から考え、これを思いついた：

（B.Bottom> A.Top && B.Top <A.Bottom）&&（B.Right> A.Left && B.Left <A.Right）

以下にド・モルガンの法則を適用すると、これが得られます。

Not（B.Bottom <A.Top || B.Top> A.Bottom || B.Right <A.Left || B.Left> A.Right）

BはAの上にあります
BはAの下にあります
BはAの左側にあります
BはAの権利です

score 0 · Accepted Answer

長方形の左下隅と右上隅の座標が次の場合：
rect1の場合は（r1x1、r1y1）、（r1x2、r1y2）、rect2の場合は
（r2x1、r2y1）、（r2x2、r2y2）
（以下のPythonのようなコード）

    intersect = False
    for x in [r1x1, r1x2]:
        if (r2x1<=x<=r2x2):
            for y in [r1y1, r1y2]:
                if (r2y1<=y<=r2y2):
                    intersect = True
                    return intersect
                else:
                    for Y in [r2y1, r2y2]:
                        if (r1y1<=Y<=r1y2):
                            intersect = True
                            return intersect
        else:  
            for X in [r2x1, r2x2]:
                if (r1x1<=X<=r1x2):
                    for y in [r2y1, r2y2]:
                        if (r1y1<=y<=r1y2):
                            intersect = True
                            return intersect
                        else:
                            for Y in [r1y1, r1y2]:
                                if (r2y1<=Y<=r2y2):
                                    intersect = True
                                    return intersect
    return intersect

score -1 · Accepted Answer

if（X1 <= X2 + W2 && X2 <= X1 + W1 && Y1> = Y2-H2 && Y2> = Y1 + H1）交差する

質問では、Yが一番上の位置です。

注：このソリューションは、長方形がX/Y軸に位置合わせされている場合にのみ機能します。

algorithm - 2つの長方形の交差点

7 に答える 7

Related

Reference