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 successfully. 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 most of the iterations.
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.
