高尔夫游戏中多边形与圆形SAT碰撞检测垂直轴误判问题

我正在开发一款高尔夫游戏，需要实现多边形与圆形的分离轴定理（SAT）碰撞检测算法。当前代码仅在水平轴方向能正常检测碰撞，但垂直轴方向无论两形状距离远近，只要某一形状的像素处于另一形状的x坐标范围内，就会被判定为碰撞。尝试修改check_overlap函数的条件，但未定位到问题所在，相关代码如下：

import math

def Axis(A, B): # RETURN A NORMALIZED NORMAL VECTOR (CHECKED)
    dx = A[0] - B[0]
    dy = A[1] - B[1]
    n = [-dy, dx]
    v = math.sqrt(dy ** 2 + dx ** 2)
    return [n[0] / v, n[1] / v]

def projections(A, B, E, r): #Should return projections perpendicular line of the edge of the 2 vertices
    n = Axis(A, B)
    A_proj, B_proj, E_proj = A[:], B[:], E[:]
    a = A_proj[0] * n[0] + A_proj[1] * n[1]
    b = B_proj[0] * n[0] + B_proj[1] * n[1]
    e = E_proj[0] * n[0] + E_proj[1] * n[1]

    F = [E_proj[0] + r * n[0], E_proj[1] + r * n[1]]
    G = [E_proj[0] - r * n[0], E_proj[1] - r * n[1]]

    for i in range(2):
        A_proj[i] = a * n[i]
        B_proj[i] = b * n[i]
    return [A_proj, B_proj, G, F]

def check_overlap(pos):
    # Extraction des points
    (x1, y1), (x2, y2) = pos[0], pos[1]
    (x3, y3), (x4, y4) = pos[2], pos[3]
    # Fonction pour vérifier si deux segments sont alignés et se chevauchent
    def is_between(a, b, c):
        return min(a, b) <= c <= max(a, b)
    # Vérification si les segments sont alignés sur le même axe (horizontal, vertical ou diagonal)
    if (x1 == x2 == x3 == x4):  # vertical alignment
        return is_between(y1, y2, y3) or is_between(y1, y2, y4) or is_between(y3, y4, y1) or is_between(y3, y4, y2)
    return is_between(x1, x2, x3) or is_between(x1, x2, x4) or is_between(x3, x4, x1) or is_between(x3, x4, x2) #if no vertical alignment

def collision_check(vertices,E, r):
    vertices_proj = [v[:] for v in vertices]
    for i in range(len(vertices)):
        if i == (len(vertices)-1) :
            A = vertices_proj[i]
            B = vertices_proj[0]
        else :
            A = vertices_proj[i]
            B = vertices_proj[(i + 1)]
        pos = projections(A, B, E, r) #points = [[xa,ya],[xb,yb],[xf,yf],[xg,yg]]
        if check_overlap(pos) :
            return True
    return False

问题根源 #

核心问题出在投影逻辑和重叠判断的方向错误：

1. projections函数错误地返回了二维平面上的投影点，而非SAT要求的一维投影区间（min/max标量值）
2. check_overlap函数在做二维线段重叠判断，完全违背了SAT通过一维投影区间重叠来判定碰撞的核心逻辑，这是垂直轴误判的直接原因

修正方案 #

1. 重构投影逻辑，返回一维区间 #

import math

def get_edge_normal(A, B):
    # 计算多边形边的单位法向量（分离轴）
    dx = B[0] - A[0]
    dy = B[1] - A[1]
    length = math.hypot(dx, dy)
    return [-dy/length, dx/length]

def project_polygon(axis, vertices):
    # 计算多边形在指定轴上的投影区间
    projections = [v[0]*axis[0] + v[1]*axis[1] for v in vertices]
    return min(projections), max(projections)

def project_circle(axis, center, radius):
    # 计算圆形在指定轴上的投影区间
    center_proj = center[0]*axis[0] + center[1]*axis[1]
    return center_proj - radius, center_proj + radius

2. 一维区间重叠判断 #

def is_intervals_overlap(min1, max1, min2, max2):
    # 检查两个一维区间是否重叠
    return not (max1 < min2 or max2 < min1)

3. 修正碰撞检测主函数 #

def collision_check(vertices, circle_center, circle_radius):
    # 检查多边形每条边对应的分离轴
    for i in range(len(vertices)):
        A = vertices[i]
        B = vertices[(i+1)%len(vertices)]
        axis = get_edge_normal(A, B)
        poly_min, poly_max = project_polygon(axis, vertices)
        circle_min, circle_max = project_circle(axis, circle_center, circle_radius)
        # 找到分离轴，直接返回无碰撞
        if not is_intervals_overlap(poly_min, poly_max, circle_min, circle_max):
            return False
    
    # 补充检查：圆心到多边形每个顶点的向量作为分离轴（SAT多边形vs圆形必须步骤）
    for vertex in vertices:
        dx = circle_center[0] - vertex[0]
        dy = circle_center[1] - vertex[1]
        length = math.hypot(dx, dy)
        if length == 0:
            # 圆心与顶点重合，直接判定碰撞
            return True
        axis = [dx/length, dy/length]
        poly_min, poly_max = project_polygon(axis, vertices)
        circle_min, circle_max = project_circle(axis, circle_center, circle_radius)
        if not is_intervals_overlap(poly_min, poly_max, circle_min, circle_max):
            return False
    
    # 所有分离轴均重叠，判定碰撞
    return True

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