QuadTrees - how to update when moving internal elements

Question

I implemented a working QuadTree. It subdivides a 2-dimensional space for placing objects indicated by their bounding box (x, y, width, height) on the smallest possible square (to the 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 was able to successfully implement insert and delete. Now I paid attention to the update () function, since the position and sizes of my positions change over time.

My first implementation works, but it is pretty naive:

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

Yup, I basically delete and reinsert each element every time they move.

This works, but I would like to optimize it a bit; after all, in most cases, moving the elements still stays on the same square node.

Is there a standard way to handle such an update?

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

I am not looking for someone to implement this for me; pointers to an existing working implementation (even in other languages).

Answer 1

You have a nice solution (element → node index) to solve the usual problem with update methods, arising from the need to remove using the old bounding box and insert with a new bounding box.

The insertion method is O (ln (N)), but an update in which the element remains in the same node can be performed in constant time. Navigating to a child of a node can also be optimized by deleting the search to node, currently holding the element, and moving to neighboring nodes can also eliminate some of these searches because each node knows its parent.

I do not 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 if it is worth scanning both the tree and down. It might be interesting to try, but it is probably worth it in a very deep tree.

The findNode method scans the tree, independently scanning the node to which the element belongs to a spatial location. Implementations can choose to scan only the node itself 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 entire tree using parent nodes:

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