python - How can I check if two segments intersect?

Question

How can I check if 2 segments intersect?

I've the following data:

Segment1 [ {x1,y1}, {x2,y2} ]
Segment2 [ {x1,y1}, {x2,y2} ] 

I need to write a small algorithm in Python to detect if the 2 lines are intersecting.

Answer 1

User @i_4_got points to this page with a very efficent solution in Python. I reproduce it here for convenience (since it would have made me happy to have it here):

def ccw(A,B,C):
    return (C.y-A.y) * (B.x-A.x) > (B.y-A.y) * (C.x-A.x)

# Return true if line segments AB and CD intersect
def intersect(A,B,C,D):
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)