Rectangular Window

Description

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

Parameters

n: number of lines

Table of Algorithms

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

Time Complexity Graph

Space Complexity Graph

Time-Space Tradeoff

References/Citation

https://dl.acm.org/doi/10.1145/357332.357333