#include<graphics.h>
#include<dos.h>
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
void main()
{
int gd,gm;
int x1[100],y1[100],x2[100],y2[100],n=12,i;
int wxmin=200,wymin=200,wxmax=400,wymax=400;
float u1=0,u2=1;
int p1[100],q1[100],p2[100],q2[100],p3[100],q3[100],p4[100],q4[100];
float r1[100],r2[100],r3[100],r4[100];
int x11[100],y11[100],x22[100],y22[100];
clrscr();
for(i=0;i<100;i++)
{
x1[100]=y1[100]=x2[100]=y2[100]=p1[100]=q1[100]=p2[100]=q2[100]=p3[100]=q3[100]=p4[100]=q4[100]=0;
r1[100]=r2[100]=r3[100]=r4[100]=x11[100]=y11[100]=x22[100]=y22[100]=0;
}
/*printf("Enter the windows left xmin , top boundry ymin\n");
scanf("%d%d",&wxmin,&wymin);
printf("Enter the windows right xmax ,bottom boundry ymax\n");
scanf("%d%d",&wxmax,&wymax);
printf("Enter the no. of lines you want to clip : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter line x1 , y1 co-ordinate for line %d\n",i);
scanf("%d%d",&x1[i],&y1[i]);
printf("Enter line x2 , y2 co-ordinate for line %d\n",i);
scanf("%d%d",&x2[i],&y2[i]);
}*/
x1[0]=250;y1[0]=100;x2[0]=250;y2[0]=450;
x1[1]=300;y1[1]=100;x2[1]=300;y2[1]=450;
x1[2]=350;y1[2]=100;x2[2]=350;y2[2]=450;
x1[3]=100;y1[3]=250;x2[3]=450;y2[3]=250;
x1[4]=100;y1[4]=300;x2[4]=450;y2[4]=300;
x1[5]=100;y1[5]=350;x2[5]=450;y2[5]=350;
x1[6]=150;y1[6]=350;x2[6]=350;y2[6]=150;
x1[7]=150;y1[7]=450;x2[7]=450;y2[7]=150;
x1[8]=250;y1[8]=450;x2[8]=450;y2[8]=250;
x1[9]=250;y1[9]=150;x2[9]=450;y2[9]=350;
x1[10]=150;y1[10]=150;x2[10]=450;y2[10]=450;
x1[11]=150;y1[11]=250;x2[11]=350;y2[11]=450;
for(i=0;i<n;i++)
{
u1=0; u2=1;
printf("liang barsky express these 4 inequalities using lpk<=qpk\n");
p1[i]=-(x2[i]-x1[i]); q1[i]=x1[i]-wxmin;
p2[i]=(x2[i]-x1[i]); q2[i]=wxmax-x1[i];
p3[i]=-(y2[i]-y1[i]); q3[i]=y1[i]-wymin;
p4[i]=(y2[i]-y1[i]); q4[i]=wymax-y1[i];
printf("p1=0 line is parallel to left clipping\n");
printf("p2=0 line is parallel to right clipping\n");
printf("p3=0 line is parallel to bottom clipping\n");
printf("p4=0 line is parallel to top clipping\n");
if(((p1[i]==0)&&(q1[i]<0))||((p2[i]==0)&&(q2[i]<0))||((p3[i]==0)&&(q3[i]<0))||((p4[i]==0)&&(q4[i]<0)))
{
printf("Line is rejected\n");
getch();
detectgraph(&gd,&gm);
initgraph(&gd,&gm,"c:\\tc\\bgi");
setcolor(RED);
rectangle(wxmin,wymax,wxmax,wymin);
setcolor(BLUE);
line(x1[i],y1[i],x2[i],y2[i]);
getch();
setcolor(WHITE);
line(x1[i],y1[i],x2[i],y2[i]);
getch();
}
else
{
if(p1[i]!=0)
{
r1[i]=(float) q1[i]/p1[i];
if(p1[i]<0)
u1=max(r1[i],u1);
else
u2=min(r1[i],u2);
}
if(p2[i]!=0)
{
r2[i]=(float) q2[i]/p2[i];
if(p2[i]<0)
u1=max(r2[i],u1);
else
u2=min(r2[i],u2);
}
if(p3[i]!=0)
{
r3[i]=(float) q3[i]/p3[i];
if(p3[i]<0)
u1=max(r3[i],u1);
else
u2=min(r3[i],u2);
}
if(p4[i]!=0)
{
r4[i]=(float) q4[i]/p4[i];
if(p4[i]<0)
u1=max(r4[i],u1);
else
u2=min(r4[i],u2);
}
if(u1>u2)
printf("line rejected\n");
else
{
x11[i]=x1[i]+(u1*(x2[i]-x1[i]));
y11[i]=y1[i]+(u1*(y2[i]-y1[i]));
x22[i]=x1[i]+(u2*(x2[i]-x1[i]));
y22[i]=y1[i]+(u2*(y2[i]-y1[i]));
printf("Original line cordinates\n");
printf("x1 = %d , y1 = %d, x2 = %d, y2 = %d\n",x1[i],y1[i],x2[i],y2[i]);
printf("Windows coordinate are \n");
printf("wxmin = %d, wymin = %d,wxmax = %d , wymax = %d ",wxmin,wymin,wxmax,wymax);
printf("New coordinates are \n");
printf("x1 = %d, y1 = %d,x2 = %d , y2 = %d\n",x11[i],y11[i],x22[i],y22[i]);
/*detectgraph(&gd,&gm);
initgraph(&gd,&gm,"C:\\TC\\BGI");
setcolor(2);
rectangle(wxmin,wymax,wxmax,wymin);
setcolor(1);
line(x1[i],y1[i],x2[i],y2[i]);
getch();
setcolor(0);
line(x1[i],y1[i],x2[i],y2[i]);
setcolor(3);
line(x11[i],y11[i],x22[i],y22[i]);
getch();*/
}
}
}
detectgraph(&gd,&gm);
initgraph(&gd,&gm,"C:\\TC\\BGI");
gotoxy(0,100);
printf("Before Clipping\n");
setcolor(2);
rectangle(wxmin,wymax,wxmax,wymin);
for(i=0;i<n;i++)
{
setcolor(12);
line(x1[i],y1[i],x2[i],y2[i]);
}
getch();
cleardevice();
gotoxy(0,100);
printf("After Clipping\n");
rectangle(wxmin,wymax,wxmax,wymin);
for(i=0;i<n;i++)
{
setcolor(0);
;
line(x1[i],y1[i],x2[i],y2[i]);
setcolor(15);
line(x11[i],y11[i],x22[i],y22[i]);
}
getch();
}
Click here to download the source code
Theory/logic:
Liang and Barsky have created an algorithm that uses floating-point arithmetic but finds the appropriate end points with at most four computations. This algorithm uses the parametric equations for a line and solves four inequalities to find the range of the parameter for which the line is in the viewport.
Parametric equations of a line are:
x=x1 + Δx . u
y=y1 + Δy . u
where Δx=x2-x1, Δy=y2-y1
For point inside the clipping window,
xmin <= x1 + Δx.u <= xmax
ymin <= y1 + Δy.u <= ymax
Rewrite the four inequalities as
pk .u <= qk, k=1,2,3,4
where
p1= - Δx q1=x1-xmin (left)
p2= Δx q2=xmax-x1 (right)
p3= -Δy q3=y1-ymin (bottom)
p4= Δy q4=ymax-y1 (top)
Algorithm: for all k,
- If pk=0, the line is parallel to the corresponding boundary.
--If qk < 0, the line is completely outside the boundary and can be eliminated.
--If qk >= 0, the line is inside the boundary and needs further consideration.
- If pk < 0, the extended line proceeds from outside to inside, calculate rk= qk/pk. Let u1 be maximum of the set containing 0 and the calculated r values.
- If pk > 0, the extended line proceeds from inside to outside, calculate rk= qk/pk. Let u2 be minimumum of the set containing 1 and the calculated r values.
- If u1 > u2 , eliminate the line since it is completely outside. Otherwise use u1 and
u2 to calculate the endpoints of the clipped line.
Data Structure: none.
Advantage:
à Easy to implement.
à It represents the line using parametric equations, so faster line clipping algorithm.
à Also no need of intersection point calculations as in Cohen Sutherland algorithm.
Disadvantage:
à Used for rectangle windows only.
Application :
à When line representation is using parametric equation, this is useful.
àIn window to view port transformation, when the region is to be
Clipped, then this algorithm is used to clip the lines.
No comments:
Post a Comment