Line clipping

Tests are conducted on a given line segment to find out whether it lies outside the view area or volume.

In 1967, flight-simulation work by Danny Cohen led to the development of the Cohen–Sutherland computer graphics two- and three-dimensional line clipping algorithms, created with Ivan Sutherland.

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.

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.