使用向量叉乘判断线段是否相交并求交点

翻译自 Stack Overflow 上的答案，这是： 原文答案 。

---

解决这个问题有一个很好的方法，就是使用向量叉乘。定义二维向量的叉积为：

v × w = v_xw_y - v_yw_x

假设两条线段分别是从点 p 出发的 p + r 和从点 q 出发的 q + s 。那么第一条线段上的任何点都可以表示为 p + t r （ t 是标量参数），第二条线段上的任何点可以表示为 q + u s 。

如果我们找到了 t 和 u 满足如下等式，那么这两条线段相交：

p + t r = q + u s

等式两边叉乘 s ，得到

( p + t r ) × s = ( q + u s ) × s

因为 s × s = 0，所以

t ( r × s ) = ( q - p ) × s

因此，解出 t ：

t = ( q - p ) × s / ( r × s )

同样，在最初等式的两边叉乘 r，我们解出 u ：

u = ( p - q ) × r / ( s × r )

为了减少计算步骤，我们变换一下形式（根据 s × r = - r × s ）：

u = ( q - p ) × r / ( r × s )

现在，有四种情况：

1. 如果 r × s = 0 并且 ( q - p ) x r = 0，那么两条线段共线。

   此时，利用第一条线段的等式 （ p + t r ） 表示第二条线段的两个端点 （ q 和 q + s ）：

   t₀ = ( q - p ) · r / ( r · r )

   t₁ = ( q + s - p ) · r / ( r · r ) = t₀ + s · r / ( r · r )

   如果 t₀ 和 t₁ 形成的区间与 [0,1] 有重合，那么这两条线段共线且重合；否则它们共线但不重合。

   注意如果 s 和 r 指向相反的方向，那么 s · r < 0 ，此时所要检查的区间不是 [ t₀ ] 而是 [ t₁ ] 。

2. 如果 r × s = 0 且 ( q - p ) × r ≠ 0 ，那么这两条线段平行不相交。

3. 如果 r × s ≠ 0 且 0 ≤ t ≤ 1 且 0 ≤ u ≤ 1 ，这两条线段在点 p + t r = q + u s 相交。

4. 其他情况，这两条线段不平行也不相交。