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

2014-3-18 18:39:48
收藏：0
阅读：209
评论：1

我已经实现了一个可工作的四叉树(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

是的，我基本上是每次物品移动时都会删除和重新插入。

这个方法有效，但我想进一步优化它; 毕竟，大多数情况下，移动的物品仍然在同一个四叉树节点中。

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

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

我不是在寻求别人为我实现它; 对现有的工作实现的指针(即使是其他语言)就足够了。

原文链接 https://stackoverflow.com/questions/2890324

点赞
stackoverflow用户38031
stackoverflow用户38031

你有一个很好的解决方案（一个项->节点索引）来处理与更新方法相关的通常问题，这些问题源于需要删除旧边界框并插入新边界框的需要。

插入方法为O（ln（N）），但是在项保留在相同节点的情况下可以在常数时间内完成更新。向子节点移动也可以通过消除对当前持有该项的节点的搜索来优化，并且移动到相邻节点也可以消除某些搜索，因为每个节点都知道其父节点。

我不知道Lua，请将以下代码视为伪代码。

function QuadTree:update（item）
    oldNode = root.assignments [item]
    newNode = oldNode：findNode（item）

    if（oldNode ~ = newNode）then

        - 如果findNode仅向下搜索树，则如果
        - 该项需要移动到/在相邻节点下，则newNode将为nil。否则
        - 下面的三行不需要
        如果（newNode == nil）then
            newNode = root：findNode（item）
        end

        oldNode：remove（item）
        newNode = newNode：insert（item）
    end

    返回newNode
end

我不确定扫描整个树，包括向上和向下扫描是否值得。尝试可能很有趣，但只有在非常深的树中才可能值得。

findNode方法从self开始扫描树，按空间位置查找该项所属的节点。实现可以选择仅扫描self节点和其相关节点：

- 按空间位置返回项所属的节点。
- 树中已经可以包含该项。该项可能使用索引
- 旧几何。
- 此方法不创建子节点。
function QuadTree：findNode（item）
    local x，y，w，h = item：getBoundingBox（）
    if（not _contained（x，y，w，h，self：getBoundingBox（）））then
        - 尝试在不包含它的QuadTree上插入项；
        - 只需返回
        返回无
    end

    对于_，节点在ipairs中做
        如果（node：findNode（item）〜= nil）则返回节点
    结束

    返回self
end

…或者使用parent节点扫描整个树：

- 按空间位置返回项所属的节点。
- 树中已经可以包含该项。该项可能使用索引
- 旧几何。
- 此方法不创建子节点。
function QuadTree：findNode（item）
    local x，y，w，h = item：getBoundingBox（）
    if（not _contained（x，y，w，h，self：getBoundingBox（）））then
        - 尝试在不包含它的QuadTree上插入项；
       - 扫描parent
        如果（parent == nil）则返回nil

        返回parent：findNode（item）
    end

    对于_，节点在ipairs中做
        如果（node：findNode（item）〜= nil）则返回节点
    结束

    返回self
end
2010-05-23 10:37:16

作者:

stackoverflow用户312586

stackoverflow用户312586
推荐文章