Cohen–Sutherland algorithm

The algorithm of Cohen- Sutherland algorithm is for cutting (clipping) of lines on a rectangle. It is named after its inventors, Dan Cohen and Ivan Sutherland. The algorithm is considered as the most popular, if not the most efficient for its purposes. It is particularly suitable for cases in which a high proportion of for clipping lines lies inside or outside the rectangle.

Steps

First, the line to draw four flags are for the two endpoints identified which are set when the endpoint to the left of the rectangle to the right of, above or below it is. If none of the flags are set, then both endpoints are inside the rectangle, there is no clipping needed and the line can easily be drawn.

If this trivial case does not occur, the flags corresponding to each other are considered both endpoints in the next step. At least one of these flags is set at both ends, then the entire line is outside of the rectangle and the line need not be drawn.

Although this simple case does not occur, the point of intersection of an ( arbitrary) rectangle side is calculated using the line segment and the overlapped portion retested (and possibly truncated ) until eventually both points within the rectangle.

Implementation

The following program is an example of an implementation of Cohen- Sutherland algorithm in C by which one can understand the functioning well.

/ * ------------------------------------------------ ----------------------------------------   Clipping of the two X, Y coordinates of a line within a two-dimensional   Clipping rectangle XMin, YMin, XMax, yMax Cohen Sutherland.     After the function, the coordinates of the two points are clipped so that they   be within the clipping rectangle and the line corresponding to the left,   if you cut off the outlying parts.     If no part of the line passes over the clipping rectangle, the function returns the   Returns FALSE.     x1, y1: coordinate of the start point of the line   x2, y2: coordinates of the end point of the line   return: FALSE line is fully clipped and does not need to be drawn.             TRUE The coordinates are clipped and the line can be drawn now   -------------------------------------------------- ---------------------------------------- * /     # define LEFT CLIP 1 / / binary 0001   # define CLIP RIGHT 2 / / 0010   # define LOWER CLIP 4 / / 0100   # define CLIP UPPER 8 / / 1000     bool clip line ( int & x1, int & y1, int & x2, int & y2)   {   int K1 = 0, K2 = 0; / / Variables, each with 4 flags for right, left, up, down.   int dx, dy;      dx = x2 - x1; / / The width of the line precalculate for later coordinate interpolation    dy = y2 - y1; / / The height of the line precalculate for later coordinate interpolation     / / The following query sets the flags CLIP LEFT, RIGHT CLIP, CLIP UPPER, LOWER CLIP, if the coordinate   / / Is on one or two sides outside of the clip rectangle. A point can not simultaneously   / / Left and right are (or up and down) outside, so only a maximum of two flags can be set.   / / There are 9 options. Of these 8 are equal to 0, indicating that the coordinate must be clipped.     if ( y1 < YMin ) K1 = CLIP LOWER; / / Determine where the initial point is outside the clip rectangle is located.   if ( y1 > yMax ) K1 = CLIP UPPER; / / It will either CLIP or CLIP LOWER UPPER and / or CLIP CLIP RIGHT LEFT or set   if ( x1 < XMin ) K1 | = CLIP LEFT; / / There are 8 to for clipping combinations, depending on which of the 8 adjacent   if ( x1 > XMax ) K1 | = CLIP RIGHT; / / Areas of the clip rectangle, the coordinate is.     if ( y2 < YMin ) K2 = CLIP LOWER; / / Determine where the endpoint outside the clip rectangle is located.   if ( y2 > yMax ) K2 = CLIP UPPER; / / If none of the flags is set, is the coordinate   if ( x2 < XMin ) K2 | = CLIP LEFT; / / Inside the rectangle and must not be changed.   if ( x2 > XMax ) K2 | = CLIP RIGHT;     / / Loop according to Cohen Sutherland, which is run through a maximum of 2 times      while ( K1 | | K2 ) / / one of the coordinates must be clipped anywhere, at least?    {     / / If both coordinates of the left, right, above or below the clipping rectangle   / / Is not a part of the line visible and therefore not further calculation is necessary.   / / The clipped line is invisible.        if ( K1 & K2 ) / / logical AND of the two coordinate flags equal to 0?        return FALSE; / / Both points lie on the same side outside the rectangle        if ( K1 ) / / fast lookup, Coordinate 1 must be clipped?      {        if ( K1 & LEFT CLIP ) / / start point is left outside?        { / / Yes          y1 = ( XMin x1) * dy / dx; / / Calculate y1 by linear interpolation, dx can never be 0 here          x1 = XMin; / / Set x1 to the left edge of the clip rectangle        }        else if ( K1 & CLIP RIGHT) / / starting point is right outside?        { / / Yes          y1 = ( XMax - x1) * dy / dx; / / Calculate y1 by linear interpolation, dx can never be 0 here          x1 = XMax; / / Set x1 to the right edge of the clip rectangle        }        if ( K1 & CLIP LOWER) / / is the starting point of the rectangle below?        { / / Yes          x1 = ( YMin - y1) * dx / dy; / / Calculate x1 by linear interpolation, dy here can never be 0          y1 = YMin; / / Set y1 to the bottom edge of the clip rectangle        }        else if ( K1 & CLIP UPPER) / / is the starting point above the rectangle?        { / / Yes          x1 = ( yMax y1) * dx / dy; / / Calculate x1 by linear interpolation, dy here can never be 0          y1 = yMax; / / Set y1 to the top of the clip rectangle        }        K1 = 0; / / First assume that the point is now within,                                   / / If it does not, will be corrected immediately.        if ( y1 < YMin ) K1 = CLIP LOWER; / / Get again, where the starting point is now outside the clip rectangle        if ( y1 > yMax ) K1 = CLIP UPPER; / / For a point where in the first pass, for example, CLIP LEFT was set,        if ( x1 < XMin ) K1 | = CLIP LEFT; / / Can the second pass, for example, Be set LOWER CLIP        if ( x1 > XMax ) K1 | = CLIP RIGHT;      }        if ( K1 & K2 ) / / logical AND of the two coordinate flags equal to 0?        return FALSE; / / Both points lie on the same side outside the rectangle        if ( K2 ) / / fast lookup, coordinate 2 must be clipped?      { / / Yes        if ( K2 & LEFT CLIP ) / / is the coordinate of the left outside of the rectangle?        { / / Yes          y2 = ( XMin x2) * dy / dx; / / Calculate y by linear interpolation, dx can never be 0 here          x2 = Xmin; / / Set the x coordinate of the left edge        }        else if ( K2 & CLIP RIGHT) / / is the coordinate of the right outside of the rectangle?        { / / Yes          y2 = ( XMax x2) * dy / dx; / / Calculate y by linear interpolation, dx can never be 0 here          x2 = XMax; / / Set the x coordinate of the right edge        }        if ( K2 & CLIP LOWER) / / is the end point outside the rectangle below?        { / / Yes          x2 = ( YMin - y2) * dx / dy; / / Calculate x by linear interpolation, dy here can never be 0          y2 = YMin; / / Set the y coordinate of the bottom edge        }        else if ( K2 & CLIP UPPER) / / is the end point of the top outside of the rectangle?        { / / Yes          x2 = ( yMax y2) * dx / dy; / / Calculate x by linear interpolation, dy here can never be 0          y2 = yMax; / / Set the y coordinate of the top edge        }        K2 = 0; / / First assume that the point is now within,                                   / / If it does not, will be corrected immediately.        if ( y2 < YMin ) K2 = CLIP LOWER; / / Get again, where the endpoint is now out of the clip rectangle        if ( y2 > yMax ) K2 = CLIP UPPER; / / A point that, for example, previously exceeded the clip rectangle can now either        if ( x2 < XMin ) K2 | = CLIP LEFT; / / Left or the right lying. If it is not within        if ( x2 > XMax ) K2 | = CLIP RIGHT; / / Flag set.      }    } / / End of the while loop, the loop is executed no more than twice.    return TRUE; / / Now the coordinates are clipped and the cut line can be drawn   } Web Links

• Description (English)
• Java applet

• Algorithm (computer graphics )