Tentukan apakah dua persegi panjang saling tumpang tindih?

337

Saya mencoba untuk menulis program C ++ yang mengambil input berikut dari pengguna untuk membangun persegi panjang (antara 2 dan 5): tinggi, lebar, x-pos, y-pos. Semua persegi panjang ini akan ada sejajar dengan sumbu x dan sumbu y, yaitu semua tepinya memiliki kemiringan 0 atau tak hingga.

Saya sudah mencoba menerapkan apa yang disebutkan dalam pertanyaan ini tetapi saya tidak memiliki banyak keberuntungan.

Implementasi saya saat ini melakukan hal berikut:

// 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;  

Namun saya tidak begitu yakin apakah (a) saya telah mengimplementasikan algoritma yang saya tautkan dengan benar, atau jika saya benar-benar bagaimana mengartikannya?

Ada saran?

Rob Burke
sumber
3
saya akan berpikir solusi untuk masalah Anda tidak melibatkan setiap perkalian.
Scott Evernden

Jawaban:

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

atau, menggunakan koordinat Cartesian

(Dengan X1 yang kiri coord, X2 menjadi kanan coord, meningkat dari kiri ke kanan dan Y1 menjadi coord Atas, dan Y2 menjadi coord Bawah, meningkat dari bawah ke atas - jika ini bukan bagaimana sistem koordinat Anda [misalnya kebanyakan komputer memiliki Arah Y terbalik], tukar perbandingan di bawah ) ...

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

Katakanlah Anda memiliki Rect A, dan Rect B. Proof adalah dengan kontradiksi. Salah satu dari empat ketentuan ini menjamin bahwa tidak ada tumpang tindih yang dapat terjadi :

  • Cond1. Jika tepi kiri A di sebelah kanan tepi kanan B, - maka A benar-benar ke kanan Dari B
  • Cond2. Jika tepi kanan A di sebelah kiri tepi kiri B, - maka A benar-benar ke kiri Dari B
  • Cond3. Jika tepi atas A di bawah tepi bawah B, - maka A benar-benar di bawah B
  • Cond4. Jika tepi bawah A di atas tepi atas B, - maka A benar-benar di atas B

Jadi syarat untuk Non-Overlap adalah

NON-Tumpang tindih => Cond1 Atau Cond2 Atau Cond3 Atau Cond4

Oleh karena itu, kondisi yang cukup untuk Tumpang tindih adalah sebaliknya.

Tumpang tindih => TIDAK (Cond1 Atau Cond2 Atau Cond3 Atau Cond4)

Hukum De Morgan mengatakan
Not (A or B or C or D)sama dengan Not A And Not B And Not C And Not D
menggunakan De Morgan, yang kita miliki

Tidak Cond1 Dan Tidak Cond2 Dan Tidak Cond3 Dan Tidak Cond4

Ini setara dengan:

  • Tepi Kiri A ke kiri tepi kanan B, [ RectA.Left < RectB.Right], dan
  • Tepi kanan A ke kanan tepi kiri B, [ RectA.Right > RectB.Left], dan
  • Atas A di atas bawah B, [ RectA.Top > RectB.Bottom], dan
  • Bawah A di bawah B's Top [ RectA.Bottom < RectB.Top]

Catatan 1 : Cukup jelas prinsip yang sama ini dapat diperluas ke sejumlah dimensi.
Catatan 2 : Seharusnya juga cukup jelas untuk menghitung tumpang tindih hanya satu piksel, mengubah batas <dan / atau >pada batas itu menjadi a <=atau a >=.
Catatan 3 : Jawaban ini, ketika menggunakan koordinat Cartesian (X, Y) didasarkan pada koordinat Cartesian aljabar standar (x meningkat dari kiri ke kanan, dan Y naik dari bawah ke atas). Jelas, di mana sistem komputer dapat memekanisasi koordinat layar secara berbeda, (mis., Meningkatkan Y dari atas ke bawah, atau X Dari kanan ke kiri), sintaks perlu disesuaikan sesuai /

Charles Bretana
sumber
489
Jika Anda mengalami kesulitan memvisualisasikan mengapa ia bekerja, saya membuat halaman contoh di silentmatt.com/intersection.html di mana Anda dapat menyeret persegi empat dan melihat perbandingannya.
Matthew Crumley
4
tidakkah Anda pikir Anda menggunakan kendala yang sulit? bagaimana jika kedua persegi panjang saling tumpang tindih persis di tepi sana? tidakkah kamu seharusnya mempertimbangkan <=,> = ??
Nawshad Farruque
6
@MatthewCrumley untuk A.Y1 <B.Y2 dan A.Y2> B.Y1 pada tautan Anda, bukankah seharusnya tanda gt & lt dibalik?
NikT
15
Saya harus menukar <dan> dalam dua perbandingan terakhir untuk membuatnya berfungsi
DataGreed
17
Tidak, Jawabannya benar seperti yang dinyatakan. Ini didasarkan pada penggunaan koordinat Kartesius standar. Jika Anda menggunakan sistem yang berbeda, (Y naik dari atas ke bawah), maka buat penyesuaian yang sesuai.
Charles Bretana
115
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;
}
e.James
sumber
15
Jawaban paling sederhana dan bersih.
ldog
1
@ e.James Saya kira yang terakhir B.heightseharusnyaA.height
mat_boy
'min' dan 'max' adalah kata kunci yang dicadangkan di <windows.h>. Anda dapat memperbaikinya dengan melakukan #undef mindan #undef max, atau dengan menggunakan nama parameter yang berbeda.
mchiasson
Jika Anda menggunakan secara luas, Anda dapat memperdagangkan valueInRange untuk a#define BETWEEN(value,min,max) \ (\ value > max ? max : ( value < min ? min : value )\ )
Ratata Tata
@Nemo Sebenarnya, memeriksa xOverlapadalah dalam satu dimensi; rectOverlapadalah dua dimensi. Itu dapat diperluas ke dimensi N menggunakan loop.
Justme0
27
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;
}
David Norman
sumber
Yang bagus! Dengan menerapkan hukum De Morgans, dapatkan: r1.x1 <= r2.x2 && r2.x1 <= r1.x2 && r1.y1 <= r2.y2 && r2.y1 <= r1.y2.
Borzh
23

Lebih mudah untuk memeriksa apakah persegi panjang lengkap di luar yang lain, jadi jika itu baik

di kiri...

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

atau di sebelah kanan ...

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

atau di atas ...

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

atau di bawah ...

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

dari persegi panjang kedua, itu tidak mungkin berbenturan dengannya. Jadi untuk memiliki fungsi yang mengembalikan Boolean mengatakan cuaca persegi panjang bertabrakan, kita cukup menggabungkan kondisi dengan OR logis dan meniadakan hasilnya:

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);
}

Untuk sudah menerima hasil positif saat hanya menyentuh, kita dapat mengubah "<" dan ">" dengan "<=" dan "> =".

Björn Kechel
sumber
3
Dan menerapkan hukum de morgan untuk itu.
Borzh
6

Tanyakan kepada diri Anda pertanyaan yang berlawanan: Bagaimana saya bisa menentukan apakah dua persegi panjang tidak berpotongan sama sekali? Jelas, persegi panjang A sepenuhnya di sebelah kiri persegi panjang B tidak berpotongan. Juga jika A sepenuhnya ke kanan. Dan juga jika A benar-benar di atas B atau sepenuhnya di bawah B. Dalam kasus lain, A dan B berpotongan.

Yang berikut mungkin memiliki bug, tetapi saya cukup yakin tentang algoritme:

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);
}
Coryan
sumber
6

Misalkan Anda telah menentukan posisi dan ukuran persegi panjang seperti ini:

masukkan deskripsi gambar di sini

Implementasi C ++ saya seperti ini:

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;
}

Contoh panggilan fungsi sesuai dengan gambar yang diberikan di atas:

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

Perbandingan di dalam ifblok akan terlihat seperti di bawah ini:

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    ))
hkBattousai
sumber
3

Begini cara melakukannya di API Java:

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));
}
Lyle
sumber
Perhatikan bahwa dalam C ++ tes-tes untuk overflow tidak akan berfungsi, karena overflow bilangan bulat yang ditandatangani tidak ditentukan.
Ben Voigt
2

Dalam pertanyaan, Anda menautkan ke matematika kapan persegi panjang berada pada sudut rotasi yang sewenang-wenang. Jika saya mengerti sedikit tentang sudut dalam pertanyaan, saya menafsirkan bahwa semua persegi panjang saling tegak lurus.

Seorang ahli yang mengetahui bidang formula yang tumpang tindih adalah:

Menggunakan contoh:

   1 2 3 4 5 6

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

1) kumpulkan semua koordinat x (kiri dan kanan) ke dalam daftar, kemudian urutkan dan hapus duplikatnya

1 3 4 5 6

2) kumpulkan semua koordinat y (baik atas dan bawah) ke dalam daftar, lalu urutkan dan hapus duplikatnya

1 2 3 4 6

3) membuat array 2D dengan jumlah kesenjangan antara koordinat x unik * jumlah kesenjangan antara koordinat y unik.

4 * 4

4) cat semua persegi panjang ke dalam kisi ini, menambah jumlah setiap sel yang terjadi pada:

   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) Saat Anda melukis persegi panjang, mudah untuk mencegat tumpang tindih.

Akan
sumber
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;
}
Adam Tegen
sumber
1

Jangan menganggap koordinat sebagai menunjukkan di mana piksel berada. Anggap mereka berada di antara piksel. Dengan begitu, luas persegi panjang 2x2 harus 4, bukan 9.

bool bOverlap = !((A.Left >= B.Right || B.Left >= A.Right)
               && (A.Bottom >= B.Top || B.Bottom >= A.Top));
Mike Dunlavey
sumber
1

Cara termudah adalah

/**
 * 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);
}

pertama-tama taruh dalam pikiran Anda bahwa di komputer sistem koordinat terbalik. Sumbu x sama dengan matematika tetapi sumbu y meningkat ke bawah dan berkurang jika naik ke atas .. jika persegi panjang diambil dari pusat. jika koordinat x1 lebih besar dari x2 ditambah bagian lebarnya. maka itu berarti setengah mereka akan saling menyentuh. dan dengan cara yang sama turun + setengah dari ketinggiannya. itu akan bertabrakan ..

Zar E Ahmer
sumber
1

Katakanlah dua persegi panjang adalah persegi panjang A dan persegi panjang B. Biarkan pusatnya menjadi A1 dan B1 (koordinat A1 dan B1 dapat dengan mudah ditemukan), biarkan ketinggiannya menjadi Ha dan Hb, lebar menjadi Wa dan Wb, biarkan dx menjadi lebar (x) jarak antara A1 dan B1 dan dy menjadi tinggi (y) jarak antara A1 dan B1.

Sekarang kita dapat mengatakan kita dapat mengatakan A dan B tumpang tindih: kapan

if(!(dx > Wa+Wb)||!(dy > Ha+Hb)) returns true
sachinr
sumber
0

Saya telah mengimplementasikan versi C #, mudah dikonversi ke 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;
}
baretta
sumber
2
Bagi mata yang terlatih, Anda bermaksud menjadikan ini sebagai kelas ekstensi untuk Rectangle, tetapi Anda tidak memberikan batasan atau kode apa pun untuk melakukan hal itu. Akan lebih baik jika Anda telah melakukan itu atau menjelaskan bahwa metode Anda dimaksudkan untuk digunakan, dan poin bonus jika variabel Anda benar-benar memiliki nama yang cukup deskriptif bagi siapa pun yang mengikuti untuk memahami tujuan / niat mereka.
penerima tamu
0

Saya punya solusi yang sangat mudah

biarkan x1, y1 x2, y2, l1, b1, l2, menjadi kordinat dan panjang dan luasnya masing-masing

pertimbangkan kondisinya ((x2

sekarang satu-satunya cara persegi panjang ini akan tumpang tindih adalah jika titik diagonal ke x1, y1 akan terletak di dalam persegi panjang lain atau sama dengan titik diagonal ke x2, y2 akan terletak di dalam persegi panjang lainnya. yang persis menyiratkan kondisi di atas.

himanshu
sumber
0

A dan B menjadi dua persegi panjang. C menjadi persegi panjang penutup mereka.

four points of A be (xAleft,yAtop),(xAleft,yAbottom),(xAright,yAtop),(xAright,yAbottom)
four points of A be (xBleft,yBtop),(xBleft,yBbottom),(xBright,yBtop),(xBright,yBbottom)

A.width = abs(xAleft-xAright);
A.height = abs(yAleft-yAright);
B.width = abs(xBleft-xBright);
B.height = abs(yBleft-yBright);

C.width = max(xAleft,xAright,xBleft,xBright)-min(xAleft,xAright,xBleft,xBright);
C.height = max(yAtop,yAbottom,yBtop,yBbottom)-min(yAtop,yAbottom,yBtop,yBbottom);

A and B does not overlap if
(C.width >= A.width + B.width )
OR
(C.height >= A.height + B.height) 

Itu menangani semua kasus yang mungkin.

Anwit
sumber
0

Ini dari latihan 3.28 dari buku Pengantar Java Programming- Comprehensive Edition. Kode menguji apakah kedua persegi panjang adalah indenticle, apakah satu berada di dalam yang lain dan apakah satu berada di luar yang lain. Jika tidak satu pun dari kondisi ini terpenuhi maka keduanya tumpang tindih.

** 3.28 (Geometri: dua persegi panjang) Tulis program yang meminta pengguna untuk memasukkan pusat x-, koordinat y, lebar, dan tinggi dua persegi panjang dan menentukan apakah persegi panjang kedua berada di dalam yang pertama atau tumpang tindih dengan yang pertama, seperti yang ditunjukkan pada Gambar 3.9. Uji program Anda untuk mencakup semua kasus. Berikut ini contoh proses:

Masukkan pusat x, koordinat y, lebar, dan tinggi r1: 2.5 4 2.5 43 Masukkan pusat x, koordinat y, lebar, dan tinggi r2: 1.5 5 0.5 3 r2 ada di dalam r1

Masukkan pusat x, koordinat y, lebar, dan tinggi r1: 1 2 3 5.5 Masukkan pusat x, koordinat y, lebar, dan tinggi r2: 3 4 4,5 5 r2 tumpang tindih r1

Masukkan pusat x, koordinat y, lebar, dan tinggi r1: 1 2 3 3 Masukkan pusat x, koordinat y, lebar, dan tinggi r2: 40 45 3 2 r2 tidak tumpang tindih dengan 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");
    }

}
}
anchan42
sumber
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;
}
Kok How Teh
sumber
0

Bagi Anda yang menggunakan titik pusat dan setengah ukuran untuk data persegi panjang mereka, alih-alih khas x, y, w, h, atau x0, y0, x1, x1, berikut ini cara melakukannya:

#include <cmath> // for fabsf(float)

struct Rectangle
{
    float centerX, centerY, halfWidth, halfHeight;
};

bool isRectangleOverlapping(const Rectangle &a, const Rectangle &b)
{
    return (fabsf(a.centerX - b.centerX) <= (a.halfWidth + b.halfWidth)) &&
           (fabsf(a.centerY - b.centerY) <= (a.halfHeight + b.halfHeight)); 
}
mchiasson
sumber
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;
}
Edward Karak
sumber
0

Jika persegi panjang tumpang tindih maka area tumpang tindih akan lebih besar dari nol. Sekarang mari kita temukan area yang tumpang tindih:

Jika mereka tumpang tindih maka tepi kiri overlap-rect akan menjadi max(r1.x1, r2.x1)dan tepi kanan akan min(r1.x2, r2.x2). Jadi panjang tumpang tindihnya adalahmin(r1.x2, r2.x2) - max(r1.x1, r2.x1)

Jadi area akan menjadi:

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

Jika area = 0kemudian mereka tidak tumpang tindih.

Sederhana bukan?

anony
sumber
3
Ini berfungsi untuk tumpang tindih (yang merupakan pertanyaan) tetapi tidak akan berfungsi untuk persimpangan, karena tidak akan berfungsi jika mereka berpotongan tepat di sudut.
Lance Roberts
Saya mencoba kode ini dan tidak berfungsi sama sekali. Saya hanya mendapatkan angka positif bahkan ketika mereka tidak tumpang tindih sama sekali.
Brett
@ Brett: Ya, karena produk dari dua angka negatif adalah positif.
Ben Voigt
@ BenVoigt, masalahnya adalah bahwa fungsi tidak mengembalikan 0 ketika tidak ada tumpang tindih. Saya sangat tidak jelas dengan komentar saya, tapi ya, saya hanya pernah menerima area> 0 dari fungsi ini.
Brett
Jika Anda bekerja dengan angka floating point, umumnya merupakan ide yang sangat buruk untuk menggunakan pengurangan dan hal-hal aritmatika lainnya sebelum perbandingan angka apa pun. Terutama jika Anda perlu membandingkan dengan nilai yang tepat - dalam hal ini nol. Ia bekerja secara teori, tetapi tidak dalam praktik.
maja
-1

Kode Java untuk mencari tahu apakah Rectangles saling kontak atau tumpang tindih

...

for ( int i = 0; i < n; i++ ) {
    for ( int j = 0; j < n; j++ ) {
        if ( i != j ) {
            Rectangle rectangle1 = rectangles.get(i);
            Rectangle rectangle2 = rectangles.get(j);

            int l1 = rectangle1.l; //left
            int r1 = rectangle1.r; //right
            int b1 = rectangle1.b; //bottom
            int t1 = rectangle1.t; //top

            int l2 = rectangle2.l;
            int r2 = rectangle2.r;
            int b2 = rectangle2.b;
            int t2 = rectangle2.t;

            boolean topOnBottom = t2 == b1;
            boolean bottomOnTop = b2 == t1;
            boolean topOrBottomContact = topOnBottom || bottomOnTop;

            boolean rightOnLeft = r2 == l1;
            boolean leftOnRight = l2 == r1;
            boolean rightOrLeftContact = leftOnRight || rightOnLeft;

            boolean leftPoll = l2 <= l1 && r2 >= l1;
            boolean rightPoll = l2 <= r1 && r2 >= r1;
            boolean leftRightInside = l2 >= l1 && r2 <= r1;
            boolean leftRightPossiblePlaces = leftPoll || rightPoll || leftRightInside;

            boolean bottomPoll = t2 >= b1 && b2 <= b1;
            boolean topPoll = b2 <= b1 && t2 >= b1;
            boolean topBottomInside = b2 >= b1 && t2 <= t1;
            boolean topBottomPossiblePlaces = bottomPoll || topPoll || topBottomInside;


            boolean topInBetween = t2 > b1 && t2 < t1;
            boolean bottomInBetween = b2 > b1 && b2 < t1;
            boolean topBottomInBetween = topInBetween || bottomInBetween;

            boolean leftInBetween = l2 > l1 && l2 < r1;
            boolean rightInBetween = r2 > l1 && r2 < r1;
            boolean leftRightInBetween = leftInBetween || rightInBetween;

            if ( (topOrBottomContact && leftRightPossiblePlaces) || (rightOrLeftContact && topBottomPossiblePlaces) ) {
                path[i][j] = true;
            }
        }
    }
}

...

Shrishakti Mishra
sumber