Liang-Barsky线段裁剪算法

在计算机图形学中,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$的上下限。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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()

png

如果您觉得这篇文章对您有帮助,请随意打赏。