碰撞检测 SAT算法 代码

以下是一个简单的 SAT（分离轴定理）算法的实现代码，用于检测两个凸多边形是否相交：

# 将向量投影到轴上，返回最小值和最大值
def project_polygon_onto_axis(axis, polygon):
    min_val = max_val = np.dot(axis, polygon[0])
    for i in range(1, len(polygon)):
        val = np.dot(axis, polygon[i])
        if val < min_val:
            min_val = val
        elif val > max_val:
            max_val = val
    return min_val, max_val

# 检查两个凸多边形是否相交
def check_polygon_collision(poly1, poly2):
    # 计算每个多边形的边向量
    edges1 = [poly1[(i+1)%len(poly1)] - poly1[i] for i in range(len(poly1))]
    edges2 = [poly2[(i+1)%len(poly2)] - poly2[i] for i in range(len(poly2))]

    # 计算所有的法向量
    axes = [np.array([-edge[1], edge[0]]) for edge in edges1]
    axes += [np.array([-edge[1], edge[0]]) for edge in edges2]

    # 遍历每个法向量，检查是否有重叠
    for axis in axes:
        min1, max1 = project_polygon_onto_axis(axis, poly1)
        min2, max2 = project_polygon_onto_axis(axis, poly2)
        if max1 < min2 or max2 < min1:
            return False

    # 所有法向量上都有重叠
    return True

这个算法并不是最优化的实现，但它足够快速并且易于理解。实际上，SAT算法还可以用于检测凸多面体的碰撞，只需要将边和法向量扩展到3D空间即可。