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

Question

我已经实现了一个有效的 QuadTree。它分割二维空间以容纳由其边界框 (x,y,width,height) 标识的最小可能四边形(直至最小面积)的项目。

我的代码基于这个实现(我的是 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 方法从 self 扫描树，查找项目所属的节点，按空间位置。实现可以选择仅扫描自身节点及其依赖项:

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