Apakah deteksi tabrakan selalu O (n ^ 2)?

14

Apakah mesin fisika dapat mengurangi kerumitan itu, misalnya dengan mengelompokkan objek yang berdekatan dan memeriksa tabrakan di dalam grup ini dan bukan terhadap semua objek? (misalnya, objek jauh dapat dihapus dari grup dengan melihat kecepatan dan jaraknya dari objek lain).

Jika tidak, apakah itu membuat tabrakan sepele untuk bola (dalam 3d) atau disk (dalam 2d)? Haruskah saya membuat loop ganda, atau membuat array pasangan?

EDIT: Untuk mesin fisika seperti peluru dan box2d, apakah deteksi tabrakan masih O (N ^ 2)?

jokoon
sumber
12
Dua kata: Partisi ruang
MichaelHouse
1
Anda bertaruh. Saya percaya keduanya memiliki implementasi SAP ( Sweep and Prune ) (antara lain) yang merupakan algoritma O (n log (n)). Cari "Deteksi Tabrakan Fase Luas" untuk mempelajari lebih lanjut.
MichaelHouse
2
@ Byte56 Sapu dan Prune memiliki kompleksitas O (n log (n)) hanya jika Anda perlu mengurutkan setiap kali Anda menguji. Anda ingin menyimpan daftar objek yang diurutkan dan setiap kali Anda menambahkannya, cukup sortir ke tempat yang benar O (log (n)) karena itu Anda mendapatkan O (log (n) + n) = O (n). Itu menjadi sangat rumit ketika benda-benda mulai bergerak sekalipun!
MartinTeeVarga
1
@ sm4, jika gerakan terbatas maka beberapa lintasan semacam gelembung dapat mengatasi hal itu (cukup tandai objek yang dipindahkan dan pindahkan ke depan atau ke belakang dalam susunan hingga disortir. hanya hati-hati terhadap objek bergerak lainnya
ratchet freak

Jawaban:

14

Divisi spasial selalu O (N ^ 2) dalam kasus terburuk dan itulah kompleksitas di bidang informatika.

Namun ada algoritma yang bekerja dalam waktu linier O (N) . Semuanya didasarkan pada semacam garis sapu.

Pada dasarnya Anda harus memiliki objek Anda diurutkan berdasarkan satu koordinat. Katakanlah X. Jika Anda melakukan pengurutan setiap kali sebelum deteksi tabrakan, kompleksitasnya adalah O (N * logN). Caranya adalah dengan menyortir hanya ketika Anda menambahkan objek ke adegan dan kemudian ketika sesuatu dalam adegan berubah. Menyortir setelah gerakan tidak sepele. Lihat kertas tertaut di bawah ini untuk algoritma yang bergerak dan masih bekerja dalam waktu linier.

Kemudian Anda menyapu dari kiri ke kanan. Setiap kali garis sapuan Anda melewati awal suatu objek, Anda memasukkannya ke dalam daftar sementara. Setiap kali garis sapuan Anda keluar dari objek, Anda mengeluarkannya dari daftar. Anda menganggap tabrakan hanya di dalam daftar sementara ini.

Garis sapu naif adalah O (N ^ 2) dalam kasus terburuk juga (Anda membuat semua objek span seluruh peta dari kiri ke kanan), tetapi Anda dapat membuatnya O (N) dengan membuatnya lebih pintar (lihat tautan di bawah). Algoritma yang sangat bagus akan sangat kompleks.

Ini adalah diagram sederhana cara kerja garis sapu:

Algoritma garis sapu

Garis menyapu dari kiri ke kanan. Objek diurutkan berdasarkan koordinat X.

  • Kasus satu: Dua objek pertama diperiksa. Tidak ada hal lain yang penting.
  • Kasus kedua: Objek pertama diperiksa dan hilang dari daftar. Dua dan tiga diperiksa.
  • Kasus ketiga: Sekalipun objek itu bertabrakan, kami tidak memeriksa.
  • Kasus empat: Karena kami memeriksa dalam kasus ini!

Algoritma seperti ini memiliki kompleksitas O (C * N) = O (N).

Sumber: Dua tahun kursus geometri komputasi.

Dalam deteksi tabrakan ini biasanya disebut Sapu dan Prune , tetapi keluarga garis algortitme berguna dalam banyak bidang lainnya.

Bacaan lebih lanjut yang direkomendasikan yang saya yakini berada di luar cakupan pertanyaan ini, namun tetap menarik: Metode Sapu dan Pemangkasan Skala Besar yang Efisien dengan Penyisipan dan Penghapusan AABB - Makalah ini menyajikan algoritme Sapu dan Pemangkas yang ditingkatkan yang menggunakan kotak-kotak yang selaras-sumbu (AABB ) dengan penyortiran yang memperhitungkan pergerakan akun. Algoritma yang disajikan dalam makalah ini bekerja dalam waktu linier.


Sekarang perhatikan bahwa ini adalah algoritma terbaik dalam teori . Itu tidak berarti bahwa itu digunakan. Dalam praktiknya, algoritma O (N ^ 2) dengan pembagian spasial akan memiliki kecepatan kinerja yang lebih baik dalam kasus khas (dekat dengan O (N)) dan beberapa persyaratan tambahan untuk memori. Ini karena konstanta C dalam O (C * N) bisa sangat tinggi! Karena kita biasanya memiliki cukup memori dan kasus-kasus tertentu memiliki objek tersebar merata di ruang angkasa - algoritma tersebut akan melakukan LEBIH BAIK. Tapi O (N) adalah jawaban untuk pertanyaan awal.

MartinTeeVarga
sumber
apakah box2d / bullet menggunakan ini?
jokoon
3
"Sapu dan pangkas" inilah yang biasa disebut fisika. Yang menyenangkan adalah Anda dapat terus menyortir penyortiran saat simulasi dilakukan. Juga, garis sapuan dalam grafik Anda sedikit kurang dalam hal implementasi (baik untuk teori meskipun) - Anda hanya akan beralih pada kotak mulai / berakhir, jadi Anda hanya akan memeriksa potensi tabrakan yang sebenarnya. Terlihat metode ini digunakan untuk menghasilkan pohon partisi spasial yang lebih mampu daripada digunakan secara langsung juga.
Sean Middleditch
3
Karena secara teknis sebenarnya bisa ada tabrakan berpasangan O (N ^ 2), tidak sepenuhnya benar untuk mengatakan bahwa sapuan-dan-pangkas selalu O (N). Alih-alih, kompleksitas inti dari algoritma ini adalah O (N + c), di mana c adalah jumlah tabrakan yang ditemukan oleh algoritma - itu peka terhadap keluaran , seperti banyak algoritma cembung hull. (Referensi: en.wikipedia.org/wiki/Output-sensitive_algorithm )
Steven Stadnicki
1
Anda harus mendukung klaim Anda dengan beberapa publikasi atau setidaknya nama algoritma.
sam hocevar
1
@SamHocevar Saya telah menambahkan tautan ke algoritma Sweep and Prune yang benar-benar canggih yang bekerja dalam waktu linier dengan rincian konstanta yang terperinci. Fakta bahwa algoritme yang disebut "Sweep and Prune" adalah hal baru bagi saya, karena saya tidak pernah bekerja dengannya. Saya telah menggunakan algoritma ini dalam pemilihan peta (yang merupakan jenis tabrakan 1 titik dengan objek lain), jadi saya hanya menerapkan pengetahuan.
MartinTeeVarga
8

Tidak. Deteksi tabrakan tidak selalu O (N ^ 2).

Misalnya, kita memiliki ruang 100x100 dengan objek dengan ukuran 10x10. Kita bisa membagi ruang ini dalam sel 10x10 dengan kisi.

Setiap objek dapat dalam hingga 4 sel kisi (bisa pas di blok atau berada di antara sel). Kita bisa menyimpan daftar objek di setiap sel.

Kita hanya perlu memeriksa tabrakan di sel-sel itu. Jika ada jumlah maksimum objek per sel kotak (katakanlah, tidak pernah ada lebih dari 4 objek di blok yang sama), maka deteksi tumbukan untuk setiap objek adalah O (1) dan deteksi tumbukan untuk semua objek adalah O (N).

Ini bukan satu-satunya cara untuk menghindari kompleksitas O (N ^ 2). Ada metode lain, lebih memadai untuk kasus penggunaan lainnya - sering menggunakan struktur data berbasis pohon.

Algoritma yang saya jelaskan adalah satu jenis partisi Ruang , tetapi ada algoritma ruang partisi lainnya. Lihat Jenis struktur data partisi ruang untuk beberapa algoritma yang menghindari kompleksitas temporal O (N ^ 2).

Mekanisme dukungan Box2D dan Bullet untuk mengurangi jumlah pasangan yang diperiksa.

Dari manual , bagian 4.15:

Pemrosesan tabrakan dalam langkah fisika dapat dibagi menjadi fase sempit dan fase luas. Dalam fase sempit kami menghitung titik kontak antara pasangan bentuk. Bayangkan kita memiliki bentuk N. Menggunakan brute force, kita perlu melakukan fase sempit untuk pasangan N * N / 2.

Kelas b2BroadPhase mengurangi beban ini dengan menggunakan pohon dinamis untuk manajemen pasangan. Ini sangat mengurangi jumlah panggilan fase sempit.

Biasanya Anda tidak berinteraksi dengan fase luas secara langsung. Sebaliknya, Box2D membuat dan mengelola fase luas secara internal. Juga, b2BroadPhase dirancang dengan loop simulasi Box2D dalam pikiran, sehingga kemungkinan tidak cocok untuk kasus penggunaan lainnya.

Dari the Bullet Wiki :

Ada berbagai macam algoritma broadphase yang meningkatkan pada algoritma naif O (n ^ 2) yang hanya mengembalikan daftar pasangan yang lengkap. Broadphases yang dioptimalkan ini kadang-kadang memperkenalkan lebih banyak pasangan yang tidak bertabrakan tetapi ini diimbangi dengan waktu eksekusi yang secara umum ditingkatkan. Mereka memiliki karakteristik kinerja yang berbeda dan tidak ada yang mengungguli yang lain dalam semua situasi.

Pohon AABB dinamis

Ini diimplementasikan oleh btDbvtBroadphase di Bullet.

Seperti namanya, ini adalah pohon AABB yang dinamis . Salah satu fitur berguna dari broadphase ini adalah bahwa struktur beradaptasi secara dinamis dengan dimensi dunia dan isinya. Ini dioptimalkan dengan sangat baik dan broadphase tujuan umum yang sangat bagus. Ini menangani dunia yang dinamis di mana banyak objek bergerak, dan penambahan dan penghapusan objek lebih cepat dari SAP.

Sapu dan Pemangkas (SAP)

Dalam Bullet, ini adalah kisaran kelas AxisSweep. Ini juga merupakan broadphase tujuan umum yang baik, dengan batasan yang memerlukan ukuran dunia tetap, yang diketahui sebelumnya. Broadphase ini memiliki kinerja terbaik untuk dunia dinamika tipikal, di mana sebagian besar objek memiliki sedikit atau tanpa gerak. Baik btAxisSweep3 dan bt32AxisSweep3 mengkuantisasi titik awal dan akhir untuk setiap sumbu sebagai bilangan bulat alih-alih angka floating point, untuk meningkatkan kinerja.

Tautan berikut adalah pengantar umum untuk broadphase dan juga deskripsi dari algoritma Sweep and Prune (meskipun disebut "Sort and Sweep"):

http://www.ziggyware.com/readarticle.php?article_id=128

Juga, lihat halaman wikipedia:

http://en.wikipedia.org/wiki/Sweep_and_prune

luiscubal
sumber
Beberapa tautan ke pertanyaan serupa dan sumber daya luar akan menjadikan ini jawaban yang bagus.
MichaelHouse
3
Ini salah. Anda masih mendapatkan O (N ^ 2). Ini akan jauh lebih cepat, seperti N ^ 2/100, tetapi masih N ^ 2. Sebagai bukti, anggap saja semua benda berada dalam satu sel.
MartinTeeVarga
4
@ sm4 Ini adalah kasus terburuk O (N ^ 2), yang memang terjadi jika semua objek berada dalam satu sel. Namun, dalam mesin fisika, objek biasanya tidak akan berada dalam satu sel. Dalam contoh saya, tidak ada objek yang dapat berbagi sel yang sama dengan lebih dari 3 objek lainnya. Ini akan menjadi apa yang terjadi dalam mesin fisika untuk benda "normal" (dan dengan "normal" maksudku "bukan hanya sensor").
luiscubal
Saya pikir algoritma Anda perlu memeriksa 8 sel di sekitar, bukan hanya 4 sel.
jokoon
6
@luiscubal Complexity selalu "kasus terburuk". Secara teori Anda mencari kompleksitas "dijamin". Sama dengan quicksort, yaitu O (N ^ 2) dan mergesort, yaitu O (N * logN). Quicksort berkinerja lebih baik pada data nyata dan memiliki persyaratan spasial yang lebih rendah. Tetapi mergesort telah menjamin kompleksitas yang lebih baik. Jika Anda perlu membuktikan sesuatu, gunakan mergesort. Jika Anda perlu mengurutkan sesuatu, gunakan quicksort.
MartinTeeVarga
2

O (N ^ 2) merujuk pada fakta bahwa jika Anda memiliki N objek, mencari tahu apa yang bertabrakan dengan apa, kasus terburuk , perhitungan tumbukan N ^ 2. Katakanlah Anda memiliki 3 objek. Untuk menemukan "siapa yang memukul siapa", Anda harus menemukan:

o1 hitting o2?  o1 hitting o3?
o2 hitting o1?  o2 hitting o3?
o3 hitting o1?  o3 hitting o2?

Itu 6 cek untuk tabrakan, atau N * (N-1) cek. Dalam analisis asimptotik kami akan memperluas polinomial dan perkiraan sebagai O (N ^ 2). Jika Anda memiliki 100 objek, maka itu akan menjadi 100 * 99, yang cukup dekat ke 100 * 100.

Jadi, jika Anda mempartisi ruang menggunakan octree misalnya, jumlah rata - rata perbandingan antara badan berkurang. Jika mungkin bagi semua objek untuk berkumpul ke area yang sangat kecil (katakanlah jika Anda melakukan semacam simulasi aliran partikel, di mana partikel dapat berkumpul di area yang sama) maka O (N ^ 2) masih dapat terjadi pada poin dalam simulasi (pada titik mana Anda akan melihat perlambatan).

Jadi, seluruh poin O (N ^ 2) ada karena sifat dari masing-masing tubuh memeriksa setiap tubuh lain di tempat kejadian. Itu hanya sifat perhitungannya. Banyak hal yang dapat membantu menjadikan ini lebih murah. Bahkan grafik adegan (misalnya mendeteksi antara objek di ruangan yang sama saja) akan mengurangi jumlah perhitungan tabrakan yang harus dilakukan secara signifikan, tetapi itu masih akan menjadi O (M ^ 2) (di mana M adalah jumlah objek di ruangan untuk dideteksi tabrakan terhadap). Volume ikatan bundar membuat pemeriksaan awal sangat cepat ( if( distance( myCenter, hisCenter ) > (myRadius+hisRadius) ) then MISS), jadi meskipun deteksi tumbukan adalah O (N ^ 2), perhitungan bola terikat kemungkinan terjadi sangat cepat.

bobobobo
sumber
Tidak perlu mengambil brute force checking sebagai referensi: terlepas dari algoritma pintar, masing-masing objek N dapat bertabrakan dengan semua objek lain, memberikan tabrakan O (N ^ 2) yang membutuhkan pekerjaan O (N ^ 2) untuk diproses. Algoritma yang baik hanya dapat melakukan lebih baik ketika ada sedikit tabrakan.
Lorenzo Gatti