3.C++实现2D凸多边形碰撞检测算法（SAT分离轴碰撞）

分离轴的定义

分离轴是一个向量，可以理解为一条平行于多边形边的线（或其法线方向）。在二维空间中，分离轴通常是一条直线，它将两个形状分开，使得它们在这条直线上的投影没有重叠部分。

从下图可以看出，左边的两个矩形没有发生碰撞，中间的分离轴将其分隔开来,而右边的两个矩形发生碰撞，找不到一条直线将其分割。

那么对于这两种情况，我们应该怎么去判断呢？
下图用不同颜色标注出了ABCD，EFGH几个坐标点，这几个坐标点是矩形的每一个角所在的坐标点在X轴上的投影，我们可以清晰的看出，左边的矩形所有投影可以分为投影蓝为[A,D]，右边的矩形所有投影可以分为投影红为[E,H]。对于左边对分离轴分隔开的投影，投影蓝与投影红是没有交集的，也就是交集为空，没有相同的地方，但对于右边的两个矩形投影来说，[C,D]与[E,F]区间是有一定的交集，交集不为空集，则两个矩形相交。

对于SAT来说，核心是找到分离轴，也就是找到交集为空的投影，所以我们要做的就是找到一条将两个凸多边形一分为二的轴。
如果我们想要证明或者说是解决SAT的核心理念，我们这里就会出现两个问题：1.我们去哪找这轴？2.我们怎么判断这条轴上的投影没有空集？

• 第一个问题。如何找到这个轴？
  我们想要找到真正的分离轴，我们就需要先找到所有的潜在轴，然后再在每条潜在轴上玩投影，检测空集。但是对于两个不规则的凸多边形来说，潜在轴太多了，我随便画条线，那都能叫潜在轴。所以我们这时候需要知道一点东西，那就是凸多边形的性质。如果把一个凸多边形的所有边中，有一条边向两边无限延长成为一条直线时，其他各边（各角）都在此直线的同旁。
  有了这个性质，我们可以得出来一个结论：我们所要检测的潜在轴是两个凸多边形的边。
• 第二个问题。那么我们如何检测多边形在每条边上的投影呢？
  这时候就要引入一个概念为法向量
  
  图中用数字标明了8个线段，分别是1-5和6-8，其中右方的蓝色直线即为线段5的投影轴，也就是线段5的法向量，线段5即为潜在轴，蓝色直线即为线段5的投影轴，那么我们如何求得线段与投影轴呢？图中可知线段的两个顶点，P1与P2，那么我们可以用向量来表示一个线段

对于线段P1P2就可以使用P1与P2做向量相减得到。代码为

// 定义向量结构体
struct Vector {
  float x;
  float y;
};

// 向量相减函数
Vector sub(Vector v1, Vector v2) 
{
  Vector result;
  result.x = v1.x - v2.x;
  result.y = v1.y - v2.y;
  return result;
}

sub为一个向量相减的静态方法，将P1与P2传入即可获得线段P1P2.具体的vector类可以查看源码。有了线段之后，去求投影轴，投影轴其实就是法向量，所以我们直接用相减得到的结果来求法向量。

// 计算法向量
Vector normL(Vector v)
{
  Vector result;
  result.x = v.y;
  result.y = -v.x;
  return result;
}

normL即为Vector类中求法向量的方法。法向量相信很多人都清楚，就是垂直于原向量的玩意，具体的法向量的性质这里就不做过多的解释了。

那么我们也就可以获取一个多边形每一条边以及每一条边所对应的法向量了：

// 获取多边形的边
std::vector<Vector> getSides(std::vector<Vector> _path) 
{
  std::vector<Vector> sides;
  Vector pre = _path[0];
  int len = _path.size();
  if (len >= 3)
  {
    for (int i = 1; i < len;++)
    {
      Vector cur = _path[i];
      sides.push_back(sub(cur, pre));
      pre = cur;
    }
    sides.push_back(sub(_path[0], _path[len - 1]));
  }
  return sides;
}

path为待检测多边形的路径集合，即每个顶点的坐标集合，如上图所示求的所有边与法向量。

那么现在来到第二个问题，我们怎么判断这条轴上的投影没有空集？

其实很简单，我们可以看到两个图中，都有着Amin，Amax和Bmin，Bmax，意思就是我们只需要判断Amax到Amin加上Bmax到Bmin小于Bmax到Amin就可以判断到投影有交集，反之没有了。那么如何来求投影呢？

基于上图我们可以从向量的性质入手，b向量在a向量方向上的投影为

而且我们知道对于a=(x1,y1),b=(x2,y2)有a·b为x1x2+y1y2，那么我们就可以求出来投影。

// 点积计算
float dot(Vector v1, Vector v2) 
{
  return v1.x * v2.x + v1.y * v2.y;
}

// 获取每个路径的当前坐标
std::vector<Vector> getRootCoord(std::vector<Vector> _path)
{
  std::vector<Vector> readlPath;
  for (int i = 0; i < _path.size(); i++) 
  {
    Vector p;
    p.x = _path[i].x;
    p.y = _path[i].y;
    readlPath.push_back(p);
  }
  return readlPath;
}

// 获取投影
std::pair<float, float> getProjection(Vector axis, std::vector<Vector> path)
{
  float min = std::numeric_limits<float>::max();
  float max = std::numeric_limits<float>::min();
  for (int i = 0; i < path.size(); i++) 
  {
    Vector p = path[i];
    float pro = dot(p, axis) / axis.length();
    if (pro < min) {
      min = pro;
    }
    if (pro > max) {
       max = pro;
    }
  }
  return std::make_pair(min, max);
}

紧接着就简单了，我们已经获取了所有潜在轴，所有潜在轴的投影轴，所有投影，所有投影的最大与最小值，那么来一个简单的判断就完事。

// 判断碰撞
bool isCollsion(std::pair<float, float> proA, std::pair<float, float> proB) 
{
  float min, max;
  if (proA.first < proB.first) {
        min = proA.first;
  } 
  else {
    min = proB.first;
  }
  if (proA.second > proB.second) 
  {
    max = proA.second;
  } 
  else {
   max = proB.second;
  }
  return (proA.second - proA.first) 
        + (proB.second - proB.first) 
        < max - min;
 }

分离轴碰撞检测的原理分析完毕。

测试验证代码如下：

int main() {
// 假设两个多边形的顶点坐标
  std::vector<Vector> polygon1 = {{0, 0}, {1, 0}, {1, 1}, {0, 1}};
  std::vector<Vector> polygon2 = {{2, 2}, {3, 2}, {3, 3}, {2, 3}};

  std::vector<Vector> sides1 = getSides(polygon1);
  std::vector<Vector> sides2 = getSides(polygon2);
  
  std::vector<Vector> allSides;
  allSides.insert(allSides.end(), sides1.begin(), sides1.end());
  allSides.insert(allSides.end(), sides2.begin(), sides2.end());

  std::vector<Vector> axises;
  for (int j = 0; j < allSides.size(); j++) 
  {
    axises.push_back(normL(allSides[j]));
  }

  std::vector<std::pair<float, float>> projections1;
  std::vector<std::pair<float, float>> projections2;

  for (int i = 0; i < axises.size(); i++) 
  {
    projections1.push_back(getProjection(axises[i], polygon1));
    projections2.push_back(getProjection(axises[i], polygon2));
  }

  bool collision = true;
  for (int i = 0; i < projections1.size(); i++) 
  {
    if (!isCollsion(projections1[i], projections2[i])) 
    {
      collision = false;
      break;
    }
  }

  if (collision) {
      std::cout << "两个多边形碰撞" << std::endl;
  } 
  else {
     std::cout << "两个多边形未碰撞" << std::endl;
   }
  return 0;
}