Polygon Clipping with Arbitrary Clipping Polygon

Description

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

Parameters

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})$ auxiliary?	Exact	Deterministic	Time
Vatti clipping algorithm	1992	$O(n^{2})$ ?	$O(n^{2})$ auxiliary?	Exact	Deterministic	Time
Weiler–Atherton clipping algorithm	1977	$O(n^{2})$	$O(n^{2})$ auxiliary?	Exact	Deterministic	Time

Time Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination

Space Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination

Time-Space Tradeoff

Error creating thumbnail: Unable to save thumbnail to destination