QuadTrees - 內部項目移動時如何更新

Question

我已經實現了一個工作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

我不會找人來實現它給我;指向現有工作實現（甚至用其他語言）的指針就足夠了。

Answer 1

您有一個很好的解決方案（一個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