QuadTrees - wie zu aktualisieren, wenn interne Elemente in Bewegung sind

Question

Ich habe eine funktionierende QuadTree implementiert. Er unterteilt den 2-d-Raum, um Objekte aufzunehmen, die durch ihre Begrenzungsbox (x, y, Breite, Höhe) auf der kleinstmöglichen Quadrate (bis zu einer minimalen Fläche) gekennzeichnet sind.

Mein Code basiert auf dieser Implementierung (Mine in Lua ist anstelle von C#): http://www.codeproject.com/KB/recipes/QuadTree.aspx

Ich habe in der Lage erfolgreich zu Einfügungen und Löschungen zu implementieren. Ich habe jetzt meine Aufmerksamkeit auf die Funktion update() gerichtet, da sich Position und Abmessungen meiner Objekte im Laufe der Zeit ändern.

Meine erste Implementierung funktioniert, aber es ist ziemlich naiv:

function QuadTree:update(item) 
    self:remove(item) 
    return self.root:insert(item) 
end 

Yup, ich im Grunde jedes Element entfernen und wieder einsetzen, jedesmal wenn sie bewegen.

Das funktioniert, aber ich möchte es ein bisschen mehr optimieren; Schließlich bleiben bewegliche Objekte immer noch auf demselben QuadTree-Knoten.

Gibt es einen Standard-Weg, um mit dieser Art von Update umzugehen?

Falls es hilft, ist mein Code hier: https://github.com/kikito/middleclass-ai/blob/master/QuadTree.lua

Ich bin nicht für jemanden zu implementieren es für mich suchen; Hinweise auf eine bestehende Arbeitsimplementierung (auch in anderen Sprachen) wären ausreichend.

Answer 1

Sie haben eine nette Lösung (ein Item-> Knotenindex) für das übliche Problem mit Update-Methoden, die aus der Notwendigkeit besteht, mit der alten Bounding Box zu entfernen und mit der neuen Bounding Box einzufügen.

Die Einfügemethode ist O (ln (N)), aber eine Aktualisierung, bei der das Element im selben Knoten bleibt, könnte in konstanter Zeit ausgeführt werden. Der Wechsel zu einem Kindknoten könnte auch optimiert werden, indem die Suche bis zu dem Knoten entfernt wird, der das Element gerade hält, und das Bewegen zu benachbarten Knoten könnte auch einen Teil dieser Suche eliminieren, da jeder Knoten seinen Elternknoten kennt.

Ich weiß nicht Lua, also bitte behandeln Sie den Code unten als Pseudo-Code.

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 

Ich bin mir nicht sicher, ob es sich lohnt, den Baum nach oben oder unten zu scannen. Es könnte interessant sein, es zu versuchen, aber es ist wahrscheinlich nur in einem sehr tiefen Baum wert.

Die findNode-Methode durchsucht die Struktur selbst nach dem Knoten, zu dem das Element nach räumlicher Position gehört. Implementationen kann wählen, nur den Selbstknoten und seinen unterhalt scannen:

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

... oder den ganzen Baum scannen übergeordneten Knoten unter Verwendung auch:

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