本文实例讲述了JS实现的四叉树算法。分享给大家供大家参考，具体如下：

成都创新互联2013年至今，是专业互联网技术服务公司，拥有项目网站制作、成都网站设计网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元台山做网站,已为上家服务,为台山各地企业和个人服务,联系电话:18982081108

最近在看canvas动画方面教程，里面提到了采用四叉树检测碰撞。之前也看到过四叉树这个名词，但是一直不是很懂。于是就又找了一些四叉树方面的资料看了看，做个笔记，就算日后忘了，也可以回来看看。

QuadTree四叉树顾名思义就是树状的数据结构，其每个节点有四个孩子节点，可将二维平面递归分割子区域。QuadTree常用于空间数据库索引，3D的椎体可见区域裁剪，甚至图片分析处理，我们今天介绍的是QuadTree最常被游戏领域使用到的碰撞检测。采用QuadTree算法将大大减少需要测试碰撞的次数，从而提高游戏刷新性能，

四叉树很简单，就是把一块2d的区域，等分成4份,如下图:    我们把4块区域从右上象限开始编号， 逆时针。

四叉树起始于单节点。对象会被添加到四叉树的单节点上。

当更多的对象被添加到四叉树里时，它们最终会被分为四个子节点。（我是这么理解的：下面的图片不是分为四个区域吗，每个区域就是一个孩子或子节点）然后每个物体根据他在2D空间的位置而被放入这些子节点中的一个里。任何不能正好在一个节点区域内的物体会被放在父节点。（这点我不是很理解，就这幅图来说，那根节点的子节点岂不是有五个节点了。）

如果有更多的对象被添加进来，那么每个子节点要继续划分（成四个节点）。

正如你看到的，每个节点仅包括几个物体。这样我们就可以明白前面所说的规则，例如，左上角节点里的物体是不可能和右下角节点里的物体碰撞的。所以我们也就没必要运行消耗很多资源的碰撞检测算法来检验他们之间是否会发生碰撞。

下面我们对四叉树进行实现：

主要代码：（代码是从整个四叉树类里面拷贝出来的，所以带有this，大家不要无视就好，末尾附有完整的代码）

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;
}

本文名称：JS实现的四叉树算法详解-创新互联
本文网址：http://cdweb.net/article/cdcgds.html