sat不能直接用于不规则多边形,因其依赖凸集分离定理;不规则多边形需用边-边相交检测加点包含判断,或预处理为凸片后使用sat。

SAT 不能直接用于不规则多边形——这是最常被忽略的前提。强行套用 SAT 会漏判,比如“U”形多边形被细长矩形横穿时,SAT 可能返回 false(误判为不相交),而实际几何上明显穿透。
为什么 SAT 对不规则多边形失效
SAT 的数学基础是凸集分离定理:只有当两个形状都是凸的,才保证「所有候选轴投影重叠 ⇔ 形状相交」。一旦多边形含凹角、自相交、带孔或顶点顺序混乱,它的边法向量就不再构成完备的分离轴集合。
典型失效场景:
- 凹多边形的真实相交发生在内部凹陷处,但
SAT只检测外轮廓边的法向量,根本看不到那个方向 - 两个“C”形多边形开口相对嵌套,投影在所有边法向上都重叠,
SAT却判定为相交(误报) - 顶点重复或共线导致边长度趋近于零,
glm::normalize产出NaN,污染后续全部点积计算
不规则多边形必须用边-边 + 点包含组合判断
可靠路径只有一条:先穷举所有边对是否规范相交;若无,则检查是否一方完全包含另一方。二者缺一不可。
- 边相交检测必须用跨立实验(
ccw判定),而非斜率法——避免除零、垂直线崩溃、浮点溢出 - 端点落在对方边上需单独处理:
direction(a,b,c) == 0仅表示共线,还需用坐标区间判断该点是否在线段内 - 点在多边形内必须用环绕数(
winding_number),不是射线法;容差阈值建议设为1e-6f,别用== 0 - 若 A 所有顶点都在 B 内,且 B 至少一个顶点不在 A 内 → A ⊂ B → 属于相交;反之亦然
真要用 SAT,得先拆成凸片
如果性能敏感且多边形确实不规则,唯一合规做法是预处理:用耳切法(ear clipping)或单调链剖分,把原始多边形分解为若干凸多边形,再两两调用 SAT。
- 别依赖顶点凹凸性检测做局部修正——共线顶点、极小面积三角形会让结果不稳定
- 拆出的凸片数量爆炸(如百顶点多边形产几十个三角形)时,
O(n×m)边检测反而更稳,此时应降级回边-边穷举 - 轻量实现可手写耳切,注意跳过面积
的退化三角形,否则 <code>ccw计算失准
AABB 包围盒必须作为第一道防线
无论选哪种主逻辑,AABB 粗筛都不可省略。它成本极低,能过滤掉绝大多数明显分离的情况。
- 实现只需四次比较:
a.minX b.minX && a.minY b.minY - 注意:不要用
或 <code>>=——浮点误差下边界接触可能被误判,统一用严格不等号 + 后续容差补偿 - 若
!aabb_intersect(a, b)成立,直接返回false,不进任何复杂逻辑
is_intersect() 函数能兜底——顶点顺序、自交、浮点抖动、退化边,每个都可能让 SAT 崩溃或静默失效。最易被忽略的,其实是包围盒之后那一步:你是否真的检查了所有边对,还是只跑了前几对就提前返回?C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!











