如何判断两条线段相交（python实现）

如何判断两条线段相交（python实现）

那如何来判断两线段是否相交呢？

假设有两条线段AB，CD，若AB，CD相交，我们可以确定：

1.线段AB与CD所在的直线相交，即点A和点B分别在直线CD的两边；

2.线段CD与AB所在的直线相交，即点C和点D分别在直线AB的两边；

上面两个条件同时满足是两线段相交的充要条件，所以我们只需要证明点A和点B分别在直线CD的两边，点C和点D分别在直线AB的两边，这样便可以证明线段AB与CD相交了。

那判断两线段是否相交与一开始提到的向量叉乘定理有什么关系呢？有，我们可以通过叉乘来证明上面说的充要条件。看下图：

这样，方法就出来了：如果线段CD的两个端点C和D，与另一条线段的一个端点（A或B，只能是其中一个）连成的向量，与向量AB做叉乘，若结果异号，表示C和D分别在直线AB的两边，若结果同号，则表示CD两点都在AB的一边，则肯定不相交。

当然，不能只证明C，D在直线AB的两边，还要用相同的方法证明A，B在直线CD的两边，两者同时满足才是线段相交的充要条件。

不过，线段相交还有一些特殊情况：

1.只有1点相交，如下图：

首先，我们给没条线段的两个端点排序，大小判断方法如下：横坐标大的点更大，横坐标相同，纵坐标大的点更大。

排好序后，每条线段中，小的点当起点，大的当终点。我们计算向量AB×向量CD，若结果为0，表示线段AB平行CD，平行才有了重合的可能；但平行也分共线和不共线，只有共线才有可能重合，看下图：

我们可以在两条线段中各取一点，用这两点组成的向量与其中一条线段进行叉乘，结果若为0，就表示两线段共线，如下图：

我们取向量BC，若BC×CD = 0，表示两点共线，即是第二种情况，否则就是第一种情况。第一种情况肯定不相交。猴子为什么不喜欢平行线？因为他们没有相交。。。（尬）

然然然然然而，即使他们共线，却还是不一定重合，就如上图中第二种情况。这时候，之前给点排序的妙处就体现出来了：

若一条线段AB与另一条线段CD共线，且线段AB的起点小于等于线段CD的起点，但线段AB的终点（注意是终点）大于等于线段CD的起点（注意是起点），或者交换一下顺序，CD的起点小于AB的起点…只要满足其中一个，就表示有重合部分。

### l1 [xa, ya, xb, yb] l2 [xa, ya, xb, yb]def Intersect(l1, l2): v1 = (l1[0] - l2[0], l1[1] - l2[1]) v2 = (l1[0] - l2[2], l1[1] - l2[3]) v0 = (l1[0] - l1[2], l1[1] - l1[3]) a = v0[0] * v1[1] - v0[1] * v1[0] b = v0[0] * v2[1] - v0[1] * v2[0] temp = l1 l1 = l2 l2 = temp v1 = (l1[0] - l2[0], l1[1] - l2[1]) v2 = (l1[0] - l2[2], l1[1] - l2[3]) v0 = (l1[0] - l1[2], l1[1] - l1[3]) c = v0[0] * v1[1] - v0[1] * v1[0] d = v0[0] * v2[1] - v0[1] * v2[0] if a*b < 0 and c*d < 0: return True else: return False

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。