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: http://github.com/kikito/passion/blob/master/ai/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.

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