EXPT-3
Line Clipping
(Cohen–Sutherland Algorithm)
https://youtu.be/NmjboAjaqWs
Description:-
In this algorithm, we are given 9 regions on the screen. Out of which one
region is of the window and the rest 8 regions are around it given by 4 digit
binary. The division of the regions are based on (x_max, y_max) and
(x_min, y_min).
The central part is the viewing region or window, all the lines which lie within
this region are completely visible. A region code is always assigned to the
endpoints of the given line.
To check whether the line is visible or not.
Algorithm
Steps
1) Assign the region codes to both endpoints.
2) Perform OR operation on both of these endpoints.
3) if OR = 0000,
then it is completely visible (inside the window).
else
Perform AND operation on both these endpoints.
i) if AND ≠ 0000,
then the line is invisible and not inside the window.
Also, it can’t be considered for clipping.
ii) else
AND = 0000, the line is partially inside the window and
considered for clipping.
4) After confirming that the line is partially inside the window, then we find
the intersection with the boundary of the window. By using the following
formula:-
Slope:- m= (y2-y1)/(x2-x1)
a) If the line passes through top or the line intersects with the top
boundary of the window.
x = x + (y_wmax – y)/m
y = y_wmax
b) If the line passes through the bottom or the line intersects with the
bottom boundary of the window.
x = x + (y_wmin – y)/m
y = y_wmin
c) If the line passes through the left region or the line intersects with the
left boundary of the window.
y = y+ (x_wmin – x)*m
x = x_wmin
d) If the line passes through the right region or the line intersects with the
right boundary of the window.
y = y + (x_wmax -x)*m
x = x_wmax
5) Now, overwrite the endpoints with a new one and update it.
6) Repeat the 4th step till your line doesn’t get completely clipped
Given a set of lines and a rectangular area of interest, the task is to remove
lines that are outside the area of interest and clip the lines which are partially
inside the area.
The algorithm can be outlines as follows:-
Nine regions are created, eight "outside" regions and one
"inside" region.
For a given line extreme point (x, y), we can quickly
find its region's four bit code. Four bit code can
be computed by comparing x and y with four values
(x_min, x_max, y_min and y_max).
If x is less than x_min then bit number 1 is set.
If x is greater than x_max then bit number 2 is set.
If y is less than y_min then bit number 3 is set.
If y is greater than y_max then bit number 4 is set
There are three possible cases for any given line.
1. Completely inside the given rectangle : Bitwise OR of region of two
end points of line is 0 (Both points are inside the rectangle)
2. Completely outside the given rectangle : Both endpoints share at least
one outside region which implies that the line does not cross the visible
region. (bitwise AND of endpoints != 0).
3. Partially inside the window : Both endpoints are in different regions. In
this case, the algorithm finds one of the two points that is outside the
rectangular region. The intersection of the line from outside point and
rectangular window becomes new corner point and the algorithm repeats
PROGRAM
#include<graphics.h>
#include<conio.h>
#include<stdio.h>
#include<math.h>
void main()
{
int
rcode_begin[4]={0,0,0,0},rcode_end[4]={0,0,0,0},region_code
[4];
int W_xmax,W_ymax,W_xmin,W_ymin,flag=0;
float slope;
int x,y,x1,y1,i, xc,yc;
int gr=DETECT,gm;
initgraph(&gr,&gm,"C:\\TURBOC3\\BGI");
printf("\n****** Cohen Sutherlsnd Line Clipping algorithm
***********");
printf("\n Now, enter XMin, YMin =");
scanf("%d %d",&W_xmin,&W_ymin);
printf("\n First enter XMax, YMax =");
scanf("%d %d",&W_xmax,&W_ymax);
printf("\n Please enter intial point x and y= ");
scanf("%d %d",&x,&y);
printf("\n Now, enter final point x1 and y1= ");
scanf("%d %d",&x1,&y1);
cleardevice();
rectangle(W_xmin,W_ymin,W_xmax,W_ymax);
line(x,y,x1,y1);
line(0,0,600,0);
line(0,0,0,600);
if(y>W_ymax) {
rcode_begin[0]=1; // Top
flag=1 ;
}
if(y<W_ymin) {
rcode_begin[1]=1; // Bottom
flag=1;
}
if(x>W_xmax) {
rcode_begin[2]=1; // Right
flag=1;
}
if(x<W_xmin) {
rcode_begin[3]=1; //Left
flag=1;
}
//end point of Line
if(y1>W_ymax){
rcode_end[0]=1; // Top
flag=1;
}
if(y1<W_ymin) {
rcode_end[1]=1; // Bottom
flag=1;
}
if(x1>W_xmax){
rcode_end[2]=1; // Right
flag=1;
}
if(x1<W_xmin){
rcode_end[3]=1; //Left
flag=1;
}
if(flag==0)
{
printf("No need of clipping as it is already in window");
}
flag=1;
for(i=0;i<4;i++){
region_code[i]= rcode_begin[i] && rcode_end[i] ;
if(region_code[i]==1)
flag=0;
}
if(flag==0)
{
printf("\n Line is completely outside the window");
}
else{
slope=(float)(y1-y)/(x1-x);
if(rcode_begin[2]==0 && rcode_begin[3]==1) //left
{
y=y+(float) (W_xmin-x)*slope ;
x=W_xmin;
}
if(rcode_begin[2]==1 && rcode_begin[3]==0) // right
{
y=y+(float) (W_xmax-x)*slope ;
x=W_xmax;
}
if(rcode_begin[0]==1 && rcode_begin[1]==0) // top
{
x=x+(float) (W_ymax-y)/slope ;
y=W_ymax;
}
if(rcode_begin[0]==0 && rcode_begin[1]==1) // bottom
{
x=x+(float) (W_ymin-y)/slope ;
y=W_ymin;
}
// end points
if(rcode_end[2]==0 && rcode_end[3]==1) //left
{
y1=y1+(float) (W_xmin-x1)*slope ;
x1=W_xmin;
}
if(rcode_end[2]==1 && rcode_end[3]==0) // right
{
y1=y1+(float) (W_xmax-x1)*slope ;
x1=W_xmax;
}
if(rcode_end[0]==1 && rcode_end[1]==0) // top
{
x1=x1+(float) (W_ymax-y1)/slope ;
y1=W_ymax;
}
if(rcode_end[0]==0 && rcode_end[1]==1) // bottom
{
x1=x1+(float) (W_ymin-y1)/slope ;
y1=W_ymin;
}
}
delay(1000);
clearviewport();
rectangle(W_xmin,W_ymin,W_xmax,W_ymax);
line(0,0,600,0);
line(0,0,0,600);
setcolor(RED);
line(x,y,x1,y1);
getch();
closegraph();
}
OUTPUT
