Liang-Barsky算法 - 好文

Liang-Barsky算法

在Cohen-Sutherland算法提出后，梁友栋和Barsky又针对标准矩形窗口提出了更快的Liang-Barsky直线段裁剪算法。

梁算法的主要思想：

（1）用参数方程表示一条直线

（2）把被裁剪的红色直线段看成是一条有方向的线段，把窗口的四条边分成两类：

入边和出边

裁剪结果的线段起点是直线和两条入边的交点以及始端点三个点里最前面的一个点，即参数u最大的那个点；

裁剪线段的终点是和两条出边的交点以及端点最后面的一个点，取参数u最小的那个点。

值得注意的是，当u从-∞到+∞遍历直线时，首先对裁剪窗口的两条边界直线（下边和左边）从外面向里面移动，

再对裁剪窗口两条边界直线（上边和右边）从里面向外面移动。

如果用u1，u2分别表示线段（u1≤u2）可见部分的开始和结束

Liang-Barsky算法的基本出发点是直线的参数方程

（1）分析Pk=0的情况

如果还满足qk<0

则线段完全在边界外，应舍弃该线段

如果qk≥0

则进一步判断

（2）当pk≠0时：

当pk<0时

线段从裁剪边界延长线的外部延伸到内部，是入边交点

当pk > 0时

线段从裁剪边界延长线的内部延伸到外部，是出边交点

线段和窗口边界一共有四个交点，根据pk的符号，就知道哪两个是入交点，哪两个是出交点

当p k < 0时：对应入边交点

当p k > 0时：对应出边交点

一共四个u值，再加上u=0、u=1两个端点值，总共六个值

把pk＜0的两个u值和0比较去找最大的，把pk＞0的两个u值和1比较去找最小的，这样就得到两个端点的参数值

热门工具换一换