梁友栋-barsky线段裁剪算法

它基于分析线段的参数化方程

对端点为$x_0,y_0,x_1,y_1$的直线段，可使用参数形式描述为
$$\begin{cases}x = x_0 + ux_1 - x_0 \\y = y_0 + uy_1 - y_0\end{cases}$$
与点裁剪的条件结合则有

$$\begin{cases}xw_{min} \leq x_0 + ux_1 - x_0 \leq xw_{max} \\yw_{min} \leq y_0 + uy_1 - y_0 \leq yw_{max}\end{cases}$$

展开上式,表示为$$up_k \leq q_k \tag{1}$$

$$\begin{cases}xw_{min} \leq x_0 + ux_1 - x_0 \Rightarrow xw_{min} - x_0 \leq u \Delta x \Rightarrow u -\Delta x \leq x_0 - xw_{min} \\x_0 + ux_1 - x_0 \leq xw_{max} \Rightarrow u \Delta x \leq xw_{max} - x_0 \Rightarrow u \Delta x \leq xw_{max} - x_0 \\yw_{min} \leq y_0 + uy_1 - y_0 \Rightarrow yw_{min} - y_0 \leq u \Delta y \Rightarrow u -\Delta y \leq y_0 - yw_{min} \\y_0 + uy_1 - y_0 \leq yw_{max} \Rightarrow u \Delta y \leq yw_{max} - y_0 \Rightarrow u \Delta y \leq yw_{max} - y_0\end{cases}$$

$p_k = 0$

线段平行于裁剪窗口的边界中的任意一条

满足$q_k < 0$

则线段完全在裁剪窗口外如下图所示

如果$q_k \geq 0$

$p_k \neq 0$

当$p_k < 0$线段从裁剪边延长线的外部延伸到内部,是入边交点
当$p_k > 0$线段从裁剪边延长线的内部延伸到外部,是出边交点

线段和窗口一共有4个交点，根据pk的符号，就可以知道那个入点，那个是出点，如下图中的$u_l,u_r,u_t,u_b$,在加上两个端点的$u=0,1$，一共6个u值

根据1式的得出

$$u = \frac{q_k}{p_k}$$

6个u值分别为

$$\begin{cases}u_s = 0 \\u_e = 1\\u_l = \frac{x_0 - xw_{min}}{-\Delta x} \\u_r = \frac{xw_{max} - x_0}{\Delta x} \\u_t = \frac{yw_{max} - y_0}{\Delta y} \\u_b = \frac{y0 - yw_{min}}{-\Delta y}\end{cases}$$

把$p_k < 0$的两个u值和0比较去找大的

当$\Delta x > 0$ && $\Delta y > 0$ 取$u_l, u_b$
当$\Delta x > 0$ && $\Delta y < 0$ 取$u_l, u_t$
当$\Delta x < 0$ && $\Delta y > 0$ 取$u_r, u_b$
当$\Delta x < 0$ && $\Delta y < 0$ 取$u_r, u_t$

把$p_k > 0$的两个u值和1比较去找小的

当$\Delta x > 0$ && $\Delta y > 0$ 取$u_r, u_t$
当$\Delta x > 0$ && $\Delta y < 0$ 取$u_r, u_b$
当$\Delta x < 0$ && $\Delta y > 0$ 取$u_l, u_t$
当$\Delta x < 0$ && $\Delta y < 0$ 取$u_l, u_b$

如果$u_{max} > u_{min}$ 则直线段在窗口外面删除
如果$u_{max} \leq u_{min}$ 求出交点坐标

注意u的有效范围是[0,1]

请参考梁友栋-barsky线段裁剪算法