判断两条线段是否相交

[ChuChencheng]

问题

在空间中有两条线段 P, Q ，由 4 个点组成，P1P2 ，Q1Q2 ，已知 4 个点的坐标，怎么判断两条线段是否相交？

快速排斥实验和跨立实验

只有同时通过这两个实验，这两条线段才是相交的。

已知点：

P1(x1, y1), P2(x2, y2), Q1(x3, y3), Q2(x4, y4)

快速排斥实验

这个实验主要是为了快速排除两条线段不相交的情况。

我们知道，一条线段两个点分别向水平和竖直方向扩展，可以得到一个矩形，那么，两条线段就可以得到两个矩形，如果这两个矩形是不相交的，那么这两条线段一定是不相交的。如果两个矩形相交呢？那我们还不能判断线段是否相交，需要再进行跨立实验才能确定，如下图：

快速排斥实验的公式就是判断两个矩形是否相交：

const passTest = (
  // 判断 x 轴
  Math.max(x1, x2) >= Math.min(x3, x4) &&
  Math.max(x3, x4) >= Math.min(x1, x2) &&
  // 判断 y 轴
  Math.max(y1, y2) >= Math.min(y3, y4) &&
  Math.max(y3, y4) >= Math.min(y1, y2)
)

公式得到一个布尔值，表示是否通过实验，如果不通过，则表示线段不相交，可以直接得出结论；如果通过，则表示线段可能相交，需要继续进一步判断。

跨立实验

到这一步可以用向量来解决。

首先需要定义什么是跨立，举个例子，我们把线段 P 延长，得到一条直线，当线段 Q 的两个端点，分别在直线的两侧时，则说明线段 Q 跨立于线段 P 。

由这个定义可以得到，当两条线段相互跨立时，它们是相交的。

那么如何判断 Q 是否跨立 P 呢？我们知道，向量的叉乘，结果是一个向量，方向是垂直于两个向量组成的平面的，结果的值可能大于 0 或者小于 0 （为 0 时两个向量平行），表示方向是向里或者向外，跟两个向量的相对位置有关，可以用右手判断。

我们可以取两个辅助向量， P1Q1, P1Q2 ，分别与向量 P1P2 做叉乘，如果 P1Q1 与 P1Q2 分别在 P1P2 的两侧，那么两个叉乘的结果一定是一个正数跟一个负数，也就是相乘小于 0 。根据这点，我们就可以知道 Q 跨立 P 的条件了：

Q 跨立 P = P1P2 x P1Q1 * P1P2 x P1Q2 < 0

如果想判断 Q 的一个端点在 P 上的情况，判定条件改成 <= 0 即可。

如下图：

这边有个可能产生疑问的点，就是为什么需要进行两次跨立实验呢？即要判断 Q 跨立 P ，也要判断 P 跨立 Q 呢？判断其中一个不够吗？

是的，只判断一个是不够的，比如下面这种情况：

Q 跨立 P ，但是两条线段明显不相交，因此要反过来再判断 P 是否也跨立 Q 。

结论

因此，要判断两条线段是否相交，需要进行如下判断：

判断线段与矩形相交

在我的流程图项目中，实际上要判断的是线段跟矩形是否相交，那要怎么做呢？

按照上面的思路，先进行快速排斥实验，我们只需要构建一个矩形，如果不通过，则不相交，这没问题，那通过了呢？表示相交吗？不是的，比如这种情况：

那么快速排斥实验就没有用了吗？不是的，它还是可以快速排除掉一些不相交的情况，虽然跟接下来的步骤结合起来确实有点鸡肋。

那接下来要怎么做呢？其实比较简单的方式是，把矩形的 4 条边都取出来，分别与线段判断是否相交即可。如果要再判断线段是否在矩形内，再加上判断两个端点是否在矩形内即可。

除了快速排斥实验，我们换一种思路，可以快速得出一些相交的情况，即判断线段是否有端点在矩形内，这个比快速排斥实验更简单。

总结一下，有几种方式可以判断线段与矩形是否相交

方式一：

1. 判断两端点是否至少有一个在矩形内，如果有，则相交
2. 如果没有，说明如果要相交，线段一定是穿过矩形的，必然与矩形中一条对角线相交，这时只需要判断线段与两条对角线是否相交

方式二：

1. 进行快速排斥实验，如果没通过，则不相交（这步也可以不做）
2. 如果通过了，判断线段与矩形每条边是否相交

总之，最后都是转换为两条线段相交的问题，如果比较懒，直接跟 4 条边判断就行，就是比较耗费性能。

对比一下，跟 4 条边判断，最多需要进行 4 次快速排斥实验， 8 次跨立实验。 而先判断端点的话，最多要判断 2 次端点是否在矩形内，2 此快速排斥实验， 4 次跨立实验。