Cohen-Sutherland Line Clipping Algorithm (Detailed Explanation)

The Cohen-Sutherland Line Clipping Algorithm is used to clip lines against a rectangular clipping window. It determines which portion of a line is inside the window and discards the rest.

1. Key Concepts

• Clipping Window: A rectangular area defined by four boundaries:

  • Left: $x_{min}$

  • Right: $x_{max}$

  • Bottom: $y_{min}$

  • Top: $y_{max}$

• Line Segment: Defined by two endpoints $(x_1, y_1)$ and $(x_2, y_2)$.

• Region Codes: Each point is assigned a 4-bit region code based on its position relative to the window.

2. Region Code Calculation

Each point is classified into one of nine regions based on its position relative to the clipping window.

The region code is a 4-bit binary value where:

• Bit 1: 1 if the point is above (TOP), else 0

• Bit 2: 1 if the point is below (BOTTOM), else 0

• Bit 3: 1 if the point is right (RIGHT), else 0

• Bit 4: 1 if the point is left (LEFT), else 0

For example:

• A point inside the window has code 0000.

• A point above and to the left of the window has code 1001.

3. Cohen-Sutherland Algorithm Steps

1. Compute region codes for both endpoints of the line.

2. Check trivial acceptance:

   • If both region codes are 0000, the entire line is inside the clipping window.

   • Print the original line as output.

3. Check trivial rejection:

   • If code1 & code2 != 0, both points share an outside region (same side of the window), so the line is completely outside and is discarded.

4. Perform Clipping (If necessary):

   • If one endpoint is outside, compute its intersection with the clipping boundary.

   • Replace the outside point with the intersection and recalculate its region code.

   • Repeat until the line is either fully inside or rejected.

5. Output the clipped line segment.

4. Clipping Intersections

The intersection of the line with the window boundaries is computed using the equation of a line:

The outside endpoint is replaced with the new intersection point, and the process repeats.

5. Example Walkthrough

Input:

Clipping Window: (x_min, y_min) = (10, 10), (x_max, y_max) = (200, 200)
Line Segment: (x1, y1) = (5, 5), (x2, y2) = (250, 250)

Step 1: Compute Region Codes

• (5,5) → Code: 0101 (Bottom-Left)

• (250,250) → Code: 1010 (Top-Right)

Step 2: Check Trivial Cases

• Neither point is inside (0000) → No trivial acceptance.

• Code1 & Code2 = 0101 & 1010 → 0000 (not completely outside) → No trivial rejection.

Step 3: Clip Against Boundaries

• Clip against Left (x = 10):

  • Compute new y:

    $$y = 5 + \frac{(250 - 5) \times (10 - 5)}{(250 - 5)} = 10$$

  • New point: (10,10) (now inside).

• Clip against Right (x = 200):

  • Compute new y:

    $$y = 5 + \frac{(250 - 5) \times (200 - 5)}{(250 - 5)} = 200$$

  • New point: (200,200) (now inside).

Step 4: Output Clipped Line

Clipped Line: (10,10) to (200,200)

6. Time Complexity

• Computing region codes: $O(1)$
  

• Bitwise checks (accept/reject): $O(1)$
  

• Finding intersections (at most 4 times): $O(1)$
  

• Overall Complexity: $O(1)$(Constant time)

---

7. Why Use Cohen-Sutherland?

✅ Fast – Uses bitwise operations for efficiency.
✅ Simple – Easy to implement and understand.
✅ Effective – Quickly discards trivial cases.

However, it only works for axis-aligned rectangular clipping. For other shapes, algorithms like Liang-Barsky or Sutherland-Hodgman are better.

---

8. Summary

Step	Description
1. Compute region codes	Assign 4-bit code to each endpoint
2. Trivial acceptance	If both endpoints are inside, draw line
3. Trivial rejection	If both share an outside region, discard line
4. Clip the line	Intersect it with clipping window
5. Output new line	Draw the clipped version

Perform the Line Clipping Algorithm in C Language

 #include <stdio.h>

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

int x_min, y_min, x_max, y_max;

int computeCode(int x, int y) {

    int code = INSIDE;

    if (x < x_min)

        code |= LEFT;

    else if (x > x_max)

        code |= RIGHT;

    if (y < y_min)

        code |= BOTTOM;

    else if (y > y_max)

        code |= TOP;

    return code;

}

void cohenSutherlandClip(int x1, int y1, int x2, int y2) {

    int code1 = computeCode(x1, y1);

    int code2 = computeCode(x2, y2);

    int accept = 0;

    while (1) {

        if ((code1 == 0) && (code2 == 0)) {

            accept = 1;

            break;

        } else if (code1 & code2) {

            break;

        } else {

            int code_out;

            int x, y;

            if (code1 != 0)

                code_out = code1;

            else

                code_out = code2;

            if (code_out & TOP) {

                x = x1 + (x2 - x1) * (y_max - y1) / (y2 - y1);

                y = y_max;

            } else if (code_out & BOTTOM) {

                x = x1 + (x2 - x1) * (y_min - y1) / (y2 - y1);

                y = y_min;

            } else if (code_out & RIGHT) {

                y = y1 + (y2 - y1) * (x_max - x1) / (x2 - x1);

                x = x_max;

            } else if (code_out & LEFT) {

                y = y1 + (y2 - y1) * (x_min - x1) / (x2 - x1);

                x = x_min;

            }

            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 after clipping: (%d, %d) to (%d, %d)\n", x1, y1, x2, y2);

    else

        printf("Line is outside the window.\n");

}

int main() {

    printf("Enter clipping window (x_min, y_min, x_max, y_max): ");

    scanf("%d %d %d %d", &x_min, &y_min, &x_max, &y_max);

    

    int x1, y1, x2, y2;

    printf("Enter line endpoints (x1, y1, x2, y2): ");

    scanf("%d %d %d %d", &x1, &y1, &x2, &y2);

    

    cohenSutherlandClip(x1, y1, x2, y2);

    return 0;

}