本文主要是介绍判断两个线段相交问题(快速排斥实验跨立实验) (计算几何),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
计算几何中,有 判断两个线段是否相交问题. 用到快速排斥实验和 跨立实验
快速排斥实验,是跨立实验的前提和基础.
假设有点 P1(x1,y1) P2(x2,y2) Q1(x3,y3) Q2(x4,y4) 构成线段 P1P2 Q1Q2 问 P1P2与Q1Q2是否相交
快速排斥实验:
P1P2 对角线构成矩形R, Q1Q2对角线构成矩形T 若 R与T 相交着 通过快速排斥, 否则不通过
矩形相交判断:
§ 方法: 假设 P1 = (x1, y1), P2 = (x2, y2), Q1 = (x3, y3),Q2 = (x4, y4),
设矩形 R的 x坐标的最小边界为 RX1 = min(x1, x2),RX2=max(x1,x2) ,RY1=min(y1,y2)
以此类推,将矩形表示为 R = (RX1, RY1, RX2, RY2)的形式,若两矩形相交,
则相交的部分构成了一个新的矩形 F,我们可以知道 F 的 FX1 = max(RX1, TX1), FY2 = max(RY1, TY1),
FX2 = min(RX2,TX2), FY2 = min(RY2, TX2),得到 F 的各个值之后,
只要判断矩形 F是否成立就知道 R和 T到底有没有相交了
若 FX1 > FX2或 FY1 > Fy1则 F无法构成,RT不相交,否则 RT相交
§跨立实验:(互相跨立)
若 P1P2 跨立 Q1Q2,则 P1,P2 分别在 Q1Q2 所在直线的两端,
则有 (P1 - Q1)*(Q2 - Q1) * (Q2 - Q1)*(P2 - Q1) > 0,当 (P1 - Q1)*(Q2 - Q1) = 0 时,
说明 (P1 - Q1) 与 (Q2 - Q1) 共线,但由于已经经过快速排斥试验,所以 Q1 必为 P1P2 与 Q1Q2 的交点,
依然满足线段相交的条件,则跨立试验可改为:
当 (P1 - Q1)*(Q2 - Q1) * (Q2 - Q1)*(P2 - Q1) >= 0,则 P1P2 跨立 Q1Q2,当 Q1Q2 也跨立 P1P2 的时候,则 P1P2 相交
[代码实现]
#include <iostream>
#include <bits/stdc++.h>
using namespace std;typedef struct Node{double x,y;
}point;
typedef struct Segments{point line;
}Line;
typedef struct Rectangle{point A,B;
}Rec;
double x1,x2,x3,x4,y1,y2,y3,y4;
bool judge1(Rec R,Rec T)
{Rec F;R.A.x=min(x1,x2);R.A.y=min(y1,y2);R.B.x=max(x1,x2);R.B.y=max(y1,y2);T.A.x=min(x3,x4);T.A.y=min(y3,y4);T.B.x=max(x3,x4);T.B.y=max(y3,y4);F.A.x=max(R.A.x,T.A.x); F.A.y=max(R.A.y,T.A.y);F.B.x=min(R.B.x,T.B.x); F.B.y=min(R.B.y,T.B.y);if(F.A.x>=F.B.x || F.A.y>=F.B.y)return false;return true;
}
bool judge2()
{Line P1Q1,P2Q1,Q2Q1,Q2P2,P1P2,Q1P2;P1Q1.line={x1-x3,y1-y3};P2Q1.line={x2-x3,y2-y3};Q2Q1.line={x4-x3,y4-y3};Q2P2.line={x4-x3,y4-y2};Q1P2.line={x3-x2,y3-y2};P1P2.line={x1-x2,y1-y2};// 叉乘 A(x1,y1) X B(x2,y2) = x1y2-x2y1 if( (P1Q1.line.x*Q2Q1.line.y-Q2Q1.line.x*P1Q1.line.y)*(Q2Q1.line.x*P2Q1.line.y-P2Q1.line.x*Q2Q1.line.y)>=0 ){if( (Q1P2.line.x*Q2P2.line.y-Q2P2.line.x*Q1P2.line.y)*(Q2P2.line.x*P1P2.line.y-P1P2.line.x*Q2P2.line.y)>=0 )return true;elsereturn false;}return false;
}
int main()
{Rec R,T;cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;if(!judge1(R,T))cout<<"矩阵R与T矩阵不相交 即 线段P1P2 与线段Q1Q2不相交"<<endl;else{if(judge2)cout<<"线段P1P2 与 线段 Q1Q2 相交"<<endl;elsecout<<"不相交"<<endl; } return 0;
}
/*
-2 0
1 2
-1 1
2 -1
*/
这篇关于判断两个线段相交问题(快速排斥实验跨立实验) (计算几何)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!