##
An Efficient Algorithm for Line and Polygon Clipping

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.