光栅图形学(三)——梁友栋-Barskey剪裁算法
光栅图形学(三)——梁友栋-Barskey剪裁算法
一、问题转换
-
直线的参数方程
其中。对于直线上的一点,若它在窗口内则有
-
条件方程转换
综合上述方程,可以归纳为。
(1) 下限组
(2) 上限组
则此时若直线落在窗口内应满足
二、算法过程
(1)输入直线的两端点坐标:和,以及窗口的四条边界坐标:。
(2)若,则。此时进一步判断是否满足或,若满足,该直线不在窗口内,算法转(7)。否则,满足且,算法转(6)。
(3)若,则。此时进一步判断是否满足或,若满足,该直线不在窗口内,算法转(7)。否则,满足且,算法转(6)。
(4)若上述都不满足,则有。此时计算下限组和上限组,算法转(5)。
(5)求得和后,若,则直线在窗口外,算法转(7)。若,算法转(6)。
(6)利用直线的扫描转换算法绘制在窗口内的直线段。
(7)算法结束。
三、Liang-Barskey算法-示例
四、代码实现(python)
import matplotlib.pyplot as plt
def 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 - x1
q2 = wxr - x1
p3 = -(y2 - y1)
q3 = y1 - wyb
p4 = y2 - y1
q4 = wyt - y1
ymax = max(y1,y2)
ymin = min(y1,y2)
if p1 == 0 and p2 == 0: # 算法过程2
if 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: # 算法过程3
if 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: # 算法过程45
ul = 0
ur = 1
for 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()
- 结果图
若有任何错误还望指正,参考博客:https://blog.****.net/soulmeetliang/article/details/79185603