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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Chazelle B, Dobkin D (1987) Intersection of convex objects in two and three dimensions. J ACM 34(1):1–27
Edelsbrunner H (1987) Algorithms in combinatorial geometry )EATCS monographs on theoretical computer science). Springer, Berlin Heidelberg New York
Edelsbrunner H, Mücke EP (1988) Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. 4th ACM Symp Proc, Computational Geometry, pp 118–133
Foley J, Van Dam A (1982) Fundamentals of Interactive Computer Graphics. Addison-Wesley, Reading, Mass
Hoffmann CM (1989) The problems of accuracy and robustness in geometric computations. IEEE Computer 22(3):31–42
Hoffmann K, Mehlhorn K, Rosenstiehl P, Tarjan R (1986) Sorting Jordan sequences in linear time using level-linked search trees. Inf Control 68(1–3):170–184
Liang Y, Barsky B (1983) An analysis and algorithm for polygon clipping. Commun ACM 26(11):868–877
Newman WM, Sproull RF (1979) Principles of interactive computer graphics, 2nd edn. McGraw-Hill, New York
Nicholl TM, Lee DT, Nicholl RA (1987) An efficient new algorithm for 2-D line clipping: its development and analysis. SIGGRAPH '87 Conf Proc. Computer Graphics 21(4):253–262
Preparata F, Shamos MI (1985) Computational geometry: an introduction. Springer, Berlin Heidelberg New York
Requicha AG, Voelcker HB (1985) Boolean operations in solid modeling: boundary evaluation and merging algorithms. Proc IEEE 73(1):30–44
Sproull RF, Sutherland IE (1968) A clipping divider (Fall Joint Computer Conf Proc). Thompson Books, Washington, DC, pp 765–775
Sutherland IE, Hodgman GW (1974) Reentrant polygon clipping. Commun ACM 17(1):32–42
Weiler K, Atherton P (1977) Hidden surface removal using polygon area sorting. SIGGRAPH '77 Conf Proc. Computer Graphics 11(2):214–222
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Rappoport, A. An efficient algorithm for line and polygon clipping. The Visual Computer 7, 19–28 (1991). https://doi.org/10.1007/BF01994114
Issue Date:
DOI: https://doi.org/10.1007/BF01994114