Polygon clipping program
Code
#include<stdio.h>
#include<dos.h>
#include<conio.h>
#include<graphics.h>
#include<stdlib.h>
int el,er,et,eb;
struct node
{
int x;
int y;
struct node *next;
};
struct node *getnode()
{
struct node *ptr;
ptr=(struct node *)malloc(sizeof(struct node));
return ptr;
}
struct node *insert(struct node *base,int x,int y)
{
struct node *p,*q=NULL;
p=base;
if(p==NULL)
{
p=getnode();
p->x=x;
p->y=y;
p->next=NULL;
return p;
}
while(p!=NULL)
{
q=p;
p=p->next;
}
p=getnode();
p->x=x;
p->y=y;
p->next=NULL;
q->next=p;
return base;
};
// Function to find the intersection
struct node *intersect(struct node *p,int edge,float m)
{
struct node *t;
t=getnode();
if(edge==0) //left
{
t->y=p->y+( m*(el-p->x) );
t->x=el;
}
if( edge==1) //right
{
t->y=p->y+( m*(er-p->x) );
t->x=er;
}
if(edge==2) //top
{
t->x=p->x+( (et-p->y)/m );
t->y=et;
}
if(edge==3) //bottom
{
t->x=p->x+( (eb-p->y)/m );
t->y=eb;
}
return t;
}
// Clips the polygon with the left egde
struct node *elclip (struct node *base)
{
float m;
struct node *fin=NULL,*p,*q,*s=NULL,*i=NULL;
p=base;q=base->next;
while(q!=NULL)
{
if (p->x >=el && q->x >=el)
{
s=fin;
while(s->next!=NULL)
s=s->next;
if(s->x != p->x || s->y != p->y)
fin=insert(fin,p->x,p->y);
if(s->x != q->x || s->y != q->y)
fin=insert(fin,q->x,q->y);
}
else
{
m=1.0 * (q->y - p->y) / (q->x - p->x);
if(p->x >= el && q->x < el)
{
s=fin;
while(s->next!=NULL)
s=s->next;
if(s->x != p->x || s->y != p->y)
fin=insert(fin,p->x,p->y);
i=intersect(q,0,m);
fin=insert(fin,i->x,i->y);
}
else
{
if(q->x >= el && p->x < el)
{
i=intersect(p,0,m);
fin=insert(fin,i->x,i->y);
s=fin;
while(s->next!=NULL)
s=s->next;
if(s->x != q->x || s->y != q->y)
fin=insert(fin,q->x,q->y);
}
}
}
p=p->next;
q=q->next;
}
return fin;
}
// Clips the polygon with the right egde
struct node *erclip (struct node *base)
{
float m;
struct node *fin=NULL,*p,*q,*s=NULL,*i=NULL;
p=base;q=base->next;
while(q!=NULL)
{
if (p->x <=er && q->x <=er)
{
s=fin;
while(s->next!=NULL)
s=s->next;
if(s->x != p->x || s->y != p->y)
fin=insert(fin,p->x,p->y);
if(s->x != q->x || s->y != q->y)
fin=insert(fin,q->x,q->y);
}
else
{
m=1.0 * (q->y - p->y) / (q->x - p->x);
if(p->x <= er && q->x > er)
{
s=fin;
while(s->next!=NULL)
s=s->next;
if(s->x != p->x || s->y != p->y)
fin=insert(fin,p->x,p->y);
i=intersect(q,1,m);
fin=insert(fin,i->x,i->y);
}
else
{
if(q->x <= er && p->x > er)
{
i=intersect(p,1,m);
fin=insert(fin,i->x,i->y);
s=fin;
while(s->next!=NULL)
s=s->next;
if(s->x != q->x || s->y != q->y)
fin=insert(fin,q->x,q->y);
}
}
}
p=p->next;
q=q->next;
}
return fin;
}
// Clips the polygon with the bottom egde
struct node *ebclip (struct node *base)
{
float m;
struct node *fin=NULL,*p,*q,*s=NULL,*i=NULL;
p=base;q=base->next;
while(q!=NULL)
{
if(p->y <=eb && q->y <=eb)
{
s=fin;
while(s->next!=NULL)
s=s->next;
if(s->x != p->x || s->y != p->y)
fin=insert(fin,p->x,p->y);
if(s->x != q->x || s->y != q->y)
fin=insert(fin,q->x,q->y);
}
else
{
m=1.0 * (q->y - p->y) / (q->x - p->x);
if(p->y <= eb && q->y > eb)
{
if(p->x==q->x)
{
i->x=p->x;
i->y=eb;
}
else
{
s=fin;
while(s->next!=NULL)
s=s->next;
if(s->x != p->x || s->y != p->y)
fin=insert(fin,p->x,p->y);
i=intersect(q,3,m);
}
fin=insert(fin,i->x,i->y);
}
else
{
if(q->y <= eb && p->y > eb)
{
if(p->x==q->x)
{
i->x=p->x;
i->y=eb;
fin=insert(fin,i->x,i->y);
}
else
{
i=intersect(p,3,m);
fin=insert(fin,i->x,i->y);
s=fin;
while(s->next!=NULL)
s=s->next;
if(s->x != q->x || s->y != q->y)
fin=insert(fin,q->x,q->y);
}
}
}
}
p=p->next;
q=q->next;
}
return fin;
}
// Clips the polygon with the top egde
struct node *etclip (struct node *base)
{
float m;
struct node *fin=NULL,*p,*q,*s=NULL,*i=NULL;
p=base;q=base->next;
while(q!=NULL)
{
if (p->y >=et && q->y >=et)
{
s=fin;
while(s->next!=NULL)
s=s->next;
if(s->x != p->x || s->y != p->y)
fin=insert(fin,p->x,p->y);
if(s->x != q->x || s->y != q->y)
fin=insert(fin,q->x,q->y);
}
else
{
m=1.0 * (q->y - p->y) / (q->x - p->x);
if(p->y >= et && q->y < et)
{
if(p->x==q->x)
{
i->x=p->x;
i->y=et;
}
else
{
s=fin;
while(s->next!=NULL)
s=s->next;
if(s->x != p->x || s->y != p->y)
fin=insert(fin,p->x,p->y);
i=intersect(q,2,m);
}
fin=insert(fin,i->x,i->y);
}
else
{
if(q->y >= et && p->y < et)
{
if(p->x==q->x)
{
i->x=p->x;
i->y=et;
fin=insert(fin,i->x,i->y);
}
else
{
i=intersect(p,2,m);
fin=insert(fin,i->x,i->y);
s=fin;
while(s->next!=NULL)
s=s->next;
if(s->x != q->x || s->y != q->y)
fin=insert(fin,q->x,q->y);
}
}
}
}
p=p->next;
q=q->next;
}
return fin;
}
//Draws the polygon
void display(struct node *fin)
{
struct node *p=fin , *q=fin->next;
while(q!=NULL)
{
line(p->x,p->y,q->x,q->y);
p=q;
q=q->next;
}
q=fin;
line(p->x,p->y,q->x,q->y);
}
main()
{
int gd=DETECT,gm,edg,i,x,y,x1,y1;
struct node *base=NULL,*final=NULL;
initgraph(&gd,&gm,"c:\\tc\\bgi");
cleardevice();
setbkcolor(15);
printf("\n");
printf("\nEnter co ordinates of clipping window (LRTB):");
scanf("%d%d%d%d",&el,&er,&et,&eb);
printf("\nEnter the number of edges :");
scanf("%d",&edg);
printf("\nEnter the coordinates:\n ");
scanf("%d %d",&x1,&y1);
base=insert(base,x1,y1);
for(i=0;i<edg-1;i++)
{
scanf("%d%d",&x,&y);
base=insert(base,x,y);
}
base=insert(base,x1,y1);
cleardevice();
setcolor(8);
line(el,et,er,et);
line(er,et,er,eb);
line(er,eb,el,eb);
line(el,eb,el,et);
//displays the original polygon
outtextxy(10,10,"Original Polygon");
display(base);
getch();
//clip with el
cleardevice();
final=elclip(base);
line(el,eb,el,et);
outtextxy(10,10,"Clipped with Left edge");
display(final);
getch();
//clip with eb
cleardevice();
final=ebclip(final);
line(er,eb,el,eb);
outtextxy(10,10,"Clipped with Bottom edge");
display(final);
getch();
//clip with er
cleardevice();
final=erclip(final);
line(er,et,er,eb);
outtextxy(10,10,"Clipped with Right edge");
display(final);
getch();
//clip with et
cleardevice();
final=etclip(final);
line(el,et,er,et);
outtextxy(10,10,"Clipped with Top edge");
display(final);
getch();
//displays the original polygon
cleardevice();
line(el,et,er,et);
line(er,et,er,eb);
line(er,eb,el,eb);
line(el,eb,el,et);
outtextxy(10,10,"Original Polygon");
display(base);
getch();
//displays the clipped polygon
cleardevice();
line(el,et,er,et);
line(er,et,er,eb);
line(er,eb,el,eb);
line(el,eb,el,et);
outtextxy(10,10,"Clipped Polygon");
display(final);
getch();
return 0;
}