QuadTrees - 当内部项目移动时如何更新

Question

我已经实现了一个工作四叉树。它细分二维空间以容纳项目，通过尽可能小的四边形（最大为最小区域）上的边界框（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

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

这可行，但我想进一步优化它；毕竟，大多数时候，移动的项目仍然保留在同一个四叉树节点上。

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

如果有帮助，我的代码在这里： 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