最近在看canvas动画方面教程，里面提到了采用四叉树检测碰撞。之前也看到过四叉树这个名词，但是一直不是很懂。于是就又找了一些四叉树方面的资料看了看，做个笔记，就算日后忘了，也可以回来看看。
QuadTree四叉树顾名思义就是树状的数据结构，其每个节点有四个孩子节点，可将二维平面递归分割子区域。QuadTree常用于空间数据库索引，3D的椎体可见区域裁剪，甚至图片分析处理，我们今天介绍的是QuadTree最常被游戏领域使用到的碰撞检测。采用QuadTree算法将大大减少需要测试碰撞的次数，从而提高游戏刷新性能，
四叉树很简单，就是把一块2d的区域，等分成4份,如下图:我们把4块区域从右上象限开始编号，逆时针。
四叉树起始于单节点。对象会被添加到四叉树的单节点上。
当更多的对象被添加到四叉树里时，它们最终会被分为四个子节点。（我是这么理解的：下面的图片不是分为四个区域吗，每个区域就是一个孩子或子节点）然后每个物体根据他在2D空间的位置而被放入这些子节点中的一个里。任何不能正好在一个节点区域内的物体会被放在父节点。（这点我不是很理解，就这幅图来说，那根节点的子节点岂不是有五个节点了。）
如果有更多的对象被添加进来，那么每个子节点要继续划分（成四个节点）。
正如你看到的，每个节点仅包括几个物体。这样我们就可以明白前面所说的规则，例如，左上角节点里的物体是不可能和右下角节点里的物体碰撞的。所以我们也就没必要运行消耗很多资源的碰撞检测算法来检验他们之间是否会发生碰撞。
下面我们对四叉树进行实现：主要代码：（代码是从整个四叉树类里面拷贝出来的，所以带有this，大家不要无视就好，末尾附有完整的代码）
functionQuadTree(boundBox,lvl){varmaxObjects=10;this.bounds=boundBox||{x:0,y:0,width:0,height:0};varobjects=[];this.nodes=[];varlevel=lvl||0;varmaxLevels=5;}maxObjects是每个节点能容纳的最多对象超过则分割4个节点,我们并不是事先就分好格子，而是在插入对象的时候才进行划分。
maxLevels是四叉树的最大层数超过则不再划分从根节点开始最多6层。
level：当前层数
objects:当前节点内的待检测的对象。
bounds：当前节点所表示的2d区域的范围
nodes:4个子节点队列。
四叉树每个节点的面积可以为任意形状。然后，我们会使用五个四叉树里会用到的方法，分别为：clear,split,getIndex,insert和retrieve。
functionclear(){objects=[];for(vari=0;i functionsplit(){//Bitwiseor[html5rocks]varsubWidth=(this.bounds.width/2)|0;varsubHeight=(this.bounds.height/2)|0;this.nodes[0]=newQuadTree({x:this.bounds.x+subWidth,y:this.bounds.y,width:subWidth,height:subHeight},level+1);this.nodes[1]=newQuadTree({x:this.bounds.x,y:this.bounds.y,width:subWidth,height:subHeight},level+1);this.nodes[2]=newQuadTree({x:this.bounds.x,y:this.bounds.y+subHeight,width:subWidth,height:subHeight},level+1);this.nodes[3]=newQuadTree({x:this.bounds.x+subWidth,y:this.bounds.y+subHeight,width:subWidth,height:subHeight},level+1);}Split方法，就是用来将节点分成相等的四份面积，并用新的边界来初始化四个新的子节点。 functiongetIndex(obj){varindex=-1;varverticalMidpoint=this.bounds.x+this.bounds.width/2;varhorizontalMidpoint=this.bounds.y+this.bounds.height/2;//ObjectcanfitcompletelywithinthetopquadrantvartopQuadrant=(obj.y 比如当前区域是Rectange(0,0,600,600)待检测矩形是Rectangel(0,0,30,30)那么他就在左上象限index=1如果是Rectange(400,400,30,30)那么他就在右下象限index=3 functioninsert(obj){if(typeofobj==="undefined"){return;}if(objinstanceofArray){for(vari=0,len=obj.length;i 一旦对象添加上后，要看看这个节点会不会分裂，可以通过检查对象被加入节点后有没有超过一个节点最大容纳对象的数量。分裂起源于节点可以插入任何对象，这个对象只要符合子节点都可以被加入。否则就加入到父节点。 functionretrieve(returnedObjects,obj){if(typeofobj==="undefined"){console.log("UNDEFINEDOBJECT");return;}varindex=this.getIndex(obj);if(index!=-1&&this.nodes.length){this.nodes[index].findObjects(returnedObjects,obj);}for(vari=0,len=objects.length;i