C++如何判断两个不规则多边形是否发生几何相交 (SAT 算法)
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噪声的场景，否则会埋下隐患。
正软商城本月促销专区，汇集办公、设计、安全、影音、系统工具及AI软件等正版软件优惠活动，提供限时折扣、特价授权和优惠购买信息，活动库存及价格以页面实时展示为准。
正软商城装机必备专区，精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件，帮助用户快速完成新电脑软件配置。
正软商城Windows软件专区，汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件，提供软件介绍、系统要求、正版授权及购买下载服务。
正软商城macOS软件专区，精选适用于Mac电脑的办公、设计、影音、效率、开发和系统工具，提供软件功能介绍、macOS兼容版本、正版授权及购买下载服务。
正软商城iOS软件专区，精选适用于iPhone和iPad的办公、学习、影音、设计、效率及AI应用，提供功能介绍、适用设备、系统要求和正版获取方式等信息。
正软商城AI软件专区，汇集AI写作、AI绘画、AI视频、AI办公、AI编程、AI翻译、智能客服和数据分析等人工智能工具，提供功能介绍、适用平台、收费方式及正版购买信息。
正软商城PDF教程频道提供PDF编辑、转换、合并、拆分、压缩及格式处理方法，同时介绍常用PDF软件和工具的使用技巧。
赤友清理大师是一款为 Mac 设计的智能清理优化工具，可精准扫描垃圾、大文件、重复文件等，释放磁盘空间。做扫描整理、文字提取和表格转换时，它能把识别后的处理步骤接得更顺，资料录入这类场景会省下不少时间。
极度公式是一款跨平台专业LaTeX公式识别编辑软件，支持OCR公式识别和多平台编辑。和使用说明，避免使用，享受完整功能与稳定支持。做扫描整理、文字提取和表格转换时，它能把识别后的处理步骤接得更顺，资料录入这类场景会省下不少时间。
一款文字处理软件，一种订阅式的跨平台办公软件，基于云平台提供多种服务，通过将 Excel 和 Outlook 等应用与 OneDrive 和 Microsoft Teams 等强大的云服务相结合，Office 365 可让任何人使用任何设备随时随地创建和共享内容。
CodeExpander 是一款快捷短语输入增强工具，通过键入缩写自动展开为自定义文段，提升工作效率。任务管理和过程控制会更完整，持续下载、批量同步或需要稳定传输流程的场景会更适合它。
Mountain Duck 是一款能将多个网盘挂载到本地的工具，像本地磁盘一样使用网盘。清理链路的完整性会更好一些，做应用卸载、残留处理和空间整理时，通常能少走很多手动排查步骤。
极度公式是一款跨平台专业LaTeX公式识别编辑软件，支持OCR公式识别和多平台编辑。和使用说明，避免使用，享受完整功能与稳定支持。做扫描整理、文字提取和表格转换时，它能把识别后的处理步骤接得更顺，资料录入这类场景会省下不少时间。
一款文字处理软件，一种订阅式的跨平台办公软件，基于云平台提供多种服务，通过将 Excel 和 Outlook 等应用与 OneDrive 和 Microsoft Teams 等强大的云服务相结合，Office 365 可让任何人使用任何设备随时随地创建和共享内容。
Wise Folder Hider Pro 是一款专业级文件和文件夹隐藏加密软件，为私密数据添加多重保护。高频操作更强调就近处理，浏览、整理和跨目录移动文件时，来回切换和重复点击都会少很多。
CodeExpander 是一款快捷短语输入增强工具，通过键入缩写自动展开为自定义文段，提升工作效率。任务管理和过程控制会更完整，持续下载、批量同步或需要稳定传输流程的场景会更适合它。
Mountain Duck 是一款能将多个网盘挂载到本地的工具，像本地磁盘一样使用网盘。清理链路的完整性会更好一些，做应用卸载、残留处理和空间整理时，通常能少走很多手动排查步骤。
