QuadTrees - как обновить, когда внутренние элементы движутся - PullRequest
Новая
       5

QuadTrees - как обновить, когда внутренние элементы движутся

7 голосов
/ 23 мая 2010

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

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

Мне удалось успешно реализовать вставки и удаления.Теперь я переключаю свое внимание на функцию update (), поскольку положение и размеры моих элементов меняются со временем.

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

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

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

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

Есть ли какой-нибудь стандартный способ справиться с такого рода обновлениями?

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

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

1 Ответ

5 голосов
/ 23 мая 2010

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

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