367

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

助言がありますか?

4

21 に答える 21

778
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) 

あなたがRectAを持っていて、RectBを持っているとしましょう。証明は矛盾によるものです。4つの条件のいずれかにより、重複が存在しないことが保証されます。

  • Cond1。Aの左端がBの右端の右側にある場合、-Aは完全にBの右側にあります
  • Cond2。Aの右端がBの左端の左側にある場合、-Aは完全にBの左側にあります
  • Cond3。Aの上端がBの下端より下にある場合、-Aは完全にBより下にあります
  • Cond4。Aの下端がBの上端より上にある場合、-Aは完全にBより上にあります

したがって、非オーバーラップの条件は

非オーバーラップ=>Cond1またはCond2またはCond3またはCond4

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

オーバーラップ=>NOT(Cond1またはCond2またはCond3またはCond4)

ド・モルガンの法則によれ ば、ド・モルガンを使用し
Not (A or B or C or D)た場合と同じです。Not A And Not B And Not C And Not D

Cond1でもCond2でもCond3でもCond4でもない

これは次と同等です。

  • Aの左端からBの右端の左側、[ RectA.Left < RectB.Right]、および
  • Aの右端からBの左端の右へ、[ RectA.Right > RectB.Left]、および
  • Aの上部とBの下部、[ RectA.Top > RectB.Bottom]、および
  • Bのトップの下のAのボトム[ RectA.Bottom < RectB.Top]

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

于 2008-11-20T18:25:30.603 に答える
126
struct rect
{
    int x;
    int y;
    int width;
    int height;
};

bool valueInRange(int value, int min, int max)
{ return (value >= min) && (value <= max); }

bool rectOverlap(rect A, rect B)
{
    bool xOverlap = valueInRange(A.x, B.x, B.x + B.width) ||
                    valueInRange(B.x, A.x, A.x + A.width);

    bool yOverlap = valueInRange(A.y, B.y, B.y + B.height) ||
                    valueInRange(B.y, A.y, A.y + A.height);

    return xOverlap && yOverlap;
}
于 2008-11-20T18:36:20.627 に答える
32
struct Rect
{
    Rect(int x1, int x2, int y1, int y2)
    : x1(x1), x2(x2), y1(y1), y2(y2)
    {
        assert(x1 < x2);
        assert(y1 < y2);
    }

    int x1, x2, y1, y2;
};

bool
overlap(const Rect &r1, const Rect &r2)
{
    // The rectangles don't overlap if
    // one rectangle's minimum in some dimension 
    // is greater than the other's maximum in
    // that dimension.

    bool noOverlap = r1.x1 > r2.x2 ||
                     r2.x1 > r1.x2 ||
                     r1.y1 > r2.y2 ||
                     r2.y1 > r1.y2;

    return !noOverlap;
}
于 2008-11-20T18:53:28.190 に答える
25

長方形が他の長方形の完全に外側にあるかどうかを確認する方が簡単です。

左に...

(r1.x + r1.width < r2.x)

それとも右側...

(r1.x > r2.x + r2.width)

または上に...

(r1.y + r1.height < r2.y)

それとも一番下...

(r1.y > r2.y + r2.height)

2 番目の長方形の場合、これと衝突する可能性はありません。したがって、四角形が衝突することを示すブール値を返す関数を作成するには、単純に条件を論理 OR で結合し、結果を否定します。

function checkOverlap(r1, r2) : Boolean
{ 
    return !(r1.x + r1.width < r2.x || r1.y + r1.height < r2.y || r1.x > r2.x + r2.width || r1.y > r2.y + r2.height);
}

タッチのみで肯定的な結果を得るには、「<」と「>」を「<=」と「>=」に変更します。

于 2010-11-04T15:51:55.987 に答える
8

次のように長方形の位置とサイズを定義したとします。

ここに画像の説明を入力

私の C++ 実装は次のようになります。

class Vector2D
{
    public:
        Vector2D(int x, int y) : x(x), y(y) {}
        ~Vector2D(){}
        int x, y;
};

bool DoRectanglesOverlap(   const Vector2D & Pos1,
                            const Vector2D & Size1,
                            const Vector2D & Pos2,
                            const Vector2D & Size2)
{
    if ((Pos1.x < Pos2.x + Size2.x) &&
        (Pos1.y < Pos2.y + Size2.y) &&
        (Pos2.x < Pos1.x + Size1.x) &&
        (Pos2.y < Pos1.y + Size1.y))
    {
        return true;
    }
    return false;
}

上記の図に従った関数呼び出しの例:

DoRectanglesOverlap(Vector2D(3, 7),
                    Vector2D(8, 5),
                    Vector2D(6, 4),
                    Vector2D(9, 4));

ブロック内の比較は次のifようになります。

if ((Pos1.x < Pos2.x + Size2.x) &&
    (Pos1.y < Pos2.y + Size2.y) &&
    (Pos2.x < Pos1.x + Size1.x) &&
    (Pos2.y < Pos1.y + Size1.y))
                 ↓  
if ((   3   <    6   +   9    ) &&
    (   7   <    4   +   4    ) &&
    (   6   <    3   +   8    ) &&
    (   4   <    7   +   5    ))
于 2014-12-23T16:38:06.017 に答える
8

反対の質問を自問してください: 2 つの長方形がまったく交差しないかどうかを判断するにはどうすればよいでしょうか? 明らかに、長方形 B の完全に左にある長方形 A は交差しません。また、A が完全に右にある場合。同様に、A が B の上に完全にある場合、または B の下に完全にある場合。それ以外の場合は、A と B は交差します。

以下にはバグがあるかもしれませんが、アルゴリズムについてはかなり自信があります。

struct Rectangle { int x; int y; int width; int height; };

bool is_left_of(Rectangle const & a, Rectangle const & b) {
   if (a.x + a.width <= b.x) return true;
   return false;
}
bool is_right_of(Rectangle const & a, Rectangle const & b) {
   return is_left_of(b, a);
}

bool not_intersect( Rectangle const & a, Rectangle const & b) {
   if (is_left_of(a, b)) return true;
   if (is_right_of(a, b)) return true;
   // Do the same for top/bottom...
 }

bool intersect(Rectangle const & a, Rectangle const & b) {
  return !not_intersect(a, b);
}
于 2008-11-20T18:47:47.500 に答える
3

Java API で行う方法は次のとおりです。

public boolean intersects(Rectangle r) {
    int tw = this.width;
    int th = this.height;
    int rw = r.width;
    int rh = r.height;
    if (rw <= 0 || rh <= 0 || tw <= 0 || th <= 0) {
        return false;
    }
    int tx = this.x;
    int ty = this.y;
    int rx = r.x;
    int ry = r.y;
    rw += rx;
    rh += ry;
    tw += tx;
    th += ty;
    //      overflow || intersect
    return ((rw < rx || rw > tx) &&
            (rh < ry || rh > ty) &&
            (tw < tx || tw > rx) &&
            (th < ty || th > ry));
}
于 2011-10-24T06:31:52.420 に答える
3

質問では、長方形が任意の回転角度にあるときの数学にリンクしています。ただし、質問の角度について少し理解すれば、すべての長方形は互いに垂直であると解釈します。

オーバーラップ式の面積を知っている一般的なものは次のとおりです。

例を使用します。

   1 2 3 4 5 6

1 +---+---+
   | | | |   
2 + A +---+---+
   | | | | ビ |
3 + + +---+---+
   | | | | | | | | | |
4 +---+---+---+---+ +
               | | | |
5 + C +
               | | | |
6 +---+---+

1) すべての x 座標 (左と右の両方) をリストに収集し、並べ替えて重複を削除します

1 3 4 5 6

2) すべての y 座標 (上と下の両方) をリストに収集し、並べ替えて重複を削除します。

1 2 3 4 6

3) 一意の x 座標間のギャップ数 * 一意の y 座標間のギャップ数で 2D 配列を作成します。

4*4

4) すべての長方形をこのグリッドにペイントし、発生する各セルのカウントを増やします。

   1 3 4 5 6

1 +---+
   | | 1 | 0 0 0
2 +---+---+---+
   | | 1 | 1 | 1 | 0
3 +---+---+---+---+
   | | 1 | 1 | 2 | 1 |
4 +---+---+---+---+
     0 0 | 1 | 1 |
6 +---+---+

5) 長方形をペイントすると、オーバーラップをインターセプトするのは簡単です。

于 2008-11-20T19:01:12.217 に答える
2
struct Rect
{
   Rect(int x1, int x2, int y1, int y2)
   : x1(x1), x2(x2), y1(y1), y2(y2)
   {
       assert(x1 < x2);
       assert(y1 < y2);
   }

   int x1, x2, y1, y2;
};

//some area of the r1 overlaps r2
bool overlap(const Rect &r1, const Rect &r2)
{
    return r1.x1 < r2.x2 && r2.x1 < r1.x2 &&
           r1.y1 < r2.y2 && r2.x1 < r1.y2;
}

//either the rectangles overlap or the edges touch
bool touch(const Rect &r1, const Rect &r2)
{
    return r1.x1 <= r2.x2 && r2.x1 <= r1.x2 &&
           r1.y1 <= r2.y2 && r2.x1 <= r1.y2;
}
于 2008-11-20T19:31:23.810 に答える
1

長方形がオーバーラップする場合、オーバーラップ領域はゼロより大きくなります。次に、オーバーラップ領域を見つけましょう。

それらがオーバーラップする場合、overlap-rectの左端がとになりmax(r1.x1, r2.x1)、右端がになりますmin(r1.x2, r2.x2)。したがって、オーバーラップの長さは次のようになりますmin(r1.x2, r2.x2) - max(r1.x1, r2.x1)

したがって、領域は次のようになります。

area = (max(r1.x1, r2.x1) - min(r1.x2, r2.x2)) * (max(r1.y1, r2.y1) - min(r1.y2, r2.y2))

その場合area = 0、それらは重複しません。

簡単ですね。

于 2010-04-23T07:25:26.143 に答える
1

2 つの長方形が長方形 A と長方形 B であるとします。それらの中心を A1 と B1 とし (A1 と B1 の座標は簡単にわかります)、高さを Ha と Hb、幅を Wa と Wb、dx をwidth(x) は A1 と B1 の間の距離であり、dy は A1 と B1 の間の高さ (y) の距離です。

これで、A と B が重なっていると言えます。

if(!(dx > Wa+Wb)||!(dy > Ha+Hb)) returns true
于 2012-06-28T15:16:15.450 に答える
1

座標をピクセルの位置を示すものと考えないでください。それらはピクセルの間にあると考えてください。そうすれば、2x2 の長方形の面積は 9 ではなく 4 になります。

bool bOverlap = !((A.Left >= B.Right || B.Left >= A.Right)
               && (A.Bottom >= B.Top || B.Bottom >= A.Top));
于 2008-11-20T19:33:15.490 に答える
0

これは本『Introduction to Java Programming-Comprehensive Edition』の演習 3.28 からのものです。このコードは、2 つの四角形がインデンティクルであるかどうか、一方が他方の内側にあるかどうか、および一方が他方の外側にあるかどうかをテストします。これらの条件のいずれも満たされない場合は、2 つの重複があります。

**3.28 (ジオメトリ: 2 つの四角形) 2 つの四角形の中心の x、y 座標、幅、高さを入力するようユーザーに促し、2 つ目の四角形が最初の四角形の内側にあるか、最初の四角形と重なっているかを判断するプログラムを作成します。図 3.9 に示すように。プログラムをテストして、すべてのケースをカバーします。サンプルの実行は次のとおりです。

r1 の中心の x、y 座標、幅、および高さを入力してください: 2.5 4 2.5 43 r2 の中心の x、y 座標、幅、および高さを入力してください: 1.5 5 0.5 3 r2 は r1 の内側にあります

r1 の中心の x、y 座標、幅、および高さを入力してください: 1 2 3 5.5 r2 の中心の x、y 座標、幅、および高さを入力してください: 3 4 4.5 5 r2 は r1 と重なっています

r1 の中心の x、y 座標、幅、および高さを入力してください: 1 2 3 3 r2 の中心の x、y 座標、幅、および高さを入力してください: 40 45 3 2 r2 は r1 と重なりません

import java.util.Scanner;

public class ProgrammingEx3_28 {
public static void main(String[] args) {
    Scanner input = new Scanner(System.in);

    System.out
            .print("Enter r1's center x-, y-coordinates, width, and height:");
    double x1 = input.nextDouble();
    double y1 = input.nextDouble();
    double w1 = input.nextDouble();
    double h1 = input.nextDouble();
    w1 = w1 / 2;
    h1 = h1 / 2;
    System.out
            .print("Enter r2's center x-, y-coordinates, width, and height:");
    double x2 = input.nextDouble();
    double y2 = input.nextDouble();
    double w2 = input.nextDouble();
    double h2 = input.nextDouble();
    w2 = w2 / 2;
    h2 = h2 / 2;

    // Calculating range of r1 and r2
    double x1max = x1 + w1;
    double y1max = y1 + h1;
    double x1min = x1 - w1;
    double y1min = y1 - h1;
    double x2max = x2 + w2;
    double y2max = y2 + h2;
    double x2min = x2 - w2;
    double y2min = y2 - h2;

    if (x1max == x2max && x1min == x2min && y1max == y2max
            && y1min == y2min) {
        // Check if the two are identicle
        System.out.print("r1 and r2 are indentical");

    } else if (x1max <= x2max && x1min >= x2min && y1max <= y2max
            && y1min >= y2min) {
        // Check if r1 is in r2
        System.out.print("r1 is inside r2");
    } else if (x2max <= x1max && x2min >= x1min && y2max <= y1max
            && y2min >= y1min) {
        // Check if r2 is in r1
        System.out.print("r2 is inside r1");
    } else if (x1max < x2min || x1min > x2max || y1max < y2min
            || y2min > y1max) {
        // Check if the two overlap
        System.out.print("r2 does not overlaps r1");
    } else {
        System.out.print("r2 overlaps r1");
    }

}
}
于 2015-08-01T10:06:02.573 に答える
0
bool Square::IsOverlappig(Square &other)
{
    bool result1 = other.x >= x && other.y >= y && other.x <= (x + width) && other.y <= (y + height); // other's top left falls within this area
    bool result2 = other.x >= x && other.y <= y && other.x <= (x + width) && (other.y + other.height) <= (y + height); // other's bottom left falls within this area
    bool result3 = other.x <= x && other.y >= y && (other.x + other.width) <= (x + width) && other.y <= (y + height); // other's top right falls within this area
    bool result4 = other.x <= x && other.y <= y && (other.x + other.width) >= x && (other.y + other.height) >= y; // other's bottom right falls within this area
    return result1 | result2 | result3 | result4;
}
于 2016-08-07T03:29:22.090 に答える
0
struct point { int x, y; };

struct rect { point tl, br; }; // top left and bottom right points

// return true if rectangles overlap
bool overlap(const rect &a, const rect &b)
{
    return a.tl.x <= b.br.x && a.br.x >= b.tl.x && 
           a.tl.y >= b.br.y && a.br.y <= b.tl.y;
}
于 2020-03-01T17:00:48.280 に答える
0

私は非常に簡単な解決策を持っています

x1,y1 x2,y2 ,l1,b1,l2, をそれぞれ座標と長さと幅とする

条件 ((x2

これらの長方形が重なる唯一の方法は、x1、y1 の対角線の点が他の長方形の内側にある場合、または同様に x2、y2 の対角線の点が他の長方形の内側にある場合です。これはまさに上記の条件が意味するものです。

于 2013-05-12T07:17:40.553 に答える
0

C# バージョンを実装しましたが、C++ に簡単に変換できます。

public bool Intersects ( Rectangle rect )
{
  float ulx = Math.Max ( x, rect.x );
  float uly = Math.Max ( y, rect.y );
  float lrx = Math.Min ( x + width, rect.x + rect.width );
  float lry = Math.Min ( y + height, rect.y + rect.height );

  return ulx <= lrx && uly <= lry;
}
于 2008-11-20T18:46:04.650 に答える