Algoritma untuk mendeteksi persimpangan dua persegi panjang?

143

Saya sedang mencari algoritma untuk mendeteksi jika dua persegi panjang berpotongan (satu pada sudut yang sewenang-wenang, yang lainnya hanya dengan garis vertikal / horizontal).

Menguji apakah sudut salah satunya ada di ALMOST yang lain berfungsi. Gagal jika persegi panjang membentuk bentuk seperti salib.

Sepertinya ide yang bagus untuk menghindari penggunaan kemiringan garis, yang akan membutuhkan kasus khusus untuk garis vertikal.

pengguna20493
sumber
bagaimana jika Anda menambah cek sudut Anda, cek untuk melihat apakah persegi panjang kedua di dalam batas (persegi panjang) dari persegi panjang bersudut?
Wes P
Anda akan menggunakan bahasa apa ini? Karena di Jawa ada kelas bawaan yang memungkinkan Anda melakukan ini.
Martijn
Saya pikir api grafis dan sebagian besar perpustakaan GUI (seperti ayunan) telah diimplementasikan.
l_39217_l
yang dapat melewatkan kasus di mana mereka tumpang tindih tetapi tidak ada sudut di dalam persegi panjang apa pun
Florian Bösch
1
Pertanyaan ini hampir sama dengan: stackoverflow.com/questions/306316/… . Meskipun, ini mencari solusi yang terutama untuk C ++. Jawaban yang diterima juga cukup sederhana dan mudah.
Silver Gonzales

Jawaban:

162

Metode standar akan melakukan tes sumbu pemisah (lakukan pencarian google pada itu).

Pendeknya:

  • Dua objek tidak berpotongan jika Anda dapat menemukan garis yang memisahkan dua objek. misalnya objek / semua titik dari suatu objek berada di sisi garis yang berbeda.

Yang menyenangkan adalah bahwa itu cukup untuk memeriksa semua tepi dari dua persegi panjang. Jika persegi panjang tidak tumpang tindih salah satu ujungnya akan menjadi sumbu pemisah.

Dalam 2D ​​Anda dapat melakukan ini tanpa menggunakan lereng. Tepi secara sederhana didefinisikan sebagai perbedaan antara dua simpul, misalnya

  edge = v(n) - v(n-1)

Anda bisa mendapatkan garis tegak lurus dengan memutar 90 °. Dalam 2D ​​ini semudah:

  rotated.x = -unrotated.y
  rotated.y =  unrotated.x

Jadi tidak ada trigonometri atau lereng yang terlibat. Normalisasi vektor ke satuan panjang juga tidak diperlukan.

Jika Anda ingin menguji apakah suatu titik ada di satu atau sisi lain dari garis tersebut, Anda bisa menggunakan produk titik. tanda akan memberi tahu Anda di sisi mana Anda berada:

  // rotated: your rotated edge
  // v(n-1) any point from the edge.
  // testpoint: the point you want to find out which side it's on.

  side = sign (rotated.x * (testpoint.x - v(n-1).x) + 
               rotated.y * (testpoint.y - v(n-1).y);

Sekarang uji semua titik persegi panjang A terhadap tepi persegi panjang B dan sebaliknya. Jika Anda menemukan tepi pemisah, objek tidak bersinggungan (memberikan semua titik lain dalam B berada di sisi lain tepi yang sedang diuji - lihat gambar di bawah). Jika Anda tidak menemukan tepi pemisah, baik persegi panjang berpotongan atau satu persegi panjang terkandung di dalamnya.

Tes bekerja dengan poligon cembung apa pun ..

Amandemen: Untuk mengidentifikasi tepi yang terpisah, tidak cukup untuk menguji semua titik dari satu persegi panjang terhadap masing-masing tepi yang lain. Tepi kandidat E (di bawah) akan diidentifikasi sebagai tepi pemisah, karena semua titik dalam A berada di setengah bidang yang sama dari E. Namun, itu bukan tepi pemisah karena simpul Vb1 dan Vb2 dari B juga di setengah pesawat itu. Itu hanya akan menjadi ujung pisah jika itu tidak terjadi http://www.iassess.com/collision.png

Nils Pipenbrinck
sumber
2
Algoritma ini tidak berfungsi untuk semua kasus. Dimungkinkan untuk menempatkan persegi panjang kedua diputar 45 derajat ke persegi panjang pertama dan mengimbangi sepanjang diagonal sehingga memenuhi tes persimpangan di atas tetapi tidak berpotongan.
Skizz
6
Mendesis, periksa semua delapan tepi. Jika objek tidak memotong salah satu dari delapan tepi akan memisahkannya. Mengapa Anda tidak memposting gambar yang menunjukkan kasus Anda? Saya bisa menunjukkan porosnya ..
Nils Pipenbrinck
2
Kesalahan saya, itu mengatasi kondisi itu.
Skizz
2
Gambar sudah mati sekarang (November 2012)
John Dvorak
2
Saya memiliki banyak masalah dalam memvisualisasikan hal ini sehingga saya menciptakan kembali seperti apa rupa gambar yang direferensikan. imgur.com/bNwrzsv
Rjdlee
16

Pada dasarnya lihat gambar berikut:


Jika kedua kotak bertabrakan, garis A dan B akan tumpang tindih.

Perhatikan bahwa ini harus dilakukan pada kedua sumbu X dan Y, dan keduanya perlu tumpang tindih untuk persegi panjang bertabrakan.

Ada artikel bagus di gamasutra.com yang menjawab pertanyaan (gambarnya dari artikel). Saya melakukan algoritma yang sama 5 tahun yang lalu dan saya harus menemukan cuplikan kode saya untuk mempostingnya di sini nanti

Amandemen : Teorema Sumbu Pemisah menyatakan bahwa dua bentuk cembung tidak tumpang tindih jika ada sumbu pemisah (yaitu satu di mana proyeksi seperti yang ditunjukkan tidak tumpang tindih). Jadi "Ada sumbu pemisah" => "Tidak ada tumpang tindih". Ini bukan implikasi ganda sehingga Anda tidak bisa menyimpulkan yang sebaliknya.

m_pGladiator
sumber
1
Jelas, karena dua kotak (0,0,1,1) dan (0,3,1,4) tidak tumpang tindih tetapi proyeksi mereka pada sumbu x sepenuhnya tumpang tindih. Kedua tes itu diperlukan, kombinasinya cukup.
MSalters
18
Proyeksi x dan y tidak cukup untuk tumpang tindih: ambil mis. Persegi panjang [(0,0), (0,3), (3,3), (3,0)] dan [(2,5), (5,2), (7,4), (4,7)].
Joel di Go
4
Saya setuju dengan @ Joel di Gö. Metode ini merindukan satu set besar kasus di mana persegi panjang tidak tumpang tindih, namun jari-jari mereka diproyeksikan lakukan di kedua x dan y.
Scottie T
5
Jawaban ini tidak salah, tetapi menyesatkan. Memang benar bahwa: Jika kedua kotak bertabrakan, garis A dan B akan tumpang tindih. tetapi juga benar bahwa: Jika garis A dan B tumpang tindih, kedua kotak itu mungkin atau mungkin tidak bertabrakan
matt burns
7
@ floater: Saya akan mengatakan itu tidak hanya salah, tetapi juga menyesatkan, yang bahkan lebih buruk.
BlueRaja - Danny Pflughoeft
4

Jawaban m_pGladiator benar dan saya lebih suka. Tes sumbu terpisah adalah metode paling sederhana dan standar untuk mendeteksi tumpang tindih persegi panjang. Garis yang interval proyeksinya tidak tumpang tindih, kami sebut sumbu pemisah . Solusi Nils Pipenbrinck terlalu umum. Ini menggunakan produk titik untuk memeriksa apakah satu bentuk benar-benar di satu sisi tepi yang lain. Solusi ini sebenarnya bisa menyebabkan n-edge cembung poligon. Namun, tidak di optmized untuk dua persegi panjang.

titik kritis dari jawaban m_pGladiator adalah bahwa kita harus memeriksa proyeksi dua persegi panjang pada kedua sumbu (x dan y). Jika dua proyeksi tumpang tindih, maka kita bisa mengatakan dua persegi panjang ini tumpang tindih. Jadi komentar di atas untuk jawaban m_pGladiator salah.

untuk situasi sederhana, jika dua persegi panjang tidak diputar, kami menyajikan sebuah persegi panjang dengan struktur:

struct Rect {
    x, // the center in x axis
    y, // the center in y axis
    width,
    height
}

kita beri nama rectangle A, B dengan rectA, rectB.

    if Math.abs(rectA.x - rectB.x) < (Math.abs(rectA.width + rectB.width) / 2) 
&& (Math.abs(rectA.y - rectB.y) < (Math.abs(rectA.height + rectB.height) / 2))
    then
        // A and B collide
    end if

jika salah satu dari dua persegi panjang diputar, mungkin perlu beberapa upaya untuk menentukan proyeksi mereka pada sumbu x dan y. Tetapkan struct RotatedRect sebagai berikut:

struct RotatedRect : Rect {
    double angle; // the rotating angle oriented to its center
}

perbedaannya adalah bagaimana lebar 'sekarang sedikit berbeda: widthA' untuk rectA: Math.sqrt(rectA.width*rectA.width + rectA.height*rectA.height) * Math.cos(rectA.angle) widthB 'untuk rectB:Math.sqrt(rectB.width*rectB.width + rectB.height*rectB.height) * Math.cos(rectB.angle)

    if Math.abs(rectA.x - rectB.x) < (Math.abs(widthA' + widthB') / 2) 
&& (Math.abs(rectA.y - rectB.y) < (Math.abs(heightA' + heightB') / 2))
    then
        // A and B collide
    end if

Dapat merujuk ke PPT GDC (Game Development Conference 2007) www.realtimecollisiondetection.net/pubs/GDC07_Ericson_Physics_Tutorial_SAT.ppt

tristan
sumber
Mengapa Anda memerlukan Math.abs () di "Math.abs (rectA.width + rectB.width)", untuk menangani lebar negatif?
AlexWien
Sumbu pemisah belum tentu arah kompas, dapat memiliki sudut apa pun.
Ben Voigt
Rectangles non-rotating rectA (x = 0, y = 0, lebar = 1, tinggi = 1) dan rectB (x = 2, y = 0, lebar = 100, tinggi = 1) tidak berpotongan tetapi metode Anda mengatakan mereka memotong. Apakah saya melakukan sesuatu yang salah?
Kagami Sascha Rosylight
4

Di Cocoa, Anda dapat dengan mudah mendeteksi apakah rectangular terpilih dipilih memotong frame NSView Anda diputar. Anda bahkan tidak perlu menghitung poligon, normal seperti itu. Cukup tambahkan metode ini ke subclass NSView Anda. Misalnya, pengguna memilih area pada superview NSView, lalu Anda memanggil metode DoesThisRectSelectMe dengan meneruskan rectArea terpilih. API convertRect: akan melakukan pekerjaan itu. Trik yang sama berfungsi ketika Anda mengklik NSView untuk memilihnya. Dalam hal ini cukup timpa metode hitTest seperti di bawah ini. API convertPoint: akan melakukan pekerjaan itu ;-)

- (BOOL)DoesThisRectSelectMe:(NSRect)selectedArea
{
    NSRect localArea = [self convertRect:selectedArea fromView:self.superview];

    return NSIntersectsRect(localArea, self.bounds);
}


- (NSView *)hitTest:(NSPoint)aPoint
{
    NSPoint localPoint = [self convertPoint:aPoint fromView:self.superview];
    return NSPointInRect(localPoint, self.bounds) ? self : nil;
}
Leonardo
sumber
2
Kode itu hanya berfungsi untuk persegi panjang yang persegi ke layar. Itu kasus sepele. Asumsinya adalah bahwa kita berhadapan dengan persegi panjang yang tidak pada sudut 90 derajat ke layar atau satu sama lain.
Duncan C
Seperti yang telah saya periksa dan gunakan dalam aplikasi saya, kode itu berfungsi pada sembarang persegi yang diputar. Tidak masalah derajat rotasi.
Leonardo
Ini tidak menggambarkan algoritme, namun, hanya menyebutkan pustaka yang sudah menggunakannya.
Ben Voigt
2

Periksa untuk melihat apakah salah satu garis dari satu persegi panjang memotong salah satu garis dari yang lain. Persimpangan segmen garis naif mudah untuk kode.

Jika Anda membutuhkan kecepatan lebih, ada algoritme canggih untuk persimpangan segmen garis (garis-sapu). Lihat http://en.wikipedia.org/wiki/Line_segment_intersection

Louis Brandy
sumber
4
Cermat! Jangan lupa kasus di mana satu persegi panjang benar-benar menutupi yang lain
Pitarou
2

Salah satu solusinya adalah menggunakan sesuatu yang disebut No Fit Polygon. Poligon ini dihitung dari dua poligon (secara konseptual dengan menggeser satu di sekitar yang lain) dan menentukan area yang tumpang tindih poligon dengan offset relatifnya. Setelah Anda memiliki NFP ini maka Anda hanya perlu melakukan tes inklusi dengan titik yang diberikan oleh offset relatif dari dua poligon. Tes inklusi ini cepat dan mudah tetapi Anda harus membuat NFP terlebih dahulu.

Lakukan pencarian untuk No Fit Polygon di web dan lihat apakah Anda dapat menemukan algoritme untuk cembung poligon (itu akan JAUH lebih kompleks jika Anda memiliki poligon cekung). Jika Anda tidak dapat menemukan apa pun maka email saya di howard dot J dot dapat gmail dot com

Howard May
sumber
1

Inilah yang saya pikir akan menangani semua kasus yang mungkin. Lakukan tes berikut.

  1. Periksa salah satu simpul persegi panjang 1 yang berada di dalam persegi panjang 2 dan sebaliknya. Setiap kali Anda menemukan titik yang berada di dalam persegi panjang lain, Anda dapat menyimpulkan bahwa mereka berpotongan dan menghentikan pencarian. Ini akan mengurus satu persegi panjang yang sepenuhnya berada di dalam yang lain.
  2. Jika tes di atas tidak dapat disimpulkan, temukan titik perpotongan dari setiap baris dari 1 persegi panjang dengan setiap baris dari persegi panjang lainnya. Setelah titik persimpangan ditemukan periksa apakah itu berada di antara di dalam persegi panjang imajiner yang dibuat oleh 4 poin yang sesuai. Ketika titik tersebut ditemukan, simpulkan bahwa mereka berpotongan dan menghentikan pencarian.

Jika 2 tes di atas mengembalikan false maka 2 persegi panjang ini tidak tumpang tindih.

John Smith
sumber
0

Jika Anda menggunakan Java, semua implementasi antarmuka Shape memiliki metode intersect yang mengambil persegi panjang.

Brendan Cashman
sumber
Sayangnya saya menggunakan C #. Kelas Rectangle memiliki metode Contains (), tetapi hanya untuk persegi yang tidak diputar.
user20493
Metode intersect () cukup berguna karena mengembalikan boolean bukan persimpangan saya kira.
ZZ 5
0

Nah, metode brute force adalah berjalan di tepi persegi panjang horizontal dan memeriksa setiap titik di sepanjang tepi untuk melihat apakah jatuh di atau di persegi panjang lainnya.

Jawaban matematis adalah untuk membentuk persamaan yang menggambarkan setiap tepi dari kedua persegi panjang. Sekarang Anda dapat dengan mudah menemukan jika salah satu dari empat garis dari persegi panjang A memotong salah satu garis persegi panjang B, yang seharusnya menjadi pemecah persamaan linier sederhana (cepat).

-Adam

Adam Davis
sumber
2
Masalah dengan persamaan adalah ketika Anda memiliki garis vertikal, yang memiliki kemiringan tak terbatas.
user20493
Ada kasus sudut untuk setiap solusi.
Adam Davis
2
dan satu kotak sepenuhnya menutup yang lain.
Oliver Hallam
0

Anda bisa menemukan persimpangan masing-masing sisi persegi panjang bersudut dengan masing-masing sisi sumbu-sejajar. Lakukan ini dengan menemukan persamaan garis tak terbatas di mana masing-masing sisi terletak (yaitu v1 + t (v2-v1) dan v'1 + t '(v'2-v'1) pada dasarnya), menemukan titik di mana garis bertemu dengan memecahkan untuk t ketika kedua persamaan itu sama (jika mereka paralel, Anda dapat menguji untuk itu) dan kemudian menguji apakah titik itu terletak pada segmen garis antara dua simpul, yaitu apakah benar bahwa 0 <= t <= 1 dan 0 <= t '<= 1.

Namun, ini tidak mencakup kasus ketika satu persegi panjang sepenuhnya menutupi yang lain. Itu bisa Anda tutupi dengan menguji apakah keempat titik persegi panjang berada di dalam persegi panjang lainnya.

HenryR
sumber
0

Inilah yang akan saya lakukan, untuk versi 3D dari masalah ini:

Modelkan 2 persegi panjang sebagai bidang yang dijelaskan oleh persamaan P1 dan P2, kemudian tulis P1 = P2 dan turun dari garis persamaan persimpangan, yang tidak akan ada jika bidangnya paralel (tidak ada persimpangan), atau berada di bidang yang sama, dalam hal ini Anda mendapatkan 0 = 0. Dalam hal ini Anda perlu menggunakan algoritma persimpangan persegi panjang 2D.

Lalu saya akan melihat apakah garis itu, yang ada di bidang kedua persegi panjang, melewati kedua persegi panjang. Jika ya, maka Anda memiliki persimpangan 2 persegi panjang, jika tidak Anda tidak (atau seharusnya tidak, saya mungkin telah melewatkan kotak sudut di kepalaku).

Untuk menemukan jika garis melewati persegi panjang di bidang yang sama, saya akan menemukan 2 titik persimpangan garis dan sisi-sisi persegi panjang (memodelkannya menggunakan persamaan garis), dan kemudian memastikan titik-titik persimpangan dengan di jarak.

Itulah uraian matematisnya, sayangnya saya tidak punya kode untuk melakukan hal di atas.

ruang bebas
sumber
Anda melewatkan bagian di mana jika Anda menemukan garis berpotongan planar, Anda harus memastikan bahwa ada sebagian di dalam kedua persegi panjang.
Lee Louviere
0

Cara lain untuk melakukan tes yang sedikit lebih cepat daripada menggunakan tes sumbu pemisah, adalah dengan menggunakan algoritma bilangan berkelok-kelok (hanya pada kuadran - bukan penjumlahan sudut yang sangat lambat) pada setiap simpul dari persegi panjang mana pun (dipilih secara sewenang-wenang). Jika salah satu dari simpul memiliki nomor belitan non-nol, kedua persegi panjang tumpang tindih.

Algoritme ini agak lebih panjang daripada tes sumbu pemisah, tetapi lebih cepat karena hanya membutuhkan uji setengah-pesawat jika ujung-ujungnya melintasi dua kuadran (dibandingkan dengan hingga 32 tes menggunakan metode sumbu pemisah)

Algoritma ini memiliki keunggulan lebih lanjut yang dapat digunakan untuk menguji tumpang tindih dari setiap poligon (cembung atau cekung). Sejauh yang saya tahu, algoritma hanya bekerja di ruang 2D.

Nyonya
sumber
3
Saya mungkin salah, tetapi bukankah itu hanya memeriksa apakah simpul dari satu persegi panjang berada di dalam yang lain? Jika ya, itu tidak cukup karena persegi panjang mungkin tumpang tindih tanpa simpul di dalamnya.
sinelaw
Bisakah mereka, dengan persegi panjang? Bagaimana? Tampak bagi saya bahwa agar 2 persegi panjang untuk berpotongan, setidaknya satu simpul dari salah satu persegi panjang harus terletak pada persegi panjang lainnya.
Duncan C
@DuncanC: Ya, mereka bisa. Contoh tandingan adalah tanda silang, dan bahkan dicantumkan dalam pertanyaan awal.
Ben Voigt
@ BenVoigt Ini adalah utas yang sangat lama, tetapi Anda benar sekali.
Duncan C
0

Entah saya kehilangan sesuatu yang lain mengapa membuatnya begitu rumit?

jika (x1, y1) dan (X1, Y1) adalah sudut-sudut persegi panjang, maka untuk menemukan persimpangan lakukan:

    xIntersect = false;
    yIntersect = false;
    if (!(Math.min(x1, x2, x3, x4) > Math.max(X1, X2, X3, X4) || Math.max(x1, x2, x3, x4) < Math.min(X1, X2, X3, X4))) xIntersect = true;
    if (!(Math.min(y1, y2, y3, y4) > Math.max(Y1, Y2, Y3, Y4) || Math.max(y1, y2, y3, y4) < Math.min(Y1, Y2, Y3, Y4))) yIntersect = true;
    if (xIntersect && yIntersect) {alert("Intersect");}
pengguna1517108
sumber
3
Anda kehilangan bahwa dia ingin satu diputar oleh sudut yang sewenang-wenang.
Robotbugs
0

Saya menerapkannya seperti ini:

bool rectCollision(const CGRect &boundsA, const Matrix3x3 &mB, const CGRect &boundsB)
{
    float Axmin = boundsA.origin.x;
    float Axmax = Axmin + boundsA.size.width;
    float Aymin = boundsA.origin.y;
    float Aymax = Aymin + boundsA.size.height;

    float Bxmin = boundsB.origin.x;
    float Bxmax = Bxmin + boundsB.size.width;
    float Bymin = boundsB.origin.y;
    float Bymax = Bymin + boundsB.size.height;

    // find location of B corners in A space
    float B0x = mB(0,0) * Bxmin + mB(0,1) * Bymin + mB(0,2);
    float B0y = mB(1,0) * Bxmin + mB(1,1) * Bymin + mB(1,2);

    float B1x = mB(0,0) * Bxmax + mB(0,1) * Bymin + mB(0,2);
    float B1y = mB(1,0) * Bxmax + mB(1,1) * Bymin + mB(1,2);

    float B2x = mB(0,0) * Bxmin + mB(0,1) * Bymax + mB(0,2);
    float B2y = mB(1,0) * Bxmin + mB(1,1) * Bymax + mB(1,2);

    float B3x = mB(0,0) * Bxmax + mB(0,1) * Bymax + mB(0,2);
    float B3y = mB(1,0) * Bxmax + mB(1,1) * Bymax + mB(1,2);

    if(B0x<Axmin && B1x<Axmin && B2x<Axmin && B3x<Axmin)
        return false;
    if(B0x>Axmax && B1x>Axmax && B2x>Axmax && B3x>Axmax)
        return false;
    if(B0y<Aymin && B1y<Aymin && B2y<Aymin && B3y<Aymin)
        return false;
    if(B0y>Aymax && B1y>Aymax && B2y>Aymax && B3y>Aymax)
        return false;

    float det = mB(0,0)*mB(1,1) - mB(0,1)*mB(1,0);
    float dx = mB(1,2)*mB(0,1) - mB(0,2)*mB(1,1);
    float dy = mB(0,2)*mB(1,0) - mB(1,2)*mB(0,0);

    // find location of A corners in B space
    float A0x = (mB(1,1) * Axmin - mB(0,1) * Aymin + dx)/det;
    float A0y = (-mB(1,0) * Axmin + mB(0,0) * Aymin + dy)/det;

    float A1x = (mB(1,1) * Axmax - mB(0,1) * Aymin + dx)/det;
    float A1y = (-mB(1,0) * Axmax + mB(0,0) * Aymin + dy)/det;

    float A2x = (mB(1,1) * Axmin - mB(0,1) * Aymax + dx)/det;
    float A2y = (-mB(1,0) * Axmin + mB(0,0) * Aymax + dy)/det;

    float A3x = (mB(1,1) * Axmax - mB(0,1) * Aymax + dx)/det;
    float A3y = (-mB(1,0) * Axmax + mB(0,0) * Aymax + dy)/det;

    if(A0x<Bxmin && A1x<Bxmin && A2x<Bxmin && A3x<Bxmin)
        return false;
    if(A0x>Bxmax && A1x>Bxmax && A2x>Bxmax && A3x>Bxmax)
        return false;
    if(A0y<Bymin && A1y<Bymin && A2y<Bymin && A3y<Bymin)
        return false;
    if(A0y>Bymax && A1y>Bymax && A2y>Bymax && A3y>Bymax)
        return false;

    return true;
}

Matriks mB adalah matriks transformasi affine yang mengkonversi titik dalam ruang B menjadi titik dalam ruang A. Ini termasuk rotasi dan terjemahan sederhana, rotasi plus penskalaan, dan warps affine penuh, tetapi bukan warp perspektif.

Ini mungkin tidak seoptimal mungkin. Kecepatan bukan masalah besar. Namun sepertinya itu berfungsi baik untuk saya.

Robotbugs
sumber
0

Berikut ini adalah implementasi matlab dari jawaban yang diterima:

function olap_flag = ol(A,B,sub)

%A and B should be 4 x 2 matrices containing the xy coordinates of the corners in clockwise order

if nargin == 2
  olap_flag = ol(A,B,1) && ol(B,A,1);
  return;
end

urdl = diff(A([1:4 1],:));
s = sum(urdl .* A, 2);
sdiff = B * urdl' - repmat(s,[1 4]);

olap_flag = ~any(max(sdiff)<0);
Jed
sumber
0

Ini adalah metode konvensional, pergi baris demi baris dan periksa apakah garis berpotongan. Ini adalah kode di MATLAB.

C1 = [0, 0];    % Centre of rectangle 1 (x,y)
C2 = [1, 1];    % Centre of rectangle 2 (x,y)
W1 = 5; W2 = 3; % Widths of rectangles 1 and 2
H1 = 2; H2 = 3; % Heights of rectangles 1 and 2
% Define the corner points of the rectangles using the above
R1 = [C1(1) + [W1; W1; -W1; -W1]/2, C1(2) + [H1; -H1; -H1; H1]/2];
R2 = [C2(1) + [W2; W2; -W2; -W2]/2, C2(2) + [H2; -H2; -H2; H2]/2];

R1 = [R1 ; R1(1,:)] ;
R2 = [R2 ; R2(1,:)] ;

plot(R1(:,1),R1(:,2),'r')
hold on
plot(R2(:,1),R2(:,2),'b')


%% lines of Rectangles 
L1 = [R1(1:end-1,:) R1(2:end,:)] ;
L2 = [R2(1:end-1,:) R2(2:end,:)] ;
%% GEt intersection points
P = zeros(2,[]) ;
count = 0 ;
for i = 1:4
    line1 = reshape(L1(i,:),2,2) ;
    for j = 1:4
        line2 = reshape(L2(j,:),2,2) ;
        point = InterX(line1,line2) ;
        if ~isempty(point)
            count = count+1 ;
            P(:,count) = point ;
        end
    end
end
%%
if ~isempty(P)
    fprintf('Given rectangles intersect at %d points:\n',size(P,2))
    plot(P(1,:),P(2,:),'*k')
end

fungsi InterX dapat diunduh dari: https://in.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections?focused=5165138&tab=function

Siva Srinivas Kolukula
sumber
0

Saya memiliki metode sederhana sendiri, jika kami memiliki 2 persegi panjang:

R1 = (min_x1, max_x1, min_y1, max_y1)

R2 = (min_x2, max_x2, min_y2, max_y2)

Mereka tumpang tindih jika dan hanya jika:

Tumpang tindih = (max_x1> min_x2) dan (max_x2> min_x1) dan (max_y1> min_y2) dan (max_y2> min_y1)

Anda dapat melakukannya untuk kotak 3D juga, sebenarnya berfungsi untuk sejumlah dimensi.

BitFarmer
sumber
0

Cukup sudah dikatakan dalam jawaban lain, jadi saya hanya akan menambahkan pseudocode one-liner:

!(a.left > b.right || b.left > a.right || a.top > b.bottom || b.top > a.bottom);
Przemek
sumber