ISSN:
1432-2315
Keywords:
Computational geometry
;
Polygon algorithms
;
Polygon elipping
;
Line clipping
;
Simulation of simplicity
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract We present an algorithm for clipping a polygon or a line against a convex polygonal window. The algorithm demonstrates the practicality of various ideas from computational geometry. It spendsO(logp) time on each edge of the clipped polygon, wherep is the number of window edges, while the Sutherland-Hodgman algorithm spendsO(p) time per edge. Theoretical and experimental analyses show that the constants involved are small enough to make the algorithm competitive even for windows with four edges. The algorithm enables image-space clipping against windows whose boundaries are convex spline curves. The paper contains detailed pseudo-code implementation of the algorithm and an adaptation of the simulation of simplicity method for handling degenerate cases.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01994114
Permalink