JS/HTML5常用算法之碰撞检测和包围盒检测算法的示例分析-创新互联

小编给大家分享一下JS/HTML5常用算法之碰撞检测和包围盒检测算法的示例分析，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！

具体如下：

概述

分离轴定理是一项用于检测碰撞的算法。其适用范围较广，涵盖检测圆与多边形，多边形与多边形的碰撞；缺点在于无法检测凹多边形的碰撞。本demo使用Js进行算法实现，HTML5 canvas进行渲染。

详细

一、准备工作，熟悉分离轴定理 算法原理

从根本上来讲，分离轴定理（以及其他碰撞算法）的用途就是去检测并判断两个图形之间是否有间隙。分离轴定理中用到的方法使算法本身显得十分独特。

我所听到过分离轴定理的最好类比方式是这样的：

假想你拿一个电筒从不同的角度照射到两个图形上，那么会有怎样的一系列的阴影投射到它们之后的墙壁上呢？

如果你用这个方式从每一个角度上对这两个图形进行处理，并都找不到任何的间隙，那么这两个图形就一定接触。如果你找到了一个间隙，那么这两个图形就显而易见地没有接触。

从编程的角度来讲，从每个可能的角度上去检测会使处理变得十分密集。不过幸运的是，由于多边形的性质，你只需要检测其中几个关键的角度。

你需要检测的角度数量就正是这个多边形的边数。也就是说，你所需检测的角度大数量就是你要检测碰撞的两个多边形边数之和。举个例子，两个五边形就需要检测10个角度。

这是一个简易但比较啰嗦的方法，以下是基本的步骤：

步骤一：从需要检测的多边形中取出一条边，并找出它的法向量（垂直于它的向量），这个向量将会是我们的一个“投影轴”。

步骤二：循环获取第一个多边形的每个点，并将它们投影到这个轴上。（记录这个多边形投影到轴上的最高和最低点）

步骤三：对第二个多边形做同样的处理。

步骤四：分别得到这两个多边形的投影，并检测这两段投影是否重叠。

如果你发现了这两个投影到轴上的“阴影”有间隙，那么这两个图形一定没有相交。但如果没有间隙，那么它们则可能接触，你需要继续检测直到把两个多边形的每条边都检测完。如果你检测完每条边后，都没有发现任何间隙，那么它们是相互碰撞的。

这个算法基本就是如此的。

顺带提一下，如果你记录了哪个轴上的投影重叠值最小（以及重叠了多少），那么你就能用这个值来分开这两个图形。

那么如何处理圆呢？

在分离轴定理中，检测圆与检测多边形相比，会有点点奇异，但仍然是可以实现的。

最值得注意的是，圆是没有任何的边，所以是没有明显的用于投影的轴。但它有一条“不是很明显的”的投影轴。这条轴就是途经圆心和多边形上离圆心最近的顶点的直线。

在这以后就是按套路遍历另一个多边形的每条投影轴，并检测是否有投影重叠。

噢，对了，万一你想知道如何把圆投影到轴上，那你只用简单地把圆心投影上去，然后加上和减去半径就能得到投影长度了。

二、完整实例：

  
  
  
  


是否碰撞：否

这里使用在线HTML/CSS/JavaScript代码运行工具：http://tools.jb51.net/code/HtmlJsRun 测试上述代码运行结果如下：

以上是“JS/HTML5常用算法之碰撞检测和包围盒检测算法的示例分析”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注创新互联行业资讯频道！