Here we will learn a pretty interesting algorithm on polygons, ** Cohen-Sutherland Line Clipping Algorithm**. This is a

**algorithm used for**

*computer graphics***. This is one of the oldest and most popular line clipping algorithm. So, without wasting the time let’s start.**

*line clipping*Table of Contents

*What is a polygon?*

*What is a polygon?*

In geometry, a polygon is defined as a two-dimensional closed shape with straight sides. It does not have curved sides. There are two types of polygons.

: Polygons that have equal sides and angles.*Regular polygons*: Polygons that have unequal sides and angles.*Irregular polygons*

*What is line clipping?*

*What is line clipping?*

Line clipping is a process of removing lines or portion of lines which are outside an area of interest. Basically, we remove or delete the lines which are outside the area and only show which are inside the area.

*Algorithms used for Line Clipping*

*Algorithms used for Line Clipping*

- Cohen–Sutherland algorithm
- Liang-Barsky Algorithm
- Cyrus-Beck Algorithm
- Nicholl-Lee-Nicholl algorithm
- Fast Clipping

In this article. we will be discussing ** Cohen-Sutherland algorithm**.

*Cohen-Sutherland Algorithm*

*Cohen-Sutherland Algorithm*

- The algorithm divides the two-dimensional plane into 9 regions.
- The algorithm uses a 4-bit code called
or*TBRL*.*Region code* stands for Top-Bottom-Right-Left.*TBRL*- Each bit in 4-bit code determines direction. Starting from the leftmost position,
.*Top-Bottom-Right-Left*

*How this algorithm uses TBRL code?*

*How this algorithm uses TBRL code?*

In this problem, we have given the endpoints of lines and for each line, we find the ** TBRL code** for both endpoints. Once we find the

**for both endpoints we apply the**

*TBLR code***operation to determine whether the endpoints are**

*bitwise AND*

*visible, partially visible, or outside the area.**Bitwise AND*

*Bitwise AND*

The output will be 1 only if all the input are 1 otherwise the output will be 0.

*Problem Statement*

*Problem Statement*

Given a set of lines and a rectangular area of interest, the task is to remove the lines which are outside the rectangular area and clip the lines which are partially inside.

** Input: **Given four coordinates

**of the rectangular area and the set of endpoints(**

*X_min, Y_min,***Y_max***X_max,***) representing the lines.**

*X1, Y1, X2, Y2**Rectangular Coordinates:-*

** Bottom left: **X_min = 4, Y_min = 4

** Top Right:** X_max = 10, Y_max = 8

*Endpoints of lines:-*

- Line1 : X1 = 5, Y1 = 5, X2 = 7, Y2 = 7
- Line2 : X1 = 7, Y1 = 9, X2 = 11, Y2 = 4
- Line3 : X1 = 1, Y1 = 5, X2 = 4, Y2 = 1

** Output**:

- Accepted from ( 5, 5 ) to ( 7, 7 ) ( Completely inside the area of interest ).
- Accepted from ( 7.8, 8 ) to ( 10, 5.25 ) ( Clipped ).
- Rejected ( completely outside from the area of interest ).

*Solution*

*Solution*

- First, we divide the rectangular area into 9 regions ( 8 outside regions and 1 inside region ).
- Now, we will find the
of all nine regions. To find*TBRL code*, we will compare the endpoint of lines (*TBRL code*) with the coordinates of the rectangular area (*X, Y*).*X_min, Y_min, X_max, Y_max* - We have
conditions to find the*four*code for the endpoint*TBRL*.*(X, Y)*

Numbering of bits are done from left to right i.e 1, 2, 3, 4. If X is less than X_min then bit number 4 ( Left ) is set. If X is greater than X_max then bit number 3 ( Right ) is set. If Y is less than Y_min then bit number 2 ( Bottom ) is set. If Y is greater than Y_max then bit number 1 ( Top ) is set.

The 4-bit code of the region inside the rectangular area is ** 0000**.

*Let’s discuss the possible number of cases for any given line:*

*Completely inside the given rectangle:*of the*Bitwise OR*code of endpoints of a line should be*TBRL*.*zero*of the*Completely outside the given rectangle: Bitwise AND*code of endpoints should not be*TBRL*.*zero*Both endpoints are in different regions. In this case, the algorithm finds one of the two points that are outside the rectangular region. Now, the algorithm clips the line to the coordinates which are the intersection of a line and rectangular boundary.*Partially inside the given rectangle:*

*Pseudo Code*

*Pseudo Code*

- Assign a
to the endpoints of a given line.*TBRL code* - If both endpoints’
is*TBRL code*then the given line is*0000*.*completely inside* - If
fails then,*point 2*- we will find the
of the endpoints and if the result is*bitwise AND*then the lines are*non zero*.*completely outside* - If the result is
then the lines are*zero*.*partially inside*- Choose an endpoint of the line that is outside the rectangular area.
- Find the intersection point of the rectangular area.
- Change the coordinates of the endpoint and update the
.*TBRL code* - Repeat
until we find a clipped line either trivially accepted or trivially rejected.*step 2*

- we will find the
- Repeat from
for every line.*step 1*

*Let’s implement the pseudo code in C*

```
// C program to implement Cohen Sutherland algorithm
// for line clipping.
#include <stdio.h>
// Defining region codes
const int INSIDE = 0; // 0000
const int LEFT = 1; // 0001
const int RIGHT = 2; // 0010
const int BOTTOM = 4; // 0100
const int TOP = 8; // 1000
// Defining x_max, Y_max and x_min, Y_min for
// clipping rectangle. Since diagonal points are
// enough to define a rectangle
const int X_max = 10;
const int Y_max = 8;
const int X_min = 4;
const int Y_min = 4;
// Function to compute TBRL code for a point(x, y)
int computeCode(double X, double Y)
{
// We assume the point is intially inside.
int code = INSIDE;
if (X < X_min) // to the left of rectangle
code |= LEFT;
else if (X > X_max) // to the right of rectangle
code |= RIGHT;
if (Y < Y_min) // below the rectangle
code |= BOTTOM;
else if (Y > Y_max) // above the rectangle
code |= TOP;
return code;
}
// Implementing Cohen-Sutherland algorithm
// Clipping a line from P1 = (x2, y2) to P2 = (x2, y2)
void cohenSutherlandClip(double x1, double y1,
double x2, double y2)
{
// Compute region codes for P1, P2
int code1 = computeCode(x1, y1);
int code2 = computeCode(x2, y2);
// Initialize line as outside the rectangular window
int accept = 0;
while (1) {
if ((code1 == 0) && (code2 == 0)) {
// If both endpoints lie within rectangle
accept = 1;
break;
}
else if (code1 & code2) {
// If both endpoints are outside rectangle,
// in same region
break;
}
else {
// Some segment of line lies within the
// rectangle
int code_out;
double x, y;
// At least one endpoint is outside the
// rectangle, pick it.
if (code1 != 0)
code_out = code1;
else
code_out = code2;
// Find intersection point;
// using formulas y = y1 + slope * (x - x1),
// x = x1 + (1 / slope) * (y - y1)
if (code_out & TOP) {
// point is above the clip rectangle
x = x1 + (x2 - x1) * (Y_max - y1) / (y2 - y1);
y = Y_max;
}
else if (code_out & BOTTOM) {
// point is below the rectangle
x = x1 + (x2 - x1) * (Y_min - y1) / (y2 - y1);
y = Y_min;
}
else if (code_out & RIGHT) {
// point is to the right of rectangle
y = y1 + (y2 - y1) * (X_max - x1) / (x2 - x1);
x = X_max;
}
else if (code_out & LEFT) {
// point is to the left of rectangle
y = y1 + (y2 - y1) * (X_min - x1) / (x2 - x1);
x = X_min;
}
// Now intersection point x, y is found
// We replace point outside rectangle
// by intersection point
if (code_out == code1) {
x1 = x;
y1 = y;
code1 = computeCode(x1, y1);
}
else {
x2 = x;
y2 = y;
code2 = computeCode(x2, y2);
}
}
}
if (accept) {
printf("Line accepted from %d, %d to %d, %d\n",x1, y1, x2, y2);
}
else
printf("Line rejected");
}
// Driver code
int main()
{
// First Line segment
// P11 = (5, 5), P12 = (7, 7)
cohenSutherlandClip(5, 5, 7, 7);
// Second Line segment
// P21 = (7, 9), P22 = (11, 4)
cohenSutherlandClip(7, 9, 11, 4);
// Third Line segment
// P31 = (1, 5), P32 = (4, 1)
cohenSutherlandClip(1, 5, 4, 1);
return 0;
}
```

*Output*

*To calculate the intersection point.*

*To calculate the intersection point.*

*using formulas:**Equation_1:**y = y1 + slope * (x – x1)**Equation_2:**x = x1 + (1 / slope) * (y – y1)*

- Slope value can be determined by the endpoints of line
*slope = ( y2 – y1 / x2 – x1 )*

- In
, the value of x will be*equation_1*, if the point is right to the rectangle.*x = x_max*, if the point is left to the rectangle.*x = x_min*

- In
, the value of y will be*equation_2*, if the point is above the rectangle.*y = y_max*, if the point is below the rectangle.*y = y_min*

Since we process all the ** N** points and it takes constant time to find whether the point is

**,**

*completely inside***, or**

*partially inside***.**

*completely outside**Time Complexity:*

*Time Complexity:*

- Worst case time complexity:
*O(N)* - Average case time complexity:
*O(N)* - Best case time complexity:
*O(N)*

*Space Complexity:*

*Space Complexity:*

Here we haven’t taken any extra space though we have used too many variables but, variables take constant space. Hence, the ** space complexity** is

*O(1).**Conclusion*

*Conclusion*

** Cohen-Sutherland line clipping algorithm** works only for rectangular clip window which means if the area of interest has any other shape than a rectangle, it will not work. For areas of interest with other shapes, we need to use other algorithms like the

**and the**

*Cyrus-Beck algorithm***.**

*Sutherland-Hodgman algorithm*Hope you like this article on ** Cohen-Sutherland line clipping algorithm**.