Mengapa orang menggunakan Octree di atas pohon-KD?

Saya memiliki beberapa pengalaman dalam komputasi ilmiah, dan telah banyak menggunakan pohon kd untuk aplikasi BSP (partisi ruang biner). Saya baru-baru ini menjadi lebih akrab dengan oktri, struktur data yang mirip untuk mempartisi ruang Euclidean 3-D, tetapi yang bekerja pada interval tetap yang tetap, dari apa yang saya kumpulkan.

Sedikit riset independen tampaknya mengindikasikan bahwa kd-tree biasanya unggul dalam kinerja untuk sebagian besar dataset - lebih cepat untuk dibangun dan di-query. Pertanyaan saya adalah, apa kelebihan oktri dalam kinerja spasial / temporal atau sebaliknya, dan dalam situasi apa yang paling bisa diterapkan (saya pernah mendengar pemrograman grafis 3D)? Ringkasan kelebihan dan masalah dari kedua jenis ini akan sangat saya hargai.

Sebagai tambahan, jika ada yang bisa menguraikan penggunaan struktur data R-tree dan keuntungannya, saya akan berterima kasih untuk itu juga. R-tree (lebih dari octrees) tampaknya diterapkan sangat mirip dengan kd-tree untuk k-terdekat-tetangga atau rentang pencarian.

Sel-sel dalam pohon -tree dapat memiliki aspek rasio tinggi, sedangkan sel-sel octree dijamin kubik. Karena ini adalah papan teori, saya akan memberi Anda alasan teoritis mengapa rasio aspek tinggi adalah masalah: itu membuat tidak mungkin untuk menggunakan batas volume untuk mengontrol jumlah sel yang harus Anda periksa ketika menyelesaikan perkiraan perkiraan tetangga terdekat.$kD$

Secara lebih terperinci: jika Anda meminta -approximate tetangga terdekat ke titik permintaan , dan tetangga terdekat sebenarnya berada pada jarak , Anda biasanya berakhir dengan pencarian yang memeriksa setiap sel struktur data yang mencapai dari dalam hingga bagian luar anulus atau annular shell dengan jari-jari dalam dan jari-jari luar . Jika sel-sel memiliki rasio aspek terikat, karena mereka berada dalam kuadratree, maka mungkin ada paling banyak sel-sel tersebut, dan Anda dapat membuktikan batas yang baik pada waktu untuk kueri. Jika rasio aspek tidak dibatasi, seperti dalam -tree, batas ini tidak berlaku.q d d ( 1 + ϵ ) d 1 / ϵ d - 1 k $\epsilon$$q$$d$$d$$(1+\epsilon)d$$1/\epsilon^{d-1}$$kD$

$kD$ -trees memiliki keunggulan berbeda dari quadtrees, karena mereka dijamin memiliki paling banyak kedalaman logaritmik, yang juga berkontribusi pada waktu untuk permintaan tetangga terdekat. Tetapi kedalaman quadtree paling banyak adalah jumlah bit presisi dari input yang umumnya tidak besar, dan ada metode teoritis untuk mengendalikan kedalaman menjadi dasarnya logaritmik (lihat struktur data quad quadree).

Sekelompok teman dan saya sedang mengerjakan game luar angkasa-RTS sebagai proyek sampingan yang menyenangkan. Kami menggunakan banyak hal yang telah kami pelajari di Ilmu Komputer untuk membuatnya sangat efisien, memungkinkan kami untuk membuat pasukan besar nantinya.

Untuk tujuan ini kami telah mempertimbangkan untuk menggunakan pohon kd, tetapi kami dengan cepat mengabaikannya: penyisipan dan penghapusan sangat umum dalam program kami (pertimbangkan sebuah kapal terbang di luar angkasa), dan ini adalah kekacauan yang tidak suci dengan pohon kd. Karena itu kami memilih oktri untuk permainan kami.

apa keuntungan dari oktri dalam kinerja spasial / temporal atau sebaliknya, dan dalam situasi apa yang paling berlaku (saya pernah mendengar pemrograman grafis 3D)?

pohon kD adalah pohon biner seimbang dan oktri dicoba sehingga keuntungan dan kerugiannya mungkin diwarisi dari struktur data yang lebih umum. Secara khusus:

• Penyeimbangan ulang bisa mahal (oktri tidak perlu penyeimbangan kembali).
• Penyeimbangan menangani heterogenitas dengan lebih baik karena bersifat adaptif.
• Faktor percabangan yang lebih tinggi dalam oktri berarti pohon yang lebih dangkal (lebih sedikit tipuan dan alokasi) untuk distribusi yang homogen.

Juga, pembelahan dua (seperti dalam octrees) cocok untuk implementasi sepele dalam hal bit-twiddling. Demikian pula, saya membayangkan octrees bisa mendapat manfaat besar dari jarak yang telah ditentukan saat melakukan pencarian rentang.

EDIT

Rupanya referensi saya untuk mencoba dan homogenitas perlu klarifikasi.

Tries adalah keluarga struktur data yang diwakili oleh pohon-pohon kamus dan digunakan sebagai kamus untuk kunci yang berurutan (terutama string tetapi juga urutan DNA dan bit dalam nilai hash untuk percobaan hash). Jika masing-masing kamus memetakan satu bit dari masing-masing koordinat x, y dan z (bit paling signifikan di tingkat pertama dari trie, bit signifikan berikutnya di tingkat kedua dll.) Maka trie adalah sebuah octree yang secara seragam membagi ruang 3D. Karenanya, oktri mewarisi karakteristik percobaan, yaitu:

• Faktor percabangan tinggi dapat berarti pohon dangkal yang menimbulkan sedikit tipuan sehingga pencarian cepat, misalnya 20 tingkat pohon biner dapat disimpan dalam 4 tingkat pohon dengan faktor percabangan 256.
• Percobaan tidak diseimbangkan kembali selama penyisipan dan penghapusan, menghemat operasi yang mahal yang diperlukan untuk pohon biner seimbang.

Kerugiannya adalah bahwa heterogenitas dapat menyebabkan upaya / oktri yang tidak seimbang sehingga pencarian dapat memerlukan banyak tipuan. Masalah yang setara dalam percobaan diselesaikan dengan menggunakan kompresi tepi untuk menutup beberapa level tipuan menjadi satu level. Oktri tidak melakukan ini, tetapi tidak ada yang menghentikan Anda dari mengompres sebuah octree (tapi saya pikir Anda tidak bisa menyebut hasilnya sebagai octree!).

Untuk perbandingan, pertimbangkan kamus khusus untuk kunci string yang direpresentasikan sebagai trie. Level pertama dari trie bercabang pada karakter pertama dalam kunci. Level kedua pada karakter kedua dan seterusnya. Setiap string dapat dicari dengan mencari karakter pertama dari kunci di kamus untuk mendapatkan kamus kedua yang digunakan untuk mencari karakter kedua dari kunci dan seterusnya. Satu set string kunci acak akan menjadi distribusi yang homogen . Satu set string kunci yang semuanya memiliki beberapa awalan (mis. Semua kata yang dimulai dengan "anti") adalah heterogendistribusi. Dalam kasus terakhir, kamus pertama hanya berisi satu penjilidan, untuk "a", yang kedua hanya untuk "n" dan seterusnya. Mencari pemetaan di trie selalu dengan mencari empat kamus yang sama dengan empat kunci yang sama. Ini tidak efisien dan inilah yang dilakukan oleh oktri jika, misalnya, mereka digunakan untuk menyimpan distribusi partikel yang heterogen di mana sebagian besar partikel berada dalam volume kecil di dalam ruang vektor.

Oktaf berguna sebagai datatype dasar untuk model kontinum, lihat misalnya pemecah aliran Gerris . Hidup cukup sulit dalam dinamika fluida, jadi mengetahui bahwa ukuran semua subkub Anda hanya bergantung pada kedalamannya harus menjadi faktor penyederhanaan.

Peringatan: Saya bukan orang yang dinamis!