在计算机图形学中,Liang-Barsky算法是一种线段裁剪算法,以梁友栋和Barsky的名字命名,它使用直线的参数方程和不等式组来描述线段和裁剪窗口的交集,求解出的交集将被用于获知线的哪些部分是应当绘制在屏幕上的。这一算法比Cohen-Sutherland算法要更加高效。这里使用Python + Matplotlib来实现并演示此算法的原理与过程。

两条直线的参数方程:

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

若直线上的一点$(x, y)$在矩形中则有

  • $x_l \leq x_1 + t(x_2 – x_1) \leq x_r$
  • $y_b \leq y_1 + t(y_2 – y_1) \leq y_t$

  • $t(x_1 – x_2) \leq x_1 – x_l$, $p_1 = -(x_2 – x_1)$, $q_1 = x_1 – x_l$
  • $t(x_2 – x_1) \leq x_r – x_1$, $p_2 = (x_2 – x_1)$, $q_2 = x_r – x_1$
  • $t(y_1 – y_2) \leq y_1 – y_b$, $p_3 = -(y_2 – y_1)$, $q_3 = y_1 – y_b$
  • $t(y_2 – y_1) \leq y_t – y_1$, $p_4 = (y_2 – y_1)$, $q_4 = y_t – y_1$

只需使得$tp_k \leq q_k$。

当$p_k < 0$时解得$t \geq q_k / p_k$;当$p_k > 0$时解得$t \leq q_k / p_k$,即可求出$t$的上下限。

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.lines import Line2D
from matplotlib.patches import Rectangle

def liang_barsky(yt, yb, xl, xr, x1, y1, x2, y2):
    dx, dy = x2 - x1, y2 - y1
    p = [-dx, dx, -dy, dy]
    q = [x1 - xl, xr - x1, y1 - yb, yt - y1]
    if dx == 0:
        if q[0] < 0 or q[1] < 0:
            return False
        else:
            if y1 > y2:
                y1, y2 = y2, y1
            if y2 < yb or y1 > yt:
                return False
            else:
                y1 = max(y1, yb)
                y2 = min(y2, yt)
                return (x1, y1, x2, y2)
    if dy == 0:
        if q[2] < 0 or q[3] < 0:
            return False
        else:
            if x1 > x2:
                x1, x2 = x2, x1
            if x2 < xl or x1 > xr:
                return False
            else:
                x1 = max(x1, xl)
                x2 = min(x2, xr)
                return (x1, y1, x2, y2)
    t0, t1 = 0, 1
    for i in range(4):
        if p[i] < 0:
            t0 = max(t0, q[i] / p[i])
        else:
            t1 = min(t1, q[i] / p[i])
    if t0 > t1:
        return False
    return (x1 + t0 * dx, y1 + t0 * dy, x1 + t1 * dx, y1 + t1 * dy)
fig, ax = plt.subplots(figsize=(10, 10))
top, bottom, left, right = 15, 5, 5, 15
rect = plt.Rectangle((left, bottom), right - left, top - bottom, color='blue', fill=False)
ax.add_patch(rect)

for i in range(20):
    x1, y1, x2, y2 = np.random.randint(0, 20, size=4)
    ax.add_line(Line2D((x1, x2), (y1, y2), color='gray'))
    ans = liang_barsky(top, bottom, left, right, x1, y1, x2, y2)
    if ans:
        x1_, y1_, x2_, y2_ = ans
        ax.scatter(x1_, y1_, c='green', marker='o')
        ax.scatter(x2_, y2_, c='green', marker='o')
        ax.add_line(Line2D((x1_, x2_), (y1_, y2_), color='yellow', linewidth=2))
ax.autoscale()
plt.show()