本文主要介绍了JS实现的四叉树算法，并简要分析了四叉树的相关概念、原理、实现方法和操作注意事项。有需要的可以参考一下。

本文描述了用JS实现的四叉树算法。分享给你，供你参考，如下：

最近看了一个画布动画的教程，里面提到了用四叉树检测碰撞。我以前见过四叉树这个术语，但不是很理解。于是找了一些关于四叉树的资料，做了笔记。就算以后忘了，也可以回来看看。

四叉树四叉树，顾名思义，是一种树状的数据结构。每个节点有四个子节点，可以递归地将一个二维平面划分为子区域。四叉树经常用于空间数据库索引、3D椎体可视区域裁剪，甚至图像分析和处理。今天介绍游戏领域最常用的四叉树碰撞检测。四叉树算法将大大减少需要测试的碰撞次数，从而提高游戏刷新性能。

四叉树很简单，就是把一个2d区域分成四等份，如下图所示：我们从右上象限开始给四个区域编号，逆时针方向。

四叉树从单个节点开始。对象被添加到四叉树的单个节点中。

当更多的对象被添加到四叉树中时，它们最终将被分成四个子节点。(我是这样理解的：下图不就是分成四个区域，每个区域都是一个子节点或者子节点)然后每个对象按照它在2D空间中的位置放入这些子节点中的一个。任何不能完全位于节点区域的东西都将被放置在父节点中。(这个我不太懂。就这张图片而言，该根节点有五个子节点。)

如果添加了更多的对象，那么每个子节点应该继续被分割(分成四个节点)。

如您所见，每个节点只包含几个对象。这样，我们就能理解前面提到的规则。例如，左上角节点中的对象不可能与右下角节点中的对象发生碰撞。所以我们不需要运行消耗大量资源的碰撞检测算法来检查它们之间是否会发生碰撞。

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

主代码：(代码是从整个四叉树类复制过来的，所以有这个。不要忽略就好，完整代码附在最后)

函数四叉树(boundBox，lvl) {

var maxObjects=10

this.bounds=boundBox || {

x: 0，

y: 0，

宽度：0，

高度：0

};

var objects=[]；

this . nodes=[]；

var level=lvl | | 0；

var max levels=5；

}

MaxObjects是如果每个节点可以容纳的对象的最大数量超过，那么它将划分四个节点。我们不预先划分网格，而是在插入对象时进行划分。

MaxLevels是四叉树的最高级别。如果超过最大级别，则不会从根节点开始划分为6个级别。

级别：当前级别。

Objects:当前节点中要检测的对象。

Bounds:由当前节点表示的2d区域的范围。

节点：4个子节点队列。

四叉树每个节点的面积可以是任意形状。然后，我们会用到四叉树中会用到的五种方法，分别是：clear、split、getIndex、insert和retrieve。

函数clear() {

objects=[]；

for(var I=0；I this . nodes . length；i ) {

this.nodes[i]。clear()；

}

this . nodes=[]；

};

清除功能是通过一个循环清除四叉树所有节点的所有对象。

函数拆分(){

//按位or [html5rocks]

var subWidth=(this . bounds . width/2)| 0；

var sub height=(this . bounds . height/2)| 0；

this.nodes[0]=新的四叉树({

x: this.bounds.x子宽度，

y: this.bounds.y，

宽度：子宽度，

高度：亚高度

}，一级)；

this.nodes[1]=新的四叉树({

x: this.bounds.x，

y: this.bounds.y，

宽度：子宽度，

高度：亚高度

}，一级)；

this.nodes[2]=新的四叉树({

x: this.bounds.x，

y: this.bounds.y子高度，

宽度：子宽度，

高度：亚高度

}，一级)；

this.nodes[3]=新的四叉树({

x: this.bounds.x子宽度，

y: this.bounds.y子高度，

宽度：子宽度，

高度：亚高度

},一级);

}

裂开方法，就是用来将节点分成相等的四份面积，并用新的边界来初始化四个新的子节点。

函数getIndex(obj) {

定义变量指数=-1;

var垂直中点=this。界限。x这个。界限。宽度/2；

var水平中点=this。界限。你这个。界限。身高/2；

//对象可以完全适合上象限

var上象限=(obj。y水平中点对象。y obj。高度水平中点)；

//对象可以完全适合底部象限

var底部象限=(obj。y水平中点)；

//对象可以完全适合左象限

if (obj.x verticalMidpoint

obj。x对象。宽度垂直中点){

如果(顶部象限){

指数=1;

}

else if (bottomQuadrant) {

指数=2;

}

}

//对象可以在合适的范围内完全修复

else if (obj.x verticalMidpoint) {

如果(顶部象限){

索引=0;

}

else if (bottomQuadrant) {

指数=3;

}

}

回报指数；

};

getIndex方法是个四叉树的辅助方法，在四叉树里，他决定了一个节点的归属，通过检查节点属于哪个象限。(最上面第一幅图不是逆时针在一个面积里划分了四块面积，上面标示了他们的序号，这个方法就是算在一个父节点里他的子节点的序号)

比如当前区域是矩形(0,0,600,600)待检测矩形是矩形(0,0,30,30)那么他就在左上象限指数=1如果是矩形(400,400,30,30)那么他就在右下象限指数=3

函数插入（对象){

if (typeof obj==='undefined') {

返回；

}

如果(数组的对象实例){

for(变量i=0，长度len=对象长度我leni ) {

这个。insert(obj[I])；

}

返回；

}

if (this.nodes.length) {

var指数=这个。getindex(obj)；

//只有当对象完全适合时，才将其添加到子节点

//一个以内

如果（索引！=-1) {

this.nodes[index].insert(obj)；

返回；

}

}

对象。push(obj)；

//防止无限拆分

如果(对象。长度最大对象级别最大级别){

if (this.nodes[0]==null) {

这个。split()；

}

var I=0；

while (i objects.length) {

var指数=这个。getindex(objects[I])；

如果（索引！=-1) {

this.nodes[index].insert((objects.splice(i，1))[0])；

}

否则{

我；

}

}

}

};

每次插入一个对象我们都先看看当前节点有没有子节点如果有我们就插入子节点。一直检测到他没有子节点为止我们就把对象插入到这个节点，如果这个节点的对象数量10个并且当前节点的层数最高级别我们就把节点继续划分四个子节点。然后把当前对象循环删除并插入子节点。如果对象在中心线上，getIndex会返回-1, 所以这些对象会被插入到父节点上面。

一旦对象添加上后，要看看这个节点会不会分裂，可以通过检查对象被加入节点后有没有超过一个节点最大容纳对象的数量。分裂起源于节点可以插入任何对象，这个对象只要符合子节点都可以被加入。否则就加入到父节点。

函数retrieve(returnedObjects，obj) {

if (typeof obj==='undefined') {

console.log('未定义的对象');

返回；

}

var指数=这个。getindex(obj)；

如果（索引！=-1 this.nodes.length) {

this.nodes[index].findObjects(returnedObjects，obj)；

}

for (var i=0，len=objects.length我leni ) {

返回的对象。push(objects[I])；

}

return返回的对象

};

最后一个四叉树的方法就是恢复方法，他返回了与指定节点可能发生碰撞的所有节点（就是不停寻找与所给节点在同样象限的节点)。这个方法成倍的减少碰撞检测数量。

四叉树的代码就到这里为止了。

完整的代码如下：

完整的代码中恢复就是查找对象。

/**

*四叉树对象。

*

*象限索引编号如下：

* |

* 1 | 0

* - -

* 2 | 3

* |

*/

函数四叉树(boundBox，lvl) {

var maxObjects=10

this.bounds=boundBox || {

x: 0，

y: 0，

宽度：0,

高度：0

};

var objects=[]；

这个。节点=[]；

var level=lvl | | 0；

var最大水平=5；

/*

*清除对象的四叉树和所有节点

*/

this.clear=function() {

objects=[]；

for(var I=0；我这个。节点。长度；i ) {

this.nodes[i].clear()；

}

这个。节点=[]；

};

/*

*获取四叉树中的所有对象

*/

这个。getallobjects=function(返回的对象){

for(var I=0；我这个。节点。长度；i ) {

this.nodes[i].getAllObjects(返回的对象)；

}

for (var i=0，len=objects.length我leni ) {

返回的对象。push(objects[I])；

}

return返回的对象

};

/*

*返回该对象可能碰撞的所有对象

*/

这个。find objects=function(返回的对象，obj) {

if (typeof obj==='undefined') {

console.log('未定义的对象');

返回；

}

var指数=这个。getindex(obj)；

如果（索引！=-1 this.nodes.length) {

this.nodes[index].findObjects(returnedObjects，obj)；

}

for (var i=0，len=objects.length我leni ) {

返回的对象。push(objects[I])；

}

return返回的对象

};

/*

*将对象插入四叉树。如果树

*超出容量时，它会拆分并添加所有

*对象到它们相应的节点。

*/

this.insert=function(obj) {

if (typeof obj==='undefined') {

返回；

}

如果(数组的对象实例){

for(变量i=0，长度len=对象长度我leni ) {

这个。insert(obj[I])；

}

返回；

}

if (this.nodes.length) {

var指数=这个。getindex(obj)；

//只有当对象完全适合时，才将其添加到子节点

//一个以内

如果（索引！=-1) {

this.nodes[index].insert(obj)；

返回；

}

}

对象。push(obj)；

//防止无限拆分

如果(对象。长度最大对象级别最大级别){

if (this.nodes[0]==null) {

这个。split()；

}

var I=0；

while (i objects.length) {

var指数=这个。getindex(objects[I])；

如果（索引！=-1) {

this.nodes[index].insert((objects.splice(i，1))[0])；

}

否则{

我；

}

}

}

};

/*

*确定对象属于哪个节点。-1表示

*对象不能完全放入节点，并且是一部分

*当前节点的

*/

this.getIndex=function(obj) {

定义变量指数=-1;

var垂直中点=this。界限。x这个。界限。宽度/2；

var水平中点=this。界限。你这个。界限。身高/2；

//对象可以完全适合上象限

var上象限=(obj。y水平中点对象。y obj。高度水平中点)；

//对象可以完全适合底部象限

var底部象限=(obj。y水平中点)；

//对象可以完全适合左象限

if (obj.x verticalMidpoint

obj。x对象。宽度垂直中点){

如果(顶部象限){

指数=1;

}

else if (bottomQuadrant) {

指数=2;

}

}

//对象可以在合适的范围内完全修复

else if (obj.x verticalMidpoint) {

如果(顶部象限){

索引=0;

}

else if (bottomQuadrant) {

指数=3;

}

}

回报指数；

};

/*

*将节点拆分为四个子节点

*/

this.split=function() {

//按位或者[html5rocks]

var subWidth=(this。界限。宽度/2)| 0；

var子高度=(this。界限。高度/2)| 0；

this.nodes[0]=新的四叉树({

x: this.bounds.x子宽度，

y: this.bounds.y，

宽度：子宽度，

高度：亚高度

},一级);

this.nodes[1]=新的四叉树({

x: this.bounds.x，

y: this.bounds.y，

宽度：子宽度，

高度：亚高度

},一级);

this.nodes[2]=新的四叉树({

x: this.bounds.x，

y: this.bounds.y子高度，

宽度：子宽度，

高度：亚高度

},一级);

this.nodes[3]=新的四叉树({

x: this.bounds.x子宽度，

y: this.bounds.y子高度，

宽度：子宽度，

高度：亚高度

},一级);

};

}

参考文章：

快速提示：使用四叉树来检测2D空间中可能的碰撞

更多关于Java脚本语言相关内容感兴趣的读者可查看本站专题： 《JavaScript数学运算用法总结》 、 《JavaScript数据结构与算法技巧总结》 、 《JavaScript数组操作技巧总结》 、 《JavaScript排序算法总结》 、 《JavaScript遍历算法与技巧总结》 、 《JavaScript查找算法技巧总结》 及《JavaScript错误与调试技巧总结》

希望本文所述对大家Java脚本语言程序设计有所帮助。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。