python - 如何检查两个线段是否相交？

Question

如何检查两个线段是否相交？

我有以下数据:

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

我需要用 Python 编写一个小算法来检测两条线是否相交。

Answer 1

用户@i_4_got 指向this page在 Python 中有一个非常有效的解决方案。为了方便起见，我在这里复制它(因为它会让我很高兴在这里拥有它):

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)