In computer graphics

Computer graphics

Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....

, line clipping is the process of removing lines or portions of lines outside of an area of interest. Typically, any line or part thereof which is outside of the viewing area is removed.

There are two common algorithms for line clipping: Cohen–Sutherland and Liang–Barsky.

Cohen–Sutherland

This algorithm divides a 2D space into 9 parts, of which only the middle part (viewport) is visible. The algorithm includes, excludes or partially includes the line based on where the two endpoints are:

• Both endpoints are in the viewport (bitwise OR of endpoints 0): trivial accept.
• Both endpoints are in the same part, which is not visible (bitwise AND of endpoints != 0): trivial reject.
• Both endpoints are in different parts: In case of this non trivial situation the algorithm finds one of the two points that are outside the viewport (there is at least one point outside). The intersection of the outpoint and extended viewport border is then calculated (i.e. with the parametric equation for the line) and this new point replaces the outpoint. The algorithm repeats until a trivial accept or reject occurs.

Liang–Barsky

The Liang–Barsky algorithm uses the parametric equation of a line and inequalities describing the range of the clipping box to determine the intersections between the line and the clipping box. With these intersections it knows which portion of the line should be drawn. This algorithm is significantly more efficient than Cohen–Sutherland, but Cohen-Sutherland does trivial accepts and rejects much faster, so it should be considered instead if most of the lines you need to clip would be completely in or out of the clip window.
Cyrus–Beck
Very similar to Liang-Barsky algorithm. The difference is that Liang-Barsky is a simplified Cyrus-Beck variation that was optimized for a rectangular clip window.

The Cyrus-Beck algorithm is of O(N) complexity, and it is primarily intended for a clipping a line in the parametric form against a convex polygon in 2 dimensions or against a convex polyhedra in 3 dimensions.
Nicholl–Lee–Nicholl

The Nicholl-Lee-Nicholl algorithm is a fast line clipping algorithm that reduces the chances of clipping a single line segment multiple times, as may happen in the Cohen-Sutherland algorithm.

Fast clipping
This algorithm has similarities with Cohen-Sutherland. The start and end positions are classified by which portion of the 9 area grid they occupy. A large switch statement jumps to a specialized handler for that case. In contrast, Cohen-Sutherland may have to iterate several times to handle the same case.
O(lg N) algorithm

This algorithm classifies vertices against the given line in the implicit form p: ax+by+c=0. As the polygon is assumed to be convex and vertices are ordered clockwise or anti-clockwise binary search can be applied and leads to a O(lg N) run time complexity.

Skala

This algorithm is based on homogeneous coordinates

Homogeneous coordinates

In mathematics, homogeneous coordinates, introduced by August Ferdinand Möbius in his 1827 work Der barycentrische Calcül, are a system of coordinates used in projective geometry much as Cartesian coordinates are used in Euclidean geometry. They have the advantage that the coordinates of points,...

 and duality

Duality (projective geometry)

A striking feature of projective planes is the "symmetry" of the roles played by points and lines in the definitions and theorems, and duality is the formalization of this metamathematical concept. There are two approaches to the subject of duality, one through language and the other a more...

. It can be used for line or line segment clipping against a rectangular window as well as against a convex polygon. The algorithm is based on classifying a vertex of the clipping window against a half-space given by a line p: ax+by+c=0. The result of the classification determines the edges intersected by the line p. The algorithm is simple, easy to implement and extensible to a convex window as well. The line or line segment p can be computed from points x1, x2 given in homogeneous coordinates directly using the cross product as
p = x1 x x2 = [x1,y1,w1] x [x2,y2,w2] or as
p = x1 x x2 = [x1,y1,1] x [x2,y2,1] if given in the Euclidean coordinates.