梁友栋-Barsky裁剪算法

　　我们知道，一条两端点为P₁（x₁，y₁）、P₂（x₂，y₂）的线段可以用参数方程形式表示：

　　式中，Δx=x₂-x₁，Δy=y₂-y₁，参数u在0～1之间取值，P（x，y）代表了该线段上的一个点，其值由参数u确定，由公式可知，当u=0时，该点为P₁（x₁，y₁），当u=1时，该点为P₂（x₂，y₂）。如果点P（x，y）位于由坐标（xw_min，yw_min）和（xw_max，yw_max）所确定的窗口内，那么下式成立：

　　这四个不等式可以表示为：

　　其中，p、q定义为：

　　从（3-12）式可以知道：任何平行于窗口某边界的直线，其p_k=0（但并不是所有的Pk均为0，是存在pk=0的意思。平行于窗口某边界的图片，会出现 （p1&&p2）||（p3&&p4）=0的情况），k值对应于相应的边界（k=1，2，3，4对应于左、右、下、上边界）。如果还满足q_k<0（默认x1为最左点?默认斜率大于0小于1？），则线段完全在边界外，应舍弃该线段。如果p_k=0并且q_k≥0，则线段平行于窗口某边界并在窗口内，见图中所示。公式（3-12）式还告诉我们：

　　1、当p_k<0时，线段从裁剪边界延长线的外部延伸到内部；

　　2、当p_k>0时，线段从裁剪边界延长线的内部延伸到外部；

　　例如，当Δx≥0时，对于左边界p₁<0（p₁=-Δx），线段从左边界的外部到内部；

　　　　 　　　　　　对于右边界p₂>0（p₂=Δx），线段从右边界的内部到外部。

　　　　　当Δy<0时，对于下边界p₃>0（p₃=-Δy），线段从下边界的内部到外部；

　　　　　　　　　　对于上边界p₄<0（p₄=Δy），线段从上边界的外部到内部。

　　　　　当p_K≠0时，可以计算出参数u的值，它对应于无限延伸的直线与延伸的窗口边界k的交点，即：

（3-13）

　　对于每条直线，可以计算出参数u₁和u₂，该值定义了位于窗口内的线段部分：

　　1、u₁的值由线段从外到内遇到的矩形边界所决定（p_k<0），对这些边界计算r_k=q_k/p_k，u₁取0和各个r值之中的最大值。

　　2、u₂的值由线段从内到外遇到的矩形边界所决定（p_k>0），对这些边界计算r_k=q_k/p_k，u₂取0和各个r值之中的最小值。

　　3、如果u₁>u₂，则线段完全落在裁剪窗口之外，应当被舍弃；否则，被裁剪线段的端点可以由u₁和u₂计算出来。

　二、梁友栋-Barsky裁剪算法实现：

　　三、梁友栋-Barsky裁剪算法特点：

　　四、梁友栋-Barsky裁剪算法程序：

        MFC编写的应用程序（包含源代码）：http://download.csdn.net/detail/marcnuth/4938143

        梁友栋算法核心源代码：

#include "graphics.h"
int clipTest(float p,float q,float *u1,float *u2) 
{int flag=1; /*flag为标志变量，0：表示舍弃；1：表示可见。*/float r;if(p<0.0) {r=q/p;if(r>*u2)flag=0;else if(r>*u1) *u1=r; /*u1取"进入"点的最大参数值*/}else if(p>0.0) {r=q/p;if(r<*u1) flag=0;else if(r<*u2)*u2=r; /*u2取"离开" 点的最小参数值*/}else if(q<0.0) /*p=0，且q<0。平行于边界，而且在界外的线*/flag=0;return(flag);
}
void clipLine(int xwmin,int ywmin,int xwmax,int ywmax,int x1,int y1,int x2,int y2) 
{float u1=0.0,u2=1.0,dx=x2-x1,dy;if(clipTest(-dx,x1-xwmin,&u1,&u2))if(clipTest(dx,xwmax-x1,&u1,&u2)) { dy=y2-y1;　if(clipTest(-dy,y1-ywmin,&u1,&u2))if(clipTest(dy,ywmax-y1,&u1,&u2)){if(u2<1.0){x2=x1+u2*dx; /*通过u2求得裁剪后的p2端点*/y2=y1+u2*dy;}if(u1>0.0){x1=x1+u1*dx; /*通过u1求得裁剪后的p1端点*/y1=y1+u1*dy;}line(x1,y1,x2,y2); /*裁剪后的线段输出*/}}
}