QuadTrees - как обновить, когда внутренние объекты перемещаются

Question

QuadTrees - как обновить, когда внутренние объекты перемещаются

Я реализовал рабочий QuadTree. Это подразделяет 2-е пространство для размещения объектов, определенных их ограничительной рамкой (x, y, ширина, высота) на самой маленькой четверке (до минимальной области).

Мой код основан на этой реализации (мой находится в Lua вместо C#): http://www.codeproject.com/KB/recipes/QuadTree.aspx

Я смог успешно реализовать вставки и удаления. У меня есть поворот теперь мое внимание к обновлению () функция, так как положение и размеры моих объектов изменяются со временем.

Мои первые работы реализации, но это довольно наивно:

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

Да, я в основном удаляю и повторно вставляю каждый объект каждый раз, когда они перемещаются.

Это работает, но я хотел бы оптимизировать его немного больше; в конце концов, большую часть времени, движущиеся объекты все еще остаются на том же узле дерева квадрантов.

Там какой-либо стандартный путь состоит в том, чтобы иметь дело с этим видом обновления?

В случае, если это помогает, мой код здесь: https://github.com/kikito/middleclass-ai/blob/master/QuadTree.lua

Я не ищу кого-то для реализации его для меня; указатели на существующую рабочую реализацию (даже на других языках) были бы достаточны.

7

lua quadtree

задан kikito 18 March 2014 в 18:39

1 ответ

Другие вопросы по тегам:

lua quadtree

Похожие вопросы:

score 5 · Accepted Answer

У вас есть хорошее решение (элемент-> индекс узла) для решения обычной проблемы с методами обновления, которая возникает из-за необходимости удалить с помощью старого ограничивающего прямоугольника и вставить с новым ограничивающим прямоугольником.

Метод вставки - 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