二维平面上线段与直线位置关系的判定

二维平面上线段与直线位置关系的判定

      和点与线段的位置关系的判定类似，在讨论线段与直线的位置关系的时候，也是采用向量的叉积的方法来做的。具体方法是在直线上取两点AB,如下图所示，对于给定的线段CD和CE，不难发现当点C与点E同在直线L（即线段AB）的顺时针方向上(同在逆时针方向上也是成立的)；点C与点D分别在L的不同方向上(一个位于顺时针一个位于逆时针方向上)，此时直线与线段相交；对与线段点落在直线L上的情况在此不做说明，很简单，动手画画就知道了。

    Problem：Segments (http://poj.org/problem?id=3304)

    给定平面上n条线段，判断是否存在一条直线，使得这n条线段在L上的投影至少有一个公共点。

    可能现在你觉得这个问题和线段与直线关系的判定没有什么联系。下面给出具体的分析：先考虑一个特殊的情况，即n=1的时候，如下图，线段AB在直线L上的投影为线段A'B'，则过任意介于A'B'之间的点C'做直线L的垂线必交线段AB与一点C；反之，过线段AB之间任意一点C做直线L的垂线，垂足必定落在A'B'之间。

     不难将此结论推广到n条线段的情况，假设存在一满足题意的直线L，则设点A为各个线段在L上投影的公共点，那么过A做一条直线L的垂线L'，则L'必定与n条线段都相交；反之，过所有线段做一个直线L1使其与n条线段均相交，做直线L1的垂线L2，容易发现垂足即为所有n条线段投影的公共点。

      这样一来就清晰了，问题转化成了判定是否存在一条直线L，L与n条线段均相交。我们只需枚举n条线段，判定是否均与直线L相交。但是，直线L该如何枚举呢？这里采用的方法也是计算几何中常用到得离散化思想。我们知道计算机只能处理离散的数据，我们没有办法来通过连续的旋转直线L来分别判定是否满足题意。但是我们可以采用离散化的思想：假设任意直线L分别于n条线段相交，我们可以采用将直线L分别向顺时针和逆时针的方向旋转，旋转的时候必须满足于n条线段均相交的限制，直到无法旋转为止。那么，最后直线会和n条线段中的某两条的端点重合。这样，我们就可以通过枚举任意两线段端点确定的直线，从而对问题进行求解。

      下面说明一下该问题的两个细节：

       <1>、n=1时要特判；

       <2>、精度问题，当枚举两线段中的端点距离很接近(<1e-8)的时候，不能作为待选直线判定，原因见下图：

 #include<iostream> #include<cstdio> #include<math.h> #define N 110 #define EPS 1e-10 using namespace std; typedef struct Node1 { double x,y; }Point; typedef struct Node2 { Point s,t; }Segment; Segment s[N]; int n; double cross(Point o,Point a,Point b)//求叉积 { return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y); } double dis(Point a,Point b) //求两点距离 { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } int judge(Point a,Point b)//判定是否与n条线段均相交 { if(dis(a,b)<EPS) return 0;//细节2 for(int i=0;i<n;i++) if(cross(a,b,s[i].s)*cross(a,b,s[i].t)>EPS)// 精度控制 return 0; return 1; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%lf%lf%lf%lf",&s[i].s.x,&s[i].s.y,&s[i].t.x,&s[i].t.y); int yes=0; if(n==1) yes=1;//特判 for(int i=0;yes==0&&i<n;i++)//枚举线段定点确定的待选直线 for(int j=i+1;yes==0&&j<n;j++) if(judge(s[i].s,s[j].s)||judge(s[i].s,s[j].t) ||judge(s[i].t,s[j].s)||judge(s[i].t,s[j].t)) yes=1; if(yes) printf("Yes!/n"); else printf("No!/n"); } return 0; }

最后

以上就是可爱芒果为你收集整理的二维平面上线段与直线位置关系的判定的全部内容，希望文章能够帮你解决二维平面上线段与直线位置关系的判定所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。