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