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

,大家好，我是前端西瓜哥。,在上篇文章我们讨论了使用 脏矩形渲染，通过重渲染局部的图形来提优化 Canvas 的性能，将 GPU 密集转换为 CPU  密集。,CPU 密集在哪？,在需要遍历 所有的图形，判断它们是否和脏矩形发生相交（碰撞），保存发生碰抓给你的图形，将它们在局部进行重绘。,有没有办法减少需要遍历的图形，不要遍历全部的图形，而是少量的图形呢？有一个办法是使用 四叉树。,四叉树本质使用了 空间分割，给图形加 索引，将视口界面分割成多个区域，每个区域记住自己包含了哪些图形。,然后移动目标图形时，判断它落在哪个区域，取出所在区域的图形，这些图形集合就是和目标图形发生碰撞图形的超集。,这些区域外的图形就被我们排除了。,,算法实现的要点：,创建根节点，根节点保存区域的信息 x、y、width 和 height。,添加图形时，当一个节点内的节点数量大于阀值，就将整个区域均等切割为 4 等份的子节点，将图形从当前区域取出，重新放入到这些子节点内，从而将节点的归属划分为更小的区域。,（原来的区域转换为索引层，真正保存节点的地方放到了它的子区域上）,当我们提供一个碰撞矩形，我们从四叉树顶节点往下找，看是否有子节点。如果有，使用矩形碰撞算法找出它所在的子节点有哪些（可能有多个）。对这些子节点重复前面的操作，进行递归，找到所有的图形。,这些图形就是碰撞矩形可能相交的矩形，但相对所有图形，又不至于太多。,先看看经典算法实现。,算法我就不自己实现了，这里展示 quadtree-js 库的代码实现。,https://github.com/timohausmann/quadtree-js。,构造函数：,这是一个内部私有方法，当节点内图形过多，超过阀值，就将当前节点分裂成 4 个子节点：,计算某个图形落在当前节点的哪个子节点，拿到对应节点索引值数组：,插入一个图形，先看是否存在子节点，有的话说明当前节点变成了索引层，通过矩形碰撞算法找到所在的子节点，对这些子节点做插入操作：,返回目标图形所在节点下的所有图形：,非常简单，一些可以改善的能力。,请根据实际需要进行扩展。,处于节点内分割线上的图形，它是归属于多个子节点的，所以最终会同时放到它的多个子节点下，会花费内存。,极端情况下，一个非常大的图形，会保存在所有的节点下。,如果想节省内存，可以直接保存到当前节点上，不放到子节点上，可以减少内存使用，只是最后返回的被碰撞图形会多一点。因为图形可能只压在了两个子节点的交界线上，比如 A、 B ，但目标矩形是在其他的子节点 C 上，但因为它们来自同一个父节点，所以拿到了这个不可能在 C 的图形。,后者会更好一些，但如果一个图形刚好在画布中心，那每次取出的碰撞图形都会有它（这点可以通过松散四叉树解决）。,经典四叉树有个问题，就是如果图形的物理信息是比较动态的，当总是在边界附近时，就会发生频繁地将图形从一个节点取出并放到另个节点下。,对此我们可以额外设置一个出口边界。这个出口边界要比入口边界要大，只有当图形离开这个出口边界，才会更新提取图形到新的节点。,这样，当图形划分到另一个节点上时，就 需要移动较长的距离才能回到原来节点下，轻微地移动不会导致剧烈的更新。,通常出口边界边长为入口边界的两倍最佳，为什么不知道，经验之谈。,,简单介绍一些也使用了 空间分割 思想的算法。,R 树的思路是最接近四叉树的，它其实是另一种 减少图形遍历的方案，可以适用于高效剔除视口范围之外的图形。,R 树有个 star 数很多的库，叫做 RBush，感兴趣可以看看。,https://github.com/mourner/rbush。