直线的裁剪： 梁友栋-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)。若u1TC 下的源程序：

#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(r0.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(rRectangle(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);

}

}

}

}