代码之家 › 专栏 › 技术社区 › kikito

四叉树-内部项目移动时如何更新

quadtree lua

7

kikito · 技术社区 · 15 年前

我已经实现了一个工作四叉树。它对二维空间进行细分,以便容纳项目,这些项目由它们的边界框(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

我不想找人来为我实现它;指向现有工作实现(甚至是其他语言)的指针就足够了。

1 回复 | 直到 11 年前

1

5

richj 15 年前

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

insert方法是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