Problem SAT collision detection algorithm (circle-polygone)

Question

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

I'm doing a golf game, so I'm trying to make a collision detection algorithm (SAT) for a polygon and a circle. This code can detect collision only if the shapes are roughly on the horizontal axis (here it works just fine). However, on the vertical axis, no matter the distance, they're considered to be touching (as long as a pixel of one shape is between the x coordinates of the other one)

I'm trying to change the conditions in check_overlaps, but now I don't see any problems, so I don't know where is it

Neil Butcher · Accepted Answer · 2025-02-18 15:58:10Z

0

I think the condition for the overlap is Both overlap in x and overlap in y.

Your check_overlap only considers y if the 4 numbers in x are identical, otherwise it only checks x.

The 4 floating point numbers are very unlikely to be identical
You want to check the y condition in all cases anyway

I don't have a test case to try but I would advise trying

def check_overlap(pos):
    (x1, y1), (x2, y2) = pos[0], pos[1]
    (x3, y3), (x4, y4) = pos[2], pos[3]
    def is_between(a, b, c):
        return min(a, b) <= c <= max(a, b)
    y_overlap =  is_between(y1, y2, y3) or is_between(y1, y2, y4) or is_between(y3, y4, y1) or is_between(y3, y4, y2)
    x_overlap =  is_between(x1, x2, x3) or is_between(x1, x2, x4) or is_between(x3, x4, x1) or is_between(x3, x4, x2) 
    return y_overlap and x_overlap

answered Feb 18 at 15:58

Neil Butcher

1,0641 gold badge3 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Problem SAT collision detection algorithm (circle-polygone)

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related