C++如何判断两个不规则多边形是否发生几何相交 (SAT 算法)

SAT算法实战：判断凸多边形相交的黄金法则

判断两个不规则多边形是否发生几何相交，这是计算机图形学里一个基础但容易踩坑的问题。先说几个核心判断：SAT（分离轴定理）是解决这个问题的利器，但它不是万能的，你得知道它的边界在哪里。

两个凸多边形用SAT判断相交，只需检查边法向量轴

对两个凸多边形A和B来说，分离轴其实就是它们所有边的法向量方向——这里必须强调，不是边本身，也不是任意随机方向。每条边 e = v1 - v0 对应一个候选轴 glm::vec2(-e.y, e.x)（2D场景）或者归一化后的垂直向量（3D场景）。A有n条边、B有m条边，所以最多检查 n + m 条轴，不是 n×m。

实践中最容易踩的坑有两个。第一，直接把“边向量”当成轴来用，或者漏掉某个多边形的一条边；第二，没做去重处理——平行边产生的法向量可能完全相同或反向，glm::all(glm::epsilonEqual(a, b, 1e-6f)) 或 glm::all(glm::epsilonEqual(a, -b, 1e-6f)) 必须检查到位。

几点经验之谈：2D场景下用 glm::vec2 就足够了，不要升维引入冗余计算；轴完全不需要归一化——投影区间只依赖点积的相对大小，归一化纯属浪费计算资源；如果某条边的长度 ，直接跳过它的法向量计算，防止除零或NaN传播。

非凸多边形不能直接套SAT，必须先分解

SAT只对凸形状有效，这一点必须刻在脑子里。遇到凹多边形或带孔多边形，硬上SAT会漏判——举个典型例子：两个“U”形多边形开口相对，投影在所有边法向上都重叠，但实际它们根本就不相交。

真实工程场景中，建模导出的多边形常含凹点。有人试图用“顶点凹凸性检测+局部修正”来绕开这个问题，但从实践来看，稳定性很差，不推荐。稳妥的做法是用耳切法（ear clipping）或单调链剖分，先把原始多边形拆成若干个凸多边形，然后再两两做SAT。

• 如果只是粗筛阶段，可以先用AABB包围盒快速排除：!aabb_intersect(aabb_a, aabb_b) 直接返回false
• 推荐轻量库如 poly2tri，或者手写耳切——但要注意处理共线顶点和极小面积三角形
• 当拆出的凸片数量爆炸时（比如百顶点多边形），可以考虑降级为边-边穷举：对所有边对调用 segment_intersect()

投影区间计算必须覆盖全部顶点，且带浮点容差

在每个轴上，必须对多边形所有顶点计算 glm::dot(p, axis)，取min和max得到 [min, max]。一个常见的低级错误：只投影前三个点，或者误以为三角形就只投三个点，忽略了其他顶点——多边形顶点数是不固定的。

区间比较这条红线绝对不能碰：不能用 proj_a_max < proj_b_min 这种裸比较，浮点误差会让本该重叠的区间被判为分离。正确的写法是：

if (proj_a_max + 1e-6f < proj_b_min || proj_b_max + 1e-6f < proj_a_min) {
    return false; // 分离
}

• epsilon值选 1e-6f 就足够了，比 FLT_EPSILON（约1e-7）更鲁棒，因为累积误差往往更大
• 不要用 std::minmax_element——它对 size
• 投影值本身不需要 clamp 或 abs，点积可正可负，min/max自然能捕获范围

退化边与共线顶点必须前置过滤，不能等crash再处理

真实输入数据经常带着“惊喜”：三点近似共线的扁平三角形、重复顶点、或者导出时精度丢失导致的微小边长。这些情况会直接让 glm::normalize() 返回 vec3(0,0,0)，后续点积全变成NaN，整个检测瞬间失效。

防护措施必须在SAT主循环之前就到位：对每条边，先算长度；对每个面（3D场景），先算叉积模长。面积 就视为退化，跳过对应轴或整个多边形。

• 2D边长检查：glm::length(v1 - v0) < 1e-6f
• 3D面积检查：0.5f * glm::length(glm::cross(v1-v0, v2-v0)) < 1e-6f
• 退化多边形可以降级为线段集：提取所有非退化边，再做O(n²)边相交检测

还有一个经常被忽略的细节：共面但非共线的多边形，在3D空间中仍然要走3D SAT流程——哪怕z坐标全为0。强行降维到2D只适用于明确已知共面且没有z噪声的场景，否则会埋下隐患。