直线的裁剪： 梁友栋-Barsky算法(Liang-Barsky算法)
1. 算法的基本思想
以直线的参数方程为基础，对不同情况下的裁剪求得相应的参数值。
2. 算法的推导过程
情形一 pk=0
（1）p1＝p2＝0
若q1<0或q2<0，则可删除直线段 若q1>=0且q2>=0,则进一步判断
u=qk/pk（k=3,4）
令 u1=max(0,u|pk<0) u2=min(1,u|pk>0)
若u1>u2,则可删除直线段
若u1<=u2,将u1,u2代入直线方程，得到直线段的两个可见端点。 （2）p3＝p4＝0 若q3<0或q4<0，则可删除直线段 若q3>=0且q4>=0,则进一步判断
u=qk/pk（k=1,2）
令 u1=max(0,u|pk<0) u2=min(1,u|pk>0)
若u1>u2,则可删除直线段
若u1<=u2,将u1,u2代入直线方程，得到直线段的两个可见端点。 情形二 pk不为0 u=qk/pk（k=1,2,3,4） 令 u1=max(0,u|pk<0,u|pk<0) u2=min(1,u|pk>0, u|pk>0)
若u1>u2,则可删除直线段
若u1<=u2,将u1,u2代入直线方程，得到直线段的两个可见端点。 3. 算法步骤 (1)输入直线段的两端点坐标以及窗口的四条边界坐标。 (2)若Δx=0，则p1=p2=0。进一步判断是否满足q1<0或q2<0，若满足，则该直线段不在窗口内，转(7)。否则，满足q1>0且q2>0，则进一步计算u1和u2。转(5)。
(3)若Δy=0，则p3=p4=0。进一步判断是否满足q3<0或q4<0，若满足，则该直线段不在窗口内，转(7)。否则，满足q1>0且q2>0，则进一步计算u1和u2。转(5)。
(4)若上述两条均不满足,则有pk≠0(k=1,2,3,4)。此时计算u1和u2。
(5)求得u1和u2后,进行判断：若u1>u2,则直线段在窗口外,转(7)。若u1
#include "graphics.h"
#include "stdio.h"
#include "conio.h"
int ClipT(float p,float q,float *u1,float *u2)
{
int flag=1;
float r;
if(p<0.0)
{
r=q/p;
if(r>*u2) flag=0;
else if(r>*u1)
*u1=r;
}
else if(p>0.0)
{
r=q/p;
if(r<*u1) flag=0;
else if(r<*u2)
*u2=r;
}
else if(q<0.0) flag=0;
return flag;
}
void LiangLine(int xwmin,int ywmin,int xwmax,int ywmax,int x1,int y1,int x2,int y2)
{
float dx,dy,u1,u2;
u1=0.0;u2=1.0;
dx=x2-x1;
if(ClipT(-dx,x1-xwmin,&u1,&u2))
if(ClipT(dx,xwmax-x1,&u1,&u2))
{
dy=y2-y1;
if(ClipT(-dy,y1-ywmin,&u1,&u2))
if(ClipT(dy,ywmax-y1,&u1,&u2))
{
if(u2<1.0)
{
x2=x1+u2*dx;
y2=y1+u2*dy;
}
if(u1>0.0)
{
x1=x1+u1*dx;
y1=y1+u1*dy;
}
line(x1,y1,x2,y2);
getch();
}
}
}
void main(void)
{
int XL,XR,YB,YT;
int x0,y0,x1,y1;
int gd=DETECT,gm=0;
initgraph(&gd,&gm,"");
cleardevice();
printf("Please input the rectangle point(XL,YT,XR,YB):n");
scanf("%d%d%d%d",&XL,&YT,&XR,&YB);
setcolor(10);
rectangle(XL,YT,XR,YB);
getch();
printf("Please input the line node(x0,y0,x1,y1):n");
scanf("%d%d%d%d",&x0,&y0,&x1,&y1);
LiangLine(XL,YT,XR,YB,x0,y0,x1,y1);
}
liang-brisky算法VC中的函数实现代码：
此方法简要实现平面矩形区域直线的的裁剪，VC中程序主体部分函数代码如下：
bool CMyView::ClipT(float p,float q,float *u1,float *u2)
//判断区域
{
bool flag=1;
float r;
{
if(p<0.0)
{
r=q/p;
if(r>*u2) flag=0;
else if(r>*u1)
*u1=r;
}
else if(p>0.0)
{
r=q/p;
if(r<*u1) flag=0;
else if(r<*u2)
*u2=r;
}
else if(q<0.0) flag=0;
}
return flag;
}
void CMyView::LiangLine(int xwmin,int ywmin,int xwmax,int ywmax,int x1,int y1,int x2,int y2)
//Liang-Barsky裁剪算法
{
CDC* pDC = GetDC();
pDC->Rectangle(xwmin,ywmin,xwmax,ywmax); //画出裁剪区域（长方）
int sx,sy,ex,ey;
float dx,dy,u1,u2;
u1=0.0;u2=1.0;
dx=x2-x1;
sx=x1;sy=y1;ex=x2;ey=y2;
if(ClipT(-dx,sx-xwmin,&u1,&u2))
{
if(ClipT(dx,xwmax-sx,&u1,&u2))
{
dy=ey-sy;
if(ClipT(-dy,sy-ywmin,&u1,&u2))
if(ClipT(dy,ywmax-sy,&u1,&u2))
{
if(u2<1.0)
{
ex=sx+u2*dx;
ey=sy+u2*dy;
}
if(u1>0.0)
{
sx+=u1*dx;
sy+=u1*dy;
}
//画出裁剪后的线
pDC->MoveTo(ex,ey);
pDC->LineTo(sx,sy);
}
}
}
}
