Sutherland–Hodgman algorithm (Polygon Clipping with Convex Clipping Polygon Polygon Clipping)

From Algorithm Wiki
Jump to navigation Jump to search

Time Complexity

$O(n^{2})$

Space Complexity

$O(n)$ words

(Each iteration, keeps track of updated polygon after clipping by a side. Note that there can be at most $O(n)$ intersection points due to the clipping polygon being convex)

Description

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word/Real RAM

Year

1974

Reference

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