How Do Shapes (Rectangles) Work in Quad Trees?

Question

I've been told that a quad tree is the ideal data structure for my game, but I'm having trouble understanding how exactly shapes work within quad trees.

I'm doing this in JavaScript, but I think these questions could apply to quad trees in any language.

I think I mostly understand how basic (x,y) points and point insertion works in quad trees, and that I could do it on paper.

Here is a JSfiddle of my experimenting with points.

Aside from one case, my tests with points are working as expected.

But my confusion starts when shapes like rectangles are involved. When you are retrieving from a quad tree with shapes, does it check each point of the shape, and what nodes they fall into? And how do shape insertions even work, when it accepts (x,y,width,height) parameters for each shape? Does it use the width/height from the starting point to calculate other corner points, which are then dispensed into appropriate nodes? If an inserted shape spans into four nodes, is that shape's data saved into all four nodes?

And when a retrieval method accepts a shape as the parameter(x,y,width,height), what is actually going on? Is it first seeing what nodes the shape would span to if it were to be inserted, and then retrieve all the objects of those nodes?

I have a JSfiddle working with shapes, but I am utterly confused on the results of my testing. I am getting duplicate objects being returned!

For example, the red square is a drawn equivalent of the parameters I am entering into my retrieval method. I would think that since this red square spans all four nodes, it should return every object in the quad tree! But it doesn't, and I am having trouble rationalizing what it does return. I have a number of other tests that are currently commented out, but you can un-comment and run them to see more confusing results!

As say, if I want to return all points in a quad tree, how would I do that? A retrieve method using a shape the entire size of the bounds? In example, retrieve(0, 0, canvas.width, canvas.height)?

The JavaScript QuadTree library I am using has been referred to by various other sources, so I assume the actual implementation is correct and reputable.

I think a lot of my confusion may stem from a misunderstanding of quad tree terminology. Like, why do they say bounds instead of dimensions, when a "point" has width/height parameters as well? Is it a matter of convention/short-hand, or are they completely different concepts?

Thanks for your time!

Answer 1

Quadtrees typically store and retrieve rectangles. A point is a specific case where width and height are zero. The following logic is used to find home for new rectangles in the tree, starting with the root node:

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
    }
}

Note that rectangles can be stored at any depth, it does not have to be a leaf quad. If the rectangle straddles the boundary right at the root level, the root quad will store the rectangle.

For example, the red square is a drawn equivalent of the parameters I am entering into my retrieval method. I would think that since this red square spans all four nodes, it should return every object in the quad tree! But it doesn't, and I am having trouble rationalizing what it does return.

When querying the quadtree, it will only return rectangles that are contained by the query. In your example, you force each of the 4 child quads to be looked at in further detail because the red query rectangle intersects each child quad. Since the children have no further children, each of the rectangles in these child quads will be compared with the red rectangle. Since none of the rectangles in the tree collide with the red query rectangle, nothing should be returned.

You really start to see benefits of quadtrees when you have lots of objects, and lots of space for the objects to exist in compared with the query area(s). In these cases, a small query area can quickly eliminate vast chunks of the quad tree from consideration. Only quads that intersect with the query rectangle will ever be looked at in more detail.

EDIT

Retrieval is usually done like the following:

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;
}

In your library however, it doesn't seem to check if if the rectangles it's returning intersect with the query, so you'll need to add that yourself.