Polygon Clipping with Arbitrary Clipping Polygon (Polygon Clipping)

From Algorithm Wiki
Jump to navigation Jump to search


Clipping is an essential part of image synthesis. Traditionally, polygon clipping has been used to clip out the portions of a polygon that lie outside the window of the output device to prevent undesirable effects. In the recent past polygon clipping is used to render 3D images through hidden surface removal and to produce high-quality surface details using techniques such as Beam tracing. Polygon clipping is also used in distributing the objects of a scene to appropriate processors in multiprocessor raytracing systems to improve rendering speeds.

Related Problems

Subproblem: Polygon Clipping with Convex Clipping Polygon


No parameters found.

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Greiner–Hormann clipping algorithm 1998 $O(n^{2})$ ? $O(n^{2})$? Exact Deterministic Time
Vatti clipping algorithm 1992 $O(n^{2})$ ? $O(n^{2})$? Exact Deterministic Time
Weiler–Atherton clipping algorithm 1977 $O(n^{2})$ $O(n^{2})$? Exact Deterministic Time

Time Complexity Graph

Polygon Clipping - Polygon Clipping with Arbitrary Clipping Polygon - Time.png