判断两条线段是否相交

extince volcano — Thu, 12 Oct 2006 08:39:00 GMT

方法一、
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 && x2Miny01 && y2Minx01 && x3Miny01 && y3             || (x0>Minx23 && x0Miny23 && y0Minx23 && x1Miny23 && y1             { //实际碰撞问题线段重合认为相交了
                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) }

//一种线段相交判断函数，当且仅当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)));
}

extince volcano 2006-10-12 16:39 发表评论

C++博客-smiling

判断两条线段是否相交