如何判断两条线段是否相交

2023-08-14 01:44| 来源: 网络整理| 查看: 265

本篇是在【C++笔记】如何判断2个线段相交的基础上加上自己的理解和实践总结出的判断两线段是否相交的方法。

判断两条线段是否相交

先附上判断函数

bool judge(int Ax1,int Ay1,int Ax2,int Ay2,int Bx1,int By1,int Bx2,int By2) { if( ( max(Ax1,Ax2)>=min(Bx1,Bx2)&&min(Ax1,Ax2)=min(By1,By2)&&min(Ay1,Ay2) return 1; } else return 0; } else return 0; }

判断一共分为两步，即code中的第一个if和第二个if 第一步：判断两线段在x轴和y轴的投影是否有交，有任何一条轴没有交点就不可能相交。（快速排斥实验）第二步：判断两条直线是否相互跨过，用跨立来判断，具体用到的知识是向量积。（跨立实验）

第一步：快速排斥实验

很好理解吧，如果两线段在x，y的投影都不重合，是不可能会相交的。求解的方法也有很多种，这里我就介绍我理解的这个方法。拿x轴举例，y轴可类比

投影要有重合（哪怕只是一个点也算），那么两线段中任意一条线段的两端点中x较大的那一个端点的x值一定要大于另一条线段的两端点中x较小的那一个端点的x值，不然这两线段一定是相离的，在x轴投影没有重合。

前面是先A线段对B线段，后面是B线段对A线段

max(Ax1,Ax2)>=min(Bx1,Bx2)&&min(Ax1,Ax2)=min(By1,By2)&&min(Ay1,Ay2)=另一个队伍中能力最弱的选手，即max(A)>=min(B)&&max(B)>=min(A)。这样，只要A派出最强的，B派出最弱的，A就会获胜或平手;B派出最强的，A派出最弱的，B就会获胜或平手。

第二步：跨立实验

两个坐标A(x1,y1),B(x2,y2),那么AxB的向量积就是x1y2-y1x2。我们假定一个向量积R，R=x1y2-y1x2。 R0 说明A在B的顺时针方向

我们证明两线段的跨立就需要证明A跨立B且B跨立A 如何证明跨立？我们以B跨立A举例 B跨立A的意思就是B线段与A所在的直线有交点。我们在A的两端点中任意选一个端点，将它与B的两个端点相连得到L1,L2 在这里插入图片描述若此时A线段向量在L1，L2的中间或L1，L2的边上，就能说明B跨立A 即L1，L2在A的不同的顺逆时针方向，我们就可以分别求出两个L的向量积，再将他们相乘，如果结果 if(judge(Ax1,Ay1,Ax2,Ay2,Bx1,By1,Bx2,By2)) cout if( ( (Bx1-Ax1)*(Ay2-Ay1)-(By1-Ay1)*(Ax2-Ax1) ) * //判断B是否跨过A ( (Bx2-Ax1)*(Ay2-Ay1)-(By2-Ay1)*(Ax2-Ax1) ) int Ax1,Ay1,Ax2,Ay2; int Bx1,By1,Bx2,By2; int n; while(cin >> n && n) { while(n--) { cin >> Ax1 >> Ay1 >> Ax2 >> Ay2 >> Bx1 >> By1 >> Bx2 >> By2; if(judge(Ax1,Ay1,Ax2,Ay2,Bx1,By1,Bx2,By2)) cout if( ( (Bx1-Ax1)*(Ay2-Ay1)-(By1-Ay1)*(Ax2-Ax1) ) * //判断B是否跨过A ( (Bx2-Ax1)*(Ay2-Ay1)-(By2-Ay1)*(Ax2-Ax1) )

【本文地址】

公司简介

联系我们