Line segment intersection

intersection.py

def intersects(line_1, line_2):
    """Whether line_1 and line_2 intersect or not."""
    A, B = line_1
    C, D = line_2
    if _ccw(A,C,D) != _ccw(B,C,D) and _ccw(A,B,C) != _ccw(A,B,D):
        # If the triangle pairs ACD, BCD and ABC, ABD have different
        # orientations, then the segments have to intersect
        return True

    for pt in line_2:
        if are_coll(A, B, pt):
            # check if pt is between A and B
            if sorted([A, B, pt])[1] == pt:
                return True

    for pt in line_1:
        if are_coll(C, D, pt):
             # check if pt is between A and D
            if sorted([C, D, pt])[1] == pt:
                return True

    return False

def are_coll(p1, p2, p3, eps=1e-6):
    """Determines whether given three points are collinear or not."""
    x, y = 0, 1
    lhs = (p2[x] - p1[x]) * (p3[y] - p1[y]) 
    rhs = (p2[y] - p1[y]) * (p3[x] - p1[x])
    return abs(lhs - rhs) < eps

def _ccw(A,B,C):
    """Determines whether triangle ABC is clockwise or anti-clockwise."""
    return (C[1]-A[1])*(B[0]-A[0]) > (B[1]-A[1])*(C[0]-A[0])