精华内容
下载资源
问答
  • 编程实现了如何判断一个平面里的两条线段是否相交
  • 判断两条线段是否相交(C++)

    千次阅读 2020-03-22 23:48:36
    判断两线段是否相交(C++)

    背景

    在做51nod上的第1951题时,需要根据给出的两条线段来判断这两条线段是否相交。所以在这里记录一下。

    判断两条线段是否相交有两步:
    ①快速排斥计算
    ②跨立计算

    快速排斥
    给出线条AB、CD,如果以AB、CD为对角线的矩形不相交,那么AB、CD也必不可能相交;如果矩形相交,那么需要再通过跨立计算进行判断。对于矩形不相交,有下面两种情况:
    在这里插入图片描述
    对于上面两种情况,可以分成四类来讨论:
    ①AB两坐标中最大的x值 小于 CD两坐标中最小x值
    ②CD两坐标中最大的x值 小于 AB两坐标中最小x值
    ③AB两坐标中最大的y值 小于 CD两坐标中最小y值
    ④CD两坐标中最大的y值 小于 AB两坐标中最小y值

    只要满足了以上四种的其中一种,就可以认为AB与CD不相交。

    跨立计算

    首先,这里需要用到向量叉乘的算法:其中ABCD是三维空间上的向量,与xOy平面平行。
    在这里插入图片描述
    其次,如下图。AB与CD相交必然有A、B在线段CD两边,C、D在线段AB两边。
    根据上面的公式和右手螺旋法则,如果相交,AB X AC的z坐标值z1与AB X AD的z坐标值z2必然异号;同样的,DC X DA的z坐标值z3与DC X DB的z坐标值z4也必然异号。
    特别的,如果B在CD上时,求得的z坐标值是0。所以只要同时满足z1 X z2 ≤ 0,z3 X z4 ≤ 0,就能保证必然相交
    在这里插入图片描述

    参考代码(C++)

    class line{
    public:
    	int xa;
    	int ya;
    	int xb;
    	int yb;
    	line(){}
    	line(int xa, int ya, int xb, int yb){
    		this->xa = xa;
    		this->ya = ya;
    		this->xb = xb;
    		this->yb = yb;
    	}
    	int get_max_x(){
    		return xa > xb ? xa : xb;
    	}
    	int get_min_x(){
    		return xa > xb ? xb : xa;
    	}
    	int get_max_y(){
    		return ya > yb ? ya : yb;
    	}
    	int get_min_y(){
    		return ya > yb ? yb : ya;
    	}
    };
    
    bool is_intersect(line myline1, line myline2){
    	if(myline1.get_max_x() < myline2.get_min_x() || 
    	   myline2.get_max_x() < myline1.get_min_x() ||
    	   myline1.get_max_y() < myline2.get_min_y() || 
    	   myline2.get_max_y() < myline1.get_min_y())   return false;
    	int res1 = (myline1.xa - myline1.xb) * (myline2.ya - myline1.yb) - (myline1.ya - myline1.yb) * (myline2.xa - myline1.xb);
    	int res2 = (myline1.xa - myline1.xb) * (myline2.yb - myline1.yb) - (myline1.ya - myline1.yb) * (myline2.xb - myline1.xb);
    	
    	int res3 = (myline2.xa - myline2.xb) * (myline1.ya - myline2.yb) - (myline2.ya - myline2.yb) * (myline1.xa - myline2.xb);
    	int res4 = (myline2.xa - myline2.xb) * (myline1.yb - myline2.yb) - (myline2.ya - myline2.yb) * (myline1.xb - myline2.xb);
    	if(res1 * res2 <= 0 && res3 * res4 <= 0) return true;
    	else return false;
    }
    

    参考文章:
    两条线段相交判断学习理解
    判断两条线段是否相交—(向量叉乘)

    展开全文
  • 1.必备知识 向量积(矢积)与数量积(标积)的区别   ...模长:(在这里θ表示两向量之间的夹角(共...判断两条线段是否相交,可以采用向量积的方式来判断,如下图所示: 现定义一个函数初步判断两线...

    1.必备知识
    向量积(矢积)与数量积(标积)的区别
      

    名称标积 / 内积 / 数量积 / 点积矢积 / 外积 / 向量积 / 叉积
    运算式(a,b和c粗体字,表示向量)a·b=|a|·|b|cosθa×b=c,其中|c|=|a|·|b|sinθ,c的方向遵守右手定则
    几何意义向量a在向量b方向上的投影与向量b的模的乘积c是垂直a、b所在平面,且以|b|sinθ为高、|a|为底的平行四边形的面积
    运算结果的区别标量(常用于物理)/数量(常用于数学)矢量(常用于物理)/向量(常用于数学)

    表示方法
    两个向量a和b的叉积写作a×b(有时也被写成a∧b,避免和字母x混淆)。
    定义
    向量积可以被定义为:
    模长:(在这里θ表示两向量之间的夹角(共起点的前提下)(0° ≤ θ ≤ 180°),它位于这两个矢量所定义的平面上。)
    这里写图片描述
    方向:a向量与b向量的向量积的方向与这两个向量所在平面垂直,且遵守右手定则。
    (一个简单的确定满足“右手定则”的结果向量的方向的方法是这样的:若坐标系是满足右手定则的,当右手的四指从a以不超过180度的转角转向b时,竖起的大拇指指向是c的方向。)

    也可以这样定义(等效):
    向量积|c|=|a×b|=|a|·|b|sin< a,b >
    即c的长度在数值上等于以a,b,夹角为θ组成的平行四边形的面积。
    而c的方向垂直于a与b所决定的平面,c的指向按右手定则从a转向b来确定。
    *运算结果c是一个伪向量。这是因为在不同的坐标系中c可能不同。

    这里写图片描述

    2.[C++]这里写图片描述

    代码:

    using namespace std;  
    struct point  
    {  
        double x,y;  
    };  
    struct segment  
    {  
        point begin,end;  
    };  
    double min(double x,double y)  
    {  
        return x<y ? x:y;  
    }  
    double max(double x,double y)  
    {  
        return x>y ? x:y;  
    }  
    bool onsegment(point pi,point pj,point pk) //判断点pk是否在线段pi pj上   
    {  
        if(min(pi.x,pj.x)<=pk.x && pk.x<=max(pi.x,pj.x))  
        {  
            if(min(pi.y,pj.y)<=pk.y && pk.y<=max(pi.y,pj.y))  
            {  
                return true;  
            }  
        }  
        return false;  
    }  
    double direction(point pi,point pj,point pk) //计算向量pkpi和向量pjpi的叉积   
    {  
        return (pi.x-pk.x)*(pi.y-pj.y)-(pi.y-pk.y)*(pi.x-pj.x);  
    }  
    bool judge(point p1,point p2,point p3,point p4) //判断线段p1p2和p3p4是否相交   
    {  
        double d1 = direction(p3,p4,p1);  
        double d2 = direction(p3,p4,p2);  
        double d3 = direction(p1,p2,p3);  
        double d4 = direction(p1,p2,p4);  
        if(d1*d2<0 && d3*d4<0)  
            return true;  
        if(d1==0 && onsegment(p3,p4,p1))  
            return true;  
        if(d2==0 && onsegment(p3,p4,p2))  
            return true;  
        if(d3==0 && onsegment(p1,p2,p3))  
            return true;  
        if(d4==0 && onsegment(p1,p2,p4))  
            return true;  
        return false;  
    }  
    int main()  
    {  
        int n,count;  
        segment seg[101];  
        while(cin>>n&&n)  
        {  
            count = 0;  
            for(int i=1; i<=n; i++)  
            {  
                cin>>seg[i].begin.x>>seg[i].begin.y>>seg[i].end.x>>seg[i].end.y;  
            }  
            for(int i=1; i<n; i++)  
                for(int j=i+1; j<=n; j++)  
                {  
                    if(judge(seg[i].begin,seg[i].end,seg[j].begin,seg[j].end))  
                    {  
                        count++;  
                    }  
                }  
                cout<<count<<endl;  
        }  
        return 0;  
    }

    3.[C++]计算几何之判断线段相交
    给定两个点:

    typedef  struct {
    
      double  x, y;
    
    } Point;
    
    Point A1,A2,B1,B2;

    首先引入两个实验:

    a.快速排斥实验
    设以线段A1A2和线段B1B2为对角线的矩形为M,N;
    若M,N 不相交,则两个线段显然不相交;
    所以:满足第一个条件时:两个线段可能相交。

    b.跨立实验
    如果两线段相交,则两线段必然相互跨立对方.若A1A2跨立B1B2,则矢量( A1 - B1 ) 和(A2-B1)位于矢量(B2-B1)的两侧,

    这里写图片描述
    即(A1-B1) × (B2-B1) * (A2-B1) × (B2-B1)<0。
    上式可改写成(A1-B1) × (B2-B1) * (B2-B1) × (A2-A1)>0。
    应该判断两次,即两条线段都要为直线,判断另一直线的两端点是否在它两边,若是则两线段相交。
    若积极满跨立实验是不行的,如下面的情况:
    这里写图片描述

    即两条线段在同一条直线上。所以我们要同时满足两次跨立和快速排斥实验。

    总体分析:
    当(A1-B1) × (B2-B1)=0时,说明(A1-B1)和(B2-B1)共线,但是因为已经通过快速排斥试验,所以 A1一定在线段 B1B2上;同理,(B2-B1)×(A2-B1)=0 说明A2一定在线段B1B2上。所以判断A1A2跨立B1B2的依据是:(A1-B1) × (B2-B1) * (B2-B1) × (A2-B1) >= 0。
    同理判断B1B2跨立A1A2的依据是:(B1-A1) × (A2-A1) * (A2-A1) × (B2-A1) >= 0。

    如图:
    这里写图片描述

    应用:
    1. 判断两个线段相交
    2. 判断线段与直线相交
    3. 判断点在矩形内

    代码:

    /* 
    (A1-B1) × (B2-B1) * (B2-B1) × (A2-A1) >= 0 
    (B1-A1) × (A2-A1) * (A2-A1) × (B2-A1) >= 0 
    */  
    
    #include<stdio.h>  
    #define min(a,b) a<b?a:b  
    #define max(a,b) a>b?a:b  
    typedef struct {  
    double x,y;  
    }Point;  
    Point A1,A2,B1,B2;  
    Point  A1B1, B2B1, A2A1, B2A1;  
    double xx(Point &s,Point &t)  
    {  
        return (s.x*t.y+s.y*t.x);  
    }  
    int kua()                           //跨立实验  
    {  
        A1B1.x=A1.x-B1.x;  A1B1.y=A1.y-B1.y;  
        B2B1.x=B2.x-B1.x;  B2B1.y=B2.y-B1.y;  
        A2A1.x=A2.x-A1.x;  A2A1.y=A2.y-A1.y;  
        B2A1.x=B2.x-A1.x;  B2A1.y=B2.y-A1.y;  
        if(xx(A1B1,B2B1) * xx(B2B1,A2A1)>=0)  
        {  
            A1B1.y=-A1B1.y;A1B1.x=-A1B1.x;  
            if(xx(A1B1,A2A1) * xx(A2A1,B2A1)>=0)  
                return 1;  
            else  
                return 0;  
        }  
        else  
            return 0;  
    }  
    int main()  
    {  
        Point A1,A2,B1,B2;  
        int flag=1,i,j,a,b,c,d,e,f;  
        while(1)  
        {  
            scanf("%lf%lf%lf%lf", &A1.x, &A1.y, &A2.x, &A2.y);  
            scanf("%lf%lf%lf%lf", &B1.x, &B1.y, &B2.x, &B2.y);  
            if( min(A1.x,A2.x) <= max(B1.x,B2.x) &&  
                min(B1.x,B2.x) <= max(A1.x,A2.x) &&  
                min(A1.y,A2.y) <= max(B1.y,B2.y) &&  
                min(B1.y,B2.y) <= max(A1.y,A2.y)   )   //快速排斥实验  
            {  
                if(kua())  
                    printf("线段相交\n");  
                else  
                    printf("线段不相交\n");  
            }  
            else  
                printf("线段不相交\n");  
    
        }  
        return 0;  
    }  

    4.[CAD]
    判断两条线段是否相交,可以采用向量积的方式来判断,如下图所示:
    这里写图片描述

    这里写图片描述

    现定义一个函数初步判断两线段是否相交,如下代码:

    /// <summary>
    /// 初步根据外围框大致判断两条线段是否相交
    /// </summary>
    /// <param name="line01Coords">线段1的坐标,长度为6</param>
    /// <param name="line02Coords">线段2的坐标,长度为6</param>
    /// <returns>返回类型为bool,如果为true表示两条线段可能相交,如果为false表示两条线段不相交</returns>
    private bool JudgeAboutCrossStatus(double[] line01Coords, double[] line02Coords)
    {
        bool returnResult = true;
        //先判断在XY方向的最值
        double maxX1, minX1, maxY1, minY1;
        maxX1 = minX1 = line01Coords[0];
        maxY1 = minY1 = line01Coords[1];
        if (line01Coords[0] < line01Coords[3])
            maxX1 = line01Coords[3];
        else
            minX1 = line01Coords[3];
        if (line01Coords[1] < line01Coords[4])
            maxY1 = line01Coords[4];
        else
            minY1 = line01Coords[4];
        double maxX2, minX2, maxY2, minY2;
        maxX2 = minX2 = line02Coords[0];
        maxY2 = minY2 = line02Coords[1];
        if (line02Coords[0] < line02Coords[3])
            maxX2 = line02Coords[3];
        else
            minX2 = line02Coords[3];
        if (line02Coords[1] < line02Coords[4])
            maxY2 = line02Coords[4];
        else
            minY2 = line02Coords[4];
        //比较最值大小
        if ((minX1 > maxX2) || (maxX1 < minX2) || (minY1 > maxY2) || (maxY1 < minY2))
        {
            returnResult = false;
        }
        return returnResult;
    }
    函数JudgeAboutCrossStatus()如果返回值为true则表示两条线段可能相交,则需要采用向量积的方式来判断是否相交,如果为false则表示两条线段不相交。现在定义一个函数Judge2LinesRelation ()用于判断两条线段是否相交,其代码如下:
    /// <summary>
    /// 判断两条线段是否相交
    /// </summary>
    /// <param name="line01Coords">线段1的坐标,长度为6</param>
    /// <param name="line02Coords">线段2的坐标,长度为6</param>
    /// <returns>返回类型为bool,如果为true表示两条线段相交,如果为false表示两条线段不相交</returns>
    private bool Judge2LinesRelation(double[] line01Coords, double[] line02Coords)
    {
        bool returnResult = true;
        returnResult = JudgeAboutCrossStatus(line01Coords, line02Coords);
        if (returnResult)//初步判断两条线段可能相交
        {
            double BAx, BAy, BCx, BCy, BDx, BDy, BABCk, BABDk;
            BAx = line01Coords[0] - line01Coords[3];
            BAy = line01Coords[1] - line01Coords[4];
            BCx = line02Coords[0] - line01Coords[3];
            BCy = line02Coords[1] - line01Coords[4];
            BABCk = BAx * BCy - BAy * BCx;
            BDx = line02Coords[3] - line01Coords[3];
            BDy = line02Coords[4] - line01Coords[4];
            BABDk = BAx * BDy - BAy * BDx;
            if (((BABCk > 0) && (BABDk > 0)) || ((BABCk < 0) && (BABDk < 0)))
            {
                returnResult = false;
            }
            else if (((BABCk > 0) && (BABDk < 0)) || ((BABCk < 0) && (BABDk > 0)))
            {
                double BCBDk;
                BCBDk = BCx * BDy - BCy * BDx;
                if (((BABDk > 0) && (BCBDk > 0)) || ((BABDk < 0) && (BCBDk < 0)))
                {
                    returnResult = true;
                }
                else
                {
                    returnResult = false;
                }                   
            }
            else if ((BABCk == 0)||(BABDk==0))//点C或D在直线AB上
            {
                double[] templine02Coords = new double[3];
                if (BABCk == 0)//点C在直线AB上
                {
                    templine02Coords[0] = line02Coords[0];
                    templine02Coords[1] = line02Coords[1];
                    templine02Coords[2] = line02Coords[2];
                }
                else//点D在直线AB上
                {
                    templine02Coords[0] = line02Coords[3];
                    templine02Coords[1] = line02Coords[4];
                    templine02Coords[2] = line02Coords[5];
                }
                if (line01Coords[0] == line01Coords[3])//是否垂直,是则比较Y值
                {
                    double maxY, minY;
                    maxY = minY = line01Coords[1];
                    if (line01Coords[1] < line01Coords[4])
                        maxY = line01Coords[4];
                    else
                        minY = line01Coords[4];
                    if ((templine02Coords[1] >= minY) && (templine02Coords[1] <= maxY))//在线段上
                        returnResult = true;
                    else
                        returnResult = false;
                }
                else //比较X值
                {
                    double maxX, minX;
                    maxX = minX = line01Coords[0];
                    if (line01Coords[0] < line01Coords[3])
                        maxX = line01Coords[3];
                    else
                        minX = line01Coords[3];
                    if ((templine02Coords[0] >= minX) && (templine02Coords[0] <= maxX))//在线段上
                        returnResult = true;
                    else
                        returnResult = false;
                }
            }
        }
        return returnResult;
    }

    相关链接:
    1.土地划分(计算几何——线段相交)
    http://blog.csdn.net/Enjoying_Science/article/details/46755993
    2.叉积、线段相交判断、凸包
    http://blog.csdn.net/hustspy1990/article/details/11082745
    3. 1288: 计算几何练习题——线段相交
    http://blog.csdn.net/da_keng/article/details/24580009

    展开全文
  • 如何判断两条线段是否相交

    千次阅读 2020-02-23 18:11:30
    本篇是在 【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)&...

    本篇是在 【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)<=max(Bx1,Bx2) )&&  //判断x轴投影
           ( max(Ay1,Ay2)>=min(By1,By2)&&min(Ay1,Ay2)<=max(By1,By2) )    //判断y轴投影
          )
        {
            if(
                ( (Bx1-Ax1)*(Ay2-Ay1)-(By1-Ay1)*(Ax2-Ax1) ) *          //判断B是否跨过A
                ( (Bx2-Ax1)*(Ay2-Ay1)-(By2-Ay1)*(Ax2-Ax1) ) <=0 &&
                ( (Ax1-Bx1)*(By2-By1)-(Ay1-By1)*(Bx2-Bx1) ) *          //判断A是否跨过B
                ( (Ax2-Bx1)*(By2-By1)-(Ay2-By1)*(Bx2-Bx1) ) <=0
              )
            {
                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)<=max(Bx1,Bx2)//判断x
    max(Ay1,Ay2)>=min(By1,By2)&&min(Ay1,Ay2)<=max(By1,By2)//判断y
    

    我还有一种非正式但很好理解的说法
    我们把投影到x轴上的投影线段看作两个队伍,这两个队伍要各派一个队员进行比赛,投影线段上的每一个点就是一个队员,点对应的值就是这个队员的能力,两投影线段有重合说明两个队伍都有获胜或平手的可能,怎么样才会出现两个队伍都有获胜或平手可能呢?那就是两个队伍中任意一个队伍能力最强的选手能力要>=另一个队伍中能力最弱的选手,即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。
    R<0 说明A在B的逆时针方向
    R=0 说明A与B共线,可能正向也可能反向
    R>0 说明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的向量积,再将他们相乘,如果结果<=0,即向量积异号或有0。

    if(
                ( (Bx1-Ax1)*(Ay2-Ay1)-(By1-Ay1)*(Ax2-Ax1) ) *          //判断B是否跨过A
                ( (Bx2-Ax1)*(Ay2-Ay1)-(By2-Ay1)*(Ax2-Ax1) ) <=0 &&
                ( (Ax1-Bx1)*(By2-By1)-(Ay1-By1)*(Bx2-Bx1) ) *          //判断A是否跨过B
                ( (Ax2-Bx1)*(By2-By1)-(Ay2-By1)*(Bx2-Bx1) ) <=0
              )
    

    完整代码

    #include <bits/stdc++.h>
    using namespace std;
    bool judge(int Ax1,int Ay1,int Ax2,int Ay2,int Bx1,int By1,int Bx2,int By2);
    int main()
    {
        int Ax1,Ay1,Ax2,Ay2;
        int Bx1,By1,Bx2,By2;
        while(cin >> Ax1 >> Ay1 >> Ax2 >> Ay2 >> Bx1 >> By1 >> Bx2 >> By2)
        {
            if(judge(Ax1,Ay1,Ax2,Ay2,Bx1,By1,Bx2,By2))
                cout << "YES!" << endl ;
            else
                cout << "NO" << endl ;
        }
        return 0;
    }
    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)<=max(Bx1,Bx2) )&&  //判断x轴投影
           ( max(Ay1,Ay2)>=min(By1,By2)&&min(Ay1,Ay2)<=max(By1,By2) )    //判断y轴投影
          )
        {
            if(
                ( (Bx1-Ax1)*(Ay2-Ay1)-(By1-Ay1)*(Ax2-Ax1) ) *          //判断B是否跨过A
                ( (Bx2-Ax1)*(Ay2-Ay1)-(By2-Ay1)*(Ax2-Ax1) ) <=0 &&
                ( (Ax1-Bx1)*(By2-By1)-(Ay1-By1)*(Bx2-Bx1) ) *          //判断A是否跨过B
                ( (Ax2-Bx1)*(By2-By1)-(Ay2-By1)*(Bx2-Bx1) ) <=0
              )
            {
                return 1;
            }
            else
                return 0;
        }
        else
            return 0;
    }
    
    

    关于代码优化

    【C++笔记】如何判断2个线段相交 中已经有谈到,如果不要第一步,可能会出现两条共线但不相交的线段判断的错误,因为共线后向量积都为0,这种情况可以在第一步中被排除掉。

    如果将第二个if的<=0改为<0呢,不就排除了共线不相交了吗?但这样的话我们把刚好相交(一点相交)和共线相交的情况也都排除了。

    那我们允许向量积最多一个为0行不行呢,同样,这样我们把共线相交的情况和两线段共用一个端点的情况也排除了

    暂时还没有想出更优的代码

    相关题目

    P922

    #include <bits/stdc++.h>
    using namespace std;
    bool judge(int Ax1,int Ay1,int Ax2,int Ay2,int Bx1,int By1,int Bx2,int By2);
    int main()
    {
        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 << "YES" << endl ;
                else
                    cout << "no" << endl ;
            }
        }
        return 0;
    }
    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)<=max(Bx1,Bx2) )&&  //判断x轴投影
            ( max(Ay1,Ay2)>=min(By1,By2)&&min(Ay1,Ay2)<=max(By1,By2) )    //判断y轴投影
        )
        {
            if(
                ( (Bx1-Ax1)*(Ay2-Ay1)-(By1-Ay1)*(Ax2-Ax1) ) *          //判断B是否跨过A
                ( (Bx2-Ax1)*(Ay2-Ay1)-(By2-Ay1)*(Ax2-Ax1) ) <=0 &&
                ( (Ax1-Bx1)*(By2-By1)-(Ay1-By1)*(Bx2-Bx1) ) *          //判断A是否跨过B
                ( (Ax2-Bx1)*(By2-By1)-(Ay2-By1)*(Bx2-Bx1) ) <=0
            )
            {
                return 1;
            }
            else
                return 0;
        }
        else
            return 0;
    }
    
    
    展开全文
  • 1 function judgeIntersect... 5 //两个线段为对角线组成的矩形,如果这两个矩形没有重叠的部分,那么两条线段是不可能出现重叠的 6 7 //这里的确如此,这一步是判定两矩形是否相交 8 //1.线段ab的低点低于c...
     1 function  judgeIntersect(x1,y1,x2,y2,x3,y3,x4,y4)
     2 {
     3 
     4     //快速排斥:
     5     //两个线段为对角线组成的矩形,如果这两个矩形没有重叠的部分,那么两条线段是不可能出现重叠的
     6 
     7     //这里的确如此,这一步是判定两矩形是否相交
     8     //1.线段ab的低点低于cd的最高点(可能重合)
     9     //2.cd的最左端小于ab的最右端(可能重合)
    10     //3.cd的最低点低于ab的最高点(加上条件1,两线段在竖直方向上重合)
    11     //4.ab的最左端小于cd的最右端(加上条件2,两直线在水平方向上重合)
    12     //综上4个条件,两条线段组成的矩形是重合的
    13     //特别要注意一个矩形含于另一个矩形之内的情况
    14 
    15     if(!(Math.min(x1,x2)<=Math.max(x3,x4) && Math.min(y3,y4)<=Math.max(y1,y2)&&Math.min(x3,x4)<=Math.max(x1,x2) && Math.min(y1,y2)<=Math.max(y3,y4)))
    16         return false;
    17 
    18     //跨立实验:
    19     //如果两条线段相交,那么必须跨立,就是以一条线段为标准,另一条线段的两端点一定在这条线段的两段
    20     //也就是说a b两点在线段cd的两端,c d两点在线段ab的两端
    21     var u,v,w,z
    22     u=(x3-x1)*(y2-y1)-(x2-x1)*(y3-y1);
    23     v=(x4-x1)*(y2-y1)-(x2-x1)*(y4-y1);
    24     w=(x1-x3)*(y4-y3)-(x4-x3)*(y1-y3);
    25     z=(x2-x3)*(y4-y3)-(x4-x3)*(y2-y3);
    26     return (u*v<=0.00000001 && w*z<=0.00000001);
    27 }
    打赏:

     

    转载于:https://www.cnblogs.com/blueridge/p/9599522.html

    展开全文
  • 计算几何中,判断线段是否相交是最基本的题目。 所谓几何, 最基本的当然就是坐标, 从坐标中我们可以知道位置和方向,比如:一个点... 说到线段, 我们很自然想到直线判断两条直线是否相交只需判断它们斜率是否...
  • 我们把障碍墙看成线段,由个点来表示(P3,P4) 障碍物—用线段点表示 P3,P4 目标点与候选点 P1,P2 class point(): #定义类 def __init__(self,x,y): self.x=x self.y=y def cross(p1,p2,p3):#跨立实验...
  • 问题:已知三维空间中四点A、B、C、D,如何判断线段AB与CD是否相交,若相交则求出交点。 分析: AB、CD要相交,则AB、CD必须要在同一平面内 快速排斥和跨立实验判断是否相交 几何法分析求出交点 先来看看效果,紫色...
  • //aa, bb为一条线段两端点 cc, dd为另一条线段端点 相交返回true, 不相交返回false bool intersect(MapPoint aa, MapPoint bb, MapPoint cc, MapPoint dd) { if (Math.Max(aa.x, bb.x) (cc.x, dd.x)) { ...
  • // 判断两条直线是否有交点,有则计算交点的坐标   // p1,p2是直线一的端点坐标   // p3,p4是直线二的端点坐标   bool  detectIntersect(Point p1, Point p2, Point p3, Point p4)  {...
  • 计算几何-判断两条线段是否相交

    千次阅读 2018-04-30 13:59:48
    原理:如果两条线段相交,那么必须跨立,就是以一条线段为标准,另一条线段的两端点一定在这条线段的两段 也就是说a b两点在线段cd的两端,c d两点在线段ab的两端struct point() { double x,y; }; double multi...
  • 如何判断两条直线是否相交

    千次阅读 2020-02-24 18:44:18
    之前写过一篇如何判断两条线段是否相交,我们紧接这个主题,再来谈谈如何判断两条直线是否相交 如何判断两条直线是否相交 总体来上,判断直线是否相交比判断线段是否相交容易多了 两条直线相交只有两种情况 第一种:...
  • 给定个点: typedef struct {  double x, y;...若M,N 不相交,则线段显然不相交; 所以:满足第一个条件时:线段可能相交。   b.跨立实验   如果线段相交,则线段必然相互跨...
  • 网上很多讲这个问题都不完整,仅仅是叉积一下...问题:给出两条线段,问两线段是否相交? 向量叉乘(行列式计算):向量a(x1,y1),向量b(x2,y2): 首先我们要明白一个定理:向量a×向量b(×为向量叉乘...
  • 问题:给出两条线段,问两线段是否相交? 向量叉乘(行列式计算):向量a(x1,y1),向量b(x2,y2): 首先我们要明白一个定理:向量a×向量b(×为向量叉乘),若结果小于0,表示向量b在向量a的顺时针...
  • 算法 判断两条线段是否相交

    千次阅读 2018-06-07 14:59:35
    if ( delta(1e-6) && delta>=-(1e-6) ) // delta=0,表示线段重合或平行 { return false; } double namenda = determinant(dd.x-cc.x, aa.x-cc.x, aa.y-cc.y, dd.y-cc.y) / delta; if ( namenda>1 || namenda) { ...
  • 方法一:线段AB 线段CD1)先对AB和CD线段的包围盒进行相交性检测,看是否 肯定不相交。2)再用叉积进行进一步判断相交可能性。令:a1 = (B点 - A点) x (D点 - A点) (叉积) a2 = (B - A) x (C - A) (叉积) a3 = ...
  • 判断两条线段是否相交 计算几何

    千次阅读 2016-12-08 21:31:14
    关键问题是:如何判断直线AB是否线段CD相交呢? 设直线AB的方程为:f(x,y) = 0,直线方程可以通过点式求得。 当C和D点不在直线的同侧时,直线AB必然与线段CD相交,也就是说直线AB与线段CD相交的条件为:f(C) * ...
  • AB的最大X坐标,如果小于PQ的最小X坐标,则不相交 CD和UV判断同理,换成Y坐标即可;  step 2: 利用向量叉乘判断(亦称跨立方法) 2D 叉乘可把 2D 点看作 3D 的点( z 轴的值为 0 ),套进 3D 叉乘公式...
  • #pragma mark ------------ 判断两条直线是否相交 + (BOOL)checkLineIntersection:(CGPoint)p1 p2:(CGPoint)p2 p3:(CGPoint)p3 p4:(CGPoint)p4 { CGFloat denominator = (p4.y - p3.y) * (p2.x - p1.x) - (p4.x...
  • 一、判断两条线段是否相交 主要依据是通过矢量的叉积(行列式)的性质: /* 设矢量 P = (x1, y1),Q = ( x2, y2 ),则矢量叉积(行列式)定义为:P × Q = x1*y2 - x2*y1 叉积的一个非常重要性质是可以通过它的...
  • 给定平面直角坐标系上的两条线段判断是否相交。 输入: 有多组测试数据。按Ctrl-C键退出程序。 每组测试数据有2行,每行4个实数,表示线段的两个端点坐标。 输出: 若相交,则输出"yes",否则输出"no"。每...
  • 首先,假设有两条线段p,q,求这两条线段的空间关系。 我们把两条线段的四个顶点看为向量,用坐标表示:p1(p1x,p1y), p2(p2x,p2y), q1(q1x,q1y), q2(q2x, q2y) 则可以计算出两线段对应向量: p = p2 - p1 q =...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,549
精华内容 5,019
关键字:

判断两条线段是否相交