如何检查点之间的连接是否相互交叉？
如何检查点之间的连接是否相互交叉？
提问于 2015-07-11 00:58:40
让我们考虑以下问题：
我们有一个4点的{a,b,c,d}，我们想检查如果我们用纸上的线连接这两个点，[a;b]和[c;d]的方式是否会相互交叉。
该点被定义为(x|y)，因此可以绘制到二维坐标系中。
如何在O(1)中进行检查
回答 1
Stack Overflow用户
发布于 2015-07-11 01:53:06
如果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
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/31346374
复制相关文章
相似问题
腾讯云开发者
