二维凸四边形快速碰撞检测：区分点、线段与多边形相交

基于SAT扩展的分类方法 #

SAT（分离轴定理）可直接扩展用于区分三种相交场景，无需计算布尔并集，且能利用提前退出机制提速：

• 先执行常规SAT检测：遍历两个凸四边形的所有边对应的分离轴，若存在分离轴则判定为不相交，直接结束。
• 统计接触轴数量与特征：当无分离轴时，记录所有满足「两四边形在该轴上的投影重叠长度为0」的轴：
  1. 无接触轴：所有轴上投影均有正重叠，判定为正面积相交。
  2. 仅1条接触轴：
     • 验证顶点与边的关系：若某一四边形的顶点落在另一四边形的边上（通过顶点到边的距离是否为0快速判断），且该接触在接触轴上的投影为单点，判定为点相交；
     • 若两四边形的对应边平行且共线部分不为空，判定为线段相交。
  3. 2条及以上接触轴：仅可能是两四边形共享公共边（或部分边），直接判定为线段相交。

提前退出优化点 #

• 统计接触轴时，一旦发现第2条接触轴，立即判定为线段相交，停止遍历剩余轴；
• 验证单接触轴的顶点-边关系时，找到符合条件的单点接触即可终止验证，无需检查所有顶点。

GJK算法的扩展思路 #

借助GJK迭代生成的单纯形特征也可快速分类：

• 单纯形为点：对应点相交；
• 单纯形为线段：且该线段属于两四边形的边（或部分边），对应线段相交；
• 单纯形为三角形：对应正面积相交。

内容的提问来源于stack exchange，提问作者Eli4ph