碰撞检测一文讲透：多边形碰撞检测有哪些方法？
Author：zhoulujun Date：
多边形碰撞检测是计算机图形学和游戏开发中的一项重要技术，它涉及到判断两个多边形是否有重叠的部分。
简单碰撞检测
简单的碰撞检测非常简单，比如矩形和圆形
对于不规则的物体，比如运动的小人等，我们可以通过抽象成一个矩形，使得这个矩形恰好可以包裹这个物体，在进行碰撞检测时，就可以使用这个矩形来代替实际的物体。这种方法，实际上就是通过抽象，将复杂简单化，对于精确度不是那么高的动画或者游戏，我们直接使用这种外接图形来检测就可以了。在抽象图形的时候，我们要根据具体的物体，比如小人可以抽象成矩形，太阳就要抽象成圆了，把具体的物体抽象的跟它相似的形状，这样在检测时就会更加准确。
因为矩形和圆形这两种形状的碰撞检测速度是最快的。其中矩形包围盒又可以分为轴对齐包围盒（AABB, Axis Aligned Bounding Box）与转向包围盒（OBB, Oriented Bounding Box）。AABB与OBB的区别在于，AABB中的矩形的其中一条边和坐标轴平行，OBB的计算复杂度要高于AABB。
矩形碰撞检测
对于两个图形是否发生碰撞，我们只需要判断它们是否存在相交的部分，如果存在相交的部分，那么则可以认为是发生了碰撞，否则就没有。
实现矩形碰撞检测的方法很简单，只需要比较两个矩形的位置和大小即可
矩形碰撞原理
矩形要相交，首先 x 的范围上就应该有交集，等价于判断两个线段是否有交点。
先看看什么情况下它们 不会相交？答案是：一条线段的右端点在另一条线的的左端点的左侧。
换成举行
所以相交的逻辑是：
!(rect1.x + rect1.width < rect2.x || rect1.x > rect2.x + rect2.width )
转换一下，就是：
rect1.x <= rect2.x + rect2.width &&rect1.x + rect1.width >= rect2.x
y 维度同理，为：
rect1.y <= rect2.y + rect2.height && rect1.y + rect1.height >= rect2.y
所以最终算法实现为：
function rectCollide(rect1, rect2) {
return (rect1.x + rect1.width >= rect2.x &&// 如果矩形1的右边界大于等于矩形2的左边界，
rect1.x <= rect2.x + rect2.width &&//且矩形1的左边界小于等于矩形2的右边界，
rect1.y + rect1.height >= rect2.y &&//且矩形1的下边界大于等于矩形2的上边界
rect1.y <= rect2.y + rect2.height) //且矩形1的上边界小于等于矩形2的下边界
return true;
}如果矩形有旋转，参考：矩形包围盒碰撞检测 https://heptaluan.github.io/2020/11/28/Essay/31/
圆形碰撞检测
圆形碰撞检测的实现方法是比较简单的，只需要计算两个圆形的距离即可。
function circleCollide(circle1, circle2) {
var dx = circle1.x - circle2.x;
var dy = circle1.y - circle2.y;
var distance = Math.sqrt(dx * dx + dy * dy);
return distance < circle1.radius + circle2.radius;
}圆形与矩形碰撞检测
怎样判断平面上一个矩形和一个圆形是否有重叠？
第一种
最终代码
function detectCollision(rect, circle) {
var closePointX, closePointY
if(circle.x < rect.x) {
closePointX = rect.x
} else if(circle.x > rect.x + rect.w) {
closePointX = rect.x + rect.w
} else {
closePointX = circle.x
}
if(circle.y < rect.y) {
closePointY = rect.y
} else if(circle.y > rect.y + rect.h) {
closePointY = rect.y + rect.h
} else {
closePointY = circle.y
}
return distance(circle.x, circle.y, closePointX, closePointY) < circle.r
}
function distance(x1, y1, x2, y2) {
return Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2))
}更多的，推荐阅读：https://www.zhihu.com/question/24251545
多边形碰撞检测（不规则形状））
在游戏或者其他图形类应用中都会有很多复杂的图形，比如下图：
以下是一些常用的多边形碰撞检测方法：
GJK算法：通过构建一个单纯形，逐步将空间分成两半，直到找到所需的点来判断多边形是否相交。GJK算法在处理过程中可以更快地缩小搜索空间，适合实时性要求高的应用（可能会产生不精确的）。
分离轴定理（SAT）：基于几何投影的思想，适用于凸多边形，通过检查多边形在每条边的中垂线上的投影是否重叠来判断是否发生碰撞
AABB碰撞检测：首先使用轴对齐包围盒（AABB）进行粗略的碰撞检测，然后对可能发生碰撞的对象使用更精确的方法进行检测，由于只考虑了物体的边界，可能会忽略内部的碰撞，不适用于需要高精度碰撞检测的场景
OBB碰撞检测：通过使用最小旋转包围盒（OBB），可以更有效地处理旋转和缩放的对象之间的碰撞检测。计算复杂度高：需要计算物体的最小旋转包围盒，以及进行更复杂的碰撞检测过程，计算量较大
AABB碰撞检测
碰撞检测可分为 Broad Phase （粗略检测）与 Narrow Phase （精细检测） 两个阶段。粗略检测阶段可直接比较两个物体的AABB包围框是否碰撞以节省计算量和时间。3D 物理引擎提供了碰撞检测算法，其中大多数也都是基于包围体。
简单理解，就是换成矩形碰撞算法就行了
这个MDN说的非常详细了： https://developer.mozilla.org/zh-CN/docs/Games/Techniques/3D_collision_detection
OBB算法
OBB (Oriented Bounding Box)是指定向包围盒，它是一种用于近似物体形状的矩形体，可以任意旋转以更好地拟合被包围的对象。OBB 通常用于游戏开发和其他需要高效碰撞检测的应用中。OBB 可以被视为一个中心点、三个正交轴（通常代表它的宽度、高度和深度方向）以及半径（每个维度的一半长度）。
OBB 碰撞检测 经常使用 SAT 来实现，通过检查一系列轴上的投影是否重叠来判断两个 OBB 是否相交。
凸多边形碰撞检测的分离轴算法（SAT）
在精细检测中，SAT（Separating Axis Theorem，分离轴定理）碰撞检测算法直观且高效，它的原理清晰易懂，即若两个物体没有发生碰撞，则总会存在一条直线，能将两个物体分离。分离轴适用的是凸多边形之间的检测，不适用于凹多边形，凹多边形的检测，可以通过算法将凹多边形分割成多个凸多边形再进行计算。
分离轴检测
如果两个物体没有发生碰撞，那么就肯定会有一条线，能将两个物体分离开，我们称这条线为分离轴。如下图所示：
从图中可以看出，左边的两个矩形没有发生碰撞，中间的分离轴将其分隔开来,而右边的两个矩形发生碰撞，找不到一条直线将其分割，那么对于这两种情况，我们应该怎么去判断呢？
图中用不同颜色标注出了ABCD，EFGH几个坐标点，这几个坐标点是矩形的每一个角所在的坐标点在X轴上的投影，我们可以清晰的看出，左边的矩形所有投影可以分为投影蓝为[A,D]，右边的矩形所有投影可以分为投影红为[E,H]。对于左边对分离轴分隔开的投影，投影蓝与投影红是没有交集的，也就是交集为空，没有相同的地方，但对于右边的两个矩形投影来说，[C,D]与[E,F]区间是有一定的交集，交集不为空集，则两个矩形相交。
SAT的核心
对于SAT来说，核心是找到分离轴，也就是找到交集为空的投影，所以我们要做的就是找到一条将两个凸多边形一分为二的轴。
如何找到这个轴
想要找到真正的分离轴，我们就需要先找到所有的潜在轴，然后再在每条潜在轴上玩投影，检测空集。但是对于两个不规则的凸多边形来说，潜在轴太多了，我随便画条线，那都能叫潜在轴。所以我们这时候需要知道一点东西，那就是凸多边形的性质。
我们直接打开浏览器百度一下：凸多边形的性质。我们可以直接的看到一条凸多边形的性质为----》》
如果把一个凸多边形的所有边中，有一条边向两边无限延长成为一条直线时，其他各边（各角）都在此直线的同旁。
有了这个性质，我们可以得出来一个结论：我们所要检测的潜在轴是两个凸多边形的边
这个时候第一个问题就解决了，那么我们如何检测多边形在每条边上的投影呢？这时候就要引入一个概念为法向量
图中用数字标明了8个线段，分别是1-5和6-8，其中右方的蓝色直线即为线段5的投影轴，也就是线段5的法向量，线段5即为潜在轴，蓝色直线即为线段5的投影轴，那么我们如何求得线段与投影轴呢？
图中可知线段的两个顶点，P1与P2，那么我们可以用向量来表示一个线段
对于线段P1P2就可以使用P1与P2做向量相减得到。
我们怎么判断这条轴上的投影没有空集
其实很简单，我们可以看到两个图中，都有着Amin，Amax和Bmin，Bmax，意思就是我们只需要判断Amax到Amin加上Bmax到Bmin小于Bmax到Amin就可以判断到投影有交集，反之没有了。
推荐阅读：2D碰撞检测算法——SAT https://zhuanlan.zhihu.com/p/710005447
GJK算法
GJK是由Gilbert，Johnson，Keerthi 三位前辈发明的，用来计算两个凸多面体之间的碰撞检测，以及最近距离。GJK算法可以在O(M+N)的时间复杂度内，检测出碰撞，算法在每次迭代的过程中，都会优先选择靠近原点的方向，因此收敛速度会很快。算法的证明过程比较复杂，但是原理还是比较容易理解的。
相比 SAT 算法，GJK 算法更加高效。 GJK算法的核心就是闵可夫斯基差，即若两个多边形相交，则它们的闵可夫斯基差必然包括原点。
闵可夫斯基差是计算两个几何体之间距离的一种强大工具，尤其是在处理凸多边形时。
闵可夫斯基差 ，三言两语解释不清，请自行搜索！
可以推荐阅读：2D碰撞检测算法——GJK https://zhuanlan.zhihu.com/p/710821113
完全不规则图像
有一些场景的图像使用完全不规则的图像，这种图形的检测一般使用像素级的检测，简单说就是判断两个图像是否有非透明的像素点有重合如果有则说明两个图形有碰撞,比如判断下面两只小兔子是否碰撞
这个一般都是用工具来做。
参考文章：
碰撞检测的向量实现 https://juejin.cn/post/6844903928501387277
几何算法：矩形碰撞和包含检测算法 https://blog.csdn.net/fe_watermelon/article/details/129600383
Html5 Canvas动画基础（碰撞检测） https://juejin.cn/post/6844903719650213901
常见的2D碰撞检测 https://github.com/FridaS/blog/issues/5
canvas-核心技术-如何实现碰撞检测 https://snayan.github.io/post/how_to_detect_collision/
SAT分离轴碰撞原理分析 https://juejin.cn/post/6986601715382353934
碰撞检测之分离轴定理算法讲解 https://blog.csdn.net/yorhomwang/article/details/54869018
碰撞检测之OBB https://busyogg.github.io/article/3c9cb66ca768/
多边形碰撞检测算法 https://blog.csdn.net/gghhb12/article/details/133179976
浅谈 Canvas 渲染引擎设计 https://github.com/yinguangyao/blog/issues/84
转载本站文章《碰撞检测一文讲透：多边形碰撞检测有哪些方法？》,
请注明出处：https://www.zhoulujun.cn/html/theory/Mathematics/Geometry/9232.html