我如何有效地修剪和合并四叉树中的节点？

Question

我正在使用四叉树来允许我有效地收集特定2D区域中的粒子。随着时间的流逝，这些粒子逐渐消失并最终消失，因此我需要在它们死后将它们从四叉树中移除。

我面临的问题是如何最好地修剪四叉树以删除空节点，并在它们不再有足够的粒子来证明被拆分时合并节点。

我的第一个想法是，我将递归地遍历树，检查每个子节点。如果所有4个节点都是空的，那么我将通过一个标志将其传递回调用堆栈（如果为空则为true，否则为false），否则，我将检查每个子节点中的粒子数量，以及它们是否为全部小于MAX_PER_NODE，将所有粒子拉入父级并删除子级。

也许像下面这样（伪代码在我写这篇文章时确实是意识流，所以请带上一点盐）：

class QuadTreeNode
{
     public bool prune();
     public void deleteChildren(); //just assume it does what you expect...
     private:
     std::vector<ParticleType> particles;
     std::vector<QuadTreeNode*> children; // size <= 4

};

bool QuadTreeNode::prune()
{
    bool allChildrenEmpty = true;
    for(QuadTreeNode & n : children)
    {
        allChildrenEmpty &= n.prune();
    }
    //Merging could be handled by returning the number of particles instead of true/false
    //If the total number of particles falls below the max per bucket, pull the particles into the
    //current node and delete the children...
    if(allChildrenEmpty) this.deleteChildren();
    return allChildrenEmpty && (!this.particles.size());    

}

但是，这似乎效率很低，因为我认为这需要我触摸树中的每个节点（尽管我认为这比访问every粒子更好）。

是否有更好的方法来实现此修剪并合并操作？

Answer 1

假设您没有受到严重的RAM约束，则可以为每个节点添加一个权重计数器，以表示其自身及其后代中粒子的总数。每当您插入或删除粒子时，都对其进行更新，实际上这并不昂贵，因为您是将这些节点拉入L1 anyway。

然后删除时，您还可以检查重量是否