Apa cara tercepat untuk mengetahui persimpangan kotak pembatas 2D?

62

Asumsikan bahwa setiap objek Box memiliki properti x, y, lebar, tinggi dan memiliki asal mereka di pusatnya, dan bahwa baik objek maupun kotak yang terikat berputar.

Iain
sumber
Apakah kotak-kotak ini sejajar dengan sumbu atau objek?
Tenpn
3
Saat Anda mengajukan pertanyaan ini, Anda pasti perlu menguji jenis persimpangan lainnya di masa depan;). Oleh karena itu saya menyarankan THE LIST tentang Object / Object intersection. Tabel ini menyediakan persimpangan antara semua jenis objek populer (kotak, bola, segitiga, putaran, kerucut, ...) dalam situasi statis maupun dinamis.
Dave O.
2
Harap ulangi pertanyaan Anda ke rect yang membatasi. Dari sudut pandang saya kotak menyiratkan objek 3d.
Dave O.

Jawaban:

55

(C-ish pseudocode - adaptasi optimasi bahasa yang sesuai)

bool DoBoxesIntersect(Box a, Box b) {
  return (abs(a.x - b.x) * 2 < (a.width + b.width)) &&
         (abs(a.y - b.y) * 2 < (a.height + b.height));
}

Dalam bahasa Inggris: Pada setiap sumbu, periksa untuk melihat apakah bagian tengah kotak cukup dekat sehingga mereka akan berpotongan. Jika mereka berpotongan di kedua sumbu, maka kotak-kotak berpotongan. Jika tidak, maka tidak.

Anda dapat mengubah <'s menjadi <= jika Anda ingin menghitung edge-touching sebagai berpotongan. Jika Anda menginginkan formula khusus tepi-sentuh saja, Anda tidak dapat menggunakan == - yang akan memberi tahu Anda jika sudut-sudutnya menyentuh, bukan jika ujung-ujungnya bersentuhan. Anda ingin melakukan sesuatu yang setara secara logis return DoBoxesIntersectOrTouch(a, b) && !DoBoxesIntersect(a, b).

Perlu disebutkan bahwa Anda bisa mendapatkan peningkatan kecepatan kecil tapi signifikan dengan menyimpan setengah lebar dan setengah tinggi di samping (atau bukannya) lebar penuh dan tinggi penuh. Di sisi lain, jarang terjadi persimpangan kotak 2d untuk menjadi hambatan kinerja.

ZorbaTHut
sumber
9
Ini jelas mengasumsikan kotak-kotaknya sejajar sumbu.
Tenpn
1
Abs seharusnya tidak terlalu lambat - setidaknya lebih lambat dari kondisi, setidaknya, dan satu-satunya cara untuk melakukannya tanpa abs (yang saya sadari) melibatkan persyaratan tambahan.
ZorbaTHut
4
Ya, itu memang mengasumsikan kotak sejajar sumbu. Struktur seperti yang dijelaskan tidak memiliki cara untuk menunjukkan rotasi, jadi saya merasa aman.
ZorbaTHut
3
Berikut adalah beberapa tips yang baik untuk mempercepat perhitungan dalam Actionscript (terutama bilangan bulat bilangan bulat): lab.polygonal.de/2007/05/10/bitwise-gems-fast-integer-math Saya memposting ini, karena juga berisi yang lebih cepat pengganti untuk Math.abs (), yang cenderung memperlambat hal-hal di Actionscript memang (berbicara tentang hal-hal penting kinerja tentu saja).
bummzack
2
Anda kehilangan bahwa mereka memiliki asal di tengah, bukan di tepi kiri. Kotak yang beroperasi dari 0 hingga 10 sebenarnya memiliki "x = 5", sementara kotak yang beroperasi dari 8 hingga 12 akan memiliki "x = 10". Anda berakhir dengan abs(5 - 10) * 2 < (10 + 4)=> 10 < 14. Anda harus melakukan beberapa penyesuaian sederhana agar dapat berfungsi dengan topleft-corner-and-size.
ZorbaTHut
37

Ini berfungsi untuk dua persegi panjang yang disejajarkan dengan sumbu X dan Y.
Setiap persegi panjang memiliki sifat:
"kiri", koordinat x sisi kirinya,
"atas", koordinat y sisi atas,
"kanan", koordinat x sisi kanannya,
"bawah", koordinat y dari sisi bawahnya,

function IntersectRect(r1:Rectangle, r2:Rectangle):Boolean {
    return !(r2.left > r1.right
        || r2.right < r1.left
        || r2.top > r1.bottom
        || r2.bottom < r1.top);
}

Perhatikan bahwa ini dirancang untuk sistem koordinat di mana sumbu + y mengarah ke bawah dan sumbu + x diarahkan ke kanan (yaitu koordinat layar / piksel tipikal). Untuk menyesuaikan ini dengan sistem kartesius khas di mana + y diarahkan ke atas, perbandingan di sepanjang sumbu vertikal akan dibalik, misalnya:

return !(r2.left > r1.right
    || r2.right < r1.left
    || r2.top < r1.bottom
    || r2.bottom > r1.top);

Idenya adalah untuk menangkap semua kondisi yang mungkin yang di atasnya persegi panjang akan tidak tumpang tindih, dan kemudian meniadakan jawabannya untuk melihat apakah mereka yang tumpang tindih. Terlepas dari arah sumbu, mudah untuk melihat bahwa dua persegi panjang tidak akan tumpang tindih jika:

  • tepi kiri r2 lebih jauh dari kanan r1

     ________     ________
    |        |   |        |
    |   r1   |   |   r2   |
    |        |   |        |
    |________|   |________|
    
  • atau tepi kanan r2 lebih jauh ke kiri dari tepi kiri r1

     ________     ________
    |        |   |        |
    |   r2   |   |   r1   |
    |        |   |        |
    |________|   |________|
    
  • atau tepi atas r2 berada di bawah tepi bawah r1

     ________ 
    |        |
    |   r1   |
    |        |
    |________|
     ________ 
    |        |
    |   r2   |
    |        |
    |________|
    
  • atau tepi bawah r2 berada di atas tepi atas r1

     ________ 
    |        |
    |   r2   |
    |        |
    |________|
     ________ 
    |        |
    |   r1   |
    |        |
    |________|
    

Fungsi asli - dan deskripsi alternatif mengapa itu bekerja - dapat ditemukan di sini: http://tekpool.wordpress.com/2006/10/11/rectangle-intersection-determine-if-two-given-rectangles-intersect- satu sama lain-atau-tidak /

Ponkadoodle
sumber
1
Anehnya intuitif dan sekali lagi menunjukkan bahwa ketika menemukan jawaban itu terlalu sulit, mencoba menemukan jawaban untuk pertanyaan yang berlawanan dapat membantu Anda. Terima kasih!
Lodewijk
1
Anda harus menyebutkan bahwa sumbu y mengarah ke bawah (seperti pada gambar). Kalau tidak, ketidaksetaraan r2.top> r1.bottom dan r2.bottom <r1.top perlu dibalik.
user1443778
@ user1443778 tangkapan bagus! Saya melanjutkan dan dengan longgar menjelaskan logika di balik algoritma ini dengan cara sistem-agnostik yang terkoordinasi juga.
Ponkadoodle
11

Jika Anda ingin kotak pembatas objek-lurus, coba tutorial ini pada teorema sumbu pemisahan dengan metanet: http://www.metanetsoftware.com/technique/tutorialA.html

SAT bukan solusi tercepat, tetapi relatif sederhana. Anda mencoba menemukan satu baris (atau pesawat jika 3D) yang akan memisahkan objek Anda. Jika garis ini ada, dijamin harus paralell ke tepi salah satu kotak Anda, sehingga Anda mengulangi semua pengujian tepi untuk melihat apakah itu memisahkan kotak.

Ini juga berfungsi untuk kotak yang disejajarkan dengan membatasi hanya sumbu x / y.

tenpn
sumber
Saya tidak memikirkan rotasi, tetapi terima kasih itu tautan yang menarik.
Iain
5

DoBoxesIntersect di atas adalah solusi berpasangan yang baik. Namun, jika Anda memiliki banyak kotak, Anda masih memiliki masalah O (N ^ 2), dan Anda mungkin perlu melakukan sesuatu di atas itu seperti apa yang dimaksud Kaj. (Dalam literatur pendeteksian tabrakan 3D, ini dikenal memiliki algoritma fase-lebar dan fase-sempit. Kami akan melakukan sesuatu yang sangat cepat untuk menemukan semua pasangan yang mungkin tumpang tindih, dan kemudian sesuatu yang lebih mahal untuk melihat apakah kami mungkin pasangan adalah pasangan yang sebenarnya.)

Algoritme fase luas yang saya gunakan sebelumnya adalah "sweep-and-prune"; untuk 2D, Anda akan mempertahankan dua daftar awal dan akhir setiap kotak yang diurutkan. Selama pergerakan kotak bukan >> skala kotak dari bingkai ke bingkai, urutan daftar ini tidak akan banyak berubah, sehingga Anda dapat menggunakan gelembung atau jenis penyisipan untuk mempertahankannya. Buku "Real-Time Rendering" memiliki tulisan bagus tentang optimisasi yang dapat Anda lakukan, tetapi bermuara pada waktu O (N + K) dalam fase luas, untuk N kotak, K yang tumpang tindih, dan dengan dunia nyata yang sangat baik kinerja jika Anda mampu membeli boolean untuk melacak pasangan kotak mana yang berpotongan dari bingkai ke bingkai. Anda kemudian memiliki keseluruhan waktu O (N + K ^ 2), yaitu << O (N ^ 2) jika Anda memiliki banyak kotak tetapi hanya beberapa tumpang tindih.

Tom Hudson
sumber
5

Banyak matematika di sini untuk masalah yang sangat sederhana, asumsikan bahwa kita memiliki 4 poin yang ditentukan untuk kotak, atas, kiri, bawah, kanan ...

Dalam hal menentukan apakah 2 rect bertabrakan, kita hanya perlu melihat bahwa semua kemungkinan ekstrem yang akan mencegah tabrakan, jika tidak ada yang terpenuhi, maka 2 rect HARUS bertabrakan, jika Anda ingin memasukkan tumbukan batas, cukup ganti> dan < dengan tepat> = dan = <.

struct aRect{
  float top;
  float left;
  float bottom;
  float right;
};

bool rectCollision(rect a, rect b)
{
  return ! ( b.left > a.right || b.right < a.left || b.top < a.bottom || b.bottom > a.top);
}
user35189
sumber
Jujur saya tidak yakin mengapa ini bukan jawaban terpilih. Sederhana, benar, dan efisien.
3Dave
3

Versi alternatif dari jawaban ZorbaTHut:

bool DoBoxesIntersect(Box a, Box b) {
     return (abs(a.x - b.x) < (a.width + b.width) / 2) &&
     (abs(a.y - b.y) < (a.height + b.height) / 2);
}
Iain
sumber
Sebenarnya aritmatika itu berfungsi dengan baik. Anda dapat melakukan operasi aritmatika ke kedua sisi <dan itu tidak mengubahnya (perkalian dengan negatif berarti Anda harus mengubah kurang dari, meskipun). Dalam contoh itu, kotak-kotak itu seharusnya tidak bertabrakan. Jika pusat kotak A adalah di 1, itu membentang dari -4 ke 6. Kotak b pusat di 10, dan membentang 7,5 hingga 12,5, tidak ada tabrakan di sana ... Sekarang, metode yang diposting Wallacoloo tidak hanya benar, tetapi akan berjalan lebih cepat pada bahasa yang menerapkan korsleting, karena sebagian besar cek akan kembali salah, korsleting dapat terputus setelahnya
Deleter
Ya saya menyadari ini ketika saya bangun pagi ini. Chris membujuk saya dengan <> campurannya.
Iain
1
Dua masalah: pertama, pembagian cenderung jauh lebih lambat daripada perkalian. Kedua, jika nilai-nilai yang terlibat adalah bilangan bulat, ini mungkin mengakibatkan beberapa masalah pemotongan bilangan bulat (kapak = 0, bx = 9, a.width = 9, b.width = 10: abs (0-9) <(9 + 10) / 2, 9 <19/2, 9 <9, fungsi mengembalikan false terlepas dari kenyataan bahwa kotak-kotak secara pasti berpotongan.)
ZorbaTHut
2

Tergantung pada masalah yang Anda coba selesaikan, Anda mungkin lebih baik melacak objek Anda saat Anda memindahkannya, yaitu, menyimpan daftar posisi x mulai dan berakhir dan satu untuk posisi awal dan akhir. Jika Anda harus melakukan BANYAK pemeriksaan yang tumpang tindih dan oleh karena itu perlu mengoptimalkan, Anda dapat menggunakan ini untuk keuntungan Anda, karena Anda dapat segera mencari siapa yang berakhir menutup di sebelah kiri Anda, semua orang yang berakhir di sebelah kiri yang dapat dipangkas segera. Sama berlaku untuk atas, bawah dan kanan.
Pembukuan tentu saja menghabiskan waktu, jadi lebih cocok untuk situasi dengan beberapa objek bergerak tetapi banyak cek yang tumpang tindih.
Pilihan lain adalah spasial hashing, di mana Anda menimbun objek berdasarkan perkiraan posisi (ukuran mungkin menempatkan mereka dalam beberapa ember), tetapi ada lagi, hanya jika ada banyak objek, dengan relatif sedikit dari mereka bergerak per iterasi karena biaya pembukuan.
Pada dasarnya segala sesuatu yang menghindari (n * n) / 2 (jika Anda memeriksa objek a terhadap b, Anda tidak perlu memeriksa b terhadap a) jelas membantu lebih dari mengoptimalkan kotak pembatas. Jika cek kotak terikat adalah hambatan, saya serius menyarankan untuk mencari solusi alternatif untuk masalah ini.

Kaj
sumber
2

Jarak antara pusat tidak sama dengan jarak antara sudut (ketika satu kotak berada di dalam yang lain misalnya), jadi DALAM UMUM, solusi ini adalah yang benar (saya pikir).

jarak antara pusat (untuk, katakanlah, x): abs(x1+1/2*w1 - x2+1/2*w2)atau1/2 * abs(2*(x1-x2)+(w1-w2)

Jarak minimum adalah 1/2 w1 + 1/2 w2 or 1/2 (w1+w2). setengahnya membatalkan begitu ..

return 
ABS(2*(x1 - x2) + (w1-w2) ) < (w1+w2)) &&
ABS(2*(y1 - y2) + (h1-h2) ) < (h1+h2));
Vladimir Dizhoor
sumber
1
Ada apa dengan pernyataan "kembali" di sana?
doppelgreener
1

Inilah implementasi saya di Jawa dengan asumsi arsitektur dua-pelengkap . Jika Anda tidak menggunakan dua-pelengkap, gunakan panggilan fungsi Math.abs standar sebagai gantinya:

boolean intersects(IntAxisAlignedBox left, IntAxisAlignedBox right) {
    return
        (
            lineDeltaFactor(left.min.x, left.max.x, right.min.x, right.max.x) |
            lineDeltaFactor(left.min.y, left.max.y, right.min.y, right.max.y) |
            lineDeltaFactor(left.min.z, left.max.z, right.min.z, right.max.z)
        ) == 0;
}

int lineDeltaFactor(int leftMin, int leftMax, int rightMin, int rightMax) {
    final int
            leftWidth = leftMax - leftMin,
            rightWidth = rightMax - rightMin,

            leftMid = leftMin + ((leftMax - leftMin) >> 1),
            rightMid = rightMin + ((rightMax - rightMin) >> 1);

    return (abs(leftMid - rightMid) << 1) / (leftWidth + rightWidth + 1);
}

int abs(int value) {
    final int mask = value >> (Integer.SIZE - 1);

    value ^= mask;
    value += mask & 1;
    return value;
}

Mengasumsikan kompiler / LLVM inline setengah layak memperluas fungsi-fungsi ini untuk menghindari tumpukan juggling mahal dan pencarian tabel-v. Ini akan gagal untuk nilai input yang dekat dengan ekstrem 32-bit (yaitu Integer.MAX_VALUEdan Integer.MIN_VALUE).

MadMartian
sumber
0

Cara tercepat adalah menggabungkan semua 4 nilai dalam register vektor tunggal.

Simpan kotak dalam vektor dengan nilai-nilai berikut [ min.x, min.y, -max.x, -max.y ]. Jika Anda menyimpan kotak seperti ini, tes persimpangan hanya membutuhkan 3 instruksi CPU:

_mm_shuffle_ps untuk menyusun ulang kotak kedua membalik min dan maks.

_mm_xor_psdengan angka ajaib _mm_set1_ps(-0.0f)untuk membalikkan tanda semua 4 nilai di kotak kedua.

_mm_cmple_ps untuk membandingkan semua 4 nilai satu sama lain, membandingkan dua register berikut:

[ a.min.x, a.min.y, -a.max.x, -a.max.y ] < [ b.max.x, b.max.y, -b.min.x, -b.min.y ]

Akhirnya, jika perlu, _mm_movemask_psuntuk mendapatkan hasil dari unit vektor ke dalam register skalar. Nilai 0 berarti kotak berpotongan. Atau jika Anda memiliki lebih dari 2 kotak ini tidak diperlukan, biarkan nilai dalam register vektor dan gunakan operasi bitwise untuk menggabungkan hasil dari beberapa kotak.

Anda belum menentukan bahasa atau platform, tetapi dukungan untuk SIMD seperti ini, atau sangat mirip, tersedia di semua platform dan bahasa. Di ponsel, ARM memiliki NEON SIMD dengan hal-hal yang sangat mirip. .NET memiliki Vector128 di System.Runtime.Intrinsics namespace, dan sebagainya.

Soonts
sumber