三种常用的直线裁剪算法

屏幕窗口是一个矩形框，图形仅在框内显示，直线位于矩形框外的部分需要将其裁剪去除。

一.Cohen-Sutherland算法

该算法的主要思想是将区域进行编码，通过与、或运算来判断直线与框的位置关系。

当点的x<Xleft:D0=1,否则D0=0；当点的x>Xright:D1=1,否则D1=0；
当点的y<Ybottom:D2=1,否则D2=0；当点的y>Ytop:D3=1,否则D3=0；

矩形方框一共将区域分成了9个区域，根据D3D2D1D0顺序编码情况如下：

当code1|code2=0时，说明线段位于框内，保留。

当code1&code2≠0时，说明线段位于框外，舍弃。

若以上两个条件均不满足时，需要计算线段与边框线的交点，交点有实交点和虚交点，对实交点进行保留虚交点进行舍弃。实交点又分为1个实交点和2个实交点，1个实交点情况：只需将实交点和框内交点连线即可；2个实交点：2个实交点连线即可。

二.中点分割法

中点分割法是基于Cohen-Sutherland算法，主要思想仍为编码。其主要的不同之处在于在求交点是用中点逼近的思想。

三.Liang-Barsky算法

直线段方程： $x=x_{1}+\Delta x*u$ 、 $y=y_{1}+\Delta y*u$

$x_{1}+\Delta x*u=x_{left}$ 、 $x_{1}+\Delta x*u=x_{right }$ 、 $y_{1}+\Delta y*u=y_{bottom}$ 、 $y_{1}+\Delta y*u=y_{top}$

根据以上四个公式可以求得4个u值，根据u值的大小关系可得，所得交点的位置关系。

线段AB的方向为由A指向B，令Xleft和Ybottom为入口，则取max{u1、u2、u3=0}；令Xright和Ytop为出口，则取min{u4、u5、u6=1}，最终获得的两点即为目标点。