如何檢查點之間的連接是否相互交叉？

我們有一個4點{a,b,c,d}和希望，如果我們通過在紙上線連接點檢查方式[a;b]和[c;d]將相互交叉。

該點被定義爲(x|y)，因此它可以被繪製到一個2維的座標系統中。

我該如何檢查O(1)？

2015-07-10 Coder55

的C++是無關緊要的。這是基本幾何：http://www.wikihow.com/Algebraically-Find-the-Intersection-of-Two-Lines –

@Marc B，問題是關於兩行**段**而不是兩行。因此，從您發佈的鏈接中獲得答案將超出許多程序員的數學技能。答案在這個鏈接中更加明顯https://en.wikipedia.org/wiki/Intersection_%28Euclidean_geometry%29#Two_line_segments – JSF

有效的方法檢查兩條線段是否相交： 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

來源

2015-07-10 17:53:05 MBo

有沒有辦法返回交點本身？ – Coder55

這是另外一個問題。 Gavin的答案在這裏：http://stackoverflow.com/a/1968345/844416給出了很好的交點計算的實際實現 – MBo

如何檢查點之間的連接是否相互交叉？

回答

相關問題