algorithm - barnes hut 树在 insert 和 internalInsert 之间无限循环

Question

我正在尝试实现这个数据结构，一个 Barnes-Hut Octree ，我一直陷入无限循环，因内存不足异常而终止。

完整的 fiddle 在这里:http://jsfiddle.net/cWvex/但是我循环的函数是这些:

OctreeNode.prototype.insert = function (body) {

    console.log('insert');

    if(this.isInternal){

        this.internalInsert(body);

        return;
    }


    if(this.isExternal){

        // insert the body into the spec. quadrant, call internalUpdate
        for(var quadrant in this.internal.quadrants){
            if(this.internal.quadrants.hasOwnProperty(quadrant)){
                this.internal.quadrants[quadrant] = new OctreeNode();
            }
        }
        this.isExternal = false;
        this.isInternal = true;

        this.internalInsert(this.external);
        this.external = null;
        this.internalInsert(body);

        return;
    }


    if(this.isEmpty){

        this.external = body;
        this.isEmpty = false;
        this.isExternal = true;

        return;
    }

};

// Precondition: quadrants' nodes must be instantiated
OctreeNode.prototype.internalInsert = function(body) {

    console.log('internalInsert');

    this.internal.quadrants[this.quadrant(body)].insert(body);
    this.internalUpdate(body);

};

有人知道我错过了什么吗？

Answer 1

我认为问题与象限函数有关:

OctreeNode.prototype.quadrant = function (body) {

    console.log('quadrant');

    var pos = this.internal.pos;

    var quadrant = (body.pos.x < pos ? 'l' : 'r') + 
        (body.pos.y < pos ? 'u' : 'd') + 
        (body.pos.z < pos ? 'i' : 'o');

    return quadrant; 
};

选择的象限应该基于象限的中心，而不是质心。我认为您需要创建一个新变量来定义象限的中心。

请注意，当您添加节点时，质心(存储在 pos 中)可以改变，但象限的中心保持不变(否则当您下降到八叉树时会出错)。

此时，每个新节点生成时的 pos 为 0,0,0，因此每个点最终都会被分配到节点的同一象限中。因此，当您尝试将两个物体放入树中时，您最终会遇到无限递归:

1. 主体 1 被插入节点 x
2. 主体 2 被插入节点 x
3. 节点 1 split 。
4. Body 1 被插入到节点 x 的象限 1
5. Body 2 被插入到节点 x 的象限 1
6. 回到第1步，x变为节点x的第1象限的节点

编辑

顺便说一句，在代码中写着:

avgPos.x = (body.pos.x*body.mass + 
            avgPos.x * totalMass) / totalMass + body.mass

我认为你需要更多的括号才能成为

avgPos.x = (body.pos.x*body.mass + 
            avgPos.x * totalMass) / (totalMass + body.mass)

否则重心更新会出错。