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

Question

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?!

Answer 1

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.)

Answer 2

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.

Answer 3

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
Insert(object, quad)
{
    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)
}

List<object> Get(area, quad)
{
    Check each object stored in storage
    Check sub quads recursively (which will in turn check their own storage)
}

It might sound wasteful to store boundary objects like this, and you may get a number of these, but it's not that bad, and there's no choice if you want to store areas in your tree. You could store points in the tree, but then area-based queries break, and that's a more common use-case.