QuadTrees - come aggiornare quando gli elementi interni si stanno muovendo

Question

Ho implementato un QuadTree funzionante. Suddivide lo spazio bidimensionale per accogliere gli oggetti, identificati dal riquadro di delimitazione (x, y, larghezza, altezza) sul quadratino più piccolo possibile (fino a un'area minima).

Il mio codice si basa su questa implementazione (il mio è in Lua invece di C#): http://www.codeproject.com/KB/recipes/QuadTree.aspx

sono stato in grado di implementare con successo inserimenti ed eliminazioni. Ho ora spostato la mia attenzione sulla funzione update(), poiché la posizione e le dimensioni dei miei articoli cambiano nel tempo.

La mia prima implementazione funziona, ma è abbastanza ingenuo:

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

Yup, ho praticamente rimuovere e reinserire ogni elemento ogni volta che si muovono.

Questo funziona, ma mi piacerebbe ottimizzarlo un po 'di più; dopo tutto, il più delle volte, gli elementi in movimento rimangono sullo stesso nodo QuadTree.

Esiste un modo standard per gestire questo tipo di aggiornamento?

In caso aiuta, il mio codice è qui: https://github.com/kikito/middleclass-ai/blob/master/QuadTree.lua

io non sto cercando qualcuno per la sua attuazione per me; i riferimenti a un'implementazione funzionante esistente (anche in altre lingue) sarebbero sufficienti.

Answer 1

Hai una soluzione carina (un indice item-> nodo) per affrontare il solito problema con i metodi di aggiornamento che nasce dalla necessità di rimuovere con il vecchio riquadro di delimitazione e inserire con il nuovo riquadro di delimitazione.

Il metodo di inserimento è O (ln (N)) ma un aggiornamento in cui l'elemento rimane nello stesso nodo potrebbe essere eseguito in tempo costante. Anche il passaggio a un nodo figlio potrebbe essere ottimizzato rimuovendo la ricerca fino al nodo che attualmente contiene l'elemento, e il passaggio a nodi adiacenti potrebbe anche eliminare parte di questa ricerca perché ogni nodo conosce il suo genitore.

Non conosco Lua, quindi per favore tratta il codice sotto come pseudo-codice.

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 

non sono sicuro che vale la pena di scansione l'albero così come verso il basso. Potrebbe essere interessante provarlo, ma è probabile che valga la pena in un albero molto profondo.

Il metodo findNode esegue la scansione dell'albero dalla ricerca automatica del nodo a cui appartiene l'elemento per posizione spaziale. Implementazioni possono scegliere di eseguire la scansione solo il nodo di sé e dei suoi dipendenti:

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

... o per eseguire la scansione l'intero albero con nodi padre così:

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