本文主要是介绍判断两线段是否相交(快速排斥和跨立),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
背景知识:
判断两线段是否相交:
我们分两步确定两条线段是否相交:
(1)快速排斥试验
设以线段 P1P2 为对角线的矩形为R,
设以线段 Q1Q2 为对角线的矩形为T,
如果R和T不相交,显然两线段不会相交。
(2)跨立试验
如果两线段相交,则两线段必然相互跨立对方。若P1P2跨立Q1Q2 ,则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧,即( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0。上式可改写成( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0。当 ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时,说明 ( P1 - Q1 ) 和 ( Q2 - Q1 )共线,但是因为已经通过快速排斥试验,所以 P1 一定在线段 Q1Q2上;同理,( Q2 - Q1 ) ×(P2 - Q1 ) = 0 说明 P2 一定在线段 Q1Q2上。所以判断P1P2跨立Q1Q2的依据是:( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) >= 0。同理判断Q1Q2跨立P1P2的依据是:( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - P1 ) × ( Q2 - P1 ) >= 0。具体情况如下图所示:
程序模版:
#include"stdio.h"
#include"string.h"
#include"math.h"
#include"stdlib.h"
#define M 101
#define inf 999999999
#define eps 1e-10
typedef struct node
{double x,y;
}P;
typedef struct line
{P s;P e;
}Line;
Line L[M];
double max(double x,double y)
{return x>y?x:y;
}
double min(double x,double y)
{return x<y?x:y;
}
int paichi(line a,line b)//快速排斥,若通过快速排斥进行跨立实验,否则无交点;
{if(max(a.e.x,a.s.x)>=min(b.s.x,b.e.x)&&max(b.s.x,b.e.x)>=min(a.s.x,a.e.x)&&max(a.s.y,a.e.y)>=min(b.s.y,b.e.y)&&max(b.s.y,b.e.y)>=min(a.s.y,a.e.y))return 1;elsereturn 0;
}
double cross(node a,node b,node c)//叉积
{double x1=b.x-a.x;double y1=b.y-a.y;double x2=c.x-a.x;double y2=c.y-a.y;return x1*y2-x2*y1;
}
int kuali(line a,line b)//跨立实验(通过相互跨立则可确定两线段相交返回1)
{if(cross(a.s,a.e,b.s)*cross(a.s,a.e,b.e)<=0&&cross(b.s,b.e,a.s)*cross(b.s,b.e,a.e)<=0)return 1;return 0;
}
相关题目:
hdu1086 判断线段相交
You can Solve a Geometry Problem too
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 6740 Accepted Submission(s): 3256
Give you N (1<=N<=100) segments(线段), please output the number of all intersections(交点). You should count repeatedly if M (M>2) segments intersect at the same point.
Note:
You can assume that two segments would not intersect at more than one point.
A test case starting with 0 terminates the input and this test case is not to be processed.
2 0.00 0.00 1.00 1.00 0.00 1.00 1.00 0.00 3 0.00 0.00 1.00 1.00 0.00 1.00 1.00 0.000 0.00 0.00 1.00 0.00 0
1 3
程序:
#include"stdio.h"
#include"string.h"
#include"math.h"
#include"stdlib.h"
#define M 101
#define inf 999999999
#define eps 1e-10
typedef struct node
{double x,y;
}P;
typedef struct line
{P s;P e;
}Line;
Line L[M];
double max(double x,double y)
{return x>y?x:y;
}
double min(double x,double y)
{return x<y?x:y;
}
int paichi(line a,line b)//快速排斥,若通过快速排斥进行跨立实验,否则无交点;
{if(max(a.e.x,a.s.x)>=min(b.s.x,b.e.x)&&max(b.s.x,b.e.x)>=min(a.s.x,a.e.x)&&max(a.s.y,a.e.y)>=min(b.s.y,b.e.y)&&max(b.s.y,b.e.y)>=min(a.s.y,a.e.y))return 1;elsereturn 0;
}
double cross(node a,node b,node c)//叉积
{double x1=b.x-a.x;double y1=b.y-a.y;double x2=c.x-a.x;double y2=c.y-a.y;return x1*y2-x2*y1;
}
int kuali(line a,line b)//跨立实验(通过相互跨立则可确定两线段相交返回1)
{if(cross(a.s,a.e,b.s)*cross(a.s,a.e,b.e)<=0&&cross(b.s,b.e,a.s)*cross(b.s,b.e,a.e)<=0)return 1;return 0;
}
int main()
{int n,i,j;while(scanf("%d",&n),n){for(i=1;i<=n;i++)scanf("%lf%lf%lf%lf",&L[i].s.x,&L[i].s.y,&L[i].e.x,&L[i].e.y);int cnt=0;for(i=1;i<=n;i++){for(j=i+1;j<=n;j++){if(paichi(L[i],L[j])&&kuali(L[i],L[j]))cnt++;}}printf("%d\n",cnt);}
}
poj1127
题目:
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 3066 | Accepted: 1376 |
Description
Input
When n=0,the input is terminated.
There will be no illegal input and there are no zero-length straws.
Output
Sample Input
7 1 6 3 3 4 6 4 9 4 5 6 7 1 4 3 5 3 5 5 5 5 2 6 3 5 4 7 2 1 4 1 6 3 3 6 7 2 3 1 3 0 02 0 2 0 0 0 0 0 1 1 1 2 2 1 2 0 00
Sample Output
CONNECTED NOT CONNECTED CONNECTED CONNECTED NOT CONNECTED CONNECTED CONNECTED CONNECTED CONNECTED分析:判断线段相交+并查集
程序:
#include"stdio.h"
#include"string.h"
#include"math.h"
#include"stdlib.h"
#define M 101
#define inf 999999999
#define eps 1e-10
typedef struct node
{double x,y;
}P;
int f[M];
int finde(int x)
{if(x!=f[x])f[x]=finde(f[x]);return f[x];
}
void make(int a,int b)
{int x=finde(a);int y=finde(b);if(x!=y)f[x]=y;
}
double max(double x,double y)
{return x>y?x:y;
}
double min(double x,double y)
{return x<y?x:y;
}
typedef struct line
{P s;P e;
}Line;
Line L[M];
int paichi(line a,line b)
{if(max(a.e.x,a.s.x)>=min(b.s.x,b.e.x)&&max(b.s.x,b.e.x)>=min(a.s.x,a.e.x)&&max(a.s.y,a.e.y)>=min(b.s.y,b.e.y)&&max(b.s.y,b.e.y)>=min(a.s.y,a.e.y))return 1;elsereturn 0;
}
double cross(node a,node b,node c)
{double x1=b.x-a.x;double y1=b.y-a.y;double x2=c.x-a.x;double y2=c.y-a.y;return x1*y2-x2*y1;
}
int kuali(line a,line b)
{if(cross(a.s,a.e,b.s)*cross(a.s,a.e,b.e)<=0&&cross(b.s,b.e,a.s)*cross(b.s,b.e,a.e)<=0)return 1;return 0;
}
int main()
{int i,n,j;while(scanf("%d",&n),n){for(i=1;i<=n;i++)scanf("%lf%lf%lf%lf",&L[i].s.x,&L[i].s.y,&L[i].e.x,&L[i].e.y);for(i=1;i<=n;i++)f[i]=i;for(i=1;i<=n;i++){for(j=i+1;j<=n;j++){if(paichi(L[i],L[j])&&kuali(L[i],L[j]))make(i,j);}}int a,b;while(scanf("%d%d",&a,&b),a||b){if(finde(a)==finde(b))printf("CONNECTED\n");elseprintf("NOT CONNECTED\n");}}return 0;
}
这篇关于判断两线段是否相交(快速排斥和跨立)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!