seamintersect.cpp

使用两个向量的叉积来判断两条线段是否相交

#include <iostream>
using namespace std;


/*求两条线段是否相交首先要求两条线段通过快速排斥实验，即做出能包含两条线段的最小的矩形，既是以两条线段作为对角线的
两个矩形，判断两个矩形是否相交，若两个矩形不能同时在x方向和y方向相交，则两条线段不可能相交，通过了快速排斥实验后再
判断两条线段是否互相跨立，既是一条线段的两个端点是否在另一条线段所在直线的两侧，若满足以上两条，则线段一定相交*/

typedef struct
{
        double x;
        double y;
        }Coordinate;
        
typedef struct
{
        Coordinate start;
        Coordinate end; 
        }Line;
 
int main()
{
      Line a,b;
      Coordinate m,n,p;
      double x,y;
      bool tag;
      cout<<"请输入两条线段的坐标:"<<endl;
      cin>>a.start.x>>a.start.y>>a.end.x>>a.end.y;
      cin>>b.start.x>>b.start.y>>b.end.x>>b.end.y;
      //先判断两矩形是否在x方向上相交
      //若要在x方向上相交，则满足end1.x>start2.x,start1.x<end2.x
      if(a.end.x>=b.start.x&&a.start.x<=b.end.x)
      tag=true;
      else
      tag=false;
      
      if(tag==false)
      {
           cout<<"两条线段不相交!"<<endl;
                system("pause");
           return 0;         
                    }
     //现在判断y方向上是否相交
     //若要在y方向上相交，则满足end1.y>start2.y,start1.y<end2.y
     if(a.end.y>=b.start.y&&a.start.y<=b.end.y)               
     tag=true;
     else
     tag=false;
     
     if(tag==false)
     {
        cout<<"两条线段不相交!"<<endl;
             system("pause");
        return 0;           
                   }
     
     //通过了快速排斥实验后，就使用叉积来判断是否跨立的问题 
     
     //先判断a是否跨立b
     //用a的起点分别与b的两端连成的两条线段与a求叉积，若两条线段分别在a的顺时针与逆时针方向，则a跨立b
     //若在同一侧，则不跨立，两条线段不相交
     m.x=b.start.x-a.start.x;
     m.y=b.start.y-a.start.y;
     n.x=b.end.x-a.start.x;
     n.y=b.end.y-a.start.y;
     p.x=a.end.x-a.start.x;
     p.y=a.end.y-a.start.y;
     x=m.x*p.y-m.y*p.x;
     y=n.x*p.y-n.y*p.x;
     if(x*y<=0)
     tag=true;
     else
     tag=false;
     if(tag==false)
     {
        cout<<"两条线段不相交!"<<endl;
             system("pause");
        return 0; 
                   }
     //现在判断b是否跨立a
  
     m.x=a.start.x-b.start.x;
     m.y=a.start.y-b.start.y;
     n.x=a.end.x-b.start.x;
     n.y=a.end.y-b.start.y;
     p.x=b.end.x-b.start.x;
     p.y=b.end.y-b.start.y;
     x=m.x*p.y-m.y*p.x;
     y=m.y*p.x-m.x*p.y;
  
     if(x*y<=0)
     tag=true;
     else
     tag=false;
     if(tag==false)
     {
         cout<<"两条线段不相交!"<<endl;
              system("pause");
         return 0;          
                   }
                   
   cout<<"两条线段相交!"<<endl;                                   
     system("pause");
     return 0;                                  
}