QuadTrees: cómo actualizar cuándo se mueven los elementos internos

Question

Implementé un QuadTree en funcionamiento. Se subdivide el espacio de 2 d para acomodar elementos, identificados por su cuadro delimitador (x, y, ancho, alto) en el cuadrángulo más pequeño posible (hasta un área mínima).

Mi código se basa en esta implementación (el mío es en Lua en lugar de C#): http://www.codeproject.com/KB/recipes/QuadTree.aspx

que he sido capaz de implementar con éxito las inserciones y deleciones. Ahora dirijo mi atención a la función update(), ya que la posición y las dimensiones de mis elementos cambian con el tiempo.

Mi primera aplicación funciona, pero es bastante ingenuo:

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

Sí, básicamente retire y vuelva a insertar cada artículo cada vez que se mueven.

Esto funciona, pero me gustaría optimizarlo un poco más; después de todo, la mayoría de las veces, los elementos en movimiento permanecen en el mismo nodo quadTree.

¿Hay alguna manera estándar de manejar este tipo de actualización?

En caso de que ayuda, mi código está aquí: https://github.com/kikito/middleclass-ai/blob/master/QuadTree.lua

no estoy buscando a alguien para ponerlo en práctica para mí; los punteros a una implementación de trabajo existente (incluso en otros idiomas) serían suficientes.

Answer 1

Tiene una buena solución (un índice item-> nodo) para resolver el problema habitual con los métodos de actualización que surge de la necesidad de eliminar con el cuadro delimitador anterior e insertar con el nuevo cuadro delimitador.

El método de inserción es O (ln (N)) pero una actualización donde el elemento permanece en el mismo nodo podría lograrse en tiempo constante. El traslado a un nodo secundario también podría optimizarse al eliminar la búsqueda hacia abajo hasta el nodo que actualmente contiene el elemento, y moverse a nodos adyacentes también podría eliminar parte de esta búsqueda porque cada nodo conoce su padre.

No conozco a Lua, por favor trate el siguiente código como pseudo-código.

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 

No estoy seguro de si vale la pena escanear el árbol o hacia abajo. Puede ser interesante intentarlo, pero solo valdrá la pena en un árbol muy profundo.

El método findNode escanea el árbol buscando el nodo al que pertenece el elemento por ubicación espacial. Las implementaciones pueden optar por analizar sólo el nodo mismo y sus dependientes:

-- 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 para escanear todo el árbol usando nodos padre así:

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