2.5.2 Cohen-Sutherland Line-Clipping Algorithm

Cf. [FvDFH90, 3.12.3].

First we test whether both endpoints are inside (and hence draw the line segment) or whether both are left of $ x=x_{\min}$, right of $ x=x_{\max}$, below $ y=y_{\min}$, or above $ y=y_{\max}$ (then we ignore line segment). Otherwise we split the line segment into two pieces at a clipping edge (and thus reject one part). Now we proceed iteratively.

A rather simple accept-reject test is the following:

Divide the plane into 9 regions and assign a 4 bit code to each:

1000
...above top edge $ y>y_{\max}$
0100
...below bottom edge $ y<y_{\min}$
0010
...right of right edge $ x>x_{\max}$
0001
...left of left edge $ x<x_{\min}$
mathcalculate the corresponding bit-codes for both endpoints.

Figure: Codes for the 9 regions associated to clipping rectangle
\begin{figure}\begin{picture}(3,3)
\put(0,1){\line(1,0){3}}
\put(0,2){\line(1,0)...
...2){\makebox(1,1){1000}}
\put(2,2){\makebox(1,1){1010}}
\end{picture}\end{figure}

If both codes are zero then the line segment is completely inside the rectangle. If the bitwise-and of these codes is not zero then the line does not hit since both endpoints lie on the wrong side of at least one boundary line (corresponding to a bit equal to 1). Otherwise take a line which is met by the segment (for this find one non-zero bit), divide the given line at the intersection point in two parts and reject the one lying in the outside halfplane.

Figure: Example of Cohen-Sutherland line-clipping algorithm
\begin{figure}\begin{picture}(8,6)(0,1)
\put(0,2){\line(1,0){8}}
\put(0,4){\line...
...ut(4,3){\makebox(0,0){$\bullet$}\makebox(1,0.5){0000}}
\end{picture}\end{figure}

Andreas Kriegl 2003-07-23