collision.py

def collision(t1,t2):
    """
        collision(t1,t2)
        @Params: t1,t2 => ((x,y),(x,y),(x,y)) where x,y are floats
        @Return: Boolean (True if the two triangles collide, else False)
        
        Triangle collision detection via a vectoral approach.
        Imagine two triangles of verticies (a,b,c) and (d,e,f)
        a,b,c,d,e,f ~ (x,y) within Reals
        We can then serialize each triangle/polygon into a 2-dimensional array ((x,y),(x,y),...,(x,y))

        If a triangle collides with another triangle within a 2D plane, then at least one of its edges
        intersect with at least one edge of the other triangle.

        Imagine we have two edges bounded by the vertices (a,b) and (d,e)
        line(a=>b) = (b-a)*mu + a
        line(d=>e) = (e-d)*lambda + d

        or
             (     )        ( a.x )
        ab = | b-a | * mu + |     |
             (     )        ( a.y )

             (     )        ( d.x )
        de = | e-d | * lm + |     |
             (     )        ( d.y )

        let <x,y> = b-a and <x',y'> = e-d

        x*mu+a.x = x'*lm+d.x
        y*mu+a.y = y'*lm+d.y

        -y(x*mu+a.x = x'*lm+d.x)
         x(y*mu+a.y = y'*lm+d.y)
        lm*(xy'-x'y) = x*a.y-y*a.x+y*d.x-x*d.y

                x*(a.y-d.y)+y*(d.x-a.x)
        lamda = -----------------------
                      xy' - x'y

        if we let a,b,d,e be represented by a tuple/array of order 2 then
        *.x = *[0]
        *.y = *[1]
        x = b[0]-a[0]
        y = b[1]-a[1]
        x' = xp = e[0]-d[0]
        y' = yp = e[1]-d[1]

        The intersection point will thus be
        (x' * lambda + d.x, y' * lambda + d.y)
        And we then check if this point is in the "range" of the line segment
    """
    permutations = (
        (0,0),(0,1),(0,2),
        (1,1),(1,2),
        (2,2)
    )

    for A,B in permutations:
        a,b = t1[A],t1[(A+1)%3]
        d,e = t2[B],t2[(B+1)%3]
        x,y = b[0]-a[0],b[1]-a[1]
        xp,yp = e[0]-d[0],e[1]-d[1]

        if not x*yp-xp*y: #Parallel or Same Line
            if not int(x) and not (a[0] == d[0]): return True  #Hrz Line: X's must be equal
            if not int(y) and not (a[1] == d[1]): return True  #Vrt Line: Y's must be equal
            if not ((d[0]-a[0])/x == (d[1]-a[1])/y): return True #Parallel
            continue

        _lambda = float(x*(a[1]-d[1])+y*(d[0]-a[0]))/(x*yp-xp*y)
        intersection = (xp*_lambda+d[0], yp*_lambda+d[1])

        #Now we have to make sure that the intersection point falls within the segment
        A_ = ((a[0],b[0]),(a[1],b[1])) # = zip(a,b)
        B_ = ((d[0],e[0]),(d[1],e[1])) # = zip(d,e)
        bool = min(A_[0])<=intersection[0]<=max(A_[0]) and min(A_[1])<=intersection[1]<=max(A_[1]) and min(B_[0])<=intersection[0]<=max(B_[0]) and min(B_[1])<=intersection[1]<=max(B_[1])
        if bool: return True
    return False

triangles = ( # Collides
             ((4.,0.), (2.,0.), (0.,2.)),
             ((1.,1.), (5.,5.), (6.,6.))
            )
triangles_2 = ( # Do Not Collide
             ((1.,0.), (2.,0.), (0.,2.)),
             ((4.,1.), (5.,5.), (6.,6.))
            )

assert collision(*triangles)
assert not collision(*triangles_2)

print "Success"