QuadTrees - comment mettre à jour lorsque des éléments internes sont en mouvement

Question

J'ai implémenté un QuadTree fonctionnel. Il subdivise l'espace 2-d afin d'accommoder les objets, identifiés par leur boîte englobante (x, y, largeur, hauteur) sur le plus petit quad possible (jusqu'à une superficie minimale).

Mon code est basé sur cette mise en œuvre (la mienne est en Lua au lieu de C#): http://www.codeproject.com/KB/recipes/QuadTree.aspx

Je suis en mesure de mettre en œuvre avec succès des insertions et des suppressions. Je me tourne maintenant vers la fonction update(), car la position et les dimensions de mes objets changent avec le temps.

Ma première mise en œuvre fonctionne, mais il est tout à fait naïve:

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

Eh oui, je supprimer essentiellement et réinsérez chaque élément à chaque fois qu'ils se déplacent.

Cela fonctionne, mais je voudrais l'optimiser un peu plus; après tout, la plupart du temps, les éléments en mouvement restent sur le même nœud quadTree.

Existe-t-il un moyen standard pour gérer ce type de mise à jour?

Dans le cas où il aide, mon code est ici: https://github.com/kikito/middleclass-ai/blob/master/QuadTree.lua

Je ne cherche pas quelqu'un pour la mettre en œuvre pour moi; des pointeurs vers une implémentation de travail existante (même dans d'autres langues) suffiraient.

Answer 1

Vous avez une bonne solution (un item-> index de noeud) pour traiter le problème habituel avec les méthodes de mise à jour qui découle de la nécessité de supprimer avec l'ancienne boîte de délimitation et insérer avec la nouvelle boîte englobante.

La méthode d'insertion est O (ln (N)) mais une mise à jour dans laquelle l'élément reste dans le même nœud peut être effectuée en temps constant. Le déplacement vers un nœud enfant pourrait également être optimisé en supprimant la recherche vers le nœud contenant actuellement l'élément, et le déplacement vers des nœuds adjacents pourrait également éliminer une partie de cette recherche car chaque nœud connaît son parent.

Je ne connais pas Lua, donc s'il vous plaît, veuillez traiter le code ci-dessous comme pseudo-code. Je ne suis pas sûr que cela vaut la peine de scanner l'arbre aussi bien que vers le bas. Il pourrait être intéressant d'essayer, mais cela ne vaut probablement la peine que dans un arbre très profond.

La méthode findNode analyse l'arborescence à partir de la recherche du nœud auquel l'élément appartient par emplacement spatial. Implémentations peuvent choisir d'analyser uniquement le nœud auto et ses personnes à charge:

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

... ou pour analyser l'arbre entier en utilisant des nœuds parents ainsi:

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