学步园

转载自：http://www.cppblog.com/smiling/archive/2006/10/12/13605.html

方法一、

bool TwoLineIsIntersect(float x0, float y0, float x1, float y1, float x2, float y2, float x3, float y3, float &InterX, float &InterY)
{ //两条线段是否相交X0X1 AND X1X2
   float x, y;
   float Minx01 = Min(x0, x1);
   float Miny01 = Min(y0, y1);
   float Minx23 = Min(x2, x3);
   float Miny23 = Min(y2, y3);
   float Maxx01 = Max(x0, x1);
   float Maxy01 = Max(y0, y1);
   float Maxx23 = Max(x2, x3);
   float Maxy23 = Max(y2, y3);
   
   if(x1!=x0 && x2!=x3)
   {
       float k1 = (y1-y0)/(x1-x0);
       float k2 = (y3-y2)/(x3-x2);
       float Den = (y1-y0)*(x3-x2) - (y3-y2)*(x1-x0);
       if(k1==k2)
       { //平行不相交
          float d1 = abs(y0*(x1-x0)-x0*(y1-y0)-y2*(x3-x2)+x2*(y3-y2)); //距离公式d = abs(c1-c2) / sqrt(a*a+b*b)
          if(d1==0)
          {//直线重合
             if((x2>Minx01 && x2<Maxy01 && y2>Miny01 && y2<Maxy01) || (x3>Minx01 && x3<Maxy01 && y3>Miny01 && y3<Maxy01)
             || (x0>Minx23 && x0<Maxy23 && y0>Miny23 && y0<Maxy23) || (x1>Minx23 && x1<Maxy23 && y1>Miny23 && y1<Maxy23))
             {  //实际碰撞问题线段重合认为相交了
                return true;
             }
             else
             {
                return false;
             }
          }
          else
          {
             return false;
          }   
       }
       x = ((y2-y0)*(x1-x0)*(x3-x2)+(y1-y0)*(x3-x2)*x0-(y3-y2)*(x1-x0)*x2)/Den;
       y = ((y1-y0)*(x-x0))/(x1-x0) + y0;
       if(Minx01<=x && x<=Maxx01 && Miny01<=y && y<=Maxy01 && Minx23<=x && x<=Maxx23 && Miny23<=y && y<=Maxy23)
       {
          InterX = x;
          InterY = y;
          return true;
       }
   }
   else if(x1==x0 && x2!=x3)
   {
       x = x0;
       y = ((y3-y2)*(x0-x2))/(x3-x2) + y2;
       if(Minx01<=x && x<=Maxx01 && Miny01<=y && y<=Maxy01 && Minx23<=x && x<=Maxx23 && Miny23<=y && y<=Maxy23)
       {
          InterX = x;
          InterY = y;
          return true;
       }
   }
   else if(x1!=x0 && x2==x3)
   {
       x = x2;
       y = ((y1-y0)*(x2-x0))/(x1-x0) + y0;
       if(Minx01<=x && x<=Maxx01 && Miny01<=y && y<=Maxy01 && Minx23<=x && x<=Maxx23 && Miny23<=y && y<=Maxy23)
       {
          InterX = x;
          InterY = y;
          return true;
       }       
   }
   return false;
}

方法二、

(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 。

#define   EP   1e-10   
    
  struct   YPoint{   
  double   x,y;   
  };   
    
  struct   YLineSeg{   
  YPoint   a,b;   
  };   
  //确定两条线段是否相交   
  int   Yu_GeometryLibrary::intersect(YLineSeg   u,YLineSeg   v)   
  {   
  return(   (max(u.a.x,u.b.x)>=min(v.a.x,v.b.x))&&   
                  (max(v.a.x,v.b.x)>=min(u.a.x,u.b.x))&&   
                  (max(u.a.y,u.b.y)>=min(v.a.y,v.b.y))&&   
                  (max(v.a.y,v.b.y)>=min(u.a.y,u.b.y))&&   
                  (multiply(v.a,u.b,u.a)*multiply(u.b,v.b,u.a)>=0)&&   
                  (multiply(u.a,v.b,v.a)*multiply(v.b,u.b,v.a)>=0));   
  }   
    
  //判断两个点是否相等   
  int   Yu_GeometryLibrary::Euqal_Point(YPoint   p1,YPoint   p2)   
  {   
  return((fabs(p1.x-p2.x)<EP)&&(fabs(p1.y-p2.y)<EP));   
  }   
    
  //一种线段相交判断函数，当且仅当u,v相交并且交点不是u,v的端点时函数为true;   
  int   Yu_GeometryLibrary::intersect_A(YLineSeg   u,YLineSeg   v)   
  {   
  return((intersect(u,v))&&   
                (!Euqal_Point(u.a,v.a))&&   
                (!Euqal_Point(u.a,v.b))&&   
                (!Euqal_Point(u.b,v.a))&&   
                (!Euqal_Point(u.b,v.b)));   
  }