Bagaimana Bentuk (Persegi Panjang) Bekerja di Quad Trees?

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.

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!

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!

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.