Liang-Barsky Algorithm

Liang-Barsky

参数方程

两点式：

$$\frac{x-x_1}{y-y_1}=\frac{x_2-x_1}{y_2-y_1}$$

换下位置，并设其等于 $t$ ：

$$\frac{x-x_1}{x_2-x_1}=\frac{y-y_1}{y_2-y_1}=t, t∈[0,1]$$

其中 $(x_1,y_1)$ 为左下边界， $(x_2,y_2)$ 为右上边界， $(x,y)$ 位于其间。

则参数方程可表示为：

$$x=x_1+t(x_2-x_1)$$ $$y=y_1+t(y_2-y_1)$$

裁剪窗口不等式

$$xw_{min}≤x_1+t(x_2-x_1)≤xw_{max}$$ $$yw_{min}≤y_1+t(y_2-y_1)≤yw_{max}$$

( $xw,yw$ 为边界)

不等式可表示为：

$$tp_k≤q_k$$

其中， $k=1,2,3,4$ 分别表示左右下上四边界。

$p$ 与 $q$ 的定义为：

$$p_1 = -(x_2-x_1), q_1 = x_1 - xw_{min} (左边界)$$ $$p_2 = (x_2-x_1), q_2 = xw_{max} - x_1 (右边界)$$ $$p_3 = -(y_2-y_1), q_3 = y_1 - yw_{min} (下边界)$$ $$p_4 = (y_2-y_1), q_4 = yw_{max} - y_1 (上边界)$$

判定

条件	线的位置
$p_k=0$	平行于裁剪边界
$p_k=0$ 且 $q_k<0$	完全在边界外
$p_k = 0$ 且 $q_k ≥ 0$	在边界内
$p_k < 0$	线从外到内
$p_k > 0$	线从内到外

参数 $t_1,t_2$ 可以判定线的某部分位于裁剪矩形内，当：

$$p_k<0, 取maximum(0,\frac{q_k}{p_k})$$ $$p_k>0, 取minimum(1,\frac{q_k}{p_k})$$

若 $t_1 > t_2$, 则线完全在窗口外，可舍弃；否则，裁剪线的止点可由参数 $t$ 决定。

Algorithm

1. Set $t_{min}=0, t_{max}=1$.
2. Calculate the values of $t$ ($t(left)$, $t(right)$, $t(top)$, $t(bottom)$),
   (a) If $t < t_{min}$ ignore that and move to the next edge.
   (b) else separate the $t$ values as entering or exiting values using the inner product.
   (c) If $t$ is entering value, set $t_{min}=t$; if $t$ is existing value, set $t_{max} = t$.
3. If $t_{min} < t_{max}$, draw a line from $(x_1 + t_{min}(x_2-x_1), y_1 + t_{min}(y_2-y_1))$ to $(x_1 + t_{max}(x_2-x_1), y_1 + t_{max}(y_2-y_1))$
4. If the line crosses over the window, $(x_1 + t_{min}(x_2-x_1), y_1 + t_{min}(y_2-y_1))$ and $(x_1 + t_{max}(x_2-x_1), y_1 + t_{max}(y_2-y_1))$ are the intersection point of line and edge.

Reference

https://www.geeksforgeeks.org/liang-barsky-algorithm/