判断两条线段是否相交——快速排斥实验和跨立实验

2022-04-20 约 938 字预计阅读 2 分钟次阅读

题目

题目：在二维坐标系中，给你两条线段的四个端点坐标，问如何判断两条线段是否相交？

初步分析：我们知道，对于直线来说不平行就相交，非常好判断。但是对于线段来说，有共线相交，共线不相交，不共线相交，不共线不相交等情况。我们要找到一个优雅的办法，把所有的情况都能考虑到。下面介绍两步就能判断的方法：

第一步：快速排斥实验

**如果两线段在x，y的投影都不重合，是不可能会相交的。**换一种说法，就是以两条线段为对角线画矩形，两矩形如果没有重合的地方，那么两线段也一定不相交。

假设给出的四个点为Ax1, Ay1,Ax2,Ay2,Bx1,By1,Bx2,By2，代码如下：

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

除此之外，这一步还能排除一个特殊情况：共线不相交

第二步：跨立实验

先了解一个线性代数知识：叉积

向量A和向量B叉积，如果AxB>0，那么B在A的逆时针方向，如果AxB<0，那么B在A的顺时针方向。如果AxB=0，那么B与A共线。

图我就不画了，很好理解，AxB = a*b*sin(theta)

把端点移到原点，向量(x1,y1)与向量 （x2，y2）的叉积为 x1*y2-x2*y1

然后对于两直线相交的情况，我们发现它有一个性质，就是向量A1B1叉乘向量A1A2的符号一定与向量A1B2叉乘向量A1A2的符号相反。为了方便写代码，我们把其中一个端点移到零点。

代码：

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
          )

还有一种特殊的情况，一条线段的端点在另一条线段上，这样的话A1B1与A1A2的叉积为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;
}

参考资料：https://blog.csdn.net/NEFU_kadia/article/details/104462906

目录

判断两条线段是否相交——快速排斥实验和跨立实验

题目

第一步：快速排斥实验

第二步：跨立实验

完整代码