QuadTrees - how to update when internal items are moving

Question

I've implemented a working QuadTree. It subdivides 2-d space in order to accomodate items, identified by their bounding box (x,y,width,height) on the smallest possible quad (up to a minimum area).

My code is based on this implementation (mine is in Lua instead of C#) : http://www.codeproject.com/KB/recipes/QuadTree.aspx

I've been able to successfully implement insertions and deletions. I've turn now my attention to the update() function, since my items' position and dimensions change over time.

My first implementation works, but it is quite naïve:

function QuadTree:update(item)
  self:remove(item)
  return self.root:insert(item)
end

Yup, I basically remove and reinsert every item every time they move.

This works, but I'd like to optimize it a bit more; after all, most of the time, moving items still remain on the same quadTree node.

Is there any standard way to deal with this kind of update?

In case it helps, my code is here: https://github.com/kikito/middleclass-ai/blob/master/QuadTree.lua

I'm not looking for someone to implement it for me; pointers to an existing working implementation (even in other languages) would suffice.

Tillotson

Answer 1

You have a nice solution (an item->node index) for dealing with the usual problem with update methods that arises from the need to remove with the old bounding box and insert with the new bounding box.

The insert method is O(ln(N)) but an update where the item stays in the same node could be accomplished in constant time. Moving to a child node could also be optimized by removing the search down to the node currently holding the item, and moving to adjacent nodes could also eliminate some of this search because each node knows its parent.

I don't know Lua, so please treat the code below as pseudo-code.

function QuadTree:update(item)
    oldNode = root.assignments[item]
    newNode = oldNode:findNode(item)

    if (oldNode ~= newNode) then

        -- if findNode only searches down the tree newNode will be nil if 
        -- the item needs to move to/under an adjacent node. Otherwise the
        -- next three lines are not needed
        if (newNode == nil) then
            newNode = root:findNode(item)
        end

        oldNode:remove(item)
        newNode = newNode:insert(item)
    end

    return newNode
end

I'm not sure that it is worth scanning up the tree as well as down. It might be interesting to try, but it is only likely to be worth it in a very deep tree.

The findNode method scans the tree from self looking for the node that the item belongs to by spatial location. Implementations can choose to scan only the self node and its dependents:

-- Returns the node that the item belongs to by spatial location.
-- The tree can already contain the item. The item might be indexed using
-- an old geometry.
-- This method does not create child nodes.
function QuadTree:findNode(item)
    local x,y,w,h = item:getBoundingBox()
    if( not _contained(x,y,w,h , self:getBoundingBox()) ) then
        -- Attempted to insert an item on a QuadTree that does not contain it;
        -- just return
        return nil
    end

    for _,node in ipairs(self.nodes) do
        if(node:findNode(item) ~= nil) then return node end
    end

    return self
end

... or to scan the whole tree using parent nodes as well:

-- Returns the node that the item belongs to by spatial location.
-- The tree can already contain the item. The item might be indexed using
-- an old geometry.
-- This method does not create child nodes.
function QuadTree:findNode(item)
    local x,y,w,h = item:getBoundingBox()
    if( not _contained(x,y,w,h , self:getBoundingBox()) ) then
        -- Attempted to insert an item on a QuadTree that does not contain it;
        -- scan the parent
        if (parent == nil) then return nil end

        return parent:findNode(item)
    end

    for _,node in ipairs(self.nodes) do
        if(node:findNode(item) ~= nil) then return node end
    end

    return self
end

Tick

Thanks for answering. The geometry is updated outside of the quadtree - the items themselves are on charge of doing that. The problem with your example is oldNode:contains() - even if it contains the item, it could be that the new node is one of oldNode's children; for example, if the item is smaller. I'm having difficulties trying to model that. – Tillotson

That's a good point that I didn't make clear: contains, remove and insert can all be non-recursive implementations because the node that they are working on is the correct one i.e. they work on a Node, not a Tree even though there is no distinct Node class. findNode has to work recursively on a tree, it is similar to insert, but without doing the actual insert. – Tick

On second thoughts, it would be better if findNode didn't split a node that is full, because not all findNode calls are followed by an insert. I've updated the pseudo-code to allow for newNode.insert(item) returning a child node of newNode. – Tick

If the geometry is updated outside of the quadtree it's very hard to find the old entry for the item without a complete search of the quadtree or an item->node index for the full tree. In the past I've used the Observer pattern to watch for a change to the item, and notify the change with both old and new values to all interested objects. So in this case the item would broadcast an "I'm moving from A to B" message, and an observer would listen for the message and update the quad tree. – Tick

The problem of finding the old node is trivial to implement with Lua tables: they are hashes that accept objects as keys. Thus I have one table called assignments. I do root.assignments[item]= node. If I ever want to retrieve the old node, I just do root.assignments[item], and there it is. No need to overcomplitace things with the Observer pattern :). I was just looking for a list of steps on the update function. Plenty of people are doing inserts and deletes, but updates are much more rare. – Tillotson

Thank you for your explanation. This is a nice way of solving the problem of finding the old item entry. Your update uses a single O(ln(N)) tree search, which isn't bad. You could make it more efficient for cases where the item stays in the same node, a child/descendant node, and where the item moves to an adjacent node, but it might not be worth the effort involved. – Tick

Thanks richj! I got a 2-hour train trip and I arrived to a similar conclusion myself. Your idea of implementing a findNode method was what put me on the right track. I had to add a parameter in order to avoid infinite recursion (search child -> search parent -> search child again...) but since your solution put me on the right track, I'm accepting it. I've also updated the github implementation in case you are curious. Thanks man! – Tillotson