内部物品移动时如何更新

我已经实现了一个可用的QuadTree。 它细分二维空间以容纳物品，通过它们的边界框（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

我不想找人帮我实施; 指向现有工作实现（甚至用其他语言）的指针就足够了。

---

您有一个很好的解决方案（item-> node index），用于处理更新方法的常见问题，这些更新方法是由于需要使用旧的边界框进行移除并使用新的边界框进行插入而产生的。

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

链接地址: http://www.djcxy.com/p/45913.html

上一篇: how to update when internal items are moving

下一篇: Does changing background color in android destroy the widget's appearance?