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 \in [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})

x w_{m i n} \leq x_{1} + t (x_{2} - x_{1}) \leq x w_{m a x}

y w_{m i n} \leq y_{1} + t (y_{2} - y_{1}) \leq y w_{m a x}

( $x w, y w$ 为边界)

不等式可表示为：

t p_{k} \leq q_{k}

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

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

p_{1} = - (x_{2} - x_{1}), q_{1} = x_{1} - x w_{m i n} (左 边 界)

p_{2} = (x_{2} - x_{1}), q_{2} = x w_{m a x} - x_{1} (右 边 界)

p_{3} = - (y_{2} - y_{1}), q_{3} = y_{1} - y w_{m i n} (下 边 界)

p_{4} = (y_{2} - y_{1}), q_{4} = y w_{m a x} - y_{1} (上 边 界)

参数 $t_{1}, t_{2}$ 可以判定线的某部分位于裁剪矩形内，当：

p_{k} < 0, 取 m a x i m u m (0, \frac{q_{k}}{p_{k}})

p_{k} > 0, 取 m i n i m u m (1, \frac{q_{k}}{p_{k}})

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

Set $t_{m i n} = 0, t_{m a x} = 1$ .
Calculate the values of $t$ ( $t (l e f t)$ , $t (r i g h t)$ , $t (t o p)$ , $t (b o t t o m)$ ),
(a) If $t < t_{m i n}$ 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_{m i n} = t$ ; if $t$ is existing value, set $t_{m a x} = t$ .
If $t_{m i n} < t_{m a x}$ , draw a line from $(x_{1} + t_{m i n} (x_{2} - x_{1}), y_{1} + t_{m i n} (y_{2} - y_{1}))$ to $(x_{1} + t_{m a x} (x_{2} - x_{1}), y_{1} + t_{m a x} (y_{2} - y_{1}))$
If the line crosses over the window, $(x_{1} + t_{m i n} (x_{2} - x_{1}), y_{1} + t_{m i n} (y_{2} - y_{1}))$ and $(x_{1} + t_{m a x} (x_{2} - x_{1}), y_{1} + t_{m a x} (y_{2} - y_{1}))$ are the intersection point of line and edge.