光栅图形学(三)——梁友栋-Barskey剪裁算法

本文主要是介绍光栅图形学(三)——梁友栋-Barskey剪裁算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

光栅图形学(三)——梁友栋-Barskey剪裁算法

一、问题转换

直线的参数方程
$\begin{aligned} &x = x_1+u(x_2-x_1) \\ &y=y_1+ u(y_2-y_1) \end{aligned}$
其中 $0\le u \le 1$ 。对于直线上的一点 $(x, y)$ ，若它在窗口内则有
$\begin{aligned} &wxl \le x_1+u(x_2-x_1)\le wxr \\ &wxb \le y_1+u(y_2-y_1) \le wyt \end{aligned}$
条件方程转换
$\begin{aligned} &u(x_1-x_2) \le x_1 - wxl \quad p_1 = -(x_2-x_1) \quad q_1=x_1-wxl\\ &u(x_2-x_1) \le wxr - x_1 \quad p_2 = x_2 - x_1 \quad q_2 = wxr - x_1 \\ &u(y_1 - y_2) \le y_1 - wyb \quad p_3=-(y_2-y_1) \quad q_3 = y_1 - wyb \\ &u(y_2 - y_1) \le wyt - y_1 \quad p_4 = y_2 - y_1 \quad q_4 = wyt - y_1 \end{aligned}$
综合上述方程，可以归纳为 $up_k \le q_k$ 。
（1） $p_k < 0\quad \qquad u \ge q_k/p_k \qquad$ 下限组
（2） $p_k > 0\quad \qquad u \le q_k/p_k \qquad$ 上限组
则此时若直线落在窗口内应满足
$\begin{aligned} & \max \{0,q_1/p_1,q_3/p_3 \} \le u \le \min\{0,q_2/p_2,q_4/p_4 \} \subseteq \{0 \le u \le 1\} \quad \text{或}\\ &\max \{0,q_2/p_2,q_4/p_4 \} \le u \le \min\{0,q_1/p_1,q_3/p_3 \} \subseteq \{0 \le u \le 1\} \end{aligned}$

二、算法过程

（1）输入直线的两端点坐标： $x_1,y_1)$ 和 $x_2,y_2)$ ，以及窗口的四条边界坐标： $w y t 、 w y b 、 w x l 、 w x r$ 。
（2）若 $\Delta x = 0$ ，则 $p_1 = p_2=0$ 。此时进一步判断是否满足 $q_1 < 0$ 或 $q_2 < 0$ ，若满足，该直线不在窗口内，算法转(7)。否则，满足 $q_1 > 0$ 且 $q_2 > 0$ ，算法转(6)。
（3）若 $\Delta y = 0$ ，则 $p_3 = p_4 = 0$ 。此时进一步判断是否满足 $q_3 < 0$ 或 $q_4 < 0$ ，若满足，该直线不在窗口内，算法转(7)。否则，满足 $q_3 > 0$ 且 $q_4 > 0$ ，算法转(6)。
（4）若上述都不满足，则有 $p_k \neq 0(k=1,2,3,4)$ 。此时计算下限组 $u_l$ 和上限组 $u_r$ ，算法转(5)。
（5）求得 $u_l$ 和 $u_r$ 后，若 $u_l > u_r$ ，则直线在窗口外，算法转(7)。若 $u_l < u_r$ ，算法转(6)。
（6）利用直线的扫描转换算法绘制在窗口内的直线段。
（7）算法结束。

三、Liang-Barskey算法-示例

在这里插入图片描述

四、代码实现(python)

import matplotlib.pyplot as pltdef plot_line(x1,x2,y1,y2,wxl,wxr,wyb,wyt):plt.plot([x1,x2], [y1,y2], 'g')plt.scatter([x1,x2], [y1,y2], color='b')#裁剪p1 = -(x2 - x1) q1 = x1 - wxl p2 = x2 - x1q2 = wxr - x1p3 = -(y2 - y1)q3 = y1 - wybp4 = y2 - y1q4 = wyt - y1ymax = max(y1,y2)ymin = min(y1,y2)if p1 == 0 and p2 == 0: # 算法过程2if q1 > 0 and q2 > 0:if ymin >= wyb and ymax <= wyt: # 两端点都在窗口内plt.plot([x1,x2], [ymin,ymax], 'm')elif ymin < wyb and ymax <= wyt:plt.plot([x1,x2], [wyb,ymax], 'm') # 一个端点在窗口内elif ymin >= wyb and ymax > wyt:plt.plot([x1,x2], [ymin,wty], 'm') # 一个端点在窗口内else:plt.plot([x1,x2], [wyb,wyt], 'm')  # 端点都不在窗口内elif p3 == 0 and p4 == 0: # 算法过程3if q3 > 0 and q4 > 0:if x1 >= wxl and x2 <= wxr: # 两端点都在窗口内plt.plot([x1,x2], [y1,y2], 'm')elif x1 < wxl and x2 <= wxr:plt.plot([wxl,x2], [y1,y2], 'm') # 一个端点在窗口内elif wxl >= x1 and x2 > wxr:plt.plot([x1,wxr], [y1,y2], 'm') # 一个端点在窗口内else:plt.plot([wxl,wxr], [y1,y2], 'm')  # 端点都不在窗口内else:	# 算法过程45ul = 0ur = 1for e in [[p1,q1],[p2,q2],[p3,q3],[p4,q4]]:if e[0] < 0:ul = max(ul,e[1]/e[0])else:ur = min(ur,e[1]/e[0])# 判断线代落在窗口内与否if ul < ur:plt.plot([x1+ul*p2,x1+ur*p2],[y1+ul*p4,y1+ur*p4],'m')def plot_window(wxl,wxr,wyb,wyt):# 要连接的两个点的坐标x = [[wxl,wxr],[wxr,wxr],[wxr,wxl],[wxl,wxl]]y = [[wyb,wyb],[wyb,wyt],[wyt,wyt],[wyt,wyb]]for i in range(len(x)):plt.plot(x[i], y[i], color='r')if __name__ == '__main__':# 设置坐标轴区间plt.axis([0,100,0,100])# 显示窗口函数plot_window(20,60,20,60)  # 显示直线函数plot_line(10,70,8,50,20,60,20,60)plot_line(50,90,40,5,20,60,20,60)plot_line(30,30,6,55,20,60,20,60)plot_line(2,15,6,95,20,60,20,60)plot_line(5,80,90,30,20,60,20,60)plot_line(8,60,70,70,20,60,20,60)plot_line(23,40,50,50,20,60,20,60)plot_line(5,68,45,30,20,60,20,60)plt.title("Liang-Barskey Algorithm")plt.show()