四叉树优化

在上一篇文章中我们已经知道四叉树的使用方法了，但同时我们也注意到一个问题：由于屏幕的物体是运行的，前一秒在象限一的物体可能下一秒就跑到象限二了，所以每一帧都需要重新初始化四叉树。这意味着，每16ms就要初始化一次四叉树，这个代价太大了：

var run = function run() {
    // 重新向四叉树中插入所有物体，重新初始化四叉树
    // ...
    // 筛选物体集合并进行碰撞检测
    // ...
};

我们想想，是不是有这样做的必要？实际上，只是部分物体从一个象限跑到另一个象限，而其他物体都是保持在原先象限中，所以我们只需要重新插入这部分物体即可，从而避免了对所有物体进行插入操作。

我们为四叉树增添这部分的功能，其名为动态更新：

// 判断矩形是否在象限范围内
function isInner(rect, bounds) {
    return rect.x >= bounds.x &&
        rect.x + width <= bounds.x + bounds.width &&
        rect.y >= bounds.y &&
        rect.y + rect.height <= bounds.y + bounds.height;
}

/*
  动态更新：
    从根节点深入四叉树，检查四叉树各个节点存储的物体是否依旧属于该节点（象限）的范围之内，如果不属于，则重新插入该物体。
*/
QuadTree.prototype.refresh = function(root) {
    var objs = this.objects,
        rect, index, i, len;

    root = root || this;

    for (i = objs.length - 1; i >= 0; i--) {
        rect = objs[i];
        index = this.getIndex(rect);

        // 如果矩形不属于该象限，则将该矩形重新插入
        if (!isInner(rect, this.bounds)) {
            if (this !== root) {
                root.insert(objs.splice(i, 1)[0]);
            }

        // 如果矩形属于该象限 且 该象限具有子象限，则
        // 将该矩形安插到子象限中
        } else if (this.nodes.length) {
            this.nodes[index].insert(objs.splice(i, 1)[0]);
        }
    }

    // 递归刷新子象限
    for (i = 0, len = this.nodes.length; i < len; i++) {
        this.nodes[i].refresh(root);
    }
}; 

现在有了动态更新功能，每一帧中只需要对该四叉树进行动态更新即可：

var run = function run() {
    // 动态更新
    tree.refresh();

    // 筛选物体集合并进行碰撞检测
    // ...

};