Convex Polygonal 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 a convex polygon.

Related Problems

Generalizations: Convex Polyhedral Window

Subproblem: Rectangular Window


$n$: number of lines

$p$: number of edges on polygon

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Cyrus–Beck 1978 $O(np)$ $O({1})$ Exact Deterministic Time

Time Complexity Graph

Line Clipping - Convex Polygonal Window - Time.png