getIndex 方法是个四叉树的辅助方法，在四叉树里，他决定了一个节点的归属，通过检查节点属于哪个象限。（最上面第一幅图不是逆时针在一个面积里划分了四块面积，上面标示了他们的序号，这个方法就是算在一个父节点里他的子节点的序号）
比如当前区域是Rectange(0, 0, 600, 600) 待检测矩形是Rectangel(0, 0, 30, 30) 那么他就在左上象限 index = 1 如果是Rectange(400, 400, 30, 30) 那么他就在右下象限 index = 3
function insert(obj) { if (typeof obj === "undefined") { return; } if (obj instanceof Array) { for (var i = 0, len = obj.length; i < len; i++) { this.insert(obj[i]); } return; } if (this.nodes.length) { var index = this.getIndex(obj); // Only add the object to a subnode if it can fit completely // within one if (index != -1) { this.nodes[index].insert(obj); return; } } objects.push(obj); // Prevent infinite splitting if (objects.length > maxObjects && level < maxLevels) { if (this.nodes[0] == null) { this.split(); } var i = 0; while (i < objects.length) { var index = this.getIndex(objects[i]); if (index != -1) { this.nodes[index].insert((objects.splice(i,1))[0]); } else { i++; } } } };
每次插入一个对象 我们都先看看当前节点有没有子节点 如果有 我们就插入子节点。 一直检测到他没有子节点为止 我们就把对象插入到这个节点， 如果这个节点的对象数量 > 10个 并且当前节点的层数 < MAX_LEVELS 我们就把节点继续划分4个子节点。 然后把当前对象循环 删除 并插入子节点。如果对象在中心线上，getIndex会返回-1， 所以这些对象会被插入到父节点上面。
一旦对象添加上后，要看看这个节点会不会分裂，可以通过检查对象被加入节点后有没有超过一个节点最大容纳对象的数量。分裂起源于节点可以插入任何对象，这个对象只要符合子节点都可以被加入。否则就加入到父节点。
function retrieve(returnedObjects, obj) { if (typeof obj === "undefined") { console.log("UNDEFINED OBJECT"); return; } var index = this.getIndex(obj); if (index != -1 && this.nodes.length) { this.nodes[index].findObjects(returnedObjects, obj); } for (var i = 0, len = objects.length; i < len; i++) { returnedObjects.push(objects[i]); } return returnedObjects; };
最后一个四叉树的方法就是 retrieve 方法，他返回了与指定节点可能发生碰撞的所有节点（就是不停寻找与所给节点在同样象限的节点）。这个方法成倍的减少碰撞检测数量。
四叉树的代码就到这里为止了。
完整的代码如下：
完整的代码中retrieve就是findObjects。
/** * QuadTree object. * * The quadrant indexes are numbered as below: * | * 1 | 0 * ----+---- * 2 | 3 * | */ function QuadTree(boundBox, lvl) { var maxObjects = 10; this.bounds = boundBox || { x: 0, y: 0, width: 0, height: 0 }; var objects = []; this.nodes = []; var level = lvl || 0; var maxLevels = 5; /* * Clears the quadTree and all nodes of objects */ this.clear = function() { objects = []; for (var i = 0; i < this.nodes.length; i++) { this.nodes[i].clear(); } this.nodes = []; }; /* * Get all objects in the quadTree */ this.getAllObjects = function(returnedObjects) { for (var i = 0; i < this.nodes.length; i++) { this.nodes[i].getAllObjects(returnedObjects); } for (var i = 0, len = objects.length; i < len; i++) { returnedObjects.push(objects[i]); } return returnedObjects; }; /* * Return all objects that the object could collide with */ this.findObjects = function(returnedObjects, obj) { if (typeof obj === "undefined") { console.log("UNDEFINED OBJECT"); return; } var index = this.getIndex(obj); if (index != -1 && this.nodes.length) { this.nodes[index].findObjects(returnedObjects, obj); } for (var i = 0, len = objects.length; i < len; i++) { returnedObjects.push(objects[i]); } return returnedObjects; }; /* * Insert the object into the quadTree. If the tree * excedes the capacity, it will split and add all * objects to their corresponding nodes. */ this.insert = function(obj) { if (typeof obj === "undefined") { return; } if (obj instanceof Array) { for (var i = 0, len = obj.length; i < len; i++) { this.insert(obj[i]); } return; } if (this.nodes.length) { var index = this.getIndex(obj); // Only add the object to a subnode if it can fit completely // within one if (index != -1) { this.nodes[index].insert(obj); return; } } objects.push(obj); // Prevent infinite splitting if (objects.length > maxObjects && level < maxLevels) { if (this.nodes[0] == null) { this.split(); } var i = 0; while (i < objects.length) { var index = this.getIndex(objects[i]); if (index != -1) { this.nodes[index].insert((objects.splice(i,1))[0]); } else { i++; } } } }; /* * Determine which node the object belongs to. -1 means * object cannot completely fit within a node and is part * of the current node */ this.getIndex = function(obj) { var index = -1; var verticalMidpoint = this.bounds.x + this.bounds.width / 2; var horizontalMidpoint = this.bounds.y + this.bounds.height / 2; // Object can fit completely within the top quadrant var topQuadrant = (obj.y < horizontalMidpoint && obj.y + obj.height < horizontalMidpoint); // Object can fit completely within the bottom quandrant var bottomQuadrant = (obj.y > horizontalMidpoint); // Object can fit completely within the left quadrants if (obj.x < verticalMidpoint && obj.x + obj.width < verticalMidpoint) { if (topQuadrant) { index = 1; } else if (bottomQuadrant) { index = 2; } } // Object can fix completely within the right quandrants else if (obj.x > verticalMidpoint) { if (topQuadrant) { index = 0; } else if (bottomQuadrant) { index = 3; } } return index; }; /* * Splits the node into 4 subnodes */ this.split = function() { // Bitwise or [html5rocks] var subWidth = (this.bounds.width / 2) | 0; var subHeight = (this.bounds.height / 2) | 0; this.nodes[0] = new QuadTree({ x: this.bounds.x + subWidth, y: this.bounds.y, width: subWidth, height: subHeight }, level+1); this.nodes[1] = new QuadTree({ x: this.bounds.x, y: this.bounds.y, width: subWidth, height: subHeight }, level+1); this.nodes[2] = new QuadTree({ x: this.bounds.x, y: this.bounds.y + subHeight, width: subWidth, height: subHeight }, level+1); this.nodes[3] = new QuadTree({ x: this.bounds.x + subWidth, y: this.bounds.y + subHeight, width: subWidth, height: subHeight }, level+1); }; }
参考文章：