Cohen-Sutherland Line Clipping Algorithm in C | Code

Here we will learn a pretty interesting algorithm on polygons, Cohen-Sutherland Line Clipping Algorithm. This is a computer graphics algorithm used for line clipping. This is one of the oldest and most popular line clipping algorithm. So, without wasting the time let’s start.

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.

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

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

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

Cohen-Sutherland Algorithm

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

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 TBLR code for both endpoints we apply the bitwise AND operation to determine whether the endpoints are visible, partially visible, or outside the area.

Bitwise AND

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

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 X_min, Y_min, X_max, Y_max of the rectangular area and the set of endpoints( X1, Y1, X2, Y2 ) representing the lines.

Rectangular Coordinates:-

Bottom left: X_min = 4, Y_min = 4

Top Right: X_max = 10, Y_max = 8

Endpoints of lines:-

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

Output:

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

Solution

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

1. Completely inside the given rectangle: Bitwise OR of the TBRL code of endpoints of a line should be zero.
2. Completely outside the given rectangle: Bitwise AND of the TBRL code of endpoints should not be zero.
3. Partially inside the given rectangle: 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.

Pseudo Code

1. Assign a TBRL code to the endpoints of a given line.
2. If both endpoints’ TBRL code is 0000 then the given line is completely inside.
3. If point 2 fails then,
• we will find the bitwise AND of the endpoints and if the result is non zero then the lines are completely outside.
• If the result is zero then the lines are 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 step 2 until we find a clipped line either trivially accepted or trivially rejected.
4. Repeat from step 1 for every line.

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.

• 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 equation_1, the value of x will be
• x = x_max, if the point is right to the rectangle.
• x = x_min, if the point is left to the rectangle.
• In equation_2, the value of y will be
• y = y_max, if the point is above the rectangle.
• y = y_min, if the point is below the rectangle.

Since we process all the N points and it takes constant time to find whether the point is completely inside, partially inside, or completely outside.

Time Complexity:

• Worst case time complexity: O(N)
• Average case time complexity: O(N)
• Best case time complexity: O(N)

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

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 Cyrus-Beck algorithm and the Sutherland-Hodgman algorithm.