Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

enter image description here

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

share|improve this question
    
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. –  Denis Narushevich Jun 21 '13 at 12:10
3  
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

3 Answers 3

up vote 2 down vote accepted

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

share|improve this answer
    
+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.

share|improve this answer
    
Because red collides with all four subnodes of rootnode. –  Denis Narushevich 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. –  sm4 Jun 21 '13 at 12:24
    
Thanks to this answer I found my mistake!) –  Denis Narushevich Jun 28 '13 at 9:26

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.