# 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: