7

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.

4

1 回答 1

5

您有一个很好的解决方案（项目-> 节点索引）来处理更新方法的常见问题，这些问题是由于需要使用旧边界框删除并使用新边界框插入而引起的。

插入方法是 O(ln(N))，但是可以在恒定时间内完成项目保持在同一节点中的更新。移动到子节点也可以通过删除搜索到当前持有该项目的节点来优化，移动到相邻节点也可以消除一些这种搜索，因为每个节点都知道它的父节点。

我不知道Lua，所以请把下面的代码当作伪代码。

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

我不确定是否值得向上和向下扫描树。尝试可能很有趣，但只有在非常深的树中才可能值得。

findNode 方法从自我中扫描树，按空间位置查找项目所属的节点。实现可以选择仅扫描自身节点及其依赖项：

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

...或者也使用父节点扫描整个树：

-- 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
于 2010-05-23T10:37:16.623 回答