7
\$\begingroup\$

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

\$\endgroup\$
6
  • \$\begingroup\$ 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? \$\endgroup\$
    – thalador
    Jun 21, 2013 at 11:54
  • \$\begingroup\$ Near - it is in same node where rectangle is positioned. \$\endgroup\$
    – user27061
    Jun 21, 2013 at 12:10
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ Jun 21, 2013 at 12:45
  • \$\begingroup\$ 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. \$\endgroup\$
    – Katana314
    Jun 21, 2013 at 14:02
  • \$\begingroup\$ @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. \$\endgroup\$ Jun 21, 2013 at 17:23

3 Answers 3

2
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ +1 That's right. Just be sure to remove the duplicate references before you return. \$\endgroup\$ Jun 21, 2013 at 21:22
4
\$\begingroup\$

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.

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

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.

\$\endgroup\$

You must log in to answer this question.