An Efficient Algorithm for Line and Polygon Clipping

Ari Rappoport

We present an efficient algorithm for clipping an arbitrary polygon or a line against a convex polygonal window. The algorithm makes use of various ideas from computational geometry and demonstrates their practicality. The algorithm spends O(log p) time on each edge of the clipped polygon, where p is the number of edges of the convex window, while the Sutherland-Hodgman algorithm spends O(p) time per edge.

Theoretical and experimental analyses show that the constants involved are small enough to make the algorithm competitive with the Sutherland-Hodgman algorithm even for windows with as few as 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, e.g. three co-linear vertices.

The Visual Computer: an International Journal of Computer Graphics, 7(1):19-28, 1991.