Apa cara tercepat untuk mengetahui persimpangan kotak pembatas 2D?

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.

(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.

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 /

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.

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.

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

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

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.

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

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

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.