如何判断线段是否与矩形相交

1. 概述

在本教程中，我们将介绍如何判断一条线段是否与矩形相交。

2. 相交判断

假设线段的两个端点为 和 ，矩形的四个顶点为：

• 
• 
• 
• 

我们说线段 与矩形 相交，当且仅当它与矩形任意一条边存在公共点。

例如：

因此，我们的思路是依次判断线段是否与四条边中的任意一条相交。只要找到一条边相交，就可以立即返回 true。

3. 判断两条线段是否相交

要判断线段 是否与边 相交，可以考虑是否存在一个点 同时位于两条线段上：

我们可以将该问题建模为以下等式：

$$ \begin{aligned} &Z = A_1 + \alpha(A_2 - A_1) = U + \beta(V - U) \ &\iff \alpha(A_2 - A_1) + \beta (U - V) = U - A_1 \ &\text{其中 } \alpha, \beta \in [0, 1] \end{aligned} $$

✅ 条件 $\alpha, \beta \in [0, 1]$ 保证了点 $Z$ 同时在线段 $A_1A_2$ 和 $UV$ 上。

3.1. 解线性方程组

将各点坐标代入后，可以得到如下二维线性方程组：

$$ \alpha \begin{bmatrix}x_2 - x_1 \ y_2 - y_1 \end{bmatrix} + \beta \begin{bmatrix}x_u - x_v \ y_u - y_v \end{bmatrix} = \begin{bmatrix} x_u - x_1 \ y_u - y_1 \end{bmatrix} $$

接下来，我们需要解这个方程组，得到 $\alpha$ 和 $\beta$ 的值。

3.2. 解的含义

• ❌ 如果无解，说明两条线段不相交。
• ✅ **如果唯一解满足 $\alpha \in [0, 1]$ 且 $\beta \in [0, 1]$**，说明两条线段在一点上相交。
• ⚠️ 如果有无穷多解，说明两条线段部分重合或完全重合，需要进一步判断重合部分是否在 $[0, 1]$ 范围内。

3.3. 算法实现

algorithm CheckIfLineSegmentIntersectsRectangle(UV, A1, A2, A3, A4):
    // INPUT
    //    UV = 一条线段
    //    A1, A2, A3, A4 = 矩形的四个顶点
    // OUTPUT
    //    返回 true 表示相交，否则 false

    for side in {A1A2, A2A3, A3A4, A4A1}:
        构建 UV 与 side 的方程组
        解方程组
        if 解在 [0, 1] × [0, 1] 范围内:
            return true
    
    return false

我们依次检查每条边，只要找到一条边相交即可返回 true。由于方程组解法复杂度是常数时间，因此整个算法的时间复杂度是 **O(1)**。

3.4. 线段完全在矩形内部的情况

上述算法仅检查线段与矩形边界的交点。如果线段完全在矩形内部，不会触发任何边的相交条件。

要处理这种情况，我们可以判断线段两端点是否都在矩形内部。具体做法是：

• 任选两个相邻边作为基向量，如 $A_2 - A_1$ 和 $A_4 - A_1$

• 将点 $U$ 和 $V$ 表示为这两个向量的线性组合：

  $$ U = \alpha_u (A_2 - A_1) + \beta_u (A_4 - A_1) $$ $$ V = \alpha_v (A_2 - A_1) + \beta_v (A_4 - A_1) $$

• 如果 $\alpha_u, \beta_u, \alpha_v, \beta_v \in [0, 1]$，说明线段完全在矩形内部。

例如：

4. 总结

本文介绍了判断线段与矩形是否相交的两种情况：

1. ✅ 线段与矩形边界相交
2. ✅ 线段完全在矩形内部

我们通过解线性方程组判断边界相交，并通过向量表示判断线段是否在矩形内部。整个算法时间复杂度为 **O(1)**，效率非常高。