Bagaimana Bentuk (Persegi Panjang) Bekerja di Quad Trees?

10

Saya telah diberitahu bahwa quad tree adalah struktur data yang ideal untuk permainan saya, tetapi saya mengalami kesulitan memahami bagaimana sebenarnya bentuk-bentuk bekerja di dalam quad tree.

Saya melakukan ini dalam JavaScript, tetapi saya pikir pertanyaan ini dapat diterapkan pada quad tree dalam bahasa apa pun.

Saya pikir saya sebagian besar mengerti bagaimana dasar (x, y) poin dan penyisipan titik bekerja di pohon quad, dan bahwa saya bisa melakukannya di atas kertas.

Ini adalah JSfiddle dari percobaan saya dengan poin.

poin quad tree

Selain satu kasus, tes saya dengan poin bekerja seperti yang diharapkan.

Tapi kebingungan saya dimulai ketika bentuk seperti persegi panjang terlibat. Ketika Anda mengambil dari pohon quad dengan bentuk, apakah itu memeriksa setiap titik bentuk, dan mereka jatuh ke dalam simpul apa? Dan bagaimana cara penyisipan bentuk bekerja, ketika ia menerima (x, y, lebar, tinggi) parameter untuk setiap bentuk? Apakah ia menggunakan lebar / tinggi dari titik awal untuk menghitung titik sudut lainnya, yang kemudian disalurkan ke simpul yang sesuai? Jika bentuk yang disisipkan terbentang ke dalam empat node, apakah data bentuk itu disimpan ke dalam empat node?

Dan ketika metode pengambilan menerima bentuk sebagai parameter (x, y, lebar, tinggi), apa yang sebenarnya terjadi? Apakah pertama-tama melihat node apa bentuknya akan span jika itu akan dimasukkan, dan kemudian mengambil semua objek dari node itu?

Saya memiliki JSfiddle yang bekerja dengan bentuk , tetapi saya benar-benar bingung dengan hasil pengujian saya. Saya mendapatkan objek duplikat dikembalikan!

bentuk pohon quad

Sebagai contoh, kotak merah adalah persamaan yang ditarik dari parameter yang saya masukkan ke dalam metode pengambilan saya. Saya akan berpikir bahwa karena kotak merah ini membentang ke empat node, itu harus mengembalikan setiap objek di quad tree! Tetapi tidak, dan saya kesulitan merasionalisasi apa yang dikembalikan. Saya memiliki sejumlah tes lain yang saat ini dikomentari, tetapi Anda dapat membatalkan komentar dan menjalankannya untuk melihat hasil yang lebih membingungkan!

Seperti yang saya katakan, jika saya ingin mengembalikan semua poin dalam quad tree, bagaimana saya melakukannya? Metode pengambilan menggunakan bentuk seluruh ukuran batas? Misalnya, ambil (0, 0, canvas.width, canvas.height)?

The JavaScript Quadtree perpustakaan yang saya gunakan telah disebut oleh berbagai sumber lainnya, jadi saya berasumsi pelaksanaan yang sebenarnya adalah benar dan terkemuka.

Saya pikir banyak kebingungan saya mungkin berasal dari kesalahpahaman terminologi quad tree. Seperti, mengapa mereka mengatakan batas bukan dimensi, ketika "titik" memiliki parameter lebar / tinggi juga? Apakah ini masalah konvensi / tulisan singkat, atau mereka konsep yang sama sekali berbeda?

Terima kasih atas waktunya!

pengguna2736286
sumber
Mereka disimpan di pohon quad seperti biasa, dengan posisi mereka. Biasanya itu ada di tengah, tetapi bisa di sudut seperti yang sudah Anda tentukan. Pertanyaan Anda mungkin merupakan duplikat dari yang ini: QuadTree: hanya menyimpan poin, atau wilayah?
MichaelHouse
Saya sudah membaca pertanyaan itu, tetapi saya masih belum sepenuhnya memahami jawabannya :(. "Anda harus menyimpannya di simpul terkecil yang benar-benar berisi itu - bahkan jika ini melebihi kapasitas (gunakan wadah yang dapat diubah ukurannya)." - Ketika ia mengatakan simpul terkecil yang SEPENUHNYA berisi itu, jika objeknya sangat besar, bukankah simpul itu sering berupa simpul non-daun? Seperti pada simpul yang lebih tinggi yang hanya terdiri dari simpul lain? Kelihatannya tidak tepat untuk saya, karena itu berarti node yang mengandung akan memiliki 1 daun dan 4 node yang lebih kecil di dalamnya
user2736286
1
@ user2736286 Jika Anda melihat kode untuk lib quadtree (ini tidak terlalu lama), Anda dapat melihatnya menyimpan persegi panjang di node tingkat yang lebih tinggi untuk menjaga mereka dari batas-batas node yang melintasi. Lihat referensi ke _stuckChildrenbidang dalam kode. Anda juga dapat melihat ini dalam sampel "mengambil item dengan batas" - selalu menyoroti merah node yang mengangkangi perbatasan dari node yang Anda klik, sepanjang jalan sampai ke node root.
Nathan Reed
@ user2736286 Juga, lib quadtree tampaknya memiliki bug dalam mengambil item dengan batas - jika Anda memberikan kueri kuadrat yang mengangkangi beberapa perbatasan node, itu tidak mengembalikan semua lintasan dalam node yang disentuh oleh kueri. Anda dapat melihat ini dengan mudah di "mengambil item dengan batas" juga, dengan mengeklik batas dekat simpul.
Nathan Reed
@NathanReed Sebelumnya saya mencoba untuk memahami kode, tetapi saya tidak cukup terampil untuk memahaminya tanpa landasan konseptual. Berkat pseudo-code John McDonald's, saya sekarang mengerti bagaimana persegi panjang dimasukkan ke dalam node, tapi saya pikir saya masih tidak jelas tentang cara kerja pengambilan. Adapun "mengambil item dengan batas" - Saya benar-benar bingung dengan contoh. Seperti, ketika saya mengklik kotak yang benar-benar pas ke salah satu simpul terkecil, mengapa semua rect lain di luar simpul itu juga disorot?
user2736286

Jawaban:

10

Quadtrees biasanya menyimpan dan mengambil persegi panjang. Titik adalah kasus khusus di mana lebar dan tinggi adalah nol. Logika berikut digunakan untuk menemukan rumah untuk persegi panjang baru di pohon, dimulai dengan simpul akar:

void Store(Rectangle rect)
{
    if(I have children nodes)
    {
        bool storedInChild = false;
        foreach(Node childNode in nodes)
        {
            if(this rectangle fits entirely inside the childNode bounds)
            {
                childNode.Store(rect);   // Go deeper into the tree
                storedInChild = true;
                break;
            }
        }
        if(not storedInChild)
        {
            Add this rectangle to the current node
        }
    }
    else
    {
        Add this rectangle to the current node
    }
}

Perhatikan bahwa persegi panjang dapat disimpan pada kedalaman berapa pun, tidak harus quad daun. Jika persegi panjang melewati batas tepat di tingkat root, kuad root akan menyimpan persegi panjang.

Sebagai contoh, kotak merah adalah persamaan yang ditarik dari parameter yang saya masukkan ke dalam metode pengambilan saya. Saya akan berpikir bahwa karena kotak merah ini membentang ke empat node, itu harus mengembalikan setiap objek di quad tree! Tetapi tidak, dan saya kesulitan merasionalisasi apa yang dikembalikan.

Saat kueri quadtree, itu hanya akan mengembalikan persegi panjang yang terkandung oleh kueri. Dalam contoh Anda, Anda memaksa masing-masing dari 4 paha depan anak-anak untuk dilihat secara lebih rinci karena kotak kueri merah memotong setiap anak quad. Karena anak-anak tidak memiliki anak lagi, masing-masing persegi panjang dalam paha depan anak-anak ini akan dibandingkan dengan persegi panjang merah. Karena tidak ada persegi panjang di pohon yang bertabrakan dengan persegi panjang kueri merah, tidak ada yang harus dikembalikan.

Anda benar-benar mulai melihat manfaat dari quadtrees ketika Anda memiliki banyak objek, dan banyak ruang untuk objek yang ada dibandingkan dengan area kueri. Dalam kasus ini, area kueri kecil dapat dengan cepat menghilangkan potongan besar pohon quad dari pertimbangan. Hanya paha depan yang bersinggungan dengan persegi panjang kueri yang akan dilihat lebih detail.

EDIT

Pengambilan biasanya dilakukan seperti berikut:

List<Rectangle> Query(Rectangle queryRect)
{
    List<Rectangle> results;
    foreach(Node childNode in children)
    {
        if(queryRect intersects with childNode bounds)
        {
            results += childNode.Query(queryRect);   // Dig deeper into the tree
        }
    }

    foreach(Rectangle I have stored in this quad)
    {
        if(queryRect intersects with rect)  // Your library doesn't do this
        {
            results += rect;
        }
    }

    return results;
}

Namun di perpustakaan Anda, sepertinya tidak memeriksa apakah persegi panjang yang dikembalikan bersinggungan dengan kueri, jadi Anda harus menambahkannya sendiri.

John McDonald
sumber
Setelah melihat pustaka Anda secara lebih rinci, pustaka Anda mengembalikan daftar semua kemungkinan kandidat tabrakan untuk kueri kueri yang Anda tentukan. Tampaknya tugas Anda untuk membandingkan persegi panjang kueri Anda dengan setiap kandidat untuk melihat apakah ada tabrakan yang sebenarnya. Sebagian besar perpustakaan melakukan langkah terakhir untuk Anda dan hanya mengembalikan tabrakan yang sebenarnya dengan area kueri. Jadi, yang perlu Anda lakukan adalah menambahkan beberapa logika dalam retrievemetode Anda untuk memangkas daftar. Anda dapat melihat apa yang dilakukannya sedikit lebih jelas di sini: mikechambers.com/html5/javascript/QuadTree/examples/…
John McDonald
1
@ user2736286 Jika Anda belum mengambilnya, penting untuk mencatat rekursi dalam fungsi Query and Store yang ditulis JohnMcDonald. Ini tidak masuk akal jika Anda tidak mendapatkan bagian itu. Untuk keduanya, setiap rekursi masuk lebih dalam ke pohon, yaitu keluar pada cabang dan akhirnya menjadi daun.
TASagent
Terima kasih John, pseudo-code Anda sangat membantu. Ketika Anda mengatakan "jika (queryRect berpotongan dengan childNode bounds)", apakah itu pada dasarnya berarti jika queryRect terkandung dalam batas - sebagian atau penuh? Hanya ingin menjadi 100% jelas. Juga, dalam contoh "mengambil item berdasarkan batas" yang sedang dibahas, saya memiliki gambar hasil klik saya. Pic Titik biru adalah tempat saya mengklik. Jadi mengapa bukan hanya dua persegi panjang di dalam simpul yang dinyalakan? Mengapa persegi panjang jauh dari itu disorot juga? Saya pikir itulah yang benar-benar membingungkan saya.
user2736286
Sebagian atau penuh. Jika dua sentuhan, atau keduanya sepenuhnya terkandung oleh yang lain. Anda ingin membaca wiki di Quadtrees , tetapi saya telah mengambil foto Anda, dan memberi kode warna untuk mewakili batas anak yang berbeda. Semua persegi panjang biru berpotongan dengan batas paha depan anak pertama, kemudian magenta menjadi satu lapisan lebih dalam, dan hijau satu lapisan lebih dalam lagi. Persegi panjang merah berpotongan dengan quad yang diklik. Pustaka Anda mengembalikan semua rect pada batas anak ditambah semua yang terkandung dalam quad anak terakhir (merah): i.imgur.com/InB8KBj.png
John McDonald
Ok, jadi saya sudah mencoba yang terbaik untuk memeriksa kode sumber lib dan akhirnya saya memahami perilaku stuckChildren, dan bahwa semua rect rect di pic saya hanyalah anak-anak yang terjebak. Awalnya saya berpikir bahwa setiap rects yang mencakup beberapa node hanya akan memiliki data yang diduplikasi dan dimasukkan ke dalam setiap node yang lebih kecil. Sekarang saya menyadari bahwa stuckChildren tidak bisa dimasukkan ke dalam node yang direntangnya, tetapi hanya tinggal di satu simpul yang berisi itu, itulah sebabnya saya juga harus memeriksa semua simpul induk, dan bukan hanya simpul terkecil yang berisi kueri kueri. Terima kasih untuk pic; sekarang lebih masuk akal :)
user2736286