# How to deal with objects placed in the root nodes of a quad tree?

I've implemented a quad tree where points and axis aligned rectangles can be put. It works fine, except for one issue that I'll try to describe.

When you put a rectangle in the tree and this rectangle collides with quadtree's node borders, than your rectangle is put in parent node of that node. It's ok! That's how it should work!

Let's consider I have a small rectangle (red) laying in quadtree's center (x: 0, y:0).
And I would like to retrieve other rectangles near my rectangle (blue rectangles).
But here's the problem, when I do that the algorithm will return all rectangles(blue + green), because my rectangle collides with quad tree nodes border and is put in quadtree's root node.
I don't need green rectangles and I can't allow myself to have such an overhead.

How can I avoid such problem? What would be the easiest way to implement solution to this problem?

The current Retrieve method recursively walks to each subnode of the node where red rectangle is positioned.

I've heard about overlapping node borders solution, but I guess it won't help in case if red rect would be 3x time bigger?!

• What kind of behavior do you expect exactly when you say "And I would like to retrieve other rectangles near my rectangle (blue rectangles". How do you define near in you context? – thalador Jun 21 '13 at 11:54
• Near - it is in same node where rectangle is positioned. – user27061 Jun 21 '13 at 12:10
• From what little bit I have read up on quadtrees, people tend to only store at the leaf nodes. They will have a pointer to the objects within these nodes and if your object is in multiple nodes you simply just have a pointer to it in each node. You can iterate through the quadtree to figure out how many nodes your object is in and only take objects from those nodes. However then you run into the problem of having multiples of one object. I think they used a hash of some type to store the pointers that way it removed duplicates. – Dean Knight Jun 21 '13 at 12:45
• When I did a quadtree in school, "only store at the leaf nodes" only made sense if you had a set number of subdivisions. But then, a large object would take up about 37 different tiny leafs. It becomes complex to resolve only sub-leafs if you have a world with both bullets hitting tin cans, and large trucks crashing into garage doors. – Katana314 Jun 21 '13 at 14:02
• @Katana314: theory points out all kinds of problems with these data structures that just never occur in practice. You will never have so many bullets in one area you end up generating a bazillion tiny nodes, and if you do have that many, just place a limit on how many subdivisions you allow. – Sean Middleditch Jun 21 '13 at 17:23

If you re-implement your quadtree to insert objects on borders into all siblings of that border, then the result you'll get is exactly the result you are trying to achieve (with an overhead of 2n per object where n is the number of borders the straddling object is in contact with.)

• +1 That's right. Just be sure to remove the duplicate references before you return. – John McDonald Jun 21 '13 at 21:22

I don't understand why do you add the green ones? If you simply test in each step if the red overlaps with the child (simple test), it would look like this:

Let's say your rectangle red is located in root and you want to retrieve the neighbours and put them into result

child = root

procedure populateResult

if red collides with child
add all neighbours located directly in child to result
if child.hasChildren
for each child
call populateResult(child)
end
endif
endif


And this should only add the blue rectangles.

• Because red collides with all four subnodes of rootnode. – user27061 Jun 21 '13 at 12:23
• But the greens and blues are not located there, right? They are located in their children. So just pick the 4 children and repeat. – MartinTeeVarga Jun 21 '13 at 12:24

I have also implemented an open-source QuadTree with a friend, and we store all objects that don't completely fit into child quads in the parent quad. This can happen at any level of the quad tree. Any time an object straddles the boundary between two quads, it needs to be stored at the parent level. When you are querying the tree, even if you're looking at some obscure corner of the earth, you need to be checking these boundary objects all the way down the tree. Here's some very rough pseudocode for a quad:

List<object> storage;

// Note this is called with the root "quad" and is called recursively
{
If the object fits completely inside the NE quad, Insert(NE), return
If the object fits completely inside the NW quad, Insert(NW), return
If the object fits completely inside the SE quad, Insert(SE), return
If the object fits completely inside the SW quad, Insert(SW), return
Else, insert it storage (specific to this quad)
}