CODEWITHSUNDEEP
pythonvectorgraphicssimulationcollision-detection
Datruc
Datruc

Reputation: 11

Problem SAT collision detection algorithm (circle-polygone)

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 alignement
        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 alignement

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 dont see any problems, so I don't know where is it

Upvotes: 1

Views: 37

Answers (1)

Neil Butcher
Neil Butcher

Reputation: 608

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

Upvotes: 0

Related Questions