裁剪算法——中点分割算法/Liang-Barsky算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了裁剪算法——中点分割算法/Liang-Barsky算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2647字，纯文字阅读大概需要4分钟。

内容图文

三、中点分割法

首先对直线段的端点进行编码。
【核心思想：通过二分逼近来确定直线段与窗口的交点。】

具体方法：

1、若中点不在窗口内，则把【中点】和离窗口边界【最远点】构成的线段丢掉，以线段上的另一点和该中点再构成线段求其中点。
2、如果中点在窗口内，则又以中点和最远点构成线段，并求其中点，直到中点与窗口边界的坐标值在规定的误差范围内想等。


【问题】中点分割算法会不会无限循环二分下去？

由于屏幕像素是有限的而且会规定误差范围，一般计算次数不会太多。

四、Liang-Barsky裁剪算法——>【基本出发点：直线的参数方程】

Liang-Barsky算法是写进国内外主流《计算机图形学》教科书里唯一一个亿中国人命名的算法。

【主要思想】
（1）用参数方程表示一条直线；

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

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


【梁先生的重大发现】如果用u1,u2分别表示线段(u1<=u2)可见部分的开始和结束——>

由直线的参数方程可知：

线段和窗口边界一共有四个交点，根据Pk的符号，可以知道那两个是入交点，那两个是出交点。：

【Liang-Barsky裁剪算法步骤】

(1)输入直线段的两端点坐标(x1,y1)、(x2,y2)，以及窗口的四条边界坐标：wxl，wxr，wyb，wyt；

(2)若Δx=0，则p1=p2=0，此时进一步判断是否满足q1<0或q2<0，若满足，则直线段不在窗口内，算法转(7)结束，否则，进一步计算Umax=max(0，Uk|pk<0)和Umin=min(Uk|pk>0，1)，其中，Uk=qk/pk；(pk≠0，k=3，4)算法转(5)；

(3)若Δy=0，则p3=p4=0，此时进一步判断是否满足q3<0或q4<0，若满足，则直线段不在窗口内，算法转(7)，否则，进一步计算Umax=max(0，Uk|pk<0)和Umin=min(Uk|pk>0，1)，其中，Uk=qk/pk；(pk≠0，k=3，4)算法转(5)；

(4)若上述两个条件均不满足，则有pk≠0(k=1,2,3,4)，此时计算Umax=max(0，Uk|pk<0，Uk|pk<0)和Umin=min(Uk|pk>0，Uk|pk>0，1)其中，Uk=qk/pk；(pk≠0，k=1，2，3，4);

(5)求得Umax和Umin后，进行判断：若Umax>Umin，则直线段在窗口外，算法转(7)若Umax≤Umin，带入直线段参数方程；

(6)利用直线的扫描转换算法绘制在窗口内的直线段；

(7)算法结束。

【裁剪算法举例】


具体步骤如下：

对于直线EF,有：
P1=-2 q1=5       U1=-5/2
P2=2  q2=3 ——> U2=3/2
P3=-3 q3=4       U3=-4/3
P4=3  q4=2       U4=2/3

——>Umax=max(0,-5/2,-4/3)=0
     Umin=min(1,3/2,2/3)=2/3
以，裁剪后的直线的两个端点是(6,6)和(7.3,8)

【Liang-Barsky算法小结】
1、直线段看成有方向的;
2、直线参数化；
3、判断线段上一点是否在窗口内，需满足下面两个不等式；

4、线段和窗口边界一共有四个交点；

【Cohen—Sutherland 和Liang—Barsky裁剪算法的比较】
1、Cohen—Sutherland算法的核心思想是编码；
2、如果被裁剪的图形大部分线段要么在窗口内或者要么完全在窗口外，很少有贯穿窗口的，Cohen—Sutherland算法效果非常好；
3、在一般情况下，Liang—Barsky裁剪算法的效率更优于Cohen—Sutherland算法；
4、Cohen—Sutherland和Liang—Barsky只能应用于【矩形窗口】。

内容总结

以上是互联网集市为您收集整理的裁剪算法——中点分割算法/Liang-Barsky算法全部内容，希望文章能够帮你解决裁剪算法——中点分割算法/Liang-Barsky算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---