Polygon Clipping with Arbitrary Clipping Polygon: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 20: | Line 20: | ||
|- | |- | ||
| [[Greiner–Hormann clipping algorithm (Polygon Clipping with Arbitrary Clipping Polygon Polygon Clipping)|Greiner–Hormann clipping algorithm]] || 1998 || $O(n^{2})$ ? || $O(n^{2})$ | | [[Greiner–Hormann clipping algorithm (Polygon Clipping with Arbitrary Clipping Polygon Polygon Clipping)|Greiner–Hormann clipping algorithm]] || 1998 || $O(n^{2})$ ? || $O(n^{2})$? || Exact || Deterministic || [http://davis.wpi.edu/~matt/courses/clipping/ Time] | ||
|- | |- | ||
| [[Vatti clipping algorithm (Polygon Clipping with Arbitrary Clipping Polygon Polygon Clipping)|Vatti clipping algorithm]] || 1992 || $O(n^{2})$ ? || $O(n^{2})$ | | [[Vatti clipping algorithm (Polygon Clipping with Arbitrary Clipping Polygon Polygon Clipping)|Vatti clipping algorithm]] || 1992 || $O(n^{2})$ ? || $O(n^{2})$? || Exact || Deterministic || [https://dl-acm-org.ezproxy.canberra.edu.au/doi/10.1145/129902.129906 Time] | ||
|- | |- | ||
| [[Weiler–Atherton clipping algorithm (Polygon Clipping with Arbitrary Clipping Polygon Polygon Clipping)|Weiler–Atherton clipping algorithm]] || 1977 || $O(n^{2})$ || $O(n^{2})$ | | [[Weiler–Atherton clipping algorithm (Polygon Clipping with Arbitrary Clipping Polygon Polygon Clipping)|Weiler–Atherton clipping algorithm]] || 1977 || $O(n^{2})$ || $O(n^{2})$? || Exact || Deterministic || [https://www.cs.drexel.edu/~david/Classes/CS430/HWs/p214-weiler.pdf Time] | ||
|- | |- | ||
|} | |} | ||
Revision as of 07:52, 10 April 2023
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})$? | 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
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