Cohen-Sutherland Line Clipping Algorithm

By | March 10, 2022

Line Clipping

Line Clipping is a procedure that determines which portion of a line lies inside the clipping window and is displayed. Lines that do not intersect the clipping window are either completely inside the window or completely outside the window. On the other hand, a line that intersects the clipping window is divided by the intersection points into segments that are either inside or outside the window. Mathematician Cohen and Sutherland developed this line clipping algorithm. It is most popular used algorithm for line clipping. In this article, we learn about Cohen-Sutherland Line Clipping Algorithm.

Therefore, we perform calculations to determine the intersection points of the lines that overlap clipping boundaries. All the line segments fall into one of the following clipping categories:

1. Visible: Both the endpoints of the line lie within the window.

2. Not-Visible: When the line lies outside the window. This will occur if the line from (x1 , y1) to (x2 , y2) satisfies any one of the following four conditions:

x1 , x2 > xmax

x1 , x2 < xmin

y1 , y2 > ymax

y1 , y2 < ymin

3. Clipping Candidates or Partially Visible: A line that is partially inside and partially outside the window.

Cohen-Sutherland Line Clipping Algorithm

Cohen-Sutherland Line Clipping Algorithm

Mathematician Cohen and Sutherland developed this line clipping algorithm. It is most popular used algorithm for line clipping. This is very fast with line segment which is completely inside or outside clipping window.

It is very efficient with line segment which is partially inside or outside the clipping window.  In this algorithm, clipping window and its surrounding divided into 9 segments.

Sections of Window in Cohen-Sutherland Line Clipping Algorithm

Each region is assigned with a nibble (4bit). [0000] for center and it uses TBRL (Top-Bottom-Left-Right) to assign values in segments. Put 1 in the segment is in the point and put other as 0.

Four-bit Region Code

After assigning 4-bit region code, the Cohen-Sutherland Line Clipping Algorithm works as follows:

1. If both the end-point of the line has the region code 0000, then line lies completely inside the window.

Eg: For line AB, the end-points of A and B are 0000. Therefore, line AB lies inside the window.

Line AB inside window

2. If both the end-point of the line has the region code non-zero, then line lies completely outside the window.

Eg: For line AB, the end-points of A and B are 0010, 0110 means non-zero. Therefore, line AB lies outside the window.

Line AB outside window

3. If one of the end-point of the line has the region code 0000, and other end-point non zero, then the line lies partially inside or outside the window.

Eg: For line AB, the end-points of A and B are 0000, 0000. Therefore, line AB lies partially inside or outside the window.

Line AB partially inside window

Check line position using Cohen-Sutherland Line Clipping Algorithm

To find any line lies inside or outside the window, take the coordinates of both points and apply logical AND on it. If the result is zero, then line is inside the window. If the result is non-zero then, lies partially inside or outside the window. Any 2 coordinates have 1 at same bit position, then the line is completely outside the window.

Line clipping by Cohen-Sutherland Algorithm

Rules for line clipping on different sides of window

1. If line intersect left boundary of the window then k'(x, y)

m = y2 – y1 / x2 – x1

[where m is slope of line]

m = y – y1 / x – x1

[x2  = x and y2  = y]

m = y – y1 / xmin – x1

[x = xmin ]

⇒ y = y1 + m(xmin – x1)

The new points of clipping candidate will be k'( xmin, y(xmin – x1)).

2. If line intersect right boundary of the window then k'(x, y)

m = y2 – y1 / x2 – x1

[where m is slope of line]

m = y – y1 / x – x1

[x2  = x and y2  = y]

m = y – y1 / xmax – x1

[x = xmax ]

⇒ y = y1 + m(xmax – x1)

The new points of clipping candidate will be k'( xmax, y(xmax – x1)).

3. If line intersect bottom boundary of the window then k'(x, y)

m = y2 – y1 / x2 – x1

[where m is slope of line]

m = y – y1 / x – x1

[x2  = x and y2  = y]

m = ymin – y1 / x – x1

[y= ymin ]

⇒ x = x1 +(ymin – y1)/m

The new points of clipping candidate will be k'( (x1 +(ymin – y1)/m), ymin ).

4. If line intersect top boundary of the window then k'(x, y)

m = y2 – y1 / x2 – x1

[where m is slope of line]

m = y – y1 / x – x1

[x2  = x and y2  = y]

m = ymax – y1 / x – x1

[y= ymax ]

⇒ x = x1 +(ymax – y1)/m

The new points of clipping candidate will be k'( (x1 +(ymax – y1)/m), ymax ).

Related posts:-