QuadTree: hanya menyimpan poin, atau wilayah?

Saya mengembangkan quadtree untuk melacak objek bergerak untuk deteksi tabrakan. Setiap objek memiliki bentuk pembatas, katakanlah mereka semua adalah lingkaran. (Ini permainan top-down 2D)

Saya tidak yakin apakah hanya akan menyimpan posisi setiap objek, atau seluruh bentuk yang terikat.

Jika bekerja dengan titik, penyisipan dan subdivisi mudah, karena objek tidak akan pernah menjangkau beberapa node. Di sisi lain, kueri kedekatan untuk objek mungkin kehilangan tumbukan, karena tidak akan mempertimbangkan dimensi objek. Bagaimana cara menghitung wilayah permintaan ketika Anda hanya memiliki poin?

Jika bekerja dengan wilayah, bagaimana menangani objek yang membentang beberapa node? Haruskah itu dimasukkan ke dalam simpul induk terdekat yang benar-benar berisi itu, bahkan jika ini melebihi kapasitas simpul itu?

Terima kasih.

Jika menyimpan objek yang diperluas (wilayah) dalam quadtree, objek harus dirujuk dari semua simpul daun yang disentuhnya. Saya tidak akan mencoba untuk menemukan leluhur yang paling tidak umum dan menyimpannya di sana, karena dengan demikian misal sebuah objek kecil yang kebetulan melewati batas level tinggi akan berakhir di simpul yang sangat tinggi, dan harus diuji terhadap semua yang lain dalam ukuran besar itu. , simpul tingkat tinggi ketika Anda melakukan collision queries dan sejenisnya.

Namun, Anda juga harus berhati-hati karena benda besar dapat menjadi referensi dari banyak node, membuatnya mahal untuk diperbarui ketika mereka bergerak, dan menyebabkan mereka diperiksa ulang berkali-kali untuk tabrakan dll. Tergantung pada kasus penggunaan Anda, itu mungkin layak menggunakan semacam heuristik untuk menyimpan objek besar di tingkat yang lebih tinggi di pohon, tetapi ini akan menyulitkan algoritma, jadi saya mungkin tidak akan repot kecuali Anda menetapkan bahwa itu benar-benar masalah kinerja dalam kasus khusus Anda.

Demikian pula, untuk kueri suatu wilayah, kueri harus melihat semua simpul daun yang disentuh wilayah yang ditanyai.

Ini pada dasarnya menggunakan algoritma yang sama, yaitu untuk memulai dengan suatu daerah dan mendorongnya ke bawah melalui pohon untuk menemukan simpul daun yang disentuhnya. Ini adalah traversal pertama-kedalaman, tetapi pada setiap node Anda dapat memangkas setiap anak yang tidak menyentuh wilayah tersebut. Anda harus memelihara tumpukan untuk melacak di mana Anda berada di traversal.

Anda harus menyimpannya di simpul terkecil yang benar-benar berisi itu - bahkan jika ini melebihi kapasitas (gunakan wadah yang dapat diubah ukurannya).

Saya akan menambahkan ini sebagai komentar sebagai jawaban atas jawaban @Nathan Reed, kecuali terlalu besar untuk menjadi komentar, dan mungkin dalam hal apa pun layak menjadi jawaban yang terpisah.

Kami melakukan persis apa yang diusulkan dalam jawabannya, dan bahkan memiliki komentar di sumber yang menghubungkan ke halaman ini. Sebagian besar, ini telah bekerja dengan sangat baik, kecuali bahwa sekali setiap dua atau tiga bulan, kami telah kehilangan server secara acak yang tidak responsif karena lamanya permintaan pencarian.

Penyebab utama masalah ini menjadi perhatian saya saat melakukan pemeriksaan kinerja untuk mencoba dan mencari tahu apa penyebabnya. Kemungkinan hanya masalah jika Anda mengizinkan objek yang tumpang tindih. Dalam permainan kami, kami lakukan, dan dalam skenario terburuk itu kadang-kadang menyebabkan lonjakan kedalaman membunuh kinerja.

Kami memiliki satu kasus tepi di mana sekitar 100 objek, semua dengan disk pembatas, dikelompokkan dalam jarak sangat dekat. Itu mengarah pada masalah lonjakan yang sangat dalam di pohon, karena kami sampai pada titik di mana objek lebih besar dari area yang dicakup oleh node quadtree, sehingga setiap objek baru muncul di beberapa node, yang mengarah ke subdivisi besar-besaran dari pohon, sehingga bola salju masalah di luar kendali.

Hal yang dapat diambil dari hal ini adalah jika Anda membiarkan daerah objek tumpang tindih, awasi dengan cermat benda-benda jika Anda mendapatkan kumpulan benda yang rapat, untuk memastikan pohon Anda tidak terlalu dalam.

Solusi yang saya selidiki saat ini adalah untuk menyimpan objek sebagai titik, dan kemudian ketika melakukan pencarian, tambahkan batas-batas persegi panjang pencarian dengan jari-jari maksimum yang tersimpan di pohon. Itu akan bekerja untuk kita, karena pohon adalah pencarian lulus pertama, kita kemudian melakukan pemeriksaan rentang berbasis lingkaran yang benar, bersama dengan beberapa pengecekan kriteria lainnya, sehingga peringatan palsu tambahan akan disaring.

Jarak tempuh Anda yang sebenarnya mungkin berbeda.