Rectangular Window (Line Clipping)

From Algorithm Wiki
Jump to navigation Jump to search


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

Related Problems

Generalizations: Convex Polygonal Window

Related: Convex Polyhedral Window


$n$: number of lines

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Cohen–Sutherland 1967 $O(n)$ $O({1})$ Exact Deterministic Time
Liang–Barsky 1984 $O(n)$ $O({1})$ Exact Deterministic Time
Nicholl–Lee–Nicholl 1987 $O(n)$ $O({1})$ Exact Deterministic Time
Fast clipping 1987 $O(n)$ $O({1})$ Exact Deterministic Time

Time Complexity Graph

Line Clipping - Rectangular Window - Time.png