向量法实战：从凹多边形切割到凸多边形碰撞检测-编程实验室

1. 为什么需要凹多边形切割

在游戏开发或者物理引擎实现中，碰撞检测是个绕不开的话题。你可能已经听说过分离轴算法（SAT），这个算法在处理凸多边形碰撞时效率很高，但有个前提条件：它只能处理凸多边形。现实情况是，我们遇到的图形往往都是凹多边形，比如一个"凹"字形的物体，或者更复杂的星形图案。

这里有个很实际的问题：如果直接把分离轴算法用在凹多边形上，会得到错误的碰撞结果。我刚开始做游戏时就踩过这个坑，明明两个物体看起来没有碰撞，系统却判定它们撞在了一起。后来才发现，原来是因为凹多边形的某些特性导致分离轴算法失效。

那么解决方案就很明确了：先把凹多边形切割成多个凸多边形，再对每个凸多边形进行碰撞检测。听起来简单，但具体怎么切？这就是我们今天要重点讨论的向量法实现方案。

2. 向量法基础：判断凹点

2.1 多边形顶点顺序约定

首先我们需要约定多边形的顶点存储顺序。在Unity等大多数游戏引擎中，我们采用逆时针顺序存储顶点。这个约定很重要，因为后续的所有计算都依赖于这个顺序。

判断一个点是不是凹点，本质上就是看这个点处的内角是否大于180度。这里就要用到向量的叉乘了。我记得刚开始学这个的时候，花了好几个小时才想明白叉乘的方向判断。

2.2 叉乘判断凹点

具体操作是这样的：对于多边形中的每个顶点，我们取它前一条边和后一条边做叉乘。在左手坐标系中（Unity就是左手系），如果叉乘结果指向屏幕外侧，说明这个点的内角大于180度，就是个凹点。

用代码表示大概是这样：

Vector3 cur = polygon[i]; Vector3 prev = polygon[(i-1 + count)%count]; Vector3 next = polygon[(i+1)%count]; if(Vector3.Cross(cur-prev, next-cur).z > 0) { // 这是个凹点 }

在实际项目中，我建议把这个判断封装成一个独立函数，因为后面会反复用到。第一次实现时我犯了个错误，没有处理好顶点索引的循环问题，导致数组越界，调试了好久才发现。

3. 边延长与相交测试

3.1 延长凹点的起始边

找到凹点后，我们需要延长这个凹点的起始边。举个例子，假设我们有个五边形ABCDE，发现点C是凹点，那么就要延长边BC。

这里的关键问题是：延长线会和哪条边相交？我们需要遍历多边形的其他边，找出与延长线相交的那条边。但要注意跳过一些特殊情况：

跳过当前边BC本身
跳过下一条边CD（因为C是凹点，延长线不可能与CD相交）

3.2 相交测试的实现

相交测试是整套算法中最容易出错的部分。我最初用的是简单的叉乘法，后来发现有些边界情况处理不了。比如当延长线正好穿过某个顶点时，就需要特殊处理。

正确的做法是：

bool IsIntersect(Vector3 a1, Vector3 a2, Vector3 b1, Vector3 b2) { float cross1 = Vector3.Cross(b1-a1, a2-a1).z; float cross2 = Vector3.Cross(b2-a1, a2-a1).z; if(cross1 * cross2 >= 0) return false; float cross3 = Vector3.Cross(a1-b1, b2-b1).z; float cross4 = Vector3.Cross(a2-b1, b2-b1).z; return cross3 * cross4 < 0; }

这个函数可以正确处理大多数情况，但要注意处理延长线穿过顶点的情况，这时候需要额外判断叉乘结果是否为零。

4. 求交点与多边形分割

4.1 直线交点计算

找到相交的边后，我们需要计算延长线与这条边的交点。这里有两种常用方法：

直线方程法
参数方程法

我更喜欢用直线方程法，虽然需要处理斜率不存在的特殊情况，但理解起来更直观。具体实现时，一定要记得处理垂直线（斜率无限大）的情况，这是最常见的bug来源。

Vector3 GetIntersection(Vector3 p1, Vector3 p2, Vector3 p3, Vector3 p4) { // 处理垂直线情况 if(Mathf.Approximately(p1.x, p2.x)) { float m = (p4.y - p3.y)/(p4.x - p3.x); float b = p3.y - m*p3.x; return new Vector3(p1.x, m*p1.x + b); } if(Mathf.Approximately(p3.x, p4.x)) { float m = (p2.y - p1.y)/(p2.x - p1.x); float b = p1.y - m*p1.x; return new Vector3(p3.x, m*p3.x + b); } // 一般情况 float m1 = (p2.y - p1.y)/(p2.x - p1.x); float b1 = p1.y - m1*p1.x; float m2 = (p4.y - p3.y)/(p4.x - p3.x); float b2 = p3.y - m2*p3.x; float x = (b2 - b1)/(m1 - m2); float y = m1*x + b1; return new Vector3(x, y); }

4.2 多边形分割策略

求得交点后，我们需要根据交点位置将原多边形分割成两个新多边形。这里有两种主要情况：

延长线与"后续"的边相交：比如延长BC与DE相交
延长线与"前面"的边相交：比如延长BC与EA相交

每种情况的分割方式略有不同。我建议在实现时，先画几个具体的例子，把顶点索引的变化规律搞清楚。第一次实现时，我就在这里搞反了顶点顺序，导致分割后的多边形顶点顺序错乱。

5. 完整算法与优化

5.1 广度优先分割流程

为了完整处理凹多边形，我们需要使用广度优先搜索（BFS）的策略：

初始化一个队列，放入原始凹多边形
从队列取出一个多边形，尝试找到凹点并进行分割
如果分割成功，将得到的新多边形放回队列
如果无法分割（已经是凸多边形），加入结果列表
重复直到队列为空

这个流程保证了我们会处理所有可能的凹多边形，直到全部变成凸多边形为止。

5.2 特殊情况的处理

在实际项目中，有几个特殊情况需要特别注意：

延长线正好穿过顶点：这时候需要修改分割逻辑，确保顶点不会被重复添加
共线边：当多边形有共线顶点时，可能会影响凹点判断
浮点数精度问题：在比较叉乘结果时，建议使用Mathf.Approximately而不是直接比较

我在项目中就遇到过因为浮点精度导致的bug，两个理论上应该相交的边因为精度问题被判定为不相交，导致整个算法失效。后来通过增加一个很小的epsilon值比较解决了这个问题。

6. 性能考量与实现建议

6.1 算法复杂度分析

这个算法的时间复杂度取决于凹多边形的复杂程度。最坏情况下，一个n边形可能需要被分割成n-2个凸多边形。每次分割都需要遍历所有边进行相交测试，所以整体复杂度大概是O(n³)。

在实际应用中，我发现对于不太复杂的凹多边形（比如只有1-2个凹点），性能还是可以接受的。但对于特别复杂的形状，可能需要考虑其他优化方法，比如预先计算凸包等。

6.2 实现优化技巧

经过几个项目的实践，我总结出几个优化建议：

缓存中间结果：比如已经确认是凸多边形的部分可以缓存起来
尽早终止：如果发现某个多边形已经是凸的，就立即停止处理
空间分区：对于场景中有大量多边形的情况，可以先做空间分区，减少需要检测的多边形数量
并行处理：现代CPU多核心，可以考虑把不同多边形的处理分配到不同线程

在移动设备上实现时，要特别注意内存分配问题。频繁创建新的多边形列表会导致GC压力，最好使用对象池来管理内存。

7. 实际应用案例

7.1 在Unity中的实现

在Unity中，我们可以把这个算法封装成一个静态类，方便各个组件调用。下面是一个简化版的调用示例：

public class CollisionHelper { public static List<List<Vector2>> SplitConcavePolygon(List<Vector2> concavePoly) { // 实现我们前面讨论的算法 } } // 使用示例 List<Vector2> originalPoly = new List<Vector2>{...}; var convexPolys = CollisionHelper.SplitConcavePolygon(originalPoly); foreach(var poly in convexPolys) { // 对每个凸多边形进行碰撞检测 }