快速检索碰撞图形：四叉树碰撞检测

大家好，我是前端西瓜哥。在上一篇文章中，我们讨论了使用脏矩形渲染通过重新渲染本地图形来优化Canvas的性能，将GPU密集型转换为CPU密集型。CPU密集型在哪里？当你需要遍历所有图形时，判断它们是否与脏矩形相交（碰撞），把已经帮你抓取的图形保存下来，在本地重新绘制。有没有办法减少需要遍历的图形，不是遍历所有图形，而是遍历少量图形？一种方法是使用四叉树。四叉树碰撞检测原理我们将区域的划分表示为“节点”，因为它是四叉树；画布上真实的图形称为“图形”。四叉树本质上是利用空间分割对图形进行索引，将视口界面划分为多个区域，每个区域记住自己包含了哪些图形。然后在移动目标图形的时候，判断它落在哪个区域，取出该区域的图形。这些图形集合是与目标图形相冲突的图形的超集。这些区域之外的图形被我们排除在外。算法实现要点：创建根节点，根节点保存区域的x、y、宽、高信息。添加图形时，当一个节点中的节点数大于阈值时，将整个区域平均切割成4个相等的子节点，将图形从当前区域中取出，并放回这些子节点中，使节点的归属地划分成更小的区域。（原来的区域转换为索引层，真正保存节点的地方放在它的子区域上）我们提供碰撞矩形的时候，从四叉树的最顶层节点往下看，看有没有子节点。如果是，则使用矩形碰撞算法找出它在哪些子节点中（可能不止一个）。对这些子节点重复前面的操作，递归，找到所有的图。这些图形是碰撞矩形可能相交的矩形，但相对于所有图形来说不会太多。四叉树碰撞检测算法首先看经典算法的实现。算法我就不自己实现了，这里是quadtree-js库的代码实现。https://github.com/timohausmann/quadtree-js。构造函数：functionQuadtree(bounds,max_objects,max_levels,level){this.max_objects=max_objects||10;//一个节点中的最大对象数this.max_levels=max_levels||4;//树的最大深度this.level=level||0;this.bounds=边界；//面积，结构为{x,y,width,height}this.objects=[];//保存图形的地方this.nodes=[];//4个子节点，只有达到阈值时才会创建}这是一个内部私有方法。当节点中的图过多超过阈值时，会将当前节点拆分为4个子节点：//Cut:generate4sub-nodesQuadtree.prototype.split=function(){varnextLevel=this.level+1,subWidth=this.bounds.width/2,subHeight=this.bounds.height/2,x=this.bounds.x,y=this.bounds.y;//右上角this.nodes[0]=newQuadtree({x:x+subWidth,y:y,width:subWidth,height:subHeight,},this.max_objects,this.max_levels,nextLevel);//左上角this.nodes[1]=newQuadtree({x:x,y:y,width:subWidth,height:subHeight,},this.max_objects,this.max_levels,nextLevel);//左下角this.nodes[2]=newQuadtree({x:x,y:y+subHeight,width:subWidth,height:subHeight,},this.max_objects,this.max_levels,nextLevel);//右下this.nodes[3]=newQuadtree({x:x+subWidth,y:y+subHeight,width:subWidth,height:subHeight,},this.max_objects,this.max_levels,nextLevel);};计算一个图落在当前节点的哪个子节点上，得到对应节点的Index值数组：//Findanbox落在哪个区域Quadtree.prototype.getIndex=function(pRect){varindexes=[],verticalMidpoint=this.bounds.x+this.bounds.width/2,horizo??ntalMidpoint=this.bounds.y+this.bounds.height/2;varstartIsNorth=pRect.yverticalMidpoint,endIsSouth=pRect.y+pRect.height>horizo??ntalMidpoint;//右上四边形if(startIsNorth&&endIsEast){indexes.push(0);}//左上四边形if(startIsWest&&startIsNorth){index.push(1);}//左下四边形if(startIsWest&&endIsSouth){indexes.push(2);}//右下四边形if(endIsEast&&endIsSouth){indexes.push(3);}returnindexes;};插入一个图，首先检查是否有子节点，如果有，说明当前节点已经成为索引层，通过矩形碰撞算法找到子节点，插入这些子节点：四叉树。prototype.insert=function(pRect){vari=0,索引;//如果有子节点，则将其插入到子节点中if(this.nodes.length){indexes=this.getIndex(pRect);//找到索引位置for(i=0;i=index;});返回返回对象；}；很简单，一些可以改进的能力。没有添加贴图功能，最终返回的图形都是box对象信息。我们可以考虑将其转化为insert(rect,data)以保存额外的信息，例如实际的形状对象或id。动态收缩：移除某个图后更新树结构，当发现图的个数低于阈值时，将图取出放到父节点上，销毁子节点；修改根节点的范围后，需要重置整棵树，如何高效重置；四叉树的图形类型通常是矩形，也可以是点、直线、曲线等，必要时可以考虑支持。请根据实际需要进行扩展。一些在节点内分界线上取舍的图属于多个子节点，所以最终会同时放在它的多个子节点下，会消耗内存。在极端情况下，所有节点下都会存储一个非常大的图。如果想节省内存，可以直接保存到当前节点，而不是放到子节点上，这样可以减少内存占用，但是最后返回的碰撞图形会比较多。因为图形可能只压在两个子节点的边界上，比如A和B，但是目标矩形是在另一个子节点C上，但是因为它们来自同一个父节点，所以不可能得到这个。图形。后者会好一些，但是如果一个图形刚好在画布的中心，那么每一个取出来的碰撞图形都会有它（这个可以通过松四叉树来解决）。松散四叉树经典四叉树有个问题，就是如果图的物理信息是比较动态的，当它总是在边界附近时，会频繁地把图从一个节点拿出来放到另一个节点下。为此，我们可以另外设置一个出口边界。出口边界大于入口边界，只有当图离开出口边界时，提取的图才会更新为新节点。这样，当图被划分到另一个节点时，需要移动很远的距离才能回到原来的节点，轻微的移动不会引起剧烈的更新。通常出口边界的边长是入口边界最优长度的两倍，不知道为什么，凭经验。其他空间分割思想的算法简单介绍一些同样使用空间分割思想的算法。跳表：有序链表。通过叠加大量的索引层，可以进行链表形式的“二分查找”，达到高效的O(logn)时间复杂度，但同时也带来了内存消耗。Redis中的有序集合（SortedSet）底层使用跳表，一个原因是可以高效获取区间内的数据集合；B+树：平衡二叉树，有点像跳表，但是树的层数最多三层，MySQL的索引实现使用B+树，因为层数少，可以减少IO操作；R树：R表示矩形。与前面两种单维范围搜索相比，R树可以进行高效的高维搜索。比如在地图中，我们可以通过R树将距离相近的高维图形组合成一个大节点。在搜索“2km以内的药店”时，如果落在某个大节点上，我们只需要遍历所有节点，而不用遍历整个城市，或者整个国家。R树的思想最接近四叉树。它实际上是另一种减少图形遍历的解决方案，可以应用于高效去除视口范围外的图形。R树有一个库，里面有很多star，叫做RBush，有兴趣的可以去看看。https://github.com/mourner/rbush。