Liang-Barsky裁剪算法

原理

Liang-Barsky算法是基于参数化线段方程和对边界的逐一检测，通过参数 $t \in [0, 1]$ 对线段进行裁剪，从而确定其在裁剪窗口内的可见部分。相比Cohen-Sutherland算法，该算法效率更高，因为它减少了不必要的交点计算和布尔判断。

令线段的两个端点为：

$$
P_0 = (x_0, y_0),\quad P_1 = (x_1, y_1)
$$

则线段的参数化形式为：

$$
x(t) = x_0 + t(x_1 - x_0),\quad y(t) = y_0 + t(y_1 - y_0),\quad t \in [0, 1]
$$

设裁剪窗口为：

$$
x_{\min} \le x \le x_{\max},\quad y_{\min} \le y \le y_{\max}
$$

将线段的裁剪过程转化为寻找满足以下不等式的 $t$ 范围：

$$
x_{\min} \le x_0 + t \Delta x \le x_{\max},\quad y_{\min} \le y_0 + t \Delta y \le y_{\max}
$$

其中 $\Delta x = x_1 - x_0,\quad \Delta y = y_1 - y_0$。

这些不等式可以重写为一组线性不等式：

$$
p_i t \le q_i,\quad i=1,2,3,4
$$

其中：

• $p_1 = -\Delta x,\quad q_1 = x_0 - x_{\min}$（对应左边界）
• $p_2 = \Delta x,\quad q_2 = x_{\max} - x_0$（对应右边界）
• $p_3 = -\Delta y,\quad q_3 = y_0 - y_{\min}$（对应下边界）
• $p_4 = \Delta y,\quad q_4 = y_{\max} - y_0$（对应上边界）

定义：

• $t_{\text{enter}} = \max(0, \text{所有 } \frac{q_i}{p_i} \text{，其中 } p_i < 0)$
• $t_{\text{leave}} = \min(1, \text{所有 } \frac{q_i}{p_i} \text{，其中 } p_i > 0)$

若 $t_{\text{enter}} > t_{\text{leave}}$，则线段完全在窗口外；否则，线段在裁剪窗口中的部分为：

$$
P(t_{\text{enter}}) \text{ 到 } P(t_{\text{leave}})
$$

推导

从裁剪窗口与线段相交的约束出发：

$$
x_{\min} \le x(t) = x_0 + t \Delta x \le x_{\max} \Rightarrow
\begin{cases}
t \ge \frac{x_{\min} - x_0}{\Delta x} & \text{if } \Delta x > 0\\
t \le \frac{x_{\max} - x_0}{\Delta x} & \text{if } \Delta x > 0
\end{cases}
$$

$$
\text{类似地有：}
\quad t \ge \frac{y_{\min} - y_0}{\Delta y},\quad t \le \frac{y_{\max} - y_0}{\Delta y}
$$

统一为：

$$
\text{对于每个边界，若 } p_i = 0 \text{ 且 } q_i < 0 \Rightarrow \text{线段与该边界平行且在窗口外，裁剪失败。}
$$

例题

已知线段端点为 $P_0 = (2, 3),\ P_1 = (10, 9)$，裁剪窗口为：

$$
x_{\min} = 4,\quad x_{\max} = 8,\quad y_{\min} = 4,\quad y_{\max} = 6
$$

1.计算增量：

$$
\Delta x = x_1 - x_0 = 8,\quad \Delta y = y_1 - y_0 = 6
$$

2.构造 $p_i, q_i$：

$$
\begin{aligned}
p_1 &= -8,\quad q_1 = 2 - 4 = -2 \\
p_2 &= 8,\quad q_2 = 8 - 2 = 6 \\
p_3 &= -6,\quad q_3 = 3 - 4 = -1 \\
p_4 &= 6,\quad q_4 = 6 - 3 = 3 \
\end{aligned}
$$

3.计算 t 值：

对于 $p_i < 0$（进入）：

$$
t_1 = \frac{-2}{-8} = 0.25,\quad
t_3 = \frac{-1}{-6} \approx 0.1667
\Rightarrow t_{\text{enter}} = \max(0, 0.25, 0.1667) = 0.25
$$

对于 $p_i > 0$（离开）：

$$
t_2 = \frac{6}{8} = 0.75,\quad
t_4 = \frac{3}{6} = 0.5
\Rightarrow t_{\text{leave}} = \min(1, 0.75, 0.5) = 0.5
$$

4.判断并计算裁剪结果：

由于 $t_{\text{enter}} = 0.25 < t_{\text{leave}} = 0.5$，线段可裁剪。

求新端点：

$$
P_{\text{new0}} = P(0.25) = (2 + 8 \cdot 0.25,\ 3 + 6 \cdot 0.25) = (4,\ 4.5) \\
P_{\text{new1}} = P(0.5) = (2 + 8 \cdot 0.5,\ 3 + 6 \cdot 0.5) = (6,\ 6)
$$

裁剪后线段为： $(4, 4.5)$ 到 $(6, 6)$

CSDN搜索