基于分离轴定理（SAT）的圆与多边形碰撞检测完整实现与修正指南-Python教程-PHP中文网

基于分离轴定理（SAT）的圆与多边形碰撞检测完整实现与修正指南

本文详解如何正确实现圆与凸多边形的sat碰撞检测，重点修复原始代码中因投影重叠判断逻辑缺陷导致的垂直方向误判问题，并提供可直接运行的健壮实现。

本文详解如何正确实现圆与凸多边形的sat碰撞检测，重点修复原始代码中因投影重叠判断逻辑缺陷导致的垂直方向误判问题，并提供可直接运行的健壮实现。

在游戏开发（如高尔夫模拟）中，精确、高效的碰撞检测至关重要。虽然分离轴定理（SAT）常用于凸多边形–凸多边形检测，但将其扩展至圆–凸多边形时需特别注意：圆可视为无限条边的正多边形，其“支持方向”并非固定边法向，而是从圆心指向多边形顶点或边的最近点方向。然而，一种更简洁且等效的常用策略是——将圆“膨胀”为以圆心为中心、半径为 r 的点集，并将多边形沿所有边法向“收缩”相同距离（即Minkowski差思想）。此时，原问题等价于判断该点是否落在“收缩后的多边形”内部。

但原始代码采用了一种简化思路：对多边形每条边计算其法向量，将圆心 E 沿该法向平移 ±r 得到两个端点 F 和 G（代表圆在该轴上的投影区间），再与边端点 A、B 在同一轴上的投影比较是否重叠。该思路本身合理，核心缺陷在于 check_overlap 函数：它错误地认为只要 x 或 y 坐标满足区间包含即可判定投影重叠，而实际上——投影重叠必须在该一维轴上成立，即应直接比较标量投影值，而非二维坐标分量。

原始 check_overlap 的逻辑混淆了“二维线段在坐标轴上的投影”与“一维投影轴上的区间重叠”。正确做法是：对每条边法向 n，我们已计算出四个标量投影值：

a = A · n（顶点 A 在法向 n 上的投影）
b = B · n（顶点 B 在法向 n 上的投影）
g = G · n = (E − r·n) · n = E·n − r（圆在负方向的投影端点）
f = F · n = (E + r·n) · n = E·n + r（圆在正方向的投影端点）

因此，该轴上的多边形投影区间为 [min(a,b), max(a,b)]，圆的投影区间为 [E·n − r, E·n + r]。二者重叠当且仅当：

not (max(a, b)  e + r)
# 等价于：
e - r <p>据此，我们重构关键函数如下（已修复、注释清晰、兼容凸多边形）：</p><pre class="brush:php;toolbar:false;">import math

def get_edge_normal(v1, v2):
    """返回边 v1->v2 的单位法向量（指向多边形外部，需确保顶点逆时针序）"""
    dx, dy = v2[0] - v1[0], v2[1] - v1[1]
    nx, ny = -dy, dx  # 逆时针旋转90°得外法向
    norm = math.sqrt(nx*nx + ny*ny)
    if norm == 0:
        return [0.0, 0.0]
    return [nx / norm, ny / norm]

def project_point_on_axis(point, axis):
    """计算点在轴（单位向量）上的标量投影值"""
    return point[0] * axis[0] + point[1] * axis[1]

def intervals_overlap(min1, max1, min2, max2):
    """判断一维区间 [min1, max1] 与 [min2, max2] 是否重叠"""
    return max1 >= min2 and max2 >= min1

def circle_polygon_collision(vertices, center, radius):
    """
    使用SAT检测圆与凸多边形碰撞（顶点须为逆时针顺序）
    :param vertices: 多边形顶点列表，如 [(x0,y0), (x1,y1), ...]
    :param center: 圆心坐标 (cx, cy)
    :param radius: 圆半径
    :return: bool，True 表示发生碰撞
    """
    if len(vertices) <p><strong>关键注意事项与总结：</strong>  </p>

顶点顺序至关重要：get_edge_normal 假设顶点为逆时针（CCW）排列，以保证法向指向多边形外部。若为顺时针，需将 nx, ny = dy, -dx；或统一用叉积符号校验。
凸性前提：SAT 仅对凸多边形有效。对凹多边形需先三角剖分或使用其他算法（如GJK）。
性能优化：实际项目中可预计算并缓存边法向；对大量对象，建议结合空间分区（如四叉树）减少检测对数。
数值稳定性：避免除零（已处理）、使用 math.isclose() 替代 == 比较浮点数（本例中非必需但推荐）。
调试技巧：可视化每条边的法向及投影区间，是定位SAT逻辑错误最有效的方式。