7

動作するQuadTreeを実装しました。可能な限り最小のクワッド（最小領域まで）のバウンディングボックス（x、y、width、height）で識別されるアイテムを収容するために、2次元スペースを細分化します。

私のコードはこの実装に基づいています（私のコードはC＃ではなくLuaにあります）： 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

私はそれを実装してくれる人を探していません。（他の言語でも）既存の動作する実装へのポインターで十分です。

4

1 に答える 1

5

古いバウンディングボックスで削除し、新しいバウンディングボックスで挿入する必要から生じる、更新メソッドの通常の問題に対処するための優れたソリューション（アイテム->ノードインデックス）があります。

挿入メソッドは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
于 2010-05-23T10:37:16.623 に答える