如何判断两条线段相交(python实现) | 您所在的位置:网站首页 › 判断两条线段是否交叉 › 如何判断两条线段相交(python实现) |
向量叉乘(行列式计算):向量a(x1,y1),向量b(x2,y2):
那如何来判断两线段是否相交呢? 假设有两条线段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点相交,如下图:
2.两条线段重合,如下图: 首先,我们给没条线段的两个端点排序,大小判断方法如下:横坐标大的点更大,横坐标相同,纵坐标大的点更大。 排好序后,每条线段中,小的点当起点,大的当终点。我们计算向量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 |
CopyRight 2018-2019 实验室设备网 版权所有 |