如何检查点之间的连接是否相互交叉？

Question

让我们考虑以下问题：

我们有一个4点{a,b,c,d}和希望，如果我们通过在纸上线连接 点检查 方式[a;b]和[c;d]将相互交叉。

该点被定义为(x|y)，因此它可以被绘制到一个2维的坐标系统 中。

我该如何检查O(1)？

Answer 1

有效的方法检查两条线段是否相交： AB和CD相交，如果C和D点位于相对于AB线的不同半平面中，并且C和D位于相对于CD线。 Here is简洁Python实现：

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

def intersect(A,B,C,D): 
     return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D) 

的特殊情况下彻底治疗（共线，重合）is described here