三年前我写过一篇文章来阐述如何用向量运算来解决圆线碰撞问题。现如今在开发一款核心战斗RTS-Like的手机游戏，需要将性能放在优先考虑的位置。

本文将讨论我在实际开发中遇到的问题和思考，并总结出一套比较通用的优化思路，文末会推荐一个视频播客来帮助大家更加直观的理解其背后的数学原理。

点在扇形内的思考

我喜欢用这道题目去面试客户端，因为这个问题的解法很多（思路开放），针对不同给定的条件其优化方案也不尽相同。

从向量运算的角度去思考这个问题，最简便的做法是先判断点D与圆心A的距离是否小于半径，然后再判断点D是否在两条半径向量与之间。

如何判断一个点是否在两条向量之间呢？只要判断点D在的右边且在的左边即可。

叉乘

如何判断一个点在向量的左右呢？用叉乘即可，根据叉乘的定义，可知其与夹角的sin值相关：

需要注意的是叉乘只在3D和7D空间中有定义，2D空间的叉乘可以简化为两个Z轴为0的3D向量的叉乘。

根据叉乘的定义，这两个只在XY平面的向量的叉乘，必然为一个只在Z轴（垂直于XY平面）上有值的向量，所以可以把2D向量的叉乘简化为一个只表示Z值的标量。

所以2D向量的叉乘可以定义为：

还需要注意的一点是叉乘不满足交换律，，也就是叉乘顺序会影响结果的正负。

有一种非常直观的记忆方式可以记忆叉乘的正负顺序，就是按照坐标轴的定义顺序来记忆。

譬如：，i向量为X轴的单位向量，j向量为Y轴的单位向量，可得，。记忆的方法是X轴的顺序在Y轴前面，所以的结果为正。

又因为X轴在Y轴右边，所以可以方便的记忆叉乘的正负值和向量左右之间的关系。即叉乘的第一个向量在第二个向量右边时为正，否则为负。

回归到问题，我们只需判断，且即可，这个方法完全避免了使用三角函数。

点积

然而在实际情况中，不大可能会给定点B和点C的坐标。在实际游戏中，通常只会给定扇形的圆心位置A，张开角度θ，半径R和扇形面朝向量。

此时再用叉乘的方法来确定点B和点C的坐标过于低效，需要更加高效的判断方法。

面试其实是一个互动的过程，在一次面试的时候我问了这道题，得到了一种不同的思路，而这种思路非常适合游戏的实际情况。

这种思路的核心是点积。因为扇形的面朝向量一定会把张开角度θ对等分为两半，所以只需判断与的夹角小于θ/2即可，并不需要区分方向。

根据点积的定义，，可以轻松得到两个向量夹角的cos值。又根据cos函数在[0, π]间是单调下降的，所以可以通过直接比较cos值的大小来比较θ值的大小，不需要通过反余弦来计算真实角度值。

回归到问题，我们只需预计算一次，然后通过计算点积得到与的夹角的cos值，若此值比大，则说明点D在扇形的张开角度范围内。

这种方法只需要计算一次cos函数，并且可以将其缓存起来供后续点的计算，相对来说开销较小。

后来我问对方是如何在这么短时间内得到这个思路的，答曰之前在Milo的博客上看到过类似的文章。读者如果对此问题感兴趣，不妨去那看一看，Milo对此问题的优化分析会更加深度一些。

点在矩形内的思考

凸多边形

如果已知矩形的四个点，那么其实问题就退化为判定点是否在凸多边形内。

对于判断点是否在凸多边形内的一个通用的快速解法就是判断点是否在凸多边形的所有边的相同的一侧。

对于上图，只需要判断点E是否都在四条边向量 和 的左侧。

对于如何判断点在向量的左侧，在上文已经详细阐述，这里就不赘述了。

仿射变换

然而游戏里的实际情况是只知道矩形宽的中心点F坐标和矩形长的方向向量以及长宽值。此时再通过反推出矩形的四个顶点，利用上述方法来做未免太过低效和绕弯子。

如果矩形的一条边与X轴平行，那么问题将变得非常简单，我们可以轻易反推出四个顶点的坐标，后续的判断甚至不用计算叉乘，只需要简单粗暴的对比XY坐标即可。

既然矩形可能是斜的，那么可以通过旋转坐标系，并将原点平移到F点，就可以将情况变换成上述的简单情况。这种变换有个听起来高大上的名字：仿射变换。其实就是线性变换（旋转坐标系）加上坐标平移（平移原点）。

回归到问题，具体做法如下。首先先应用平移，即将E的坐标减去F的坐标，得到E的相对坐标，然后再应用旋转。

怎么计算旋转后的新坐标是个非常有意思的问题。如上图，将坐标系旋转θ度，如何得到P点在旋转后新的坐标系下坐标呢？

基变换

大学里学的线性代数终于派上用场！其实这个旋转就是一个简单的线性变换：即将基向量从和变换为和。

如果你和之前的我一样已经把线性代数忘的差不多的话，这里正好可以来复习一下线性代数的一个最重要概念。

我们知道在原来的XY坐标系下，任意一个点可以表示成。这看似很寻常，其实可以从更加泛化的角度来理解：即在XY坐标系下的任意一个点都可以表示为所有基向量乘与点在该基向量上的长度。

所以假设基向量为和，则P的坐标可以表示为，这其实就是矩阵乘法：

我们可以认为在旋转坐标系之前:
在旋转坐标系之后，基向量发生了变化：
需要注意的是，Z是P在旋转后在原XY坐标系下的坐标。我们需要知道的是在旋转坐标系后原来的P点在新的坐标系下的坐标：
根据逆矩阵的性质，可得：

回归到问题本身，只需再将应用上述的旋转，得到新的坐标，然后问题本身便退化为最简单的情况。

三角函数

折腾了这么久，结果还是需要算三角函数sin和cos的值。我们知道三角函数的计算开销非常大，那前面岂不是白费精力？

其实不然，聪明的读者可能已经发现当两个方向向量都是单位向量时，其夹角的sin值就是它们的叉乘；其夹角的cos值就是它们点积。

通用优化思路

在游戏优化上的一个通用思路就是需要知道什么操作开销大，然后尽可能的去避免使用它们，或者缓存它们以避免重复运算。

三角函数和开方函数的开销就比较高，能尽量避免就尽量避免。加减乘除的开销相对来说就没有那么高，如果可以替代它们就尽可能的替代。

比如在比较距离的时候，如果硬算距离，会需要一次开方计算；然而选择比较距离的平方，则可以免去开方运算又可以达到比较距离的目的。

又比如已知两个单位向量，需要计算它们的夹角的sin值，如果直接用sin函数，开销会很大，如果知道叉乘，则可以免去使用sin函数，而用简单的加减法和乘法即可求出。

同理，对于cos值，只需要计算一次点积，也可以免去使用cos函数。

总结一下，游戏内通用的优化思路是找到开销大的地方，用更小开销的方法去替代它们，如果它们后续还会用到的话，将它们缓存起来。

找到开销大的地方有两种方式，一种是利用已知的知识知道哪些操作的开销较大；还有一种就是通过profiler来检测出性能热点。前者适于小型算法，后者则适用于较为复杂的代码环境。

总而言之，不要进行凭臆想优化，通过实测找到热点，然后优化会事半功倍。

推荐

任何知识如果只是知其然不知其所以然，一定会忘记的很快。如果能记住向量运算背后的几何意义，能直观的去理解整个过程，那么学习也能变得更加轻松和牢固。

在此，我力荐一个视频播客3Blue1Brown，如果翻不了墙可以去B站看已经翻译的版本，可能会略微滞后于源播客。

3b1b的视频能带领你直观的领略数学的魅力和意义。对于本文的读者，我强烈推荐他在线性代数系列讲线性变换的视频，这对于你们理解向量运算和线性代数有着很大的帮助。

看完回来，你们一定会感谢我的。