之前在准备高考，没有更新；今天高考开始了，我决定不考了来更新嗯嗯【嗯？？？】......


之前在准备高考，没有更新；今天高考开始了，我决定不考了来更新嗯嗯【嗯？？？】

------

之前俺们聊了一下圆与矩形的碰撞检测，说实话还是比较讨巧的，充分利用了在限定条件下的他们的特殊图形性质。然而有简单的情形就有蛋疼的情形，面对不规则的多边形，该如何考虑进行检测嘞？

## 聚光灯上场！

让我们想象二维世界里有两个分离的（凸）多边形，四周是墙，如果我们用一个聚光灯（其实平行光源更合适啦）环绕它们去照射，那么肯定存在某个角度，它们的投影是分离的！这就是俺们这次所要使用的算法——分离轴定理！！

## 抽象实现

在具体实现时，俺们需要考虑这几个问题

- 我们最少需要哪些聚光灯位——如何确定投影轴
- 如何得到影子——如何将多边形投影到投影轴上
- 怎么判断影子是否重叠——怎么判断投影是否重叠

### 确定投影轴

由于凸多边形本身的特点，易证（嗯有意见？）我们只需要将光线平行于多边形的每条边进行投影就行；换句话说，所有需要检测的投影轴就是多边形的边缘法向量⬇️，CD便是一个边缘向量，IH就是它的边缘法向量。显然对于向量位置是无所谓的，直线GF的方向与向量IH平行，更有利于理解投影嗯嗯。

![边缘法向量](https://hukua-blog.oss-cn-beijing.aliyuncs.com/markdown-imgs/%E5%88%86%E7%A6%BB%E8%BD%B4_%E8%BE%B9%E7%BC%98%E6%B3%95%E5%90%91%E9%87%8F.png)

### 如何确定投影的大小及它们是否重叠

这是卡了我很久的一个问题，首先看图好吧，大家都很喜欢看图我明白

这里的投影轴是BC的法向量，正好是一个符合投影不重叠的投影轴（三角形的投影为JL，四边形的投影为MN）。对于人脑来说，我们可以一眼看出它们不重叠的事实，但是我们该如何将其抽象到程序中呢————？如何记录J，L以及M，N（事实上由于每条边都要投影，还有很多没标出来的点需要记录）并判断它们组成的线段是否重叠？对于我萎缩的大脑，有点蛋疼......

![不重叠](https://hukua-blog.oss-cn-beijing.aliyuncs.com/markdown-imgs/%E5%88%86%E7%A6%BB%E8%BD%B4_%E4%B8%8D%E9%87%8D%E5%8F%A0.png)

### 原点登场

不要忘了我们的坐标系，要知道我们在程序中所使用的**向量、顶点**都是按照坐标系的思路来抽象的，对于每个顶点（x, y），坐标都是相对于原点的！因此对于上图，与其试图投影**线段AB**到投影轴得到**投影JL**，我们可以将其看作**原点H与顶点B**投影得到**投影KL**、**原点H与顶点A**投影得到**投影KJ**，其他顶点类似——想要得到多边形的投影，只要得到**顶点投影到投影轴后相对于原点投影到投影轴的位置的“距离”（可正可负），相对最大最小值便可代表这个投影**。而这个相对值也甚至几乎是现成的：**原点到顶点的向量点乘边缘法向量便可（显然，为了结果有可比性，边缘法向量的大小必须固定，一般normalize大小为1）**，点乘的意义我相信大家也明白，就不赘述了。在比较两个多边形的投影时，其实比较的也是这样一个投影顶点相对投影原点的值。

### 小小的经验

如果觉得上文概念混淆，那就对了！投影就是投影，是我们想到的最直观的比较方法。然而我们的目的只是**借助投影比较多边形是否重叠，而不是投影本身**，因此我们没有抽象出一个**直观的代表投影的数据结构**（比如用两个坐标表示？），而是**借助原点与投影性质抽象出一个尽管不是投影，却更容易比较的结构**，在我的代码里它是这样的：

```javascript
/* 
    投影，
    用min和max来记录，
    因为实际上是顶点与原点构成的线段在轴上的投影，
    因为顶点的投影位置是固定的，
    所以比较时只需要考虑投影的“长度”（可以为负），
    min和max分别是一个多边形的所有顶点（与原点）投影长度的最小与最大值
*/
class Projection {
    constructor(min, max) {
        this.min = min;
        this.max = max;
    }
    overlaps(pro) {
        return this.max > pro.min && pro.max > this.min;
    }
}
```

## 成品

俺的[分离轴实现](https://codepen.io/padfoot_07/full/pKyOYm)，比较核心的部分就是`Polygon对象的project、getNormals实现与Projection对象实现`

<p data-height="265" data-theme-id="0" data-slug-hash="pKyOYm" data-default-tab="js,result" data-user="padfoot_07" data-embed-version="2" data-pen-title="分离轴-碰撞检测" class="codepen">See the Pen <a href="https://codepen.io/padfoot_07/pen/pKyOYm/">分离轴-碰撞检测</a> by Zhouyi (<a href="https://codepen.io/padfoot_07">@padfoot_07</a>) on <a href="https://codepen.io">CodePen</a>.</p>
<script async src="https://static.codepen.io/assets/embed/ei.js"></script>

------

今天是高考，又有很多人将要步入新一阶段的学习。感觉大家在学习中总是关注到很多很了不起的方面，却对于自己的生活方式没有认真的思考过呢。“赞美太阳！”虽是游戏中看似有些搞笑的台词，实际上对于个人来说，意味却是很认真的啊。（......我看你是传火传的活尸化严重了）

LWDW!