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

> 发布于：2022-04-20 | 分类：刷题, 笔记 | 原文：https://www.imbailey.cn/post/line-segments-intersect-rapid-rejection-straddle-test

##  题目

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

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

### 第一步：快速排斥实验

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

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

```c++
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
```

{{< figure src="https://myblog-1257298572.cos.ap-shanghai.myqcloud.com/mypic/img/image-20220420192637246.png" >}}



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

{{< figure src="https://myblog-1257298572.cos.ap-shanghai.myqcloud.com/mypic/img/image-20220420192903407.png" >}}



## 第二步：跨立实验

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

向量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`

{{< figure src="https://myblog-1257298572.cos.ap-shanghai.myqcloud.com/mypic/img/image-20220420194457870.png" >}}

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

{{< figure src="https://myblog-1257298572.cos.ap-shanghai.myqcloud.com/mypic/img/image-20220420194742929.png" >}}

代码：

```c++
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，我们只要把判断条件加一个等于号就行了。

{{< figure src="https://myblog-1257298572.cos.ap-shanghai.myqcloud.com/mypic/img/image-20220420195012826.png" >}}



## 完整代码

```C++
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