QuadTrees - 内部项目移动时的更新方式

Question

我已经实现了一个有效的QuadTree.它细分了2-d空间,以便容纳在最小可能的四边形(最小区域)上由边界框(x,y,宽度,高度)标识的项目.

我的代码基于这个实现(我的是Lua而不是C#):http://www.codeproject.com/KB/recipes/QuadTree.aspx

我已经能够成功实现插入和删除.我现在把注意力转向update()函数,因为我的项目的位置和尺寸会随着时间的推移而变化.

我的第一个实现工作,但它是天真的:

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

是的,我基本上每次移动时都会删除并重新插入每个项目.

这有效,但我想更优化一下; 毕竟,大多数情况下,移动项仍然保留在同一个quadTree节点上.

有没有标准的方法来处理这种更新？

如果它有帮助,我的代码在这里:https://github.com/kikito/middleclass-ai/blob/master/QuadTree.lua

我不是在寻找有人为我实施它; 指向现有工作实现的指针(即使在其他语言中)就足够了.

Answer 1

您有一个很好的解决方案(项目 - >节点索引)来处理更新方法的常见问题,这些问题源于需要使用旧边界框删除并使用新边界框插入.

插入方法是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