Polygon Clipping (Sutherland Hodgman algorithm)
To clip a polygon, we cannot directly apply a line-clipping method to the individual
polygon edges because this approach would produce a series of unconnected line
segments. For polygon clipping, we require an algorithm that will generate one or
more closed areas that are then scan converted for the appreciate area fill. The
output of a polygon clipper should be a sequence of vertices that defines the clipped
polygon boundaries. We can use Sutherland-Hodgman algorithm for polygon
clipping. Polygon is clipped by comparing it against each boundary in turn.
Sutherland-Hodgman does four tests on every edge of the
polygon:
Inside – Inside ( I-I)
Inside –Outside (I-O)
Outside –Outside (O-O)
Outside-Inside(O-I)
Output co-ordinate list is created by doing these tests on every edge of polygon.
Display clipped polygon.
Learn how to run C/C++ graphics programs on Ubuntu here
polygon edges because this approach would produce a series of unconnected line
segments. For polygon clipping, we require an algorithm that will generate one or
more closed areas that are then scan converted for the appreciate area fill. The
output of a polygon clipper should be a sequence of vertices that defines the clipped
polygon boundaries. We can use Sutherland-Hodgman algorithm for polygon
clipping. Polygon is clipped by comparing it against each boundary in turn.
Sutherland-Hodgman does four tests on every edge of the
polygon:
Inside – Inside ( I-I)
Inside –Outside (I-O)
Outside –Outside (O-O)
Outside-Inside(O-I)
Output co-ordinate list is created by doing these tests on every edge of polygon.
Algorithm:
- Clip a polygon by processing the polygon boundary as a whole against each window edge.
- Processing all polygon vertices against each clip rectangle boundary in turn.
- Beginning with the initial set of polygon vertices, we could first clip the polygon
against the left rectangle boundary to produce a new sequence of vertices. - The new set of vertices could be successively passed to a right boundary clipper, a
bottom boundary clipper, and a top boundary clipper, a right boundary clipper. - At each step, a new sequence of output vertices is generated and passed to the
next window boundary clipper. - There are four possible cases when processing vertices in sequence around the
perimeter of a polygon. - As each pair of adjacent polygon vertices is passed to a next window boundary
clipper, we make the following tests: - If the first vertex is outside the window boundary and the second vertex is
inside. Then , both the intersection point of the polygon edge with the window
boundary and the second vertex are added to the output vertex list. - If both input vertices are inside the window boundary.Then, only the second
vertex is added to the output vertex list. - If the first vertex is inside the window boundary and the second vertex is
outside.Then, only the edge intersection with the window boundary is added to
the output vertex list. - If both input vertices are outside the window boundary.Then, nothing is added to
the output vertex list.
Output:
Display clipped polygon.
#include<iostream>
using namespace std;
#include<graphics.h>
#define round(a) ((int)(a+0.5))
int k;
float xmin,ymin,xmax,ymax,arr[20],m;
void clipl(float x1,float y1,float x2,float y2)
{
if(x2-x1)
m=(y2-y1)/(x2-x1);
else
m=100000;
if(x1 >= xmin && x2 >= xmin)
{
arr[k]=x2;
arr[k+1]=y2;
k+=2;
}
if(x1 < xmin && x2 >= xmin)
{
arr[k]=xmin;
arr[k+1]=y1+m*(xmin-x1);
arr[k+2]=x2;
arr[k+3]=y2;
k+=4;
}
if(x1 >= xmin && x2 < xmin)
{
arr[k]=xmin;
arr[k+1]=y1+m*(xmin-x1);
k+=2;
}
}
void clipt(float x1,float y1,float x2,float y2)
{
if(y2-y1)
m=(x2-x1)/(y2-y1);
else
m=100000;
if(y1 <= ymax && y2 <= ymax)
{
arr[k]=x2;
arr[k+1]=y2;
k+=2;
}
if(y1 > ymax && y2 <= ymax)
{
arr[k]=x1+m*(ymax-y1);
arr[k+1]=ymax;
arr[k+2]=x2;
arr[k+3]=y2;
k+=4;
}
if(y1 <= ymax && y2 > ymax)
{
arr[k]=x1+m*(ymax-y1);
arr[k+1]=ymax;
k+=2;
}
}
void clipr(float x1,float y1,float x2,float y2)
{
if(x2-x1)
m=(y2-y1)/(x2-x1);
else
m=100000;
if(x1 <= xmax && x2 <= xmax)
{
arr[k]=x2;
arr[k+1]=y2;
k+=2;
}
if(x1 > xmax && x2 <= xmax)
{
arr[k]=xmax;
arr[k+1]=y1+m*(xmax-x1);
arr[k+2]=x2;
arr[k+3]=y2;
k+=4;
}
if(x1 <= xmax && x2 > xmax)
{
arr[k]=xmax;
arr[k+1]=y1+m*(xmax-x1);
k+=2;
}
}
void clipb(float x1,float y1,float x2,float y2)
{
if(y2-y1)
m=(x2-x1)/(y2-y1);
else
m=100000;
if(y1 >= ymin && y2 >= ymin)
{
arr[k]=x2;
arr[k+1]=y2;
k+=2;
}
if(y1 < ymin && y2 >= ymin)
{
arr[k]=x1+m*(ymin-y1);
arr[k+1]=ymin;
arr[k+2]=x2;
arr[k+3]=y2;
k+=4;
}
if(y1 >= ymin && y2 < ymin)
{
arr[k]=x1+m*(ymin-y1);
arr[k+1]=ymin;
k+=2;
}
}
int main()
{
int gdriver=DETECT,gmode=0;
float xi,yi,xf,yf,polyy[20];
int n,poly[20],i;
//clrscr();
cout<<"Coordinates of rectangular clip window :\nxmin,ymin :";
cin>>xmin>>ymin;
cout<<"xmax,ymax :";
cin>>xmax>>ymax;
cout<<"\n\nPolygon to be clipped :\nNumber of sides :";
cin>>n;
cout<<"Enter the coordinates :";
for(i=0;i<2*n;i++)
cin>>polyy[i];
polyy[i]=polyy[0];
polyy[i+1]=polyy[1];
for(i=0;i < 2*n+2;i++)
poly[i]=round(polyy[i]);
initgraph(&gdriver,&gmode,NULL);
setcolor(RED);
rectangle(xmin,ymax,xmax,ymin);
cout<<"\t\tUNCLIPPED POLYGON";
setcolor(WHITE);
fillpoly(n,poly);
getch();
cleardevice();
k=0;
for(i=0;i < 2*n;i+=2)
clipl(polyy[i],polyy[i+1],polyy[i+2],polyy[i+3]);
n=k/2;
for(i=0;i < k;i++)
polyy[i]=arr[i];
polyy[i]=polyy[0];
polyy[i+1]=polyy[1];
k=0;
for(i=0;i < 2*n;i+=2)
clipt(polyy[i],polyy[i+1],polyy[i+2],polyy[i+3]);
n=k/2;
for(i=0;i < k;i++)
polyy[i]=arr[i];
polyy[i]=polyy[0];
polyy[i+1]=polyy[1];
k=0;
for(i=0;i < 2*n;i+=2)
clipr(polyy[i],polyy[i+1],polyy[i+2],polyy[i+3]);
n=k/2;
for(i=0;i < k;i++)
polyy[i]=arr[i];
polyy[i]=polyy[0];
polyy[i+1]=polyy[1];
k=0;
for(i=0;i < 2*n;i+=2)
clipb(polyy[i],polyy[i+1],polyy[i+2],polyy[i+3]);
for(i=0;i < k;i++)
poly[i]=round(arr[i]);
if(k)
fillpoly(k/2,poly);
setcolor(RED);
rectangle(xmin,ymax,xmax,ymin);
cout<<"\tCLIPPED POLYGON";
getch();
closegraph();
return 0;
}
Learn how to run C/C++ graphics programs on Ubuntu here
No comments: